# Striking applications of linearity of expectation

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?

• I've always liked the fact that a (uniformly) randomly selected permutation of a finite set is expected to have a unique fixed point. I don't find that claim at all intuitive.
– lulu
Jan 14, 2021 at 20:22
• Yes, that's is a good one! I have no intuition for that either, or for the (more involved) fact that this number is asymptotically a Poisson(1) r.v. Yet the proof for the expectation fits in one line... Jan 14, 2021 at 20:31
• I am planning on leaving that question open to gather more answers as time passes. Is this the standard way to handle "big lists" questions, or is there a better one? Jan 26, 2021 at 20:32

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}$$.

• This looks really awesome but I have some confusion. What if the curve of length $l$ cannot be divided into straight line parts? This is the case for a circle. Do we take 'shortcuts' that connect some points on the curve? But then the sum of their lengths might not equal the total length of the curve. I might be missing something simple... Jun 11, 2021 at 14:59

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\,.$$

• To me, "is expected to have a unique fixed point" (as per the original comment) sounds far more impressive than "has in expectation one fixed point". For the former, I would expect (no pun intended) to see an argument that proves that the expectation of $u(\pi)$ is one or close to one, where $u(\pi)\in[0,1]$ somehow quantities the truth of the statement "$\pi$ has a unique fixed point". Jan 15, 2021 at 8:21
• @EvangelosBampas You can also prove that the variance is 1 (not hard, though that does not follow readily from linearity of expectation). Heck, you can also prove that as n grows the distribution converges to a Poisson with parameter 1 (also, again, that requires more than just linearity of expectation). Jan 15, 2021 at 8:30
• But to be honest, I think your interpretation/reading of lulu's comment is a tad nitpicky :) Jan 15, 2021 at 8:35
• Sorry, I'm always cautious with statements about expectation. Lying with statistics is a thing :-) Jan 15, 2021 at 9:03
• Fair point :) @EvangelosBampas Jan 15, 2021 at 9:07

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}} = \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).

• That's quite neat! Jan 14, 2021 at 22:25

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.

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.

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.

• I enjoy that book. A proof I enjoyed from that book is the one regarding rotten fenceposts. Neat use of indicator functions. cf. artofproblemsolving.com/community/… Jan 15, 2021 at 23:37

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.

Just saw a nice application in a lecture1 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.

• At the end, you meant to say that $H_b$ is increasing on $[0,1/2]$ (not $[0,1]$), didn't you? Jan 14, 2021 at 20:49
• Yes, thanks for the catch! Just fixed Jan 14, 2021 at 20:50

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.

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.