1 Probability and Computing 1.1 Events and Probability 1.3 Moments and Deviations

1.2 Discrete Random Variable and Expectation

Exercise 1.2.1 (Exercise 2.2 [MU17]).

A monkey types on a 26-letter keyboard that has lowercase letters only. Each letter is chosen independently and uniformly at random from the alphabet. If the monkey types 1,000,000 letters, what is the expected number of times the sequence “proof” appears?

Proof.

This is exactly a brain teaser in linearity of expectation.

Say $X_{i}$ are 0-1 random variables indicating if the sequence “proof” appears at $i^{\mathrm{th}}$ alphabet. Then $X=\sum X_{i}$ is the random variable for the number of appearances of the sequence “proof”.

By linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\operatorname*{\mathbb{E}}\left[\sum_% {i\in[1,999996]}X_{i}\right]=\sum_{i\in[1,999996]}\operatorname*{\mathbb{E}}% \left[X_{i}\right]=999996\times\left(\frac{1}{26}\right)^{5}.

∎

Exercise 1.2.2 (Exercise 2.12 [MU17]).

We draw cards uniformly at random with replacement from a deck of $n$ cards. What is the expected number of cards we must draw until we have seen all $n$ cards in the deck? If we draw $2n$ cards, what is the expected number of cards in the deck that are not chosen at all? Chosen exactly once?

Proof.

The problem is a combination of “coupon collection” problem and “indicator” problem.

First one is the “coupon collection” problem, then let $X_{i}$ be the number of draws to draw $i^{\mathrm{th}}$ different card, which is a geometrically distributed random variable with parameter $\frac{n-i+1}{n}$ , and $X=\sum X_{i}$ be the total number of draws to draw all $n$ different cards. $\operatorname*{\mathbb{E}}\left[X\right]=n\ln n+\Theta(n)$ .

Later, we introduce 0-1 random variables $\{Y_{i}\}_{i\in[1,n]}$ indicating if the $i^{\mathrm{th}}$ cards is not drawn once in the $2n$ draws, then $\Pr\left[Y_{i}=1\right]=\left(\frac{n-1}{n}\right)^{2n}$ . Let $Y=\sum Y_{i}$ for the number of cards not drawn at all in $2n$ draws, then

\operatorname*{\mathbb{E}}\left[Y\right]=\operatorname*{\mathbb{E}}\left[\sum_% {i\in[1,n]}Y_{i}\right]=\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}\left[Y_{i}% \right]=n\cdot\left(\frac{n-1}{n}\right)^{2n}.

We also introduce 0-1 random variables $\{Z_{i}\}_{i\in[1,n]}$ indicating if the $i^{\mathrm{th}}$ card is drawn only once in the $2n$ draws, then $\Pr\left[Z_{i}=1\right]=2n\cdot\frac{1}{n}\cdot\left(\frac{n-1}{n}\right)^{2n-1}$ . Let $Z=\sum Z_{i}$ for the number of cards drawn only once in $2n$ draws, then

\operatorname*{\mathbb{E}}\left[Z\right]=\operatorname*{\mathbb{E}}\left[\sum_% {i\in[1,n]}Z_{i}\right]=\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}\left[Z_{i}% \right]=2n\cdot\left(\frac{n-1}{n}\right)^{2n-1}.

∎

Exercise 1.2.3 (Exercise 2.16 [MU17]).

Suppose we flip a coin $n$ times to obtain a sequence of flips $\{X_{i}\}_{i\in[1,n]}$ . A streak of flips is a consecutive subsequence of flips that are all the same.

•

Let $n$ be a power of 2. Show that the expected number of streaks of length $\log_{2}n+1$ is $1-o(1)$ .
•

Show that, for sufficiently large $n$ , the probability that there is no streak of length at least $\left\lfloor\log_{2}n-2\log_{2}\log_{2}n\right\rfloor$ is less than $1/n$ .

Proof.

We first consider the expected number of streaks of length at least $\log_{2}n+1$ . This is solved by the linearity of expectation, by introducing $\{X_{i}\}_{i\in[1,k]}$ 0-1 random variables, where $k=n-\log_{2}n$ , indicating the $i^{\mathrm{th}}$ flip starts a streak of length at least $\log_{2}n+1$ . The probability for $X_{i}=1$ can be upper bounded as follows

\Pr\left[X_{i}=1\right]=2\cdot\frac{1}{2^{\log_{2}n+1}}=\frac{1}{n},

