iii. Probability and Expectation

Almost every expectation problem is solved by one of: linearity over indicators, the tail-sum formula, conditioning on the first step (a DP or linear system), or a martingale / potential function with optional stopping. Answers are usually requested as $P\cdot Q^{-1}\mathrm{mod}p$: keep all probabilities as mint and never touch floating point. Expectation DPs are in Expected Value DP.

Rules

Rule	Statement
conditional probability	$P(A\mid B)=P(A\cap B)/P(B)$
total probability	$P(A)={\sum }_{i}P(A\mid B_i)P(B_i)$ for a partition $B_i$
Bayes	$P(B_i\mid A)=P(A\mid B_i)P(B_i)/{\sum }_{j}P(A\mid B_j)P(B_j)$
inclusion–exclusion / union bound	$P(\bigcup A_i) = \sum_{\emptyset \ne S}(-1)^{
independence	$P(A\cap B)=P(A)P(B)$; pairwise independence does not imply mutual
linearity	$E[\sum X_i]=\sum E[X_i]$ always
indicators	$E[\#\text{events}]=\sum P({\text{event}}_i)$
tail sum	$E[X]={\sum }_{t\ge 1}P(X\ge t)$ for $X\in {\mathbb{Z}}_{\ge 0}$; $E[X]={\int }_0^{\infty }P(X>t)dt$ for $X\ge 0$
total expectation	$E[X]={\sum }_{i}P(B_i)E[X\mid B_i]$
products	$E[XY]=E[X]E[Y]$ only for independent (uncorrelated) $X,Y$
variance	$\text{Var}(X)=E[X^2]-E[X{]}^2$; $\text{Var}(\sum X_i)=\sum \text{Var}(X_i)+2{\sum }_{i<j}\text{Cov}(X_i,X_j)$
second moment of a count	$E[X^2]={\sum }_{i,j}P(A_i\cap A_j)$ for $X=\sum [A_i]$

Proof: linearity, tail sum, and the variance identities

Linearity: $E[X+Y]={\sum }_{\omega }P(\omega )(X(\omega )+Y(\omega ))=E[X]+E[Y]$, using only the definition, so no independence is needed; an indicator has $E[[A]]=P(A)$. Tail sum: $X={\sum }_{t\ge 1}[X\ge t]$ for non-negative integers; take expectations (for real $X\ge 0$, $X={\int }_0^{\infty }[X>t]dt$ and exchange by Tonelli). Bayes and total probability are the definition of conditional probability rearranged and summed over a partition. Variance: expand $E[(\sum (X_i-{\mu }_i){)}^2]$; covariance vanishes for independent pairs because $E[XY]={\sum }_{x,y}xyP(X=x)P(Y=y)=E[X]E[Y]$. Second moment: $X^2={\sum }_{i,j}[A_i][A_j]={\sum }_{i,j}[A_i\cap A_j]$.

Distributions

Distribution	$P(X=k)$	$E[X]$	$\text{Var}(X)$
Bernoulli$(p)$	$p,1-p$	$p$	$p(1-p)$
binomial distribution $(n,p)$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$	$np$	$np(1-p)$
geometric distribution $(p)$ (trials until first success)	$(1-p{)}^{k-1}p$	$1/p$	$(1-p)/p^2$
negative binomial (trials until $r$ successes)	$\left(\genfrac{}{}{0ex}{}{k-1}{r-1}\right)p^r(1-p{)}^{k-r}$	$r/p$	$r(1-p)/p^2$
hypergeometric (draw $n$ of $N$, $K$ good)	$\left(\genfrac{}{}{0ex}{}{K}{k}\right)\left(\genfrac{}{}{0ex}{}{N-K}{n-k}\right)/\left(\genfrac{}{}{0ex}{}{N}{n}\right)$	$nK/N$	$n\frac{K}{N}\frac{N-K}{N}\frac{N-n}{N-1}$
Poisson$(\lambda )$	$e^{-\lambda }{\lambda }^k/k!$	$\lambda$	$\lambda$
uniform on $\{\mathrm{1..}n\}$	$1/n$	$\frac{n+1}{2}$	$\frac{n^2-1}{12}$
exponential$(\lambda )$ (density $\lambda e^{-\lambda t}$)	—	$1/\lambda$	$1/{\lambda }^2$

Binomial$(n,\lambda /n)\to$ Poisson$(\lambda )$ as $n\to \infty$ (rare events: number of collisions, of fixed points of a random permutation, of occurrences of a pattern). Geometric and exponential are memoryless: $P(X>s+t\mid X>s)=P(X>t)$.

Proof: the moments

Binomial and hypergeometric: sums of $n$ indicators with probability $p$ (resp. $K/N$ each by symmetry); variance adds for independent trials, and for the hypergeometric the pairwise covariance is $\frac{K}{N}\cdot \frac{K-1}{N-1}-\frac{K^2}{N^2}$ per ordered pair, which gives the finite-population factor $\frac{N-n}{N-1}$. Geometric: by the tail sum, $E[X]={\sum }_{t\ge 1}(1-p{)}^{t-1}=1/p$, and $E[X(X-1)]=\sum k(k-1)(1-p{)}^{k-1}p=2(1-p)/p^2$ (differentiate the geometric series twice), so $\text{Var}=2(1-p)/p^2+1/p-1/p^2=(1-p)/p^2$. Negative binomial: a sum of $r$ independent geometrics. Poisson: $\sum k{e}^{-\lambda }{\lambda }^k/k!=\lambda$ and $E[X(X-1)]={\lambda }^2$. Limit: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(\lambda /n{)}^k(1-\lambda /n{)}^{n-k}=\frac{{\lambda }^k}{k!}{\prod }_{i<k}(1-i/n)(1-\lambda /n{)}^{n-k}\to \frac{{\lambda }^k}{k!}{e}^{-\lambda }$. Uniform: $\sum i^2/n-((n+1)/2{)}^2=(n^2-1)/12$. Memorylessness: $P(X>s+t)/P(X>s)=(1-p{)}^t$ (resp. $e^{-\lambda t}$).

Classic expectations

Quantity	Value	Why
fixed points of a random permutation	$1$ (distribution $\to$ Poisson(1))	$n$ indicators of probability $1/n$
cycles / records (left-to-right maxima)	$H_n$	position $i$ is a record with probability $1/i$
inversions	$\left(\genfrac{}{}{0ex}{}{n}{2}\right)/2$	each pair inverted with probability $1/2$
local maxima (interior)	$(n-2)/3$	each interior triple: probability $1/3$
distinct values among $t$ uniform draws from $n$	$n(1-(1-1/n{)}^t)$	value $v$ missing with probability $(1-1/n{)}^t$
coupon collector: all $n$	$n{H}_n\approx n\ln n$	sum of geometrics with $p=\frac{n-i}{n}$
coupon collector: $m$ of $n$	$n(H_n-H_{n-m})$	the first $m$ phases
first repeated value (birthday)	$\approx \sqrt{\pi n/2}$; 50% at $\approx 1.18\sqrt{n}$	$P(\text{no repeat in }k)={\prod }_{i<k}(1-i/n)\approx e^{-k^2/2n}$
randomized quicksort comparisons	$2(n+1)H_n-4n\approx 2n\ln n$	elements of ranks $i<j$ compared iff one is the first pivot among ranks $i..j$: $\frac{2}{j-i+1}$
depth of a key in a random BST / treap	$2H_n-O(1)$	ancestors are records in both directions
$k$-th smallest of $n$ uniforms on $[0,1]$	$\frac{k}{n+1}$	$n+1$ points on a circle cut it into exchangeable gaps
maximum of $k$ fair $m$-sided dice	${\sum }_{t=1}^m(1-(\frac{t-1}{m}{)}^k)$	tail sum

double expectedMaxDice(int m, int k) { double e = 0; for (int t = 1; t <= m; t++) e += 1 - pow(double(t - 1) / m, k); return e; }
mint couponAll(int n) { mint s = 0; for (int i = 1; i <= n; i++) s += mint(n) / i; return s; }                  // n H_n
mint allCollectedBy(int n, ll t, const Comb& cb) {        // P(all n types seen within t draws), inclusion-exclusion
    mint s = 0; for (int k = 0; k <= n; k++) s += (k & 1 ? -1 : 1) * cb.C(n, k) * (mint(n - k) / n).pow(t); return s;
}
double birthdayNoCollision(ll n, ll k) { double p = 1; for (ll i = 0; i < k && p > 0; i++) p *= 1.0 - double(i) / n; return p; }

Birthday vs. coupon collector — two ends of the same occupancy process, easy to conflate: “when does the first collision happen” is $\Theta (\sqrt{n})$ (birthday — see Birthday Problem); “when has every value been seen” is $\Theta (n\log n)$ (coupon collector — Coupon Collector). Generalizing birthday to a collision among $j$ items (not just 2) pushes the threshold to $k\approx n^{(j-1)/j}$ — a triple collision needs $n^{2/3}$ draws, which is what Wagner’s generalized birthday algorithm exploits for $k$-sum problems. Generalizing coupon collector to “random walk visits every vertex” gives the cover time: $\Theta (n\log n)$ for the complete graph, $\Theta (n^2)$ for a path or cycle, $O(n^3)$ for any connected graph.

Both thresholds are the real engine behind several named algorithms, not just these two puzzles: Pollard’s rho and kangaroo (a random walk mod an unknown factor collides after $O(\sqrt{p})$ steps), meet-in-the-middle and baby-step-giant-step ($2^{n/2}$ from each half, matched by collision), and why an $n$-bit cryptographic hash gives only $n/2$ bits of collision resistance. Practically: $10^9+7$ collides with probability near 1 after hashing only $10^5$ distinct strings (birthday with $d\approx 10^9$), which is exactly why $2^{61}-1$ or double hashing is the right default modulus — see Hashing.

Proof: records, quicksort, order statistics, coupon collector

Records: among the first $i$ values every position is equally likely to hold the maximum, so position $i$ is a record with probability $1/i$; the cycle count has the same distribution (Foata’s bijection maps records to cycle starts). Quicksort: ranks $i<j$ are compared iff the first pivot chosen from ranks $i..j$ is $i$ or $j$ (until then they stay together; a pivot strictly between separates them forever); each of the $j-i+1$ ranks is equally likely to be first. Summing $\frac{2}{d+1}$ over the $n-d$ pairs at distance $d$ gives ${\sum }_{d=1}^{n-1}\frac{2(n-d)}{d+1}=2(n+1)H_n-4n$. BST depth: $j$ is an ancestor of $i$ iff $j$ is inserted first among the keys between them, probability $\frac{1}{|i-j|+1}$; sum over $j$. Order statistics: place $n+1$ uniform points on a circle of length 1 and cut at the first; the $n+1$ gaps are exchangeable with total 1, so each has mean $\frac{1}{n+1}$ and the $k$-th smallest is the sum of $k$ gaps. Coupon collector: after $i$ types are found, each draw is new with probability $\frac{n-i}{n}$, so the wait is geometric with mean $\frac{n}{n-i}$; sum by linearity. All by time $t$: inclusion–exclusion over the set of missing types, each fixed set of $k$ types missing with probability $(1-k/n{)}^t$. Birthday: the $i$-th draw avoids the previous $i$ values with probability $1-i/n$, and $\prod (1-i/n)\le e^{-\sum i/n}=e^{-k(k-1)/2n}$; the expected first repeat follows from the tail sum ${\sum }_k{\prod }_{i<k}(1-i/n)\approx {\int }_0^{\infty }{e}^{-x^2/2n}dx$.

Martingales and potential functions

A sequence $X_0,X_1,\dots$ is a martingale if $E[X_{t+1}\mid \text{history}]=X_t$. Optional stopping: for a stopping time $T$ with $E[T]<\infty$ and bounded increments (or bounded $T$), $E[X_T]=E[X_0]$. The contest form: find a potential $f$ of the state with $E[f(S_{t+1})\mid S_t]=f(S_t)-1$ for every non-final state; then $f(S_t)+t$ is a martingale and

$E[T]=f(S_0)-E[f(S_T)],$

which is often a constant (all final states share one potential). This solves processes whose state space is far too large for a DP: the potential is usually a sum of a function over parts (e.g. ${\sum }_{i}g({\text{size}}_i)$), and the condition becomes a recurrence for $g$.

Process	Result
gambler’s ruin, fair, from $i$ in $[0,N]$	$P(\text{reach }N)=i/N$, $E[T]=i(N-i)$
biased ($p$ up, $q=1-p$ down, $r=q/p\ne 1$)	$P=\frac{1-r^i}{1-r^N}$, $E[T]=\frac{i}{q-p}-\frac{N}{q-p}\cdot \frac{1-r^i}{1-r^N}$
waiting time for a pattern $s$ in uniform letters over $\sigma$ symbols	$\sum_{k \text{ border of } s,\ k =
random walk on a tree, edge $u$–$v$	$E[\text{hit } v \text{ from } u] = 2
random walk on a connected graph	stationary $\pi (v)=\mathrm{deg}v/2m$; return time to $v$ is $2m/\mathrm{deg}v$

pair<double, double> gamblersRuin(ll i, ll N, double p) {  // {P(hit N before 0), expected duration}
    double q = 1 - p;
    if (fabs(p - q) < 1e-12) return {double(i) / N, double(i) * (N - i)};
    double r = q / p, P = (1 - pow(r, i)) / (1 - pow(r, N));
    return {P, i / (q - p) - N / (q - p) * P};
}
mint patternWaitingTime(const string& s, int sigma) {     // expected letters until s first appears
    int n = sz(s); vector<int> pi(n);
    for (int i = 1; i < n; i++) { int k = pi[i - 1]; while (k && s[i] != s[k]) k = pi[k - 1]; pi[i] = k + (s[i] == s[k]); }
    mint res = 0; for (int k = n; k > 0; k = pi[k - 1]) res += mint(sigma).pow(k);
    return res;
}

Proof: optional stopping and its applications

OST: $X_{T\wedge n}-X_0={\sum }_{t<n}[T>t](X_{t+1}-X_t)$, and $[T>t]$ is determined by the history up to $t$, so each term has conditional mean 0: $E[X_{T\wedge n}]=E[X_0]$. If $T$ is bounded take $n$ large; otherwise $|X_{T\wedge n}|\le |X_0|+cT$ with $E[T]<\infty$, and dominated convergence gives $E[X_T]=E[X_0]$. Potential: if $E[f(S_{t+1})\mid S_t]=f(S_t)-1$ before stopping, $Y_t=f(S_{t\wedge T})+t\wedge T$ is a martingale, so $E[f(S_T)]+E[T]=f(S_0)$ (with the boundedness conditions, which hold for finite chains that stop with probability 1 geometrically fast).

Gambler’s ruin: the position is a martingale in the fair case: $i=N\cdot P$; and $X_t^2-t$ is a martingale ($E[(x\pm 1{)}^2]=x^2+1$), giving $i^2=N^{2}P-E[T]$, so $E[T]=iN-i^2$. Biased: $r^{X_t}$ is a martingale ($p{r}^{x+1}+q{r}^{x-1}=r^x(q+p)=r^x$), giving $r^i=P{r}^N+(1-P)$; and $X_t-(p-q)t$ is a martingale, giving $E[T]=(NP-i)/(p-q)$, which rearranges to the table. Patterns: before each letter a new gambler arrives with $1 and bets everything, fair odds $\sigma :1$, that the next letters spell $s$ in order. The casino’s net gain is a martingale with zero mean. When $s$ first completes at time $T$, the casino has received $T$ dollars and pays out ${\sigma }^k$ to each gambler still alive, exactly those who arrived at the starts of the suffixes of length $k$ that are also prefixes (borders, including $s$ itself). So $E[T]={\sum }_{\text{borders}}{\sigma }^k$; the KMP failure chain enumerates the borders. Tree walk: from $u$ the walk steps to $v$ immediately with probability $1/\mathrm{deg}u$, otherwise into a subtree of $u$‘s side and must come back; solving $h(u)=1+\frac{1}{\mathrm{deg}u}{\sum }_{w\ne v}(h(w\to u)+h(u))$ with $h(w\to u)=2|E(T_w)|+1$ by induction gives $h(u)=2|E(T_u)|+1$. Stationary distribution: ${\sum }_u\pi (u)P(u,v)={\sum }_{u\sim v}\frac{\mathrm{deg}u}{2m}\cdot \frac{1}{\mathrm{deg}u}=\frac{\mathrm{deg}v}{2m}$; the return time is $1/\pi (v)$ (Kac’s lemma, by renewal).

Markov chains

Distribution after $t$ steps: ${\pi }_t={\pi }_0{P}^t$ (matrix power in $O(k^3\log t)$). For an absorbing chain with transient part $Q$, the expected number of steps from each transient state solves $(I-Q)h=1$, and absorption probabilities solve $(I-Q)B=R$; use Gaussian elimination (modular when exact answers are required, Gaussian Elimination). A state with self-loop probability $s$ and no other cycle back simply gets $h=(1+{\sum }_v{p}_v{h}_v)/(1-s)$.

vector<double> expectedSteps(const vector<vector<double>>& P, const vector<char>& absorbing) {   // steps to absorption
    int k = sz(P); vector<vector<double>> A(k, vector<double>(k + 1));
    for (int i = 0; i < k; i++) {
        A[i][i] = 1;
        if (absorbing[i]) continue;
        for (int j = 0; j < k; j++) A[i][j] -= P[i][j];
        A[i][k] = 1;
    }
    for (int c = 0; c < k; c++) {                          // Gauss-Jordan with partial pivoting
        int piv = c; for (int r = c; r < k; r++) if (fabs(A[r][c]) > fabs(A[piv][c])) piv = r;
        swap(A[c], A[piv]);
        for (int r = 0; r < k; r++) if (r != c && A[r][c] != 0) { double f = A[r][c] / A[c][c]; for (int j = c; j <= k; j++) A[r][j] -= f * A[c][j]; }
    }
    vector<double> h(k); for (int i = 0; i < k; i++) h[i] = A[i][k] / A[i][i];
    return h;
}

Proof: the absorbing-chain equations

Conditioning on the first step: for transient $i$, $h_i=1+{\sum }_j{P}_{ij}{h}_j$ with $h=0$ on absorbing states, i.e. $(I-Q)h=1$. If absorption happens with probability 1 from every state, $Q^t\to 0$, so $I-Q$ is invertible with $(I-Q{)}^{-1}={\sum }_t{Q}^t$ (the expected number of visits to each transient state), and the system has the unique solution above. Absorption probabilities satisfy the same recursion with right-hand side $R$ (one-step absorption). The self-loop shortcut is the one-variable case: $h=1+sh+\sum p_v{h}_v$.

Concentration

Inequality	Statement
Markov	$P(X\ge a)\le E[X]/a$ for $X\ge 0$
Chebyshev	$P(
Chernoff (sum of independent Bernoullis, mean $\mu$)	$P(X\ge (1+\delta )\mu )\le e^{-{\delta }^2\mu /3}$, $P(X\le (1-\delta )\mu )\le e^{-{\delta }^2\mu /2}$ for $0<\delta \le 1$
Hoeffding (independent, values in $[0,1]$, $n$ of them)	$P(
union bound	$P(\text{any bad})\le \sum P({\text{bad}}_i)$

Use them to argue that a randomized solution fails with tiny probability: repeat a Monte Carlo test $k$ times to push a one-sided error $\epsilon$ to ${\epsilon }^k$; a sum of many independent random choices stays within $O(\sqrt{n\log n})$ of its mean with high probability.

Proof: Markov, Chebyshev, Chernoff

Markov: $a[X\ge a]\le X$; take expectations. Chebyshev: Markov applied to $(X-\mu {)}^2$. Chernoff: for $t>0$, $P(X\ge a)\le E[e^{tX}]/e^{ta}$ (Markov on $e^{tX}$). By independence $E[e^{tX}]=\prod (1+p_i(e^t-1))\le e^{\mu (e^t-1)}$. With $a=(1+\delta )\mu$ and $t=\ln (1+\delta )$ this is $(e^{\delta }/(1+\delta {)}^{1+\delta }{)}^{\mu }$, and $\delta -(1+\delta )\ln (1+\delta )\le -{\delta }^2/3$ on $[0,1]$ (both sides vanish at 0 and the derivative $-\ln (1+\delta )\le -2\delta /3$ there). The lower tail is symmetric with $t<0$. Hoeffding follows the same route with Hoeffding’s lemma $E[e^{t(Y-EY)}]\le e^{t^2/8}$ for $Y\in [0,1]$.