I want to introduce Monte Carlo methods for a group of 16-18-years-old high school students. Besides classic examples (coin flips and count of heads/tails, rolls of a pair of dice) which other examples could I do? I thought to present the solution of the birthday problem by simulation, but I would like some other problem that mimics a real life situation. Any suggestion?
6
-
$\begingroup$ Have you already looked through en.wikipedia.org/wiki/Monte_Carlo_method#Applications? $\endgroup$– Stephan KullaAug 21, 2016 at 20:07
-
$\begingroup$ The book "The Goal" by Eli Goldratt describes an interesting simulation performed with a die, 4 bowls, and a collection of matchsticks (which can be replaced by toothpicks of you are worried about 16 year old pyros). In the context of the book it is a simulation about throughput in a 4-department plant, but it also has a queuing-theory flavor. A nice description of it is found here: maaw.info/MatchBowlExperiment.htm $\endgroup$– John ColemanAug 21, 2016 at 20:29
-
2$\begingroup$ Another idea: computing probabilities in the game of Risk is nontrivial. I don't know of any way other than simulation to find the probability that e.g. an attacker with 30 armies can defeat a defender with 20 armies. I have used this very problem for projects in programming courses. Most students found it fairly interesting since most students were familiar with the game. $\endgroup$– John ColemanAug 21, 2016 at 23:56
-
1$\begingroup$ Estimate $\pi$ by dropping sticks on a ruled region of the plane, via Buffon't needle problem. E.g., here. $\endgroup$– Joseph O'RourkeAug 23, 2016 at 1:07
-
$\begingroup$ What sort of Monte Carlo are you doing? Are you looking for physical examples (like dropping needles or rolling dice) or computer examples. If by computer, are you using canned software (e.g. Excel) or writing short programs? If the latter, in what language? $\endgroup$– John ColemanAug 25, 2016 at 15:45
|
Show 1 more comment
7 Answers
$\begingroup$
$\endgroup$
Anything with probabilistic estimates should work. As a demonstration, an idea mentioned already by @Joseph O'Rourke, that is, estimating $\pi$ using Buffon's needle is excellent. Estimating area of a shape by calculating the number of random points that fall into it, could also work, but it is not as illuminating.
For some examples that are closer to real life, you could estimate the proportion of red cards in a stack by picking a few random samples (explain connection to pools and voting). You could also estimate average height in the class by picking a few random samples and explain connection to various statistical estimates on population and how it differs from census data.
Game-related algorithms use Monte Carlo a lot. You could make them play multiple random games of tic-tac-toe and for each put $+1$ on every square of color that won and $-1$ on every square of color that lost (zero otherwise). Sum all these numbers and see how it corresponds to good/bad moves (a few hundred playouts should be ok, so it would work for a big class; for a smaller class use symmetries and average the four corners and the four middles). See also a small script here.
If you have too few $\geq 9$ sided dice, teach them first how to make $12$-sided die from a $6$-sided die and a coin (or two $6$-sided dice). Then also teach them how to make $5$-sided die from a $6$-sided die simply by repeating the throw if the result "falls outside the range" (or in general $k$-sided die from $n$-sided die for any $2\leq k < n$).
You could also try them various algorithms that use Monte Carlo approach like quicksort:
- You are given a sequence of numbers.
- Sort it naively if the sequence is of length $\leq 4$ (to make it less tedious).
- Pick a random number $x$ from it and split the sequence into two subsequences $\leq x$ and $> x$.
- Repeat recursively for each subsequence.
- Write down $\mathrm{result}_1, x ,\mathrm{result}_2$.
$\begingroup$
(Image from YouTube.)
$\endgroup$
How about the famous Monty Hall Problem—stick, or switch?
(Image from YouTube.)
There is a nice Python simulation described at this link. A sample run verifies the counterintuitive $\frac{2}{3}$ vs. $\frac{1}{3}$ probabilities:
answered Aug 25, 2016 at 12:40
$\begingroup$
$\endgroup$
Here are 2 computer examples using random numbers and a unit square.
!. Find the area of a circle in the unit square. 2. Two people decide to meet between noon (0) and 1 o'clock at a certain location with the understanding that the longest either should wait for the other is 15 minutes (.25 of a unit.) What is probability of a meeting taking place?
In both cases 2 random numbers are generated (x and y)
In case 1 the distance from (0.5, 0.5) to x,y is computed and if <= .5^2 then plot & color the point green else red.
In case 2 the x and y represent the different times that each arrives.
if |x-y| <= 0.25 then plot & color the point green else red.
In both case count the number of red/green points.
$\begingroup$
$\endgroup$
Disease transmission might work well. Assume a certain percentage of unvaccinated students (some localities have high single-digit percentages) in the school when one person contracts measles, for example. About 90% of unvaccinated people who have close contact with a measles patient in the first four days or so will catch the disease. If students keep track of who they contact daily in classes, sports, etc., you could run a few cycles to see how fast an outbreak spreads given various levels of unvaccinated populations. Not only is this highly relevant to real-life vaccination decisions and policy, but it could be extended to more sophisticated models if you consider how soon patients are quarantined, etc.
$\begingroup$
$\endgroup$
Here is an Excel example. It simulates the winnings of a person (or persons) who buys a \$1 "Pick 3" lottery ticket (which wins \$500 with probability 1/1000, hence nets \$499 with probability 1/1000). For 1 player it looks like:
In A2 I have the formula =IF(RAND()<0.001,499,-1). In A3 I have the formula =A2+IF(RAND()<0.001,499,-1), which I copied down 363 rows and then plotted.
I also did it for 10 players, with the same formulas plus a sum of the final results (with conditional formatting to display red if a net collective loss). It looks something like this:
The point of the simulation was to better understand the following "paradox". I worked in a factory with several hundred employees for two summers when I was an undergraduate (this was in the mid 80s before the rust belt became rusty). Many times during those summers I heard of workers there winning the lottery. This created the strong psychological impression that winning this lottery was a fairly easy thing to do. I don't have the numbers, but I got the impression that a couple dozen workers were buying Pick 3 tickets almost every day in such a way that there was 1 or 2 winners per month. The simulation illustrates how it is possible to be in a small group of friends where at most points in time several of your friends are winners but nevertheless the group of friends is steadily becoming collectively poorer in time.
If you are interested in the spreadsheet itself, send me an e-mail and I'll send you a copy.
$\begingroup$
$\endgroup$
Correctness of algebraic and trigonometric and other identities can usually be tested quite effectively by plugging in random argument-values, and seeing whether the outputs match.
Maybe this doesn't count as "practical" for them, though, ...
answered Aug 26, 2016 at 21:50
$\begingroup$
$\endgroup$
Returns on a stock portfolio.
Moneychimp will give you data, the S&P 500 return for each year since 1871. The classic exercise is to suggest we start with some amount of money, say $1M, at retirement time. We assume a targeted rate of withdrawal each year, and run the simulation, i.e. randomly choose the return for each year, generally based on the market average 9% and standard deviation of 18.7%, and see if you outlive the portfolio. Then, of course you run it a few thousand times.
When I hear the phrase "Monte Carlo simulation" this is exactly what comes to mind.
answered Oct 22, 2016 at 13:17