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?

Answer

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

Consider dropping any (continuous) curve of length onto the surface. Imagine dividing up the curve into N straight line segments, each of length /N. Let Xi 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,
E[X]=E[Xi]=E[Xi]=NE[X1].
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 πd, so a curve of length crosses a line 2πd times.

Now observe that a straight needle of length d can cross a line either 0 or 1 times. So the probability it crosses a line is precisely this expectation value 2πd.

Attribution
Source : Link , Question Author : Clement C. , Answer Author : jlammy

Leave a Comment