15-451/651 Algorithms 9/02/14 RECITATION NOTES - Hashing, Universal Hash Functions, and Karp-Rabin - Different kinds of randomized algorithms ============================================================== 1. UNIVERSAL AND K-UNIVERSAL - Recall the definitions - Show that 2-universal implies universal - Show that universal does not mean 2-universal - Show that (k+1)-universal implies k-universal. ---------- 2. ALICE AND BOB TEST EQUALITY Suppose Alice has some string A, and Bob has some string B. Both strings are N bits long, where N is very large. They want to compare whether A and B are identical. (Alice does not know what B is, and Bob does not know what A is.) But Alice lives in Australia, and Bob in Brazil. And it is very costly to transmit data between their homes. So they want reduce the amount of communication. [OPTIONAL: [ If we use only deterministic algorithms, then you can show that the ] [ best strategy is for one of them to send their string to the other ] [ person, and for the other person to check. It is not difficult but ] [ is beyond the scope of the current course.] But randomly we can do better. One way to do this is for Alice to pick a random prime q in some range [2..K] and send across - the prime q, and - the "residue" (A mod q). Then Bob checks if B mod q = A mod q: if so, he says "EQUAL" else he says "UNEQUAL". Clearly, if the strings are equal, then Bob will always say EQUAL. What if A != B? Then Bob will make a mistake (and say EQUAL) when A mod q = B mod q. That is, when (A - B) = 0 mod q. Or q | (A-B). In other words, q is a prime divisor of A-B. Note that A-B is an (at most) N-bit non-zero number, since A and B are N bit numbers, and A != B. So A-B has at most N prime divisors. So if we choose K large enough so that [2..K] has 100N primes, then the chance of hitting one of the prime divisors of (A-B) is only 1/100. How big should this K be? As in lecture, we use the prime number theorem. We want (7/8) (K/log K) >= 100 N. By algebra this is satisfied when, say, K = 250 N log N. So how many bits did Alice send? A prime q <= K requires at most log K = log( 250 N log N) = O(log N) bits. And the residue (A mod q) < q, so also requires O(log N) bits. A total of O(log N) bits sent, and they are correct with probability 99/100. ---- Want a higher probability? Repeat this 100 times. What is the chance that we are incorrect every time? Only (1/100)^{100}. Smaller than the number of particles in the universe. ---------- 3. MONTE CARLO and LAS VEGAS We have been talking about randomized algorithms while discussing hashing. There are (at least) two kinds of algorithms --- * MONTE CARLO algorithms: these have some fixed running time, but the output is correct only with some probability p. * LAS VEGAS algorithms: these are always correct, but whose running time is a random variable. Going From Monte Carlo to Las Vegas: Suppose you had a (Monte Carlo) randomized algorithm WeirdSort that takes an unsorted array I of elements as input, and outputs another array O. The algorithm always runs in time T(n), and the output O is always some permuted version of the input I. Moreover, we know that Pr[ output O is in sorted order ] >= p. So the algorithm does the right thing with probability at least p. Remember: this probability is over the randomness of the algorithm and holds for every input I. Question: Prove that you can convert such an algorthm into a (Las Vegas) randomized sorting algorithm that has expected running time O((T(n)+n) * 1/p). (Recall that the definition of Las Vegas algorithms means we always have to output a *sorted* array containing the elements of the input array A, but now the runtime of the Las Vegas algorithm is a random variable.) Any ideas? The simplest idea works: try the algorithm once, see if the output is sorted, and if not, repeat the process (with fresh randomness, so that the outcome is independent of the previous rounds). One "round" of the algorithm takes T(n) time to run the algorithm once, and O(n) time to check if the output is sorted. What is the expected number of rounds we will take before we stop? Well, each run of the algorithm succeeds (independently of the past runs) with probabability at least p, so it's as though we are flipping a coin with bias (probability of heads) at least p and want to know the expected number of flips before we see a heads. From previous classes, we know this is at most 1/p. Multiplying the two, the expected running time is ( T(n) + O(n) ) * (1/p). [[In case you haven't seen it before, here is a brute force calculation showing that the expected number of flips before we see a heads is 1/p, when the bias is p. Let N be the random variable denoting the number of flips until the first head when flipping a coin with heads probability exactly p. Then E[N] = \sum_{i >= 0} (i * Pr[ we first succeed in the i^{th} round ] ) = \sum_{i >= 0} (i * (1-p)^{i-1} * p ) <---- (!) But note that (1-p)E[N] is then = \sum_{i >= 0} (i * (1-p)^{i} * p ) and replacing the index i by j-1, we get = \sum_{j >= 1} ((j-1) * (1-p)^{j-1} * p ) now replacing the index j by i, we get = \sum_{i >= 1} ((i-1) * (1-p)^{j-1} * p ) which looks very much like (!). So E[N] - (1-p)E[N] = \sum_{i >= 1} ((i - (i-1)) * (1-p)^{i-1} * p ) = \sum_{i >= 1} (1-p)^{i-1} * p This is just the geometric sum, and is sums to 1. Whew. Now that the dust has settled, p.E[N] = 1, or E[N] = 1/p. And if the heads probability is at least p, the expected number of flips becomes at most 1/p. ]] ------------------------------------------------------------