Chapter 8

Show that \(\mathrm{P}[\mathcal{A} \cap B] \mathrm{P}[\mathcal{A} \cup \mathcal{B}] \leq \mathrm{P}[\mathcal{A}] \mathrm{P}[\mathcal{B}]\) for all events \(\mathcal{A}, \mathcal{B}\).

Suppose \(\mathcal{A}, \mathcal{B}, \mathcal{C}\) are events such that \(\mathcal{A} \cap \overline{\mathcal{C}}=\mathcal{B} \cap \overline{\mathcal{C}}\). Show that \(|\mathrm{P}[\mathcal{A}]-\mathrm{P}[\mathcal{B}]| \leq \mathrm{P}[\mathcal{C}]\)

Let \(m\) be a positive integer, and let \(\alpha(m)\) be the probability that a number chosen at random from \(\\{1, \ldots, m\\}\) is divisible by either \(4,5,\) or \(6 .\) Write down an exact formula for \(\alpha(m),\) and also show that \(\alpha(m)=14 / 30+O(1 / m)\).

This exercise asks you to generalize Boole's inequality (8.6), proving Bonferroni's inequalities. Let \(\left\\{\mathcal{A}_{i}\right\\}_{i \in I}\) be a finite family of events, where \(n:=|I| .\) For \(m=0, \ldots, n,\) define $$ \alpha_{m}:=\sum_{k=1}^{m}(-1)^{k-1} \sum_{J \subseteq I \atop|J|=k} \mathrm{P}\left[\bigcap_{j \in J} \mathcal{A}_{j}\right] $$ Also, define $$ \alpha:=\mathrm{P}\left[\bigcup_{i \in I} \mathcal{A}_{i}\right] $$ Show that \(\alpha \leq \alpha_{m}\) if \(m\) is odd, and \(\alpha \geq \alpha_{m}\) if \(m\) is even. Hint: use induction on \(n\).

For events \(\mathcal{A}_{1}, \ldots, \mathcal{A}_{n}\), define \(\alpha_{1}:=\mathrm{P}\left[\mathcal{A}_{1}\right],\) and for \(i=2, \ldots, n,\) define \(\alpha_{i}:=\mathrm{P}\left[\mathcal{A}_{i} \mid \mathcal{A}_{1} \cap \cdots \cap \mathcal{A}_{i-1}\right]\) (assume that \(\left.\mathrm{P}\left[\mathcal{A}_{1} \cap \cdots \cap \mathcal{A}_{n-1}\right] \neq 0\right)\). Show that \(\mathrm{P}\left[\mathcal{A}_{1} \cap \cdots \cap \mathcal{A}_{n}\right]=\alpha_{1} \cdots \alpha_{n}\)

Let \(\mathcal{B}\) be an event, and let \(\left\\{\mathcal{B}_{i}\right\\}_{i \in I}\) be a finite, pairwise disjoint family of events whose union is \(B\). Generalizing the law of total probability (equations (8.9) and (8.10)\(),\) show that for every event \(\mathcal{A},\) we have \(\mathrm{P}[\mathcal{A} \cap \mathcal{B}]=\) \(\sum_{i \in I} \mathrm{P}\left[\mathcal{A} \cap \mathcal{B}_{i}\right],\) and if \(\mathrm{P}[B] \neq 0\) and \(I^{*}:=\left\\{i \in I: \mathrm{P}\left[\mathcal{B}_{i}\right] \neq 0\right\\},\) then $$ \mathrm{P}[\mathcal{A} \mid \mathcal{B}] \mathrm{P}[\mathcal{B}]=\sum_{i \in I^{*}} \mathrm{P}\left[\mathcal{A} \mid \mathcal{B}_{i}\right] \mathrm{P}\left[\mathcal{B}_{i}\right] $$ Also show that if \(\mathrm{P}\left[\mathcal{A} \mid \mathcal{B}_{i}\right] \leq \alpha\) for each \(i \in I^{*},\) then \(\mathrm{P}[\mathcal{A} \mid \mathcal{B}] \leq \alpha\)

