582421 Randomised algorithms (Autumn 2005)
Midterm examination, 17 October, 9:00{12:00, lecture hall B123
In all problems you may assume that n is even etc. as convenient and disregard the eects of rounding.
Maximum score 8 + 8 + 8 = 24.
1. Let X1; : : : ; Xn be independent coin ips. If Xi = Xi+1 = : : : = Xi+k 1, where k 2, we say that there is a streak of length k beginning from i. (If k > 2, then there is also a streak of length j for all 2 j < k.)
(a) Show that the expected number of streaks of length log2n + 1 is 1 o(1).
(b) Show that, for suciently large n, the probability that there is no streak of length at least log2n 2 log2log2 is less than 1=n.
2. Let X1; : : : ; Xn be independent Poisson trials, X =Pn
i=1Xi and = E[X].
(a) Prove that the moment generating function MX of the random variable X satises the upper bound
MX(t) exp (et 1) : (b) Prove that
Pr(X (1 ))
e
(1 )1
for all 0 < < 1.
3. Consider the familiar situation where n balls are distributed independently and uniformly at random into n bins. Suppose now that each bin can hold only two balls. If we attempt to place three or more balls into the same bin, we say that an overow occurs in that bin. Let Z be the number of bins where an overow occurs.
(a) What is E[Z]? Give the exact value and an approximation that holds when (1 1=n)n e 1. (You do not need to analyse the accuracy of the approximation.)
(b) Derive an upper bound for the probability of the event Z < 12E[Z]. It is not important to optimise numerical constants in the bound, but the bound should be of the order of O(e cn) for some c > 0.
(Sama suomeksi kaantopuolella.)
