# Neat topics or problems to include in a probability class

I'd like to get suggestions for neat topics or problems to include in an undergraduate, upper division Introduction to Probability class. Many people have taught probability for many years and I'm sure that, over the years, they have collected many gems of probability that aren't as well known as they should be.

An example would be discussing the Google PageRank algorithm as an application of Markov chains. But I'm interested in any neat topics or insights of any flavor.

It would be especially nice to give students a taste of how probability is applied in practical situations, in a way that makes students feel empowered -- as if they now have a powerful tool at their disposal. For example, Monte Carlo methods for numerically evaluating integrals could be a good topic. Another idea could be to include a taste of coding theory (that is, methods to reliably transmit a sequence of bits over a noisy communication channel, where each bit has a certain probability of being flipped).

Seriously? Probability? There's a lot! eg Star Trek:   Markov chains:  Laplace transform:  • Awesome, thank you! – eternalGoldenBraid Mar 17 '18 at 4:02
• Thanks for the accept. I was really not expecting this. @eternalGoldenBraid – BCLC Aug 16 '18 at 7:35
1. A lighthearted one is the Caltech sweepstakes hijinks:

(alluded to in the movie Real Genius, some fun clips you could fair use)

1. The old 2 people in class birthday stunt:

1. Financial options (can get complicated--wouldn't teach them per se but can be discussed)

2. Insurance (same as 3)

3. Many military or search problems from OR have a probability foundation (again not just some toy problems or to try to teach a whole OR class but to mention the topic and that it is practical.)

4. Experimental derivation of pi (I did it for a science project in HS geometry):

https://en.wikipedia.org/wiki/Buffon%27s_needle#Estimating_%CF%80

I suggest the probabilistic method in combinatorics and graph theory, for a few reasons:

1. This will introduce the students to other mathematical concepts that they may not be aware of already, but you can also quickly teach them enough of the basics to apply topics from your probability course to a new problem.
2. This is a somewhat surprising application of probability, in the sense that it will be used to non-constructively demonstrate something exists without exhibiting a specific object.
3. If you extend the discussion just a little bit, you can bring the students to the edge of current human understanding and pose some open problems. This will hopefully excite them, as I assume they are used to being taught known results and are under the impression that math is somehow "solved".

Specifically, I recommend discussing Ramsey Numbers. The Wikipedia entry for the Probabilistic Method has a good explanation of how this method can provide a lower bound on the Ramsey number $R(r,r)$ (defined as the smallest $n$ such that any 2-coloring of the edges of $K_n$ must yield a $K_r$ subgraph whose edges are all the same color). Specifically, it can be shown that $R(r,r)\geq n+1$ as long as ${n \choose r}2^{{1-{r \choose 2}}}<1$.

That quantity on the left-hand side of the inequality is the expected value of the random variable that counts the number of monochromatic $K_r$ subgraphs in a 2-coloring of $K_n$. Since that random variable only takes on integer values, if that expected value is less than 1, then there must be some instance where the variable takes on the value 0. In such an instance, there are no monochromatic $K_r$ subgraphs, meaning it is possible to avoid having a monochromatic $K_r$ by 2-coloring $K_n$ in a particular way. Thus, $R(r,r)>n$ must be true.

However, this argument does not show at all how to achieve such a coloring! Indeed, this is still a genuinely hard problem, in general. After this presentation, you can share some further facts with the students about Ramsey Numbers, especially how we know $R(3,3)$ and $R(4,4)$ exactly, but even $R(5,5)$ is unknown. (Note: The upper bound on $R(5,5)$ was just improved recently in 2017.)

• Great suggestion, thanks. Exactly the kind of thing I'm looking for. – eternalGoldenBraid Mar 7 '18 at 3:46

If you just wanted to do a fun, surprising, and easy one, I would do the Montey Hall problem.

If you wanted to overlap some social issues, you could use Bayesian statistics to talk about whether or not screening well people for rare diseases is a good policy. You could talk about what the prevalence of the disease would have to be compared to the efficacy of the test to make the test worthwhile (for many screening tests in sufficiently rare diseases, if you are tested positive the most likely reason for a positive test is a false positive).

If you wanted to do an information theory one, you could talk about Hubert Yockey's critique of RNA World from the perspective of Shannon information theory. "Origin of life on earth and Shannon's theory of communication", Computers and Chemistry, 2000. https://www.sciencedirect.com/science/article/pii/S0097848500800108

There are some ideas here: these include links to various paradoxes (e.g., Simpson's, Bertrand's, and exchange paradoxes) random walks; random graph; ping pong on a Galton board, and others. There is also a pretty general misunderstanding of what "randomness" looks like: this activity is similar to something I've done in class. The idea is you ask students to write down the results of 100 coin flips and a sequence of "random" H and T they generate. The human-generated list will have no long runs of H or T, while the one generated by coin flips will.

• You should give a short summary of what you link to in case the links rot. – Joel Reyes Noche Mar 7 '18 at 5:42

If the target audience includes applied mathematics, physicists or engineers (is not a pure math course) you could also give a shout-out to some easy Markovian models used in science and engineering. Many of these can be introduced pretty easily with little background.

For instance the 2D-Ising model of phase transitions is one of the simplest models demonstrating a thermodynamic phase transition.

A few others that come to mind is the field of percolation theory which studies the critical fraction of 'edges' on a graph where systems transition from having isolated small clusters to a spanning cluster on the order of system size.

Markov Chain Monte Carlo algorithms for integral solving are actually the basis for almost all of statistical mechanics and are some of the earliest examples of computer simulations (See Rosenbluth 1953). These computer simulations are used extensively to sample the partition function of the system, which is an high dimensional integral over the positions and momenta of every particle in the system of the negative exponential of the Hamiltonian operator (energy). Designing it into a homework project might be a bit hard without requiring at least some programming. Plug: I used to do research in this area, and I'll point out that our simulator HPMC is open source.

At the very least to introduce statistics driven simulation that may be fun for students is a basic model used to describe mosh pits. The paper also includes a browser-based simulation, and their model can capture and study differences in what causes the mosh pit to be gas-like (random) or have circular motion. It's fun, the model is simple, and it describes thermodynamics.