5. Probabilistic Analysis and Randomized Algorithms

Exercises

5.1-1

We prove the contrapositive, if we don't have total order on the ranks of the candidates, then we cannot always determine which candidate is best, in line 4 of procedure Hire-Assistant.

A lack of total order implies that there are incomparable candidates. Assume one such pair is denoted by indices $i<j$ and currently $best=i$. When we reach candidate $j$, we cannot evaluate the condition in line 4. Consequently, we are unable to decide should we keep $i$ or switch to $j$.

★ 5.1-2 🌟

This exercise introduces the technique called rejection sampling.

Let $n=b-a+1$ be a size of the interval $[a,b]$ and assume that calling Random(0,1) takes $\Theta(1)$ time.

One simple method is to perform a binary search over the interval, using the basic RNG at each step to choose the direction. However, this produces a uniform distribution only when $n$ is a power of two.

The algorithm proceeds as follows:

1. Compute $k = \lceil \lg n \rceil$, the number of bits required to represent $n-1$ (distance of $b$ from $a$).

2. Generate a random $k$-bit number, $d$, by making $k$ calls to RANDOM(0, 1). Treat each call as one bit of $d$, thus $d \in [0, 2^k - 1]$.

3. If $d<n$, we accept the result and return $a+d$.

4. Otherwise, we reject the sample and goto step 2.

Because every number in the range $[0, n-1]$ has the exact same probability of being generated in step 2 (specifically, $1/2^k$), and we only accept numbers in this range, the final accepted value is guaranteed to be uniformly distributed.

Step 2 requires $\Theta(k)$ time. We can view each iteration as a Bernoulli trial, where “success” means that the iteration returns a value. The probability of success at step 3 is $1/2<p=n/2^k \le 1$, so the expected number of iterations follows a geometric distribution and equals $1/p<2$. Therefore, the total expected running time is $\Theta(\lg (b-a+1))$.

The + 1 is intentionally retained here to ensure the domain of the logarithm is strictly positive and the math remains sound across all valid inputs (including $a=b$).

★ 5.1-3

Available in the latest revision of the IM.

5.2-1

Available in the latest revision of the IM.

5.2-2

Available in the latest revision of the IM.

5.2-3

Available in the latest revision of the IM.

5.2-4

Available in the latest revision of the IM.

5.2-5

Available in the latest revision of the IM.

5.2-6

Available in the latest revision of the IM.

5.3-1

Available in the latest revision of the IM.

5.3-2

Available in the latest revision of the IM.

5.3-3

Available in the latest revision of the IM.

5.3-4

Available in the latest revision of the IM.

5.3-5 🌟

Describes an algorithm for generating a random sample of size $1 \le m \le n$ from $n$ elements in $\Theta(m)$ time.

Available in the latest revision of the IM.

5.4-1

In both subproblems, we assume that birthdays are independent and uniformly distributed.

Subproblem 1

We follow a similar analysis as for the birthday paradox from the book. Let $A_i$ be the event that person $i$ has a different birthday than you do, so $\Pr \{A_i\}=1-1/n$. Let $B_k = \bigcap_{i=1}^kA_i$ be the event that none of the $k$ people has the same birthday as you do. Observe that $\Pr\{A_k|B_{k-1}\}=\Pr\{A_k\}$. We iteratively apply the recurrence (5.8) to obtain

$$\begin{align*} \Pr\{B_k\} &= \prod_{i=1}^k\Pr\{A_i\} \\ &= \prod_{i=1}^k\left(1-\frac{1}{n}\right) \\ &= \left(1-\frac{1}{n}\right)^k. \end{align*}$$

We need $\Pr\{B_k\} \le 1/2$. This gives $k= \lceil\log_{1-1/n}(1/2)\rceil$. For $n=365$ it is $k=253$.

Subproblem 2

Let the random variable $X_k$ denote the number of people (out of $k$) having a birthday on July 4. This variable follows the binomial distribution, so $\Pr\{X_k=i\}=b(i;k,1/n)$. We are looking for the smallest $k$ such that $\Pr\{X_k=0\}+\Pr\{X_k=1\} < 1/2$. For $n=365$ this gives $k=613$.

5.4-2

We need to find $k$ such that $\Pr\{B_k\}\le1-0.99=0.01$. Solving for $k$ gives

$$k \ge \frac{1+\sqrt{1+8n\ln100}}{2}$$

For $n=365$ it is $k=59$. Plugging these values into the formula $\frac{k(k-1)}{2n}$, the the expected number of pairs of people with the same birthday is approximately 4.69.

5.4-3

