Estimating Probabilities Using Simulation

A food truck knows from months of receipts that about 30% of its customers order the daily special. The owner wants to know how often at least 3 of the first 5 customers will order it, because that is when the special runs out before the lunch rush. You could wait and watch hundreds of mornings. Or you can imitate the mornings with random numbers, thousands of times in a few seconds, and count how often the special runs out. That imitation is a simulation, and the fraction of times the event happens is an estimate of its probability.

Random processes, outcomes and events

A random process is a repeatable situation whose result is decided by chance: you know what results are possible, but not which one you'll get on a given try. A customer deciding what to order is one; so are rolling a die, dealing a card, or picking 4 employees at random from a list. One repetition of the process is a trial.

An outcome is the result of one trial. If one trial is "the next 5 customers order," an outcome is a full record of what happened, such as S N N S N (special, not, not, special, not).

An event is a collection of outcomes, usually named with a capital letter. The event $A$ = "at least 3 of the 5 order the special" contains every outcome with three or more S's: S S S N N, N S S S N, S S S S S, and many more. An event happens on a trial if the outcome of that trial is one of the outcomes in the event.

The distinction matters when you design a simulation: you simulate outcomes, then check each one against the event.

Probability as long-run relative frequency

The probability of an event is the proportion of times it would happen if the random process were repeated a very large number of times. That is a definition, not a formula: "the probability of rolling a 6 is $\frac{1}{6}$" means that in a huge number of rolls, about one roll in six is a 6.

You will never see an infinite number of trials, but the relative frequency you observe in a real set of trials (the count of times the event happened, divided by the number of trials) is an estimate of the probability. The food truck's "about 30%" is exactly this: an estimate from many past customers.

How good is the estimate? The law of large numbers answers that: when trials are independent (one trial's result doesn't change the chances on another), the relative frequency of an event settles down to a single value, the probability, as the number of trials grows. The graph below follows the proportion of sixes in 1,000 simulated rolls of a fair die.

Early on, the relative frequency jumps around wildly: one 6 in the first roll makes it 1, and one 6 in the first 10 rolls makes it 0.1. Each new roll changes a proportion based on few rolls a lot and a proportion based on many rolls very little, which is why the line flattens out. After 1,000 rolls, 166 sixes give 0.166, very close to $\frac{1}{6} \approx 0.167$.

Read the law carefully. It describes the long run only. It does not say that after a string of non-sixes, a 6 is "due": the die has no memory, and each roll has the same $\frac{1}{6}$ chance. The proportion gets closer to $\frac{1}{6}$ because the early streaks get swamped by a growing number of later rolls, not because later rolls compensate for them.

Designing and running a simulation

A simulation replaces the real random process with a chance device (random digits, a random number generator, cards, coins) set up so that each simulated outcome has the same probability as the real one. On the exam, a description has to be complete enough that someone else could carry it out and get comparable results. That takes four parts.

1. Assign values to outcomes so the probabilities match. For the food truck, each customer orders the special with probability 0.3. Using random digits 0 to 9, let 0, 1, 2 mean "orders the special" and 3 to 9 mean "does not." Three of the ten equally likely digits gives probability 0.3.
2. Describe one trial and what to record. One trial is 5 consecutive digits, one per customer. Record how many of the 5 digits are 0, 1 or 2.
3. Repeat many times. Do many trials, keeping track of the count of trials and the count of trials where the event happened.
4. Estimate. The estimated probability is the number of trials where the event happened divided by the total number of trials.

Here are 40 digits from a random number table, split into 8 trials of 5 digits:

Count the 0s, 1s and 2s in each group: 2, 1, 3, 1, 1, 1, 3, 2. Trials 3 and 7 have at least 3 specials, so this run of 8 trials estimates the probability as $\frac{2}{8} = 0.25$.

Eight trials is far too few to trust; the law of large numbers says the estimate is only reliable with many trials. A computer running the same design for 500 trials gave these results:

At least 3 specials happened in $60 + 15 + 0 = 75$ of 500 trials, so the estimate is $\frac{75}{500} = 0.15$. The special runs out early on roughly 15% of mornings, about one weekday in seven. (Topic 2.10 computes this probability exactly; it is about 0.163, so the simulation landed close.)

Three design details need care:

• Probabilities that don't fit single digits. For a probability of 0.15, use pairs of digits: 00 to 14 for the event, 15 to 99 for not. For 0.25, you can use 0 and 1 for the event, 2 to 7 for not, and skip 8 and 9, which leaves 8 equally likely digits, 2 of them assigned to the event.
• Sampling without replacement. When the real process can't pick the same individual twice (choosing 4 different people), label the individuals, and skip any label that has already been chosen in the current trial. Also skip labels that match no one (00, or 13 to 99 if there are 12 people).
• Random number generators. On a calculator, randInt(1, 12) gives a random whole number from 1 to 12 with equal chances. The same rules apply: say what the numbers stand for, what one trial is, and whether repeats are skipped.

Worked examples

Where students lose points