What are fun elementary subjects in probability?

I have to read several lectures on probability or applications of probability for high school students (of high level). There is no necessary part I must lecture, that is, my aim is just advertisement. What are possible subjects?

There are many nice examples in Alon-Spencer book, with applications to combinatorics and number theory. Is there something in this spirit, but rather on probability itself?

On a more elementary side, the are these probabilistic paradoxes, such as: https://en.wikipedia.org/wiki/Monty_Hall_problem, https://en.wikipedia.org/wiki/Two_envelopes_problem, https://en.wikipedia.org/wiki/Boy_or_Girl_paradox, https://en.wikipedia.org/wiki/Sleeping_Beauty_problem, etc.

Also, this one is fun: https://en.wikipedia.org/wiki/Secretary_problem

I nominate the Overlapping Words Paradox. E.g., see pages 42-44 in a book excerpt, a research paper, or an elementary exposition in Russian Kvant journal.

Random walk! That is a fascinating topic which can be treated with combinatorial methods. Associated is the ruin problem. Treat the facts that simple random walk is recurrent in dimension two but not in dimension three.

• The result you mention is often called Polya's Theorem – David White Feb 13 '16 at 21:16
1. A proof using the coupling method, say the coupling proof of the convergence theorem of finite-state Markov chains. See Lindvall's beautiful book for other examples.

2. The proof of existence of phase transition for the percolation model in two dimension is simple and elementary (sub-additivity + counting + coupling), but the conclusion is quite exciting.

• What is the best exposition of 2)? – Fedor Petrov Feb 13 '16 at 17:25
• Mmm.. I'm not sure about the "best" exposition, but you can find it in many places. Grimmett's book Probability on Graph has it (Chapter 3), and of course also his Percolation book, but the former is available online. The place I learned it from was Jeff Steif's lecture notes. – Algernon Feb 13 '16 at 18:41

The book "The Drunkard's Walk: How Randomness Rules Our Lives" by Leonard Mlodinow is probably close to what you are looking for.

The connection between random walks and electrical networks, e.g. as laid out by Doyle and Snell: http://arxiv.org/abs/math/0001057. This gives really slick proofs of many classical results about random walks (e.g. Polya's Theorem regarding recurrence vs. transience on lattices $\mathbb{Z}^n$, cover time, hitting time), and also generalizes them to other graphs.

The book of Santosh Venkatesh The Theory of Probability, Explorations and Applications, Cambridge University Press, 2012 has many interesting examples that would be accessible to a good high school student. Let me mention a few to give you a taste.

1. A beautiful probabilistic proof of Cayley's formula on the number of trees.

2. A nice connection between Viete's formula

$$\frac{\sin x}{x} =\prod_{k=1}^\infty \cos\left(\frac{x}{2^k}\right)$$

and the distribution of digits in the binary expansion of a random number $x\in [0,1]$.

1. Random graphs.