Let \(\mathcal{B}\) be an event with \(\mathrm{P}[\mathcal{B}] \neq 0,\) and let \(\left\\{\mathcal{C}_{i}\right\\}_{i \in I}\) be a finite, pairwise disjoint family of events whose union contains \(\mathcal{B}\). Again, generalizing the law of total probability, show that for every event \(\mathcal{A},\) if \(I^{*}:=\left\\{i \in I: \mathrm{P}\left[B \cap C_{i}\right] \neq 0\right\\},\) then we have $$ \mathrm{P}[\mathcal{A} \mid \mathcal{B}]=\sum_{i \in I^{*}} \mathrm{P}\left[\mathcal{A} \mid \mathcal{B} \cap C_{i}\right] \mathrm{P}\left[\mathcal{C}_{i} \mid \mathcal{B}\right] $$

Three fair coins are tossed. Let \(\mathcal{A}\) be the event that at least two coins are heads. Let \(\mathcal{B}\) be the event that the number of heads is odd. Let \(\mathcal{C}\) be the event that the third coin is heads. Are \(\mathcal{A}\) and \(\mathcal{B}\) independent? \(\mathcal{A}\) and \(\mathcal{C} ? \mathcal{B}\) and \(\mathcal{C} ?\)

Consider again the situation in Example \(8.13,\) but now suppose that the patient is visiting the doctor because he has symptom \(Y\). Furthermore, it is known that everyone who has disease \(X\) exhibits symptom \(Y,\) while \(10 \%\) of the population overall exhibits symptom \(Y\). Assuming that the accuracy of the test is not affected by the presence of symptom \(Y,\) how should the doctor advise his patient should the test come out positive?

This exercise develops an alternative proof, based on probability theory, of Theorem 2.11 . Let \(n\) be a positive integer and consider an experiment in which a number \(a\) is chosen uniformly at random from \(\\{0, \ldots, n-1\\}\). If \(n=p_{1}^{e_{1}} \cdots p_{r}^{e_{r}}\) is the prime factorization of \(n,\) let \(\mathcal{A}_{i}\) be the event that \(a\) is divisible by \(p_{i},\) for \(i=1, \ldots, r\) (a) Show that \(\varphi(n) / n=\mathrm{P}\left[\overline{\mathcal{A}}_{1} \cap \cdots \cap \overline{\mathcal{A}}_{r}\right],\) where \(\varphi\) is Euler's phi function. (b) Show that if \(J \subseteq\\{1, \ldots, r\\},\) then $$ \mathrm{P}\left[\bigcap_{j \in J} \mathcal{A}_{j}\right]=1 / \prod_{j \in J} p_{j} $$ Conclude that \(\left\\{\mathcal{A}_{i}\right\\}_{i=1}^{r}\) is mutually independent, and that \(\mathrm{P}\left[\mathcal{A}_{i}\right]=1 / p_{i}\) for each \(i=1, \ldots, r\) (c) Using part (b), deduce that $$ \mathrm{P}\left[\overline{\mathcal{A}}_{1} \cap \cdots \cap \overline{\mathcal{A}}_{r}\right]=\prod_{i=1}^{r}\left(1-1 / p_{i}\right) . $$ (d) Combine parts (a) and (c) to derive the result of Theorem 2.11 that $$ \varphi(n)=n \prod_{i=1}^{r}\left(1-1 / p_{i}\right) $$

Suppose \(X\) and \(X^{\prime}\) are random variables that take values in a set \(S\) and that have essentially the same distribution. Show that if \(f: S \rightarrow T\) is a function, then \(f(X)\) and \(f\left(X^{\prime}\right)\) have essentially the same distribution.

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a family of random variables, and let \(S_{i}\) be the image of \(X_{i}\) for \(i=1, \ldots, n .\) Show that \(\left\\{X_{i}\right\\}_{i=1}^{n}\) is mutually independent if and only if for each \(i=2, \ldots, n,\) and for all \(s_{1} \in S_{1}, \ldots, s_{i} \in S_{i},\) we have $$ \mathrm{P}\left[X_{i}=s_{i} \mid\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]=\mathrm{P}\left[X_{i}=s_{i}\right] $$

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a family of random variables, and let \(S_{i}\) be the image of \(X_{i}\) for \(i=1, \ldots, n .\) Show that \(\left\\{X_{i}\right\\}_{i=1}^{n}\) is mutually independent if and only if for each \(i=2, \ldots, n,\) and for all \(s_{1} \in S_{1}, \ldots, s_{i} \in S_{i},\) we have $$ \mathrm{P}\left[X_{i}=s_{i} \mid\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]=\mathrm{P}\left[X_{i}=s_{i}\right] $$

