Introduction

Next: Game-Theoretic Techniques

Problems

1.1

Due to J. von Neumann [409].

1. Suppose you are given a coin for which the probability of HEADS, say $p$, is unknown. How can you use this coin to generate unbiased coin-flips, i.e.

$$\mathrm{Pr}[\text{HEADS}]=\mathrm{Pr}[\text{TAILS}]=\frac{1}{2}?$$

Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than $\frac{1}{p(1-p)}$. Hint: consider two consecutive flips of the biased coin. 2. Devise an extension of the scheme that extracts the largest possible number of independent, unbiased coin-flips from a given number of flips of the biased coin.

---

1.2

Due to D. E. Knuth and A. C.-C. Yao [264].

1. Suppose you are provided with a source of unbiased random bits. Explain how you will use this to generate uniform samples from the set $S=\{0,\dots ,n-1\}$. Determine the expected number of random bits required by your sampling algorithm.
2. What is the worst-case number of random bits required by your sampling algorithm? Consider the case when $n$ is a power of $2$, as well as the case when it is not.
3. Solve parts (1) and (2) when, instead of unbiased random bits, you are required to use as the source of randomness uniform random samples from the set $\{0,\dots ,p-1\}$; consider the case when $n$ is a power of $p$, as well as the case when it is not.

---

1.3

Due to D. E. Knuth and A. C.-C. Yao [264].

Suppose you are provided with a source of unbiased random bits. Provide efficient schemes, in terms of expected running time and expected number of random bits used, for generating samples from the distribution over the set $\{2,3,\dots ,12\}$ induced by rolling two unbiased dice and taking the sum of their outcomes.

---

1.4

1. Suppose you are required to generate a random permutation of size $n$. Assuming that you have access to a source of independent and unbiased random bits, suggest a method for generating random permutations of size $n$. Efficiency is measured in terms of both time and number of random bits. What lower bounds can you prove for this task?
2. Consider the following method for generating a random permutation of size $n$. Pick $n$ random values $X_1,\dots ,X_n$ independently from the uniform distribution over the interval $[0,1]$. Now, the permutation that orders the random variables in ascending order is claimed to be a random permutation, and it can be determined by sorting the random values. Is the claim correct? How efficient is this scheme?
3. Consider the following lazy implementation of the scheme suggested in part (2). The binary representation of the fraction $X_j$ is a sequence of unbiased and independent random bits. At any given stage of the sorting algorithm, we would have chosen only as many bits of each $X_j$ as necessary to resolve all the comparisons performed up to that point. When comparing $X_i$ to $X_j$, if the current prefixes of their binary expansions do not determine the outcome of the comparison, then we extend their prefixes by choosing further random bits until this happens. Compute tight bounds on the expected number of random bits used by this implementation.

---

1.5

Consider the problem of using a source of unbiased random bits to generate samples from the set $S=\{0,\dots ,n-1\}$ such that the element $i$ is chosen with probability $p_i$. Show how to perform this sampling using $O(\log n)$ random bits per sample, regardless of the values of $p_i$. Use the result from Problem 1.4(3).

---

1.6

Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of HEADS over the number of TAILS seen in the first $i$ flips. Define

$$H=\underset{i}{\max }{H}_i.$$

Show that

$$\mathbb{E}[H^2]=\Theta (n)$$

and that

$$\mathbb{E}[H]=\Theta (\sqrt{n}).$$

---

1.7

Suppose we choose a permutation $\pi$ of the ordered set $N=\{1,2,\dots ,n\}$ uniformly at random from the space of all permutations of $N$. Let $L(\pi )$ denote the length of the longest increasing subsequence in permutation $\pi$.

1. For large $n$ and some positive constant $c$, prove that

$$\mathbb{E}[L(\pi )]\ge c\sqrt{n}.$$

2. Is the bound in part (1) tight?

---

1.8

Consider adapting the min-cut algorithm of Section 1.1 to the problem of finding an $s$-$t$ min-cut in an undirected graph. In this problem, we are given an undirected graph $G$ together with two distinguished vertices $s$ and $t$. An $s$-$t$ cut is a set of edges whose removal from $G$ disconnects $s$ from $t$; we seek an $s$-$t$ cut of minimum cardinality. As the algorithm proceeds, the vertex $s$ may get amalgamated into a new vertex as a result of an edge being contracted; we call this vertex the $s$-vertex, initially the $s$-vertex is $s$ itself. Similarly, we have a $t$-vertex. As we run the contraction algorithm, we ensure that we never contract an edge between the $s$-vertex and the $t$-vertex.

1. Show that there are graphs in which the probability that this algorithm finds an $s$-$t$ min-cut is exponentially small.
2. How large can the number of $s$-$t$ min-cuts in an instance be?

---

1.9

Consider the Find algorithm described in Section 1.4 for selecting the $k$th smallest of a set $S$ of $n$ elements. Show that the algorithm finds the $k$th smallest element in $S$ in expected time $O(n)$.

---

1.10

Consider the setting of Example 1.1. Show that the probability that no sailor returns to her own cabin approaches $\frac{1}{e}$ as the number of sailors grows large.

---

1.11

Verify the following inclusions:

$$P\subseteq RP\subseteq NP\subseteq PSPACE\subseteq EXP\subseteq NEXP.$$

It is not known whether these inclusions are strict.

---

1.12

Verify the following inclusions:

$$RP\subseteq BPP\subseteq PP.$$

It is not known whether these inclusions are strict.

---

1.13

Show that

$$PP=\mathrm{co}\text{-}PP$$

and

$$BPP=\mathrm{co}\text{-}BPP.$$

---

1.14

Show that

$$NP\subseteq PP\subseteq PSPACE.$$

---

1.15

Due to K.-I. Ko [265].

Show that

$$NP\subseteq BPP$$

implies

$$NP=RP.$$