Striking applications of linearity of expectation

Question

Linearity of expectation is a very simple and "obvious" statement, but has many non-trivial applications, e.g., to analyze randomized algorithms (for instance, the coupon collector's problem), or in some proofs where dealing with non-independent random variables would otherwise make any calculation daunting.

What are the cleanest, most elegant, or striking applications of the linearity of expectation you've encountered?

Answer 1

You can prove the tail sum formula for expectation using linearity of expectation. Will only prove in the discrete case. Let $X$ be a non-negative discrete R.V., and note that

$$X = \mathbb{I}\{X \ge 1\} + \mathbb{I}\{X \ge 2\} + \ldots$$

Use linearity of expectation on the above and you are done.

Somewhat circularly, you get back the definition of expectation from a property of expectation.

Answer 2

Just saw a nice application in a lecture¹ that fits neatly with the case of non-independent random variables you mentioned - let $S = \{(x_1, \ldots, x_n) \in \{0, 1\}^n | \sum_i x_i \leq k\}$. If $k \leq \frac{n}{2}$, then $|S| \leq 2^{n \cdot H_b\left(\frac{k}{n}\right)}$ where $H_b(p)$ is the binary entropy function.

We show this by letting $(X_1, \ldots, X_n)$ be distributed uniformly in $S$. Then $H(X_1, \ldots, X_n) = \log |S|$. Noticing that the $X_i$ are identically distributed: $$H(X_1, \ldots, X_n) \leq H(X_1) + \ldots + H(X_n) = n \cdot H(X_1)$$

$X_1$ takes values in $\{0, 1\}$, so we could calculate $H(X_1) = H_b(\mathbb{E}[X_1])$ and finish this if we can bound $\mathbb{E}[X_1]$. Now comes the use of linearity of expectation: we have $$n \cdot \mathbb{E}[X_1] = \mathbb{E}[X_1] + \ldots + \mathbb{E}[X_n] = \mathbb{E}[X_1 + \ldots + X_n] \leq k$$ so $\mathbb{E}[X_1] \leq \frac{k}{n}$. As $\frac{k}{n} \leq \frac{1}{2}$ and $H_b(p)$ is increasing on $[0, \frac{1}{2}]$, we have $H(X_1) \leq H_b\left(\frac{k}{n}\right)$, finishing the proof.

1: From https://ttic.uchicago.edu/~madhurt/courses/infotheory2017/l2.pdf

Answer 3

Buffon's needle: rule a surface with parallel lines a distance $d$ apart. What is the probability that a randomly dropped needle of length $\ell\leq d$ crosses a line?

Consider dropping any (continuous) curve of length $\ell$ onto the surface. Imagine dividing up the curve into $N$ straight line segments, each of length $\ell/N$. Let $X_i$ be the indicator for the $i$-th segment crossing a line. Then if $X$ is the total number of times the curve crosses a line, $$\mathbb E[X]=\mathbb E\left[\sum X_i\right]=\sum\mathbb E[X_i]=N\cdot\mathbb E[X_1].$$ That is to say, the expected number of crossings is proportional to the length of the curve (and independent of the shape).

Now we need to fix the constant of proportionality. Take the curve to be a circle of diameter $d$. Almost surely, this curve will cross a line twice. The length of the circle is $\pi d$, so a curve of length $\ell$ crosses a line $\frac{2\ell}{\pi d}$ times.

Now observe that a straight needle of length $\ell\leq d$ can cross a line either $0$ or $1$ times. So the probability it crosses a line is precisely this expectation value $\frac{2\ell}{\pi d}$.

Answer 4

As lulu mentioned in a comment, the fact that a uniformly random permutation $\pi\colon\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ has in expectation one fixed point is a quite surprising statement, with a one-line proof.

Let $X$ be the number of fixed points of such a uniformly random $\pi$. Then $X=\sum_{k=1}^n \mathbf{1}_{\pi(k)=k}$, and thus $$ \mathbb{E}[X] = \mathbb{E}\left[\sum_{k=1}^n \mathbf{1}_{\pi(k)=k}\right] = \sum_{k=1}^n \mathbb{E}[\mathbf{1}_{\pi(k)=k}] = \sum_{k=1}^n \mathbb{P}\{\pi(k)=k\} = \sum_{k=1}^n \frac{1}{n} = 1\,. $$

Answer 5

I really love this proof of Bickel and Lehmann (Ann. Math. Stat. 1969), Unbiased Estimation in Convex Families: we can use linearity of expectation to prove unbiased estimators for certain quantities are impossible. $\newcommand{\PP}{\mathbb{P}} \DeclareMathOperator{\E}{\mathbb{E}}$

Let $T(\PP)$ be some property of a distribution you wish to estimate, where $\PP$ is a distribution in some class $\mathcal P$. Let $\PP_0 \ne \PP_1$ both in $\mathcal P$ such that $\PP_\alpha = (1-\alpha) \PP_0 + \alpha \PP_1$, a weighted mixture of the two distributions, is also in $\mathcal P$ for any $\alpha \in [0, 1]$. We want to know whether there exists any estimator $\hat T(X_1, \dots, X_n)$ such that $$\E_{X_i \stackrel{iid}{\sim} \PP} \hat T(X_1, \dots, X_n) = T(\PP).$$ Assume that there is some such estimator. Then \begin{align*} R(\alpha) &= T(\PP_\alpha) \\&= \int_{x_1} \cdots \int_{x_n} \hat T (x_1, \dots, x_n) \,\mathrm{d}\PP_\alpha(x_1) \cdots \mathrm{d}\PP_\alpha(x_n) \\&= \int_{x_1} \cdots \int_{x_n} \hat T(x_1, \dots, x_n) \,\left[ (1-\alpha) \, \mathrm{d}\PP_0(x_1) + \alpha \, \mathrm{d}\PP_1(x_1) \right] \cdots \left[ (1-\alpha) \, \mathrm{d}\PP_0(x_n) + \alpha \, \mathrm{d}\PP_1(x_n) \right] \\&= (1-\alpha)^n \E_{X_i \stackrel{iid}{\sim} \PP_0}[ \hat T(X_1, \dots, X_n)] + \dots + \alpha^n \E_{X_i \stackrel{iid}{\sim} \PP_1}[ \hat T(X_1, \dots, X_n)] ,\end{align*} and so $R(\alpha)$ must be a polynomial in $\alpha$ of degree at most $n$.

Now, for example, let $T$ be the standard deviation, take $\PP_0 = \mathcal N(0, 1)$ [the standard normal distribution] and $\PP_1 = \mathcal N(0, 2^2)$. Then by the law of total variance, $$ R(\alpha) = T(\PP_\alpha) = \sqrt{(1-\alpha) \cdot 1 + \alpha \cdot 4 + \operatorname{Var}[0]} = \sqrt{1 + 3 \alpha} ,$$ which is not polynomial in $\alpha$ – and hence no unbiased estimator of the standard deviation exists, at least on any class of distributions containing two-component Gaussian mixtures.

You can also easily use this same technique to show, e.g., the non-existence of unbiased estimators for Hellinger distance or integral probability metrics (Theorem 3 here).

Answer 6

One I enjoy is:

Enumerate $n$-many balls, place in an urn and draw $k$-many at random without replacement. Let $S = X_1+ \ldots X_k$ be their sum where $X_i$ is the value on the $i^{th}$ ball. Then by linearity of expectation we have

$\displaystyle E[S]= E \bigg [ \sum_{j = 1}^k X_j \bigg ] = \sum_{j = 1}^k E[X_j] = k \cdot E[X_j] = k \cdot \frac{n+1}{2}$.

And as we draw without replacement we do not have independence.

cf. Expectation of sum of numbered balls

Answer 7

Here is a simple but cute one:

The expected number of instances of consecutive pairs of cards of the same suit is $12$ in a shuffled standard deck ($4$ suits of $13$ cards each).

The proof is trivial once you use linearity of expectation, since each of the $51$ pair-positions contributes $1$ to the total count with probability $12/51$ and $0$ otherwise. It is a little cute that the $51$ cancels.

Answer 8

Here is an application from theoretical computer science: recall that a 3-SAT formula is a CNF (conjunctive normal form) formula where each clause has three literals: that is, $\phi = C_1\land C_2\land \dots \land C_k$, where each $C_k$ (a clause) is an $\lor$ of 3 (distinct) literals.

Theorem. For every 3-SAT formula formula over $n$ variables, there exists an assignment $x\in\{0,1\}^n$ satisfying at least $7/8$ of the clauses.

Proof. Consider a 3-SAT formula $\phi = C_1\land C_2\land \dots \land C_k$ (we can assume wlog that no clause is trivially true). Letting $I_j$ be the indicator r.v. of whether the $j$-th clause $C_j$ is satisfied, we have that the number $N$ of clauses satisfied by a uniformly random assignment is $$ \mathbb{E}[N] = \mathbb{E}\left[\sum_{j=1}^k I_j\right] = \sum_{j=1}^k \mathbb{E}[I_j] = \sum_{j=1}^k \mathbb{P}\{C_j \text{ satisfied}\} = \sum_{j=1}^k \frac{7}{8} = \frac{7}{8}k $$ since each clause has 3 (distinct) literals, and therefore is satisfied with probability $1-1/2^3=7/8$.

Now, since $N$ has expectation $\frac{7}{8}k$, we have that $\mathbb{P}\{N\geq \frac{7}{8}k\}>0$; that is, there exists some realization of $x$ satisfying at least a $7/8$ fraction of the clauses.

Answer 9

This one is quick and quite surprising application of linearity of expectation.

Let $G=(V, E)$ be a graph with $n$ vertices and $e$ edges. Then it contains a bipartite subgraph of at least $\frac{e}{2}$ edges.

Let $T \subseteq V$ be a random subset given by $\mathbb{P}[x\in T] = \frac{1}{2}$. An edge $\{x, y\}$ is a crossing if exactly one of $x, y$ are in $T$.

Denote by $X_{xy}$ the random indicator for ${x, y}$ being a crossing, and set $$ X = \sum_{\{x, y\} \in E} X_{xy}. $$

Since $\mathbb{E}[X_{xy}] = \frac{1}{2}$, by linearity of expectation we have $$ \mathbb{E}[X] = \sum_{\{x, y\} \in E} \mathbb{E}[X_{xy}] = \frac{e}{2}. $$ Consequently, there exists a choice of $T$ with at least $\frac{e}{2}$ crossing edges, which form a bipartite graph.

---

This beautiful proof is from Noga Alon and James Spencer's excellent book 'The Probabilistic Method'. I know it can be directly proved by induction, but the above probabilistic argument is way more elegant.

Answer 10

If you randomly shuffle a deck of $n$ cards numbered $1, 2,...,n$ and deal them out, then the expected number of cards that are greater than all previous cards is the $n$-th partial sum of the harmonic series: That is, the expected number of cards that are the 'maximum so far' is given by $H(n)=1+\frac12+\frac13+\cdots +\frac1n$

To see this: Let $X_i=1$ if the $i$-th card is the greatest so far; and $X_i=0$ otherwise. Then $X:=\displaystyle\sum_{i=1}^n{X_i}$ gives the number of cards that are maximums so far. But $E[X_i] = \frac1i$ since there is a $\frac1i$ probability that the greatest of the first $i$ cards is in fact the $i$-th card.

Answer 11

It also helps calculate the falling factorial momentum of the Poisson distribution.

As recall:

1. The falling factorial momentum is defined as:

$$\mathbb E[(X)_r]=\mathbb E[X(X-1)\cdots(X-r+1)]=r!\mathbb E\left[\binom{X}{r}\right].$$

2. A Poisson random variable with parameter $\lambda$ can be seen as the limit of a binomial random variable $Bin(n,\lambda/n)$ when $n \rightarrow \infty$, which in turn can be seen as the number of success in $n$ trials each of which has the success rate of $\lambda / n$.

---

Imagine $B \sim Bin(n,\lambda/n)$.

$$\mathbb E\left[\binom{B}{r}\right]=\mathbb E\Big[\sum_{A\in\binom{[n]}{r}}\mathbb{1}_A\Big]=\sum_{A\in\binom{[n]}{r}}\mathbb E[1_A]=\binom{n}{r}\Big(\frac\lambda{n}\Big)^r,$$ which goes to $\lambda^r/r!$ when $n\rightarrow \infty$. This implies that $\mathbb E[(X)_r]= \lambda^r$ for Poisson random variable $X$.