Observe that the first toss will land in an empty bin. Let $X$ be a random variable denoting how many additional tosses are needed until some bin contains two balls. Obviously $\Pr\{X \ge 1\}=1$, as we surely need at least one extra toss. $\Pr\{X \ge 2\}=(b-1)/b$, since we must have 1 miss. In general, at least $k$ tosses are required, when none of the first $k-1$ balls ended up in an occupied bin, so

$$\begin{align*} \Pr\{X\ge k\} &= \frac{b-1}{b}\cdot\frac{b-2}{b}\cdots\frac{b-(k-1)}{b} \\[1mm] &= \frac{b}{b}\cdot\frac{b-1}{b}\cdot\frac{b-2}{b}\cdots\frac{b-(k-1)}{b} \\[1mm] &= \frac{b!}{(b-k)!b^k}. \end{align*}$$

We know that $\Pr\{X=k\}=\Pr\{X \ge k\}-\Pr\{X \ge k+1\}$ and $\Pr\{X \ge b+1\}=0$. When a random variable $X$ takes on values from the set of natural numbers, then we have a nice formula for its expectation (see equation (C.28) on page 1193 in the book). Therefore, the expected number of tosses is

$$1+\sum_{k=1}^b \Pr\{X \ge k\} = 1+\sum_{k=1}^b\frac{b!}{(b-k)!b^k}=\Theta(\sqrt b).$$

The expression above is exactly the same as for finding an average number of people to get at least one shared birthday. You can read more about it here, where you can also find an explanation for the asymptotic growth.

★ 5.4-4

It is important that the birthdays be mutually independent for the probability analysis, but for the expected value analysis, pairwise independence is completely sufficient thanks to the linearity of expectation (see Exercise 5.2-4).

The conditional probability chain, obtained by iteratively applying the recurrence (5.8), depends on ensuring that, at each step, the birthday variable $b_i$ has the same uniform distribution, unaffected by the previous choices apart from not colliding with earlier birthdays. This chain is only valid when the entire joint assignment is described by uniform, mutually independent random variables. Dependencies among larger groups can profoundly alter probabilities for intersections and unions of events. On page 1188 of the book, you have a concrete example about the difference between pairwise and mutual independence.

★ 5.4-5

OEIS A014088 lists solutions for variations of the birthday problem depending on how many people should share the same birthday. For this exercise, it is $k=88$. Let us see how to derive it analytically.

We assume that birthdays are mutually independent and uniformly distributed, so any sequence of $k$ birthdays occurs with probability $1/n^k$. For $k>1$ and $i=0, 1, \dots, \lfloor k/2\rfloor$, let $Q_i$ be an event that among $k$ people exactly $i$ pairs of people have matching birthdays, which implies that no triples of people share birthdays. Let $T_k$ be an event that among $k$ people there are triples sharing birthdays. The probability of this event is

$$\Pr\{T_k\}=1-\sum_{i=0}^{\lfloor k/2\rfloor}\Pr\{Q_i\}.$$

We can select $i$ days out of $n$, and assign these to $i$ unallocated pairs of people, in $\binom{n}{i}$ ways. The remaining $n-i$ days can be assigned to the remaining $k-2i$ people in $\binom{n-i}{k-2i}$ ways. Since people are distinguishable, the total number of allocations should be multiplied by $k!$. We also need to divide the resulting number by $2^i$, since people sharing the same birthday are relatively unordered. After combining these pieces, we get

$$\Pr\{Q_i\} = \frac{1}{n^k} \cdot \frac{k!}{2^i}\binom{n}{i}\binom{n-i}{k-2i}.$$

You can verify that $k=88$ entails $\Pr\{T_k\} \ge 1/2$.

★ 5.4-6

We can form $n^k$ $k$-strings over a set of size $n$. Any $k$-string with distinct elements is a $k$-permutation. By equation (C.1), there are $n(n-1)\cdots(n-k+1)$ possible $k$-permutations. If we denote by $B_k$ the event that $k$ people have distinct birthdays, then the probability that a $k$-string over a set of size $n$ forms a $k$-permutation equals $\Pr\{B_k\}$; on page 141 of the book you have this in expanded form.

★ 5.4-7

Available in the latest revision of the IM.

It is an amazing fact that the expected number of empty bins matches the number of applicants to reject for maximizing the probability of hiring the best candidate in the on-line variant of the hiring problem! This shows how frequently the same limit definition $\lim_{n \to \infty} \left(1 - \frac{1}{n}\right)^n = \frac{1}{e}$ appears in various contexts.

★ 5.4-8