Let \(X\) and \(Y\) be independent random variables, where \(X\) is uniformly distributed over a set \(S,\) and \(Y\) is uniformly distributed over a set \(T \subseteq S\). Define a third random variable \(Z\) as follows: if \(X \in T,\) then \(Z:=X\); otherwise, \(Z:=Y\). Show that \(Z\) is uniformly distributed over \(T\).

Let \(n\) be a positive integer, and let \(X\) be a random variable, uniformly distributed over \(\\{0, \ldots, n-1\\} .\) For each positive divisor \(d\) of \(n\), let us define the random variable \(X_{d}:=X \bmod d\). Show that: (a) if \(d\) is a divisor of \(n,\) then the variable \(X_{d}\) is uniformly distributed over \(\\{0, \ldots, d-1\\}\) (b) if \(d_{1}, \ldots, d_{k}\) are divisors of \(n,\) then \(\left\\{X_{d_{i}}\right\\}_{i=1}^{k}\) is mutually independent if and only if \(\left\\{d_{i}\right\\}_{i=1}^{k}\) is pairwise relatively prime.

Suppose \(X\) and \(Y\) are random variables, each uniformly distributed over \(\mathbb{Z}_{2},\) but not necessarily independent. Show that the distribution of \((X, Y)\) is the same as the distribution of \((X+1, Y+1)\).

Let \(I:=\\{1, \ldots, n\\},\) where \(n \geq 2,\) let \(B:=\\{0,1\\},\) and let \(G\) be a finite abelian group, with \(|G|>1 .\) Suppose that \(\left\\{X_{i b}\right\\}_{(i, b) \in I \times B}\) is a mutually independent family of random variables, each uniformly distributed over \(G\). For each \(\beta=\left(b_{1}, \ldots, b_{n}\right) \in B^{\times n},\) let us define the random variable \(Y_{\beta}:=X_{1 b_{1}}+\cdots+X_{n b_{n}}\) Show that each \(Y_{\beta}\) is uniformly distributed over \(G,\) and that \(\left\\{Y_{\beta}\right\\}_{\beta \in B^{\times n}}\) is 3 -wise independent, but not 4 -wise independent.

Suppose \(X\) and \(Y\) take non-negative real values, and that \(Y \leq c\) for some constant \(c .\) Show that \(E[X Y] \leq c E[X]\)

Let \(X\) be a \(0 / 1\) -valued random variable. Show that \(\operatorname{Var}[X] \leq 1 / 4\).

Let \(\mathcal{B}\) be an event with \(\mathrm{P}[\mathcal{B}] \neq 0,\) and let \(\left\\{\boldsymbol{B}_{i}\right\\}_{i \in I}\) be a finite, pairwise disjoint family of events whose union is \(\mathcal{B}\). Generalizing the law of total expectation \((8.24),\) show that for every real-valued random variable \(X,\) if \(I^{*}:=\left\\{i \in I: \mathrm{P}\left[\mathcal{B}_{i}\right] \neq 0\right\\},\) then we have $$ \mathrm{E}[X \mid \mathcal{B}] \mathrm{P}[\mathcal{B}]=\sum_{i \in I^{*}} \mathrm{E}\left[X \mid \mathcal{B}_{i}\right] \mathrm{P}\left[\mathcal{B}_{i}\right] $$ Also show that if \(\mathrm{E}\left[X \mid \mathcal{B}_{i}\right] \leq \alpha\) for each \(i \in I^{*}\), then \(\mathrm{E}[X \mid \mathcal{B}] \leq \alpha\)

