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?

-
Some fun problems on probability theory are at ocw.mit.edu/courses/mathematics/…. Many of them can be gateways to further discussion. – Richard Stanley Feb 15 at 0:31
The branching process is quite elementary and funny. – Stéphane Laurent Feb 20 at 21:41

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

-
In the same line is the birthday paradox – kjetil b halvorsen Feb 13 at 15:25
I like the Bertrand paradox, en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29 – Marcel Feb 13 at 17:31
Simpson's Paradox is a good one which comes up in real-life fairly frequently – BlueRaja Feb 13 at 20:35

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.

-
Also known as: en.wikipedia.org/wiki/Penney%27s_game – radomaj Feb 14 at 4:00

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 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 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 at 18:41

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 "The Drunkard's Walk: How Randomness Rules Our Lives" by Leonard Mlodinow is probably close to what you are looking for.

-

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.

The problems at the end of each chapter are excellent, of varied degrees of difficulty.

-

I think the proof that the normal PDF is a PDF (i.e. integrates to 1) is beautiful and deserves to be in a probability course. Obviously, it's mostly calculus, so perhaps not elementary enough for what you have in mind, but it's really beautiful.

-

The obvious application of probability is to gambling. Not only is this the major historical motivation to study probability, coin flips and rolling dice are still the easiest examples for students to understand while containing very meaty problems (e.g. if a friend flips a coin 20 times and 15 are heads, is the coin biased and how certain can you be? ).

-

The Central Limit Theorem and how it even works for something as discrete as counting coin flips.

-

A wealth of interesting probability problems for high school students can be found in the book Henk Tijms, Understanding Probability, third edition, Cambridge University Press, 2012.

-