Let's partition the $n$ coin flips into at least $\lfloor n/s \rfloor$ groups of $s=\lfloor \lg n-2\lg\lg n\rfloor$ consecutive flips and bound the probability that no group comes up all heads. By equation (5.9), the probability that the group starting in position $i$ comes up all heads is

$$\begin{align*} \Pr\{A_{i,\,s}\} &= \cfrac{1}{2^{s}} \\[1mm] &\ge \cfrac{1}{2^{\lg n-2\lg\lg n}} \\[3mm] &= \cfrac{2^{2\lg\lg n}}{2^{\lg n}} \\[3mm] &= \cfrac{\lg^2n}{n}. \end{align*}$$

The probability that a streak of heads of length at least $s$ does not begin in position $i$ is therefore at most $1-(\lg^2n)/n$. Since the $\lfloor n/s \rfloor$ groups are formed from mutually exclusive, independent coin flips, the probability that everyone of these groups fails to be a streak of length $s$ is at most

$$\begin{align*} \left(1-\frac{\lg^2n}{n}\right)^{\lfloor n/s \rfloor} &\le \left(1-\frac{\lg^2n}{n}\right)^{n/s-1} \\ &\le \left(1-\frac{\lg^2n}{n}\right)^{n/(\lg n-2\lg\lg n)-1} \\ &\le \left(e^{-(\lg^2n)/n}\right)^{n/(\lg n-2\lg\lg n)-1} && \text{(by inequality (3.14))} \\ &= e^{-(\lg^2n)/(\lg n-2\lg\lg n)+(\lg^2n)/n} \\ &< e^{-(\lg^2n)/\lg n} && \text{(for sufficiently large $n$)} \\ &= e^{-\lg n} \\ &\le e^{-\ln n} \\ &= 1/n. \end{align*}$$

Using the same reasoning as for deriving equation (5.13) (see page 148 in the book), the probability that the longest streak equals or exceeds $s$ is at least $1-1/n$.

Problems

5-1 Probabilistic counting

Available in the latest revision of the IM.

The current edition of the IM contains a false claim about pairwise independence of random variables $X_j$ representing increments in each iteration. They are pairwise dependent, but uncorrelated. The latter fact allows the variance of a random variable $V_n=\sum_j X_j$ to be computed as a sum of variances of $X_j$.

5-2 Searching an unsorted array

Available in the latest revision of the IM.

A more rigorous treatment of tasks (e) and (f) is based on the law of total expectation. Let $X_i=I\{A[i] \text{ is examined}\}$ and $X=\sum_{i=1}^n X_i$ equal the number of indices of A that are examined. Define $S=\{i:A[i]=x\}$ and $\overline S=\{i:A[i] \neq x\}$, so that $|S|=k$ and $|\overline S|=n-k$. A position $i \in S$ is examined only if it’s the first position in $S$, which occurs with probability $1/k$. A position $i \notin S$ is examined only if, out of position $i$ and all $k$ positions in $S$, $i$ is the first position, which occurs with probability $1/(k+1)$. Let $C_S$ be an event that the indices of elements we are searching for belong in $S$. We have

$$\begin{align*} \mathbb{E}[X_i] &= \mathbb{E}[\mathbb{E}[X_i|C_S]] \\ &= \sum_{\text{all }S} \mathbb{E}[X_i|C_S] \Pr\{C_S\} \\ &= \cfrac{1}{\displaystyle{\binom{n}{k}}} \sum_{\text{all }S} \mathbb{E}[X_i|C_S] && \text{($\Pr\{C_S\}=1/\binom{n}{k}$)} \\ &= \cfrac{1}{\displaystyle\binom{n}{k}} \cdot \binom{n}{k} \cdot \Pr\{X_i|C_S\} && \text{($\mathbb{E}[X_i|C_S]=\Pr\{X_i|C_S\}$)} \\ &= \Pr\{X_i|C_S\} \\ &=\begin{cases} 1/k &\text{if } i \in S, \\ 1/(k+1) &\text{otherwise}. \end{cases} \end{align*}$$

$$\begin{align*} \mathbb{E}[X] &= \mathbb{E}[\sum_{i=1}^n X_i] \\ &= \sum_{i=1}^n \mathbb{E}[X_i] && \text{(by linearity of expectation)} \\ &= \sum_{i \in S} \mathbb{E}[X_i] + \sum_{i \notin S} \mathbb{E}[X_i] \\ &= \sum_{i \in S} \frac{1}{k} + \sum_{i \notin S} \frac{1}{k+1}\\ &= k \cdot \frac{1}{k} + (n-k) \cdot \frac{1}{k+1} \\ &= \frac{n+1}{k+1}. \end{align*}$$