Let \(B\) be an event with \(\mathrm{P}[B] \neq 0,\) and let \(\left\\{C_{i}\right\\}_{i \in I}\) be a finite, pairwise disjoint family of events whose union contains \(\mathcal{B}\). Again, generalizing the law of total expectation, show that for every real-valued random variable \(X,\) if \(I^{*}:=\left\\{i \in I: \mathrm{P}\left[B \cap C_{i}\right] \neq 0\right\\},\) then we have $$ \mathrm{E}[X \mid \mathcal{B}]=\sum_{i \in I^{*}} \mathrm{E}\left[X \mid \mathcal{B} \cap C_{i}\right] \mathrm{P}\left[\mathcal{C}_{i} \mid \mathcal{B}\right] $$

This exercise makes use of the notion of convexity (see \(\$ \mathrm{~A} 8\) ). (a) Prove Jensen's inequality: if \(f\) is convex on an interval, and \(X\) is a random variable taking values in that interval, then \(\mathrm{E}[f(X)] \geq f(\mathrm{E}[X]) .\) Hint: use induction on the size of the image of \(X\). (Note that Theorem 8.19 is a special case of this, with \(f(s):=s^{2}\).) (b) Using part (a), show that if \(X\) takes non-negative real values, and \(\alpha\) is a positive number, then \(\mathrm{E}\left[X^{\alpha}\right] \geq \mathrm{E}[X]^{\alpha}\) if \(\alpha \geq 1,\) and \(\mathrm{E}\left[X^{\alpha}\right] \leq \mathrm{E}[X]^{\alpha}\) if \(\alpha \leq 1\) (c) Using part (a), show that if \(X\) takes positive real values, then \(\mathrm{E}[X] \geq e^{\mathrm{E}[\log X]}\). (d) Using part (c), derive the arithmetic/geometric mean inequality: for all positive numbers \(x_{1}, \ldots, x_{n},\) we have $$ \left(x_{1}+\cdots+x_{n}\right) / n \geq\left(x_{1} \cdots x_{n}\right)^{1 / n} $$

For real-valued random variables \(X\) and \(Y\), their covariance is defined as \(\operatorname{Cov}[X, Y]:=E[X Y]-E[X] E[Y] .\) Show that: (a) if \(X, Y,\) and \(Z\) are real-valued random variables, and \(a\) is a real number, then \(\operatorname{Cov}[X+Y, Z]=\operatorname{Cov}[X, Z]+\operatorname{Cov}[Y, Z]\) and \(\operatorname{Cov}[a X, Z]=a \operatorname{Cov}[X, Z]\) (b) if \(\left\\{X_{i}\right\\}_{i \in I}\) is a finite family of real-valued random variables, then $$ \operatorname{Var}\left[\sum_{i \in I} X_{i}\right]=\sum_{i \in I} \operatorname{Var}\left[X_{i}\right]+\sum_{i, j \in I \atop i \neq j} \operatorname{Cov}\left[X_{i}, X_{j}\right] $$

Let \(f:[0,1] \rightarrow \mathbb{R}\) be a function that is "nice" in the following sense: for some constant \(c,\) we have \(|f(s)-f(t)| \leq c|s-t|\) for all \(s, t \in[0,1] .\) This condition is implied, for example, by the assumption that \(f\) has a derivative that is bounded in absolute value by \(c\) on the interval \([0,1] .\) For each positive integer \(n,\) define the polynomial \(B_{n, f}:=\sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right) f(k / n) T^{k}(1-T)^{n-k} \in \mathbb{R}[T] .\) Show that \(\left|B_{n, f}(p)-f(p)\right| \leq c / 2 \sqrt{n}\) for all positive integers \(n\) and all \(p \in[0,1] .\) Hint: let \(X\) be a random variable with a binomial distribution that counts the number of successes among \(n\) Bernoulli trials, each of which succeeds with probability \(p,\) and begin by observing that \(\boldsymbol{B}_{n, f}(p)=\mathrm{E}[f(X / n)] .\) The polynomial \(\boldsymbol{B}_{n, f}\) is called the \(n\) th Bernstein approximation to \(f,\) and this result proves a classical result that any "nice" function can approximated to arbitrary precision by a polynomial of sufficiently high degree.

