Flipping 100 Coins

You have 100 fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains? What if you start with 1000 coins? Click below for the answer.

When you flip 100 coins in the first round, you should expect to see about 50 heads. When you flip those 50 coins again in the second round, you should expect about 25 heads. This (approximate) halving pattern will continue until you're left with only one coin. On average, it will take 6 or 7 rounds when starting with 100 coins because $$log_2(100) = 6.644$$
When you start with 1000 coins, the game will last about 10 rounds. (So if you want to bet someone that you can flip a coin and have it come up heads 10 times in a row, you'll greatly improve your odds if you start with 1000 coins!)

See my Probability GitHub repository for a script that shows how to model this problem in Python.

Three Coin Flips

The following game has a $10 entry fee. You are to flip a fair coin three times. The first time it comes up heads you are paid $5. The second time it comes up heads you're paid an additional $7. The third time it comes up heads you're paid $9 more, for a possible maximum prize of $21. Would you pay the $10 entry fee to play?

If not, what would be a fair price for this game? Click below for the answer.

It's not a good idea to play this game at the offered entry fee. Here are the eight possible outcomes when flipping a coin three times, along with how much you would win after each flip.

When you subtract out the $10 entry fee, you only win "big" ($11) one out of eight times. Three times you win only $2, three times you lose $5, and one out of the eight times you lose your entire $10 entry fee. If you average these, you can expect to lose $1 every time you play. So, if you lower the entry fee to $9 this would be a fair game.

This problem appeared as an exercise in Introductory Graph Theory by Gary Chartrand.
See my Probability GitHub repository for a script that shows how to model this problem in Python.

Bags of Marbles

You have three identical bags, each containing two marbles. Bag A contains two white marbles, Bag B contains two black marbles, and Bag C contains one white and one black marble. You pick a bag at random and draw out one marble. If the marble is white, what is the probability that the other marble in the same bag is also white? Click below to see the answer.

Many people will instinctively answer 50%, or 1/2, since the marble has two possible colors, but the probability is actually 2/3 (66.67%). Why? If the first marble is white, then you know you didn't randomly select Bag B. That means that the first marble you selected has three (not two) possibilities:

1. The first marble in Bag A.
2. The second marble in Bag A.
3. The white marble in Bag C.

Only in the third case will the other marble be black, so there's a 2/3 probability that when the first marble is white, the second marble will also be white.

If you want to see how you would model this problem in Python, you can look at my solution on GitHub.

Russian Roulette

Here's a nice little probability problem that I first saw in David Darling's Universal Book of Mathematics:

You're in a game of Russian Roulette (with only one other player), but instead of one bullet the gun (a six-shooter revolver) is loaded with three bullets in three consecutive chambers. The barrel is spun only once. Each player points the gun at his head and pulls the trigger. If he is still alive, the gun is passed to the other player. The game ends when one player dies. Would you stand a better chance of surviving if you shot first or second, or does it make a difference?

This puzzle, or a variation of it, is often used as a brain teaser interview question. To avoid spoiling it for anyone, I'll add the solution as a comment to this post (so don't scroll down until you think you've worked it out).

Getting a Fair Toss From a Biased Coin

A paper out of Stanford and UCSC, Dynamical Bias in the Coin Toss (PDF, 5MB), reveals a small but significant bias in the process of flipping a coin.

James Devlin of Coding the Wheel provides the following summary:

1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there's a 51% chance it will end as heads).
2. If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit "huge bias" (some spun coins will fall tails-up 80% of the time).
3. If the coin is tossed and allowed to clatter to the floor, this probably adds randomness.
4. If the coin is tossed and allowed to clatter to the floor where it spins, as will sometimes happen, the above spinning bias probably comes into play.
5. A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
6. The same initial coin-flipping conditions produce the same coin flip result. That is, there's a certain amount of determinism to the coin flip.
7. A more robust coin toss (more revolutions) decreases the bias.

The article goes on to suggest a coin-flipping strategy that tries to take advantage of the small bias, but what about getting a completely fair toss from a biased coin?

It turns out to be fairly easy. Just follow these steps:

1. Flip the coin twice.
2. If both tosses are the same (heads-heads or tails-tails), repeat step 1.
3. If the tosses come up heads-tails, count the toss as heads. If the tosses come up tails-heads, count it as tails.

To see why this method makes even a biased coin fair, let's pretend we have a weighted coin that comes up heads 60% of the time. If you toss it twice and throw out the result when both tosses are the same, you're left with two possible outcomes. The probabilities of the two remaining outcomes are the same.

P(HT) = P(TH)
P(H) * P(T) = P(T) * P(H)
0.6 * 0.4 = 0.6 * 0.4 = 0.24

Since both outcomes have exactly the same probability, the bias is removed. This method will work no matter how biased the coin you use, as long as there's some possibility of it coming up either heads or tails (so no two-headed coins allowed).

Note: This method for simulating a fair coin using a biased coin was introduced by John von Neumann in Various techniques used in connection with random digits (1951).

The Broken Stick Revisited

In my earlier post The Broken Stick Experiment, I introduced a problem I had seen in a BLOSSOMS video lecture of the same name. The problem asks

If you break a stick randomly in two places, what is the probability that you can form a triangle from the three pieces?

If you watched the video or ran the simulation code I provided, you found out that the probability of forming a triangle by chance is 25%.

Reader Tom Raywood asks, "Do obtuse triangles count here, or is the solution limited to acute?" The answer to that question is that the solution accounts for triangles of all types, acute, obtuse, and even right triangles. When you break the stick randomly, any of the three are possible (although, as we'll see, right triangles are so unlikely that the probability of getting one randomly is effectively 0).

This question piqued my curiosity enough to investigate another related question.

What proportion of the resulting triangles from the broken stick experiment will be obtuse?

I decided to modify the simulation program to find out the answer.

The first question I had to answer was "How do you tell if a triangle is acute or obtuse?" The easy way is look at it and see if it contains one angle greater than 90° (the definition of an obtuse triangle). However, in the original experiment we only know the lengths of the three sides of the triangles, and none of the angles. It seemed unnecessary to compute all three angles just to see if the triangle was acute or obtuse, although this approach is not totally infeasible. Fortunately, there's an easier way.

We all know from the Pythagorean Theorem that for a right triangle

a² + b² = c²

That is, if one angle is exactly right (90°), the sum of the squares of the two sides adjacent to that angle will be exactly the same as the side opposite that angle.

But if the angle changes (while the two sides a and b stay the same length) then the relationship changes as well. If you open the angle up, side c (and its square) gets larger. If you close the angle, side c (and its square) gets smaller. Meanwhile, the sum of the squares of sides a and b stays the same. This leads to the following relationships for acute and obtuse triangles:

If the triangle is acute:

a² + b² > c²

If the triangle is obtuse:

a² + b² < c²

Using those relationships, I modified the simulation to count how many of the resulting triangles were acute, obtuse, and right triangles.

import java.util.Arrays;
import java.util.Random;

public class BrokenStickRevisited
{
 public static void main(String[] args)
 {
     Random random = new Random();

     int trials = 1000000;
     int triangles = 0;
     int acute = 0;
     int obtuse = 0;
     int right = 0;

     double[] breaks = new double[2];
     double[] sides = new double[3];

     for( int i=0; i < trials; ++i )
     {
         breaks[0] = random.nextDouble();
         breaks[1] = random.nextDouble();
         Arrays.sort(breaks);

         sides[0] = breaks[0];
         sides[1] = breaks[1] - breaks[0];
         sides[2] = 1.0 - breaks[1];
         Arrays.sort(sides);

         if( sides[2] < (sides[0] + sides[1]) )
         {
             triangles++;

             double aSquared = sides[0] * sides[0];
             double bSquared = sides[1] * sides[1];
             double cSquared = sides[2] * sides[2];

             if( aSquared + bSquared > cSquared )
             {
                 acute++;
             }
             else if( aSquared + bSquared < cSquared )
             {
                 obtuse++;
             }
             else // highly unlikely, but still...
             {
                 right++;
             }
         }
     }

     System.out.println("Triangles: " + triangles);
     System.out.println("Acute: " + acute);
     System.out.println("Obtuse: " + obtuse);
     System.out.println("Right: " + right);
     System.out.println("Trials: " + trials);

     double p = (double)triangles / trials;
     System.out.println("Proportion: " + p);

     double pAcute = (double)acute / triangles;
     double pObtuse = (double)obtuse / triangles;
     System.out.println("Acute Proportion: " + pAcute);
    System.out.println("Obtuse Proportion: " + pObtuse);
 }
}

I let the simulation run for 1,000,000 trials to be sure I get a result accurate to three decimal digits. I ran the simulation several times, and never got a single right triangle. That's not surprising, since we knew the odds were quite against it from the beginning.

The proportion of triangles that were obtuse was 0.682, or about 68.2%. The rest (about 31.8%) were acute triangles. This seemed like a strange result. I was hoping for a nice even proportion like the 1/4 probability we got for generating a triangle from the first broken stick problem. It took a bit of exploration for me to explain the result. Read on if you're still curious.

In order to explain the odd proportion we got from the simulation, I need to start with the solution to the original problem. If we break the stick at two random points, x and y, the three resulting pieces will have lengths x, (y - x), and (1 - y) if x is to the left of y


and y, (x - y), and (1 - x) if x is to the right of y


The three pieces form a triangle if none of the pieces is greater than half the length of the stick. In other words, if

(y > 1/2) and (x < 1/2) and (y - x) < 1/2

when point x is to the left of point y (first image above), and

(x > 1/2) and (y < 1/2) and (x - y) < 1/2

when x is to the right of y (second image above). If we plot all six of these inequalities we get the area that represents the proportion of triangles formed from our broken stick.


The shaded regions representing the conditions that form a triangle add up to 1/4 of the total area, or a 0.25 probability of forming a triangle. Now all we need to do to explain the odd results of the second simulation is figure out how much of these shaded regions represent an obtuse triangle and how much represents an acute triangle.

In order to do that, we can plot the inequalities we used earlier that were derived from the Pythagorean Theorem. Since any of the three pieces of our broken stick could be the longest piece, and either break x or break y could be to the left of the other, we need to plot six different inequalities. We get these inequalities by substituting our stick lengths for the values a, b, and c in the Pythagorean Theorem.

Substituting each of the three lengths x, (y - x), and (1 - y) for each of the values a, b, and c in the Pythagorean equation

a² + b² = c²

gives us the following equations

x² + (y - x)² = (1 - y)²
x² + (1 - y)² = (y - x)²
(y - x)² + (1 - y)² = x²

Similarly, substituting the three lengths y, (x - y), and (1 - x) for the values a, b, and c gives the remaining three equations

y² + (x - y)² = (1 - x)²
y² + (1 - x)² = (x - y)²
(x - y)² + (1 - x)² = y²

Utilities like the Online Equation Solver or QuickMath's equation solver come in handy for solving the equations for y before plotting them in a spread sheet or on a graphing calculator. If you add the plots for the six new equations to the existing plot you should see something like the following illustration.


The small region in the center of each of the two triangles in the plot represent the probability of the broken stick forming an acute triangle. The remaining areas near the edges of the the triangles sum to the probability of forming an obtuse triangle. Using integration to find the area of the bounded areas shows that these values are within a small margin of error of the probability we arrived at using the simulation program. (This post is already a little long, so calculating the integral of the bounded areas is left as an exercise for the reader.)

Related: If you liked this post, Professor Gilbert Strang shows several different approaches to a very similar problem in another BLOSSOMS video lecture, Are Random Triangles Acute or Obtuse? In that lecture all random triangles are considered, not just those constructed from the pieces of a broken stick.

Rolling Sevens

What's the probability of rolling a 7 on one roll of two standard six-sided dice? To make it easier to visualize, here's a listing of all of the different outcomes of rolling two six-sided dice.

(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)
(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)
(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)
(4,1)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)
(5,1)	(5,2)	(5,3)	(5,4)	(5,5)	(5,6)
(6,1)	(6,2)	(6,3)	(6,4)	(6,5)	(6,6)

If you look at the long diagonal starting in the bottom left, you can see that there are six ways out of a possible thirty-six to reach a total of exactly 7.

So for two six-sided dice the probability of rolling a seven is

P(7) = 6/36 = 0.1667

Or about one in every six tries.

That question was too easy, so let's make it a little bit tougher. What's the probability of rolling seven 7s in a row? Okay, it's not that hard if you know how to calculate the probability of independent events. You just need to multiply the probabilities of each event. In this case we want to multiply 0.1667 by itself seven times,

0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667

or we can just raise it to the 7th power.

(0.1667)⁷ = 0.0000036

You can see that rolling seven 7s in a row has some pretty long odds. That will only happen about 36 times in 10 million tries!

But what if you've already rolled six 7s in a row? What's the probability of rolling a seventh 7? Before we do any calculations, would you say that the odds are pretty good or pretty bad of getting a seventh 7?

If you think the probability is extremely bad, you're falling for a very common cognitive bias called the Gambler's fallacy. This fallacy accounts for the belief that a streak of good or bad luck is "due" to change. A gambler who has had a long streak of losing hands in blackjack might decide to increase his bet, banking on the feeling that his luck is about to change.

The Gambler's fallacy arises from out intuitive sense that things have a way of "evening out" in the long run. The truth is that over the very long run, things do even out. This is called the Law of large numbers. If I flip a coin a million times, I can expect to get reasonably close to half-a-million heads. But if I flip the same coin only ten times and get ten heads in a row, the probability of seeing a head on the next flip is still exactly one-half. The Law of large numbers only applies to the average of a large sample, not to individual coin flips, hands of blackjack, or rolls of the dice. The coin (or the cards, or the dice, or the universe for that matter) doesn't remember the result of the previous trials, and therefore cannot be influenced by them.

Oh, I almost forgot, the probability of getting that seventh 7 after rolling six in a row is 0.1667, exactly the same odds as getting a 7 on any other roll. The dice have no memory.

The Monty Hall Problem

The Monty Hall Problem is a probability puzzle based on a game that contestants played on the popular old TV game show Let's Make a Deal, hosted by Monty Hall. On the show, contestants were given a choice of three doors. Behind one door is a car, behind each of the other two, goats. The contestant got to choose a door, and won whatever was revealed to be behind that door. The twist was that after the contestant had selected a door, Monty would show them what was behind one of the two doors not selected, and give them the option of changing their mind.*

The game was deceptively simple, in that it seemed as though the contestant always had one chance in three of winning the car, whether they switched their choice or not. There was a strategy that would double the odds of winning though. It turns out that the winning strategy is as simple as the game.

All a contestant had to do to double their odds of winning was always switch their guess after Monty opened one of the doors. This simple strategy worked because the contestant had only one chance in three of guessing the right door initially. Once they had made their guess, Monty would open one of the other doors that did not conceal the car. Since the player's initial guess was wrong 2/3 of the time, Monty was opening the only other losing door 2/3 of the time (the car was behind one door, so he wouldn't open that).

