Exercises

1.

We flip a fair coin ten times. Find the probability of the following events.

1. The number of heads and the number of tails are equal.
2. There are more heads than tails.
3. The $i$-th flip and the $(11-i)$-th flip are the same for $i = 1, \dots , 5.$
4. We flip at least four consecutive heads.

2.

The following approach is often called reservoir sampling. Suppose we have a sequence of items passing one by one. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen so far. Assume that we do not know the total number of items in advance. How can we sample without storing all the items that we see.

Consider the following algorithms which just stores one item in memory at all times. When the first item appears, it is stored in memory. When the $k$th item appears it replaces the item in memory with probability $\frac{1}{k}$. Explain why this algorithm solves the problem.

3.

Consider the following algorithm for computing the $k$-smallest of a set of $n$ elements ($k$-median):

Input: a set $S$ of $n$ different numbers and a number $k$ between $1$ and $n$

Output: the $k$ smallest element of $S$

Algorithm: $Find(S, k)$

1. Choose $y$ from $S$ uniformly at random
2. $S_1 = \{x \in S \mid x < y\}; S_2 = \{x \in S \mid x > y\};$
3. If $\vert S_1\vert \geq k$ then $Find(S_1, k)$
4. If $\vert S_1\vert = k - 1$ then $Output~y$
5. If $\vert S_1\vert < k - 1$ then $Find(S_2, k - \vert S_1\vert - 1)$

Show that the expected running time of the algorithm is $O(n)$. (Hint: Try to write the running time as a recurrence and solve it).

4.

Given a circle with circumference $1$ and a marked point on the circle. Choose $n$ additional points on the circle uniformly and independently at random. The random points partition the circle into n intervals.

• What is the average interval length?
• What is the expected interval length of the interval containing $x$.

5.

Consider the interval $[0, 1]$ on the real line. Choose a point of the interval uniformly at random. This point partitions the line into 2 intervals.

• What is the expected length of the longer (shorter) interval?
• What is the expected length of the interval containing the median (i.e., the point 0.5)