In each step of a random walk, we toss a coin, and move either one unit to the right, or one unit to the left, depending on the outcome of the coin toss. The question is, after \(n\) steps, what is our expected distance from the starting point? Let us model this using a mutually independent family of random variables \(\left\\{Y_{i}\right\\}_{i=1}^{n},\) with each \(Y_{i}\) uniformly distributed over \(\\{-1,1\\},\) and define \(Y:=Y_{1}+\cdots+Y_{n} .\) Show that the \(c_{1} \sqrt{n} \leq \mathrm{E}[|Y|] \leq c_{2} \sqrt{n},\) for some constants \(c_{1}\) and \(c_{2}\)

The goal of this exercise is to prove that with probability very close to \(1,\) a random number between 1 and \(m\) has very close to log \(\log m\) prime factors. To prove this result, you will need to use appropriate theorems from Chapter 5 . Suppose \(N\) is a random variable that is uniformly distributed over \(\\{1, \ldots, m\\},\) where \(m \geq 3 .\) For \(i=1, \ldots, m,\) let \(D_{i}\) be the indicator variable for the event that \(i\) divides \(N\). Also, define \(X:=\sum_{p \leq m} D_{p},\) where the sum is over all primes \(p \leq m,\) so that \(X\) counts the number of distinct primes dividing \(N\). Show that: (a) \(1 / i-1 / m<\mathrm{E}\left[D_{i}\right] \leq 1 / i,\) for each \(i=1, \ldots, m ;\) (b) \(|\mathrm{E}[X]-\log \log m| \leq c_{1}\) for some constant \(c_{1} ;\) (c) for all primes \(p, q,\) where \(p \leq m, q \leq m,\) and \(p \neq q,\) we have $$ \operatorname{Cov}\left[D_{p}, D_{q}\right] \leq \frac{1}{m}\left(\frac{1}{p}+\frac{1}{q}\right) $$ where Cov is the covariance, as defined in Exercise \(8.26 ;\) (d) \(\operatorname{Var}[X] \leq \log \log m+c_{2}\) for some constant \(c_{2}\); (e) for some constant \(c_{3},\) and for every \(\alpha \geq 1,\) we have $$ \mathrm{P}\left[|X-\log \log m| \geq \alpha(\log \log m)^{1 / 2}\right] \leq \alpha^{-2}\left(1+c_{3}(\log \log m)^{-1 / 2}\right) $$

You are given three biased coins, where for \(i=1,2,3, \operatorname{coin} i\) comes up heads with probability \(p_{i} .\) The coins look identical, and all you know is the following: (1) \(\left|p_{1}-p_{2}\right|>0.01\) and (2) either \(p_{3}=p_{1}\) or \(p_{3}=p_{2}\). Your goal is to determine whether \(p_{3}\) is equal to \(p_{1}\), or to \(p_{2}\). Design a random experiment to determine this. The experiment may produce an incorrect result, but this should happen with probability at most \(10^{-12}\). Try to use a reasonable number of coin tosses.

Consider the following game, parameterized by a positive integer \(n .\) One rolls a pair of dice, and records the value of their sum. This is repeated until some value \(\ell\) is recorded \(n\) times, and this value \(\ell\) is declared the "winner." It is intuitively clear that 7 is the most likely winner. Let \(\alpha_{n}\) be the probability that 7 does not win. Give a careful argument that \(\alpha_{n} \rightarrow 0\) as \(n \rightarrow \infty\). Assume that the rolls of the dice are mutually independent.

Let \(\alpha_{1}, \ldots, \alpha_{m}\) be real numbers that sum to 1. Show that \(0 \leq\) \(\overline{\sum_{s=1}^{m}\left(\alpha_{s}-1 / m\right)^{2}}=\sum_{s=1}^{m} \alpha_{s}^{2}-1 / m,\) and in particular, \(\sum_{s=1}^{m} \alpha_{s}^{2} \geq 1 / m\)