This strategy isn't intuitive to a lot of people. In fact, when the strategy was first published in Parade magazine, thousands of people wrote in to claim the solution was wrong. It becomes more clear if you look at a bigger variation of the same problem.

Imagine you're on a game show where there are 100 doors. Behind one of them is a new car, while the other 99 conceal goats. Your odds of selecting the right door are 1 in 100. Now imagine that after you've made your selection, the host of the show opens 98 of the doors, revealing 98 of the goats. (Keep in mind that he doesn't randomly open doors. He knows where all the goats are.) Would you switch your original guess to the one remaining door? You only had a 1% chance of winning with your original guess, so does it seem advantageous to switch after the choices are narrowed down to only two?

With a bigger set of doors to choose from, it becomes much easier to see that you have a distinct advantage when you switch from your initial guess. The same holds true for the original problem. By always switching after one door was opened in the original game, the odds of winning were improved from 1/3 to 2/3. That's certainly not a sure thing, but it's not bad odds on a brand new car.

Additional Note: If you want to try out an online interactive version of the original game, you can play it here. Make sure you give yourself enough trials to confirm that the optimal strategy wins 2/3 of the time.

---

* It turns out, Monty Hall never offered to let contestants switch which door (or curtain) they picked on Let's Make a Deal. Instead, he would offer them cash to opt out of the game entirely. The problem that would be known as the Monty Hall Problem was originally published as the Game Show Problem by columnist Marilyn vos Savant in 1990.