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. ]]
------------------------------------------------------------