Suppose that the family of random variables \(X, Y, Y^{\prime}\) is mutually independent, where \(X\) has image \(S,\) and where \(Y\) and \(Y^{\prime}\) have the same distribution on a set \(T\). Let \(\phi\) be a predicate on \(S \times T,\) and let \(\alpha:=\mathrm{P}[\phi(X, Y)] .\) Show that \(\mathrm{P}\left[\phi(X, Y) \cap \phi\left(X, Y^{\prime}\right)\right] \geq \alpha^{2} .\) In addition, show that if \(Y\) and \(Y^{\prime}\) are both uniformly distributed over \(T,\) then \(\mathrm{P}\left[\phi(X, Y) \cap \phi\left(X, Y^{\prime}\right) \cap\left(Y \neq Y^{\prime}\right)\right] \geq \alpha^{2}-\alpha /|T|\)

Let \(\alpha_{1}, \ldots, \alpha_{m}\) be non-negative real numbers that sum to 1. Let \(S:=\\{1, \ldots, m\\},\) and for \(n=1, \ldots, m,\) let \(S^{(n)}:=\\{\mathcal{T} \subseteq S:|\mathcal{T}|=n\\},\) and define $$ P_{n}\left(\alpha_{1}, \ldots, \alpha_{m}\right):=\sum_{T \in S^{(n)}} \prod_{t \in T} \alpha_{t} $$ Show that \(P_{n}\left(\alpha_{1}, \ldots, \alpha_{m}\right)\) is maximized when \(\alpha_{1}=\cdots=\alpha_{m}=1 / m\). Hint: first argue that if \(\alpha_{s}<\alpha_{t},\) then for every \(\varepsilon \in\left[0, \alpha_{t}-\alpha_{s}\right],\) replacing the pair \(\left(\alpha_{s}, \alpha_{t}\right)\) by \(\left(\alpha_{s}+\varepsilon, \alpha_{t}-\varepsilon\right)\) does not decrease the value of \(P_{n}\left(\alpha_{1}, \ldots, \alpha_{m}\right)\)

Suppose that \(\left\\{X_{i}\right\\}_{i \in I}\) is a finite, non-empty, mutually independent family of random variables, where each \(X_{i}\) is uniformly distributed over a finite set \(S\). Suppose that \(\left\\{Y_{i}\right\\}_{i \in I}\) is another finite, non-empty, mutually independent family of random variables, where each \(Y_{i}\) has the same distribution and takes values in the set \(S\). Let \(\alpha\) be the probability that the \(X_{i}\) 's are distinct, and \(\beta\) be the probability that the \(Y_{i}\) 's are distinct. Using the previous exercise, show that \(\beta \leq \alpha\).

Suppose \(n\) balls are thrown into \(m\) bins. Let \(\mathcal{A}\) be the event that there is some bin that is empty. Assuming that the throws are mutually independent, and that \(n \geq m(\log m+t)\) for some \(t \geq 0,\) show that \(\mathrm{P}[\mathcal{A}] \leq e^{-t}\).

Show that for every prime \(p,\) there exists a pairwise independent family of random variables \(\left\\{X_{i}\right\\}_{i \in \mathbb{Z}_{p}},\) where each \(X_{i}\) is uniformly distributed over \(\mathbb{Z}_{p},\) and yet the probability that all the \(X_{i}\) 's are distinct is \(1-1 / p\).

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a finite, non-empty, 4 -wise independent family of random variables, each uniformly distributed over a set \(S\). Let \(\alpha\) be the probability that the \(X_{i}\) 's are distinct. For \(i, j=1, \ldots, n,\) let \(C_{i j}\) be the indicator variable for the event that \(X_{i}=X_{j},\) and define \(K:=\\{(i, j): 1 \leq i \leq n-1, i+1 \leq j \leq n\\}\) and \(Z:=\sum_{(i, j) \in K} C_{i j} .\) Show that: (a) \(\left\\{C_{i j}\right\\}_{(i, j) \in K}\) is pairwise independent; (b) \(\mathrm{E}[Z]=n(n-1) / 2 m\) and \(\operatorname{Var}[Z]=(1-1 / m) \mathrm{E}[Z] ;\) (c) \(\alpha \leq 1 / \mathrm{E}[Z]\) (d) \(\alpha \leq 1 / 2,\) provided \(n(n-1) \geq 2 m\) (hint: Exercise 8.4).

