Probability & Expectation

Expected fixed points of a random permutation: $n\cdot\tfrac1n = 1$. Expected number of adjacent equal letters, expected number of records in a random sequence ($H_n$), expected inversions ($\binom n2/2$) — all indicator sums. The distribution may be a nightmare; the expectation is a one-liner. Coupon collector: waits are geometric with expectations $\tfrac{n}{n-k}$, summing to $nH_n$ ($\tfrac{25}{3}$ for $n = 4$).

Two uniform points on $[0,1]$: $E|X - Y| = \tfrac13$, $E[\max] = \tfrac23$, $P(|X - Y| < \tfrac14) = \tfrac{7}{16}$ (unit-square pictures). Broken-stick triangle: $\tfrac14$. Buffon's needle: $\tfrac{2\ell}{\pi d}$. Random walk returns: $\binom42/16 = \tfrac38$ after four steps; the $\tfrac{1}{\sqrt{\pi n}}$ decay is why $\sum P(\text{return at } 2n) = \infty$ and the 1D walk is recurrent, while in 3D it is not.

Expected rolls until two consecutive sixes: $42$. Expected steps for a walker advancing with probability $\tfrac23$ else staying, to go $3$ steps: $3\cdot\tfrac32 = 4.5$. Gambler's ruin from $k$ with target $N$ (fair coin): ruin probability $1 - \tfrac kN$, expected duration $k(N - k)$. Markov-chain steady states (the Linear Algebra course) are the long-run version of the same conditioning.

For discrete variables, $E[X + Y] = \sum_{x,y}(x + y)P(X = x, Y = y) = \sum_xx\sum_yP(X=x, Y=y) + \sum_yy\sum_xP(X=x,Y=y) = \sum_xxP(X = x) + \sum_yyP(Y = y)$ — the joint distribution marginalizes, and no independence was used. $\blacksquare$ Significance: the ENTIRE indicator method rests on this; it is worth stating in a solution that independence is not required, because graders check that you know.

After $k$ distinct coupons are held, each draw is new with probability $\tfrac{n-k}{n}$, independently of the past; the number of draws until the next new one is geometric with mean $\tfrac{n}{n-k}$. Sum over $k = 0, \ldots, n - 1$ (linearity): $n\left(\tfrac1n + \tfrac{1}{n-1} + \cdots + 1\right) = nH_n$. $\blacksquare$ Significance: $nH_n \approx n\ln n$ is the universal cost of "cover everything by random sampling" — hashing, epidemic spreading, and randomized algorithms all hit this bound.

Step 1 — the CDF of the max: $P(\max \le t) = t^3$.

Step 2 — for a nonnegative variable, $E[M] = \int_0^1P(M > t)\,dt = \int_0^1(1 - t^3)dt = 1 - \tfrac14 = \tfrac34$.

Step 3 — general pattern: $E[\max\text{ of }n] = \tfrac{n}{n+1}$ and $E[\min] = \tfrac{1}{n+1}$; the $n$ order statistics split $[0,1]$ into $n + 1$ pieces of equal expected length.

Step 4 — the tail-integral formula $E[X] = \int_0^\infty P(X > t)\,dt$ is the fastest route to expectations of maxima, minima, and waiting times.

Step 1 — let $p_k$ be the probability of reaching $10$ from $k$: $p_k = \tfrac12p_{k-1} + \tfrac12p_{k+1}$, $p_0 = 0$, $p_{10} = 1$. The recurrence forces $p_k$ linear: $p_k = \tfrac{k}{10}$, so $p_3 = 0.3$.

Step 2 — let $E_k$ be the expected duration: $E_k = 1 + \tfrac12E_{k-1} + \tfrac12E_{k+1}$ with $E_0 = E_{10} = 0$; the particular solution of the constant inhomogeneity is $-k^2$, so $E_k = k(10 - k)$ and $E_3 = 21$.

Step 3 — sanity: from the midpoint $E_5 = 25$ is the longest expected game; near the boundaries games end fast.

Step 4 — conditioning on one step turned a random process into two linear recurrences — the whole method.