as streak on either face works. Therefore, number of streaks is $X=\sum_{i\in[1,k]}X_{i}$ , and the expectation is

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{i\in[1,k]}X_{i}\right]=% \sum_{i\in[1,k]}\operatorname{\mathbb{E}}\left[X_{i}\right]$
		$\displaystyle=\left(n-\log_{2}n\right)\operatorname*{\mathbb{E}}\left[X_{i}\right]$
		$\displaystyle=\frac{n-\log_{2}n}{n}=1-o(1).$

We now show that the probability of no streaks of length at least $\ell=\left\lfloor\log_{2}n-2\log_{2}\log_{2}n\right\rfloor$ is less than $1/n$ . We consider $n/\ell$ segments of $\ell$ length flips, and thus introduce $n/\ell$ independent 0-1 random variables indicating if the $i^{\mathrm{th}}$ segment starts a streak of length at least $\ell$ . Therefore $\Pr\left[Y_{i}=1\right]=2/2^{\ell}$ .

Though $n/\ell$ segments is less than the total number of potential segments among $n$ flips, it suffices for giving a sufficiently low probability. We now bound the probability of all $n/\ell$ segments has no streaks of length $\ell$ by

\Pr\left[\bigcap_{i\in[1,n/\ell]}Y_{i}=0\right]=\left(1-\frac{2}{2^{\ell}}% \right)^{n/\ell}=\left(1-\frac{1}{2^{\ell-1}}\right)^{2^{\ell-1}\cdot n/(\ell% \cdot 2^{\ell-1})}\leq\left(\frac{1}{e}\right)^{n/(\ell\cdot 2^{\ell-1})}.

Let $\eta=n/\left(\ell\cdot 2^{\ell-1}\right)$ . By $\left\lfloor x\right\rfloor\leq x$ for any $x$ , we lower bound $\eta$ by

	$\displaystyle\eta$	$\displaystyle=\frac{n}{\ell\cdot 2^{\ell-1}}=\frac{2n}{\left\lfloor\log_{2}n-2% \log_{2}\log_{2}n\right\rfloor}\cdot\frac{1}{2^{\left\lfloor\log_{2}n-2\log_{2% }\log_{2}n\right\rfloor}}$
		$\displaystyle\geq\frac{2n}{\log_{2}n-2\log_{2}\log_{2}n}\cdot\frac{\log_{2}^{2% }n}{n}=\frac{2\log_{2}^{2}n}{\log_{2}n-2\log_{2}\log_{2}n}$
		$\displaystyle\geq 2\log_{2}n.$

Therefore, $\exp(-\eta)$ is at most $1/n$ , and thus completes the proof. ∎

Exercise 1.2.4 (Exercise 2.20 [MU17]).

A permutation on the numbers $[1,n]$ can be represented as a function $\pi:[1,n]\mapsto[1,n]$ . A fixed point of a permutation $\pi$ is a value for which $\pi(x)=x$ . Find the expected number of fixed points for a permutation chosen uniformly at random for all permutations.

Proof.

This is another indicator counting problem.

We introduce $n$ 0-1 random variables $\{X_{i}\}_{i\in[1,n]}$ indicating if $i^{\mathrm{th}}$ value is a fixed point for the permutation. Then $\Pr\left[X_{i}=1\right]=1/n$ , and thus the expectation of $X=\sum X_{i}$ , which is the number of fixed points in $\pi$ , is

\operatorname*{\mathbb{E}}\left[X\right]=\operatorname*{\mathbb{E}}\left[\sum_% {i\in[1,n]}X_{i}\right]=\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}\left[X_{i}% \right]=1.

∎

Theorem 1.2.5 (Jensen’s Inequality).

If $f$ is a convex function, then

\operatorname*{\mathbb{E}}\left[f(X)\right]\geq f(\operatorname*{\mathbb{E}}% \left[X\right]).

If $f$ is concave, then

\operatorname*{\mathbb{E}}\left[f(X)\right]\leq f(\operatorname*{\mathbb{E}}% \left[X\right]).

Definition 1.2.6.

The expression $\operatorname*{\mathbb{E}}\left[Y\mid X\right]$ is a random variable $f(X)$ that takes on value $\operatorname*{\mathbb{E}}\left[Y\mid X=x\right]$ when $X=x$ .

Lemma 1.2.7.

\operatorname*{\mathbb{E}}\left[Y\right]=\operatorname*{\mathbb{E}}\left[% \operatorname*{\mathbb{E}}\left[Y\mid X\right]\right].