Let \(k\) be a positive integer, let \(n:=k^{2}-k+1,\) let \(I\) and \(S\) be sets of size \(n,\) and let \(s_{0}\) be a fixed element of \(S .\) Also, let \(I^{(k)}:=\\{J \subseteq I:|J|=k\\}\), and let \(\Pi\) be the set of all permutations on \(S\). For each \(J \in I^{(k)},\) let \(f_{J}\) be some function that \(\operatorname{maps} J\) to \(s_{0},\) and maps \(I \backslash J\) injectively into \(S \backslash\left\\{s_{0}\right\\} .\) For \(\pi \in \Pi\) \(J \in I^{(k)},\) and \(i \in I,\) define \(\rho_{i}(\pi, J):=\pi\left(f_{J}(i)\right) .\) Finally, let \(Y\) be uniformly distributed over \(\Pi \times I^{(k)},\) and for \(i \in I,\) define \(X_{i}:=\rho_{i}(Y) .\) Show that \(\left\\{X_{i}\right\\}_{i \in I}\) is pairwise independent, with each \(X_{i}\) uniformly distributed over \(S,\) and yet the number of \(X_{i}\) 's with the same value is always at least \(\sqrt{n}\).

Let \(S\) be a set of size \(m \geq 1,\) and let \(s_{0}\) be an arbitrary, fixed element of \(S\). Let \(F\) be a random variable that is uniformly distributed over the set of all \(m^{m}\) functions from \(S\) into \(S .\) Let us define random variables \(X_{i},\) for \(i=0,1,2, \ldots,\) as follows: $$ X_{0}:=s_{0}, \quad X_{i+1}:=F\left(X_{i}\right)(i=0,1,2, \ldots) $$ Thus, the value of \(X_{i}\) is obtained by applying the function \(F\) a total of \(i\) times to the starting value \(s_{0}\). Since \(S\) has size \(m,\) the sequence \(\left\\{X_{i}\right\\}_{i=0}^{\infty}\) must repeat at some point; that is, there exists a positive integer \(n\) (with \(n \leq m\) ) such that \(X_{n}=X_{i}\) for some \(i=0, \ldots, n-1 .\) Define the random variable \(Y\) to be the smallest such value \(n .\) (a) Show that for every \(i \geq 0\) and for all \(s_{1}, \ldots, s_{i} \in S\) such that \(s_{0}, s_{1}, \ldots, s_{i}\) are distinct, the conditional distribution of \(X_{i+1}\) given the event \(\left(X_{1}=s_{1}\right) \cap\) \(\cdots \cap\left(X_{i}=s_{i}\right)\) is the uniform distribution on \(S .\) (b) Show that for every integer \(n \geq 1,\) we have \(Y \geq n\) if and only if the random variables \(X_{0}, X_{1}, \ldots, X_{n-1}\) take on distinct values. (c) From parts (a) and (b), show that for each \(n=1, \ldots, m,\) we have $$ \mathrm{P}[Y \geq n \mid Y \geq n-1]=1-(n-1) / m $$ and conclude that $$ \mathrm{P}[Y \geq n]=\prod_{i=1}^{n-1}(1-i / m) \leq e^{-n(n-1) / 2 m} $$ (d) Using part (c), show that $$ \mathrm{E}[Y]=\sum_{n \geq 1} \mathrm{P}[Y \geq n] \leq \sum_{n \geq 1} e^{-n(n-1) / 2 m}=O\left(m^{1 / 2}\right) $$ (e) Modify the above argument to show that \(\mathrm{E}[Y]=\Omega\left(m^{1 / 2}\right)\).