Posts Tagged ‘probability’

Bayesian Bro Balls and Monty Hall

April 13, 2013

I don’t think this is very good, but I’m tired of working on it and I said I’d write it, so here it is. See http://yudkowsky.net/rational/bayes for a better essay on thinking about probability.

A woman and a man (who are unrelated) each have two children. We know that at least one of the woman’s children is a boy and that the man’s oldest child is a boy. Can you explain why the chances that the woman has two boys do not equal the chances that the man has two boys?

(text copied from here, which attributes the problem’s popularity to an “Ask Marilyn” column in 1996)

Given a tricky problem, some people are stumped, clever people find a tricky answer, and brilliant people find a way of thinking so the problem isn’t tricky any more. This problem is about interpreting evidence, and the brilliant person who discovered how to think about evidence is Laplace. (His method is called Bayes’ Rule. Bayes came first, but Laplace seems more important based on my cursory reading of the history.) To illustrate it, let’s start with different problem, related only by the fact that it’s also about using evidence.

I picked a day of the week by first choosing randomly between weekend and weekday, then picking randomly inside that set. I wrote my chosen day down and picked a letter at random. The letter was ‘d’. What is your best guess for the day that I picked? How confident are you? (“At random” means there was uniform probability.)

First, write out all the possibilities. These are called the “hypotheses” (plural of “hypothesis”).

• Saturday
• Sunday
• Monday
• Tuesday
• Wednesday
• Thursday
• Friday

Next, find their starting probabilities, the ones we have before learning what letter was picked. Half the probabilities goes to the weekend, so they’re 1/4 each. The rest goes to the five weekdays, so they’re 1/10 each. This is called the “prior”. The picture shows lengths proportional to probability.

Let’s imagine we did this experiment 10,080 times (a number I’m choosing since it will work out well later). Then the weekends come up 2520 times each and the weekdays 1008 times each. (This is the expectation value for how many times these days would show up. In a real experiment there would be random deviations.)

Next we look at the evidence – the letter ‘d’. Out of our 10,080 experiments, how many have the letter ‘d’ result? It turns out this will happen 1565 times – 315 times on Saturday, 420 times on Sunday, etc.

The illustration looks like this (partially filled in)

The bottom bar represents all the trial where the letter ‘d’ popped up. It is too small to read, so we’ll blow it up.

We can divide by the total number of times the letter ‘d’ came up to get the probabilities. (Individually this step is called “normalizing”, but it’s really part of updating.)

We don’t really need to consider doing the experiment 10,080 times; I just thought that made it more convenient to visualize. What’s important is the probability distribution at the end. This solves the problem. We now know, given that ‘d’ was the chosen letter, the probability for each day of the week.

To recap, an outline for the procedure is

1. Find all the possibilities (i.e. define the hypotheses).
2. Determine how likely the hypotheses are beforehand (i.e. choose the prior).
3. Update the hypotheses based on how well they explain the data (i.e. multiply them by their probabilites of producing the evidence).
4. Finish updating by making the hypotheses’ probability add up to one (i.e. normalize).

Let’s reword the original problem to make it clear exactly what evidence we’re collecting, then apply the method:

There are two bros who like to tan their balls. Unfortunately, this can cause testicular cancer. Given their amount of ball-tanning, each testicle of each bro has a 50% chance of having cancer. (The testicles are all statistically independent of each other.) The two bros decide to conduct testicular exams to see whether they have cancer, and their self-administered exams are perfectly accurate. The first bro decides to examine both his testicles, then report whether or not at least one of them has cancer. The second bro decides to examine only his left testicle because he thinks that examining both would count as cradling them and be gay. Suppose the first bro reports that indeed, at least one of his balls has cancer. The second bro reports that his left ball has cancer. Do they have the same probability of having two balls with cancer?

The bros go about collecting different data. The evidence they bring to bear is different, so a good way of handling evidence should be able to show us that the probabilities are different. But there is no need to be clever about finding the solution when you have a general method at hand.

The hypotheses we’ll use are left/right both cancerous, left cancerous/right healthy, left healthy/right cancerous, both healthy. They are all equally likely.

In this case, updating is very simple. Each hypothesis explains the results either perfectly or not at all. Here is what updating looks like for the bro who tested both balls:

Here it is for the bro who tested on the left ball:

So the bro who tested both balls has a 1/3 chance of having cancer in both balls, while the bro who tested the left ball has a 1/2 chance. Both came back with a positive result, but the bro who tested both balls has weaker evidence. It is easier to satisfy “at least one ball has cancer” than to satisfy “the left ball has cancer”, so when he comes back and reports that at least one ball has cancer, he hasn’t given as much information, and his probability doesn’t shift upwards as much. A strong test is one which the hypothesis of interest passes, but which eliminates the competing hypotheses. More hypotheses pass the test “at least one ball has cancer”, so that test doesn’t eliminate as much and is not as strong.

Let’s apply the same method to the Monty Hall problem. Your hypotheses are that the prize is behind door one, door two, or door three. These are equally-likely to begin. You choose door one, and Monty Hall opens door two. That’s the evidence.

If the prize is behind door one (the door you chose), Monty Hall could have opened either door 2 or door 3, so there was a 50% chance to see the observed evidence. If the prize was behind door 2, there was 0% chance, so that hypothesis is gone. If the prize was behind door 3, Monty Hall was forced to open door two, so that hypothesis explained the evidence 100% and becomes more likely.

Here’s a diagram for the probabilities after updating:

So you should switch doors. The usefulness of this method is you don’t need a clever trick specific to the Monty Hall problem. As long as you understand how evidence works, you can solve the problem without thinking and spend your limited thinking power somewhere else.

Within this framework, we can notice some things that help make the problem more intuitive, even after it’s solved. Suppose you have a hypothesis and you collect some evidence. How much more-likely does the hypothesis become? What matters is how much better the hypothesis explains the data than the other hypotheses, not just how well it does by itself. So, if you have two hypotheses and they both explain the data equally well, that data isn’t evidence either way.

You can apply this idea to the bro who tested his left testicle. Whether the right testicle has cancer or not, the data on the left testicle is equally-well explained. Therefore, the right testicle’s probability remains unchanged from 50%, so the bro has a 50% chance of two cancerous balls.

The same is not true for the bro who tested both testicles. If that bro has cancer in his right testicle, that explains the result better than if he doesn’t. That is to say, if the bro has cancer on his right testicle, that explains the result perfectly. But if he doesn’t, there’s only a 50% chance of explaining the result. As a result, the 1:1 odds for the right testicle get multiplied by 2:1 to give 2:1 odds. The probability for his right ball to have cancer increases to 2/3. (The probability for his left testicle to have cancer is also 2/3, but they are not independent.)

In the Monty Hall problem, Monty Hall will reveal an empty door no matter what, so the hypothesis “the prize was behind your original door” explains the data just as well as “the prize was not behind your original door”. Therefore, the probability that the prize was behind your original door doesn’t change; there was no evidence for it. So your original door still has a 1/3 chance. So good Bayesians are not confused by the Monty Hall problem.

Flat Priors and Other Improbable Tales

September 8, 2010

Some collected and invented stories about erroneous thinking in probability.

A Visit

It’s night. You are coming downstairs for a glass of water. You hear a creaking sound and look around a corner to see a man in a ski mask opening your front door. “What are the odds?” you think. “Normally that guy would have set off my burglar alarm and been scared off by the loud wailing, but he happened to stop by for a visit just one minute after the power went out.”

Feynman

You know, the most amazing thing happened to me tonight. I was coming here, on the way to the lecture, and I came in through the parking lot. And you won’t believe what happened. I saw a car with the license plate ARW 357. Can you imagine? Of all the millions of license plates in the state, what was the chance that I would see that particular one tonight? Amazing!

Immortality

About 100 billion people have ever lived, and there are about 7 billion people alive now. Therefore about 7% of people are extremely long-lived.

Astronaut

A man makes it through a long battery of physical and psychological tests and finally achieves his lifelong dream of joining the astronaut program. He immediately takes up heavy smoking. “What gives,” asks his friend. “I thought you were a health nut.”

“I am,” replies the man. “Anybody who smokes a lot will probably die of lung cancer.”

“Why would you want to die of lung cancer?” his friend asks.

“A shuttle explosion will kill you in two seconds,” he replies. “But now I’m gonna die of lung cancer, and that’ll take at least forty years.”

Hitchhiker’s Guide

It is known that there is an infinite number of worlds, simply because there is an infinite amount of space for them to be in. However, not every one of them is inhabited. Therefore, there must be a finite number of inhabited worlds. Any finite number divided by infinity is as near to nothing as makes no odds, so the average population of all the planets in the universe can be said to be zero. From this it follows that the population of the universe is also zero, and that any people you may meet from time to time are merely the product of a deranged imagination.

Foreign Lands

In a certain country, people always name their first child a name that starts with “A”, their second child a name that starts with “B”, etc. Families in this country are anywhere from one to ten children; equal numbers of families have each. It is a tradition in this country for each father to randomly select one of his children each day to accompany him on a walk.

When visiting this country, you meet a man out walking with his daughter, who he introduces as Evelyn. You now know the man has at least five children. If he had exactly five, your chances of meeting the one whose names starts with “E” are 1/5. If he had more, say eight, your chances of meeting the one whose name starts with “E” are 1/8. Therefore, you conclude that it is most likely that Evelyn is the oldest child. You realize there was nothing special about Evelyn, and conclude that any time you meet a man walking with his child in this country, he is most likely to be walking with the oldest one.

Casablanca

Of all the gin joints, in all the towns, in all the world, she walks into mine.

DNA

While rummaging around in his parents’ attic, Sean comes across an old love letter to his mother. It’s from Rodrigo Valenzuela, a man he never knew, to his mother. It refers to “nights of fevered frenzy and mornings of muted passion”, is signed, “a mi amor”, and asks when her husband will be away again. The letter is dated eight months before Sean’s birth date. He looks in the mirror, wondering why he didn’t inherit his parent’s fiery orange hair and why salsa music has always stirred his soul.

Sean looks up information on paternity tests, and finds that if you send in one sample of DNA as the suspected father and one as the suspected child, the test will report a probability, which represents the probability that a man with the “father” DNA would sire a child at least as genetically different from him as the “child” DNA. Thus, a low percentage, like 0.001%, means that a true child would have only small chance of being as different from the father as the “child” sample is. This is the result we expect if the child is not from the father. A high percentage, like 60%, means the “child” and “father” DNA are very close, and is what we expect if the man is the true father.

Secretly, Sean collects a sample of the DNA of the man he’s always called “dad” and one of his own and sends them in for testing. As a control, Sean also collects a sample from his own son, and a second sample from himself and sends this sample in as well. Finally, Sean hunts down Rodrigo Valenzuela using Facebook, “friends” him, studies his “likes” and “interests”, uses them to befriend Roderigo in real life, asks to borrow his car, and steals a hair from the headrest. He sends in a third sample of Rodrigo and himself for testing.

Two weeks later the test results come back. Sean isn’t shocked. The probability for him and his “dad” is a scant 0.00004%. The probability from Roderigo and himself is 7%. Finally, the result from his son is 74%. Sean realizes that there’s some natural variation in the test, but the evidence is still clear: Roderigo is his true father.

The next day the clinic and says there’s been a mix up. They accidentally switched the samples from Sean and his son, so the 74% was actually the result of testing Sean’s son in the “father” role and Sean in the “child”. Sean is understandably upset. He goes to bed that night thinking that although Roderigo may be his father, it’s ten times as likely that his own son will, in the course of his life, discover time travel and go back to impregnate Sean’s mother.

Flat Prior

On whether or not the Large Hadron Collider would create a black hole that would consume Earth:

John Oliver: So, roughly speaking, what are the chances that the world is going to be destroyed? Is it one in a million, one in a billion?

Walter Wagner: Well, the best we can say right now is about a one in two chance.

JO: Hold on a second. Is the, if, 50 – 50?

WW: Yeah, 50-50.
….
WW: It’s a chance. It’s a 50-50 chance.

JO: You keep coming back to this 50-50 thing. It’s weird, Walter.

WW: Well, if you have something that can happen and something that won’t necessarily happen. It’s either gonna happen or it’s gonna not happen. And, so it’s, the best guess is one in two.

JO: I’m not sure that’s how probability works, Walter.

from The Daily Show

Flip It One More Time

March 10, 2010

A couple weeks ago I posted about flipping an unfair coin. There, I imagined a coin that came out of a flip the same way it went in 51% of the time. The coin didn’t prefer heads or tails in general, but if it started out heads it was slightly more likely to stay heads, and likewise for tails.

If you flip that coin once, it’s not bad – just a little bit away from fair. If you flip it twice, it’s so close to fair you’d have to flip do tens of thousands of repetitions of double-flips to see they were biased.

But what if instead of 51% chance to land the same way, the coin had 90% chance? Then how many times would you have to flip it to get pretty close to fair?

The trick to this is not to try to calculate all the strings of length six, for example, and see what the probability is for heads on the sixth toss, and then go to seven if six wasn’t good enough. Instead, flip it once, and make the second flip act on the uncertain state.

Here’s what I mean: We’ll write heads as a column vector like this:

$\left( \begin{array}{c} 1 \\ 0 \end{array}\right)$

and tails like this:

$\left( \begin{array}{c} 0 \\ 1 \end{array}\right)$

For an uncertain state, where we haven’t looked at the coin yet, we write:

$\left( \begin{array}{c} P_H \\ P_T \end{array}\right)$.

Flipping is then the symmetric operator that takes us from the certain state to the 90-10 state. This is

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right)$

Flipping a coin that started out heads corresponds to the equation

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right) \left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .9 \\ .1 \end{array}\right)$

To flip twice, act with the operator again.

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array} \right)\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right) \left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .82 \\ .18 \end{array}\right)$

To flip $n$ times, evaluate

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right)^n \left( \begin{array}{c} 1 \\ 0 \end{array}\right)$

Intuitively, one eigenvector of that operator is the 50-50 state. Since the operator is symmetric, if we begin with complete uncertainty, we must still have complete uncertainty after flipping. Evidently, the eigenvalue is one.

The eigenvectors of a symmetric operator on a real vector space are orthogonal1, so the other eigenvector is

$\left( \begin{array}{c} .5 \\ -.5 \end{array}\right)$,

which is not very meaningful by itself, but forms a basis along with the first eigenvector. Its eigenvalue is 0.8.

We can break any heads/tails probability down into a sum of these two eigenvectors. The first eigenvector is the fair state. The second eigenvector is what takes us away from the fair state. When its component is positive, we lean towards heads, and the higher its component the more we lean towards heads. When the component of this second eigenvector is negative, we lean towards tails.

The pure heads state can be written in the eigenbasis by

$\left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .5 \\ .5 \end{array}\right) + \left( \begin{array}{c} .5 \\ -.5 \end{array}\right)$.

Flip $n$ times, and the component of the first eigenvector is unchanged because its eigenvalue is 1, but the second eigenvector’s component dies away exponentially, because it’s multiplied by 0.8 each time. That leaves us with

$\left( \begin{array}{c} .5 + .5*,8^n \\ .5 - .5*.8^n\end{array} \right)$.

If we want to probability for heads to be within $\epsilon$ of 50%, we know

$\epsilon = .8^n$

and so

$n = \ln(\epsilon)/\ln(0.8)$

We’d have to flip 21 times to get down to 51%. We can see that the second eigenvalue, the one that was .8 here, comes from .9 – .1. In general, if the chance to stay what you are is $p$, then this second eigenvalue will be $2 p - 1$. If $p<.5$, then this eigenvalue is negative, and the component of the second eigenvector will switch each flip. We'll go from biased towards heads, to biased towards tails, and back again, flip-flopping with each coin toss.

1 if $A$ and $B$ are two eigenvectors of a symmetric operator $M$ with eigenvalues $\alpha$ and $\beta$, then

$AMB = A\beta B = \beta AB$

by acting with $M$ on the right. Since $M$ is symmetric, it can also act on the left, giving

$AMB = \alpha AB$.

These expressions are the same, so

$\beta AB = \alpha AB$

which implies

$AB = 0$

as long as $\alpha \neq \beta$. If they are equal, we have a two-dimensional eigenspace, and can simply choose two orthogonal vectors inside it using Gram-Schmidt. Either way, once you find the first eigenvector, whatever is perpendicular will be another one.

Also, there may be complex eigenvectors, but there must be an even number of them, so once we found one real eigenvector we knew there was another.

Some Birthday Problems

February 24, 2010

One of the most famous counter-intuitive problems in probability is, “How many people must there be in a room before the probability that at least two of them have the same birthday exceeds one half?”. Most likely, you’ve heard this problem and its solution (which is 23) before. I seem to remember doing it in the fourth grade. But test your intuition against the following:

1. How many people must there be in a room before the probability of at least one of them having your birthday exceeds one half?
2. How does the birthday problem change if we’re not looking for two people with the same birthday, but two people with adjacent birthdays?
3. How does the birthday problem change if we account for the distribution of birthdays not being flat?
4. How many people must there be in a room before the probability that every day of the year has at least one person with that birthday exceeds one half? (Ignore Feb. 29)
5. People walk into a room one by one, and continue doing so until there’s a pair of people in the room with the same birthday. What is the expectation value of the number of people who walk into the room? Is it more, less, or the same as the 23 that solve the birthday problem?
6. How do the answers to these questions (including the original birthday problem) scale with the length of the year? For example, if the year were twice as long (and days were the same length), would the answer to the birthday problem be 46?

There are other obvious questions, such as how many people to have a 1/2 chance of three people with the same birthday, or how many to have two pairs of repeat birthdays, but these seem more tedious than interesting to me. Here is one more, though, which I got from a problem book:

Labor laws in Erewhon require factory owners to give every worker a holiday whenever one of them has a birthday and to hire without discrimination on grounds of birthdays. Except for these holidays they work a 365-day year. The owners want to maximize the expected total number of man-days worked per year in a factory. How many workers do factories have in Erewhon?

Flip Better

February 20, 2010

After posting this, I realized I made an error that seemed small but messed up everything.
You can see the correction here.

Depending on the internet circles you run in, a friend may have linked you to this quotation recently:

When faced with 2 choices, simply toss a coin. It works not because it settles the question for you, but because in that brief moment, when the coin is in the air, you suddenly know what you are hoping for.

Or, as another pointed out to me, this poem by Piet Hien:

Whenever you’re called on to make up your mind,
and you’re hampered by not having any,
the best way to solve the dilemma, you’ll find,
is simply by spinning a penny.
No – not so that chance shall decide the affair
while you’re passively standing there moping;
but the moment the penny is up in the air,
you suddenly know what you’re hoping.

I recently had a binary choice to make, so I gave this tactic a shot. I report that it doesn’t work if you’re counting on it. That is, it might work by serendipity, but if you toss the coin specifically so that you’ll understand your subliminal desires, the effect is ruined. I want my money back. (I didn’t pay anything for the advice, but I dropped three coins down a gutter before I finally managed to catch one I had flipped.)

This reminds of a paper saying that if you flip a coin vigorously, it’ll come up the same way it started about 51% of the time.

Here, I’ll ask if you can substantially avert this bias by flipping best-two-of-three. (Another way to avoid the 51% problem is not to flip the coin at all. Take it out of your pocket, look at it, and go with that.)

Let’s say that when you flip a coin, its chance to land the same way it started is $p$, regardless of whether it started heads or tails. Then its probability to flip to the other state is $1-p$, and let’s agree to call that $q$ for short. In an ideal world, $p = q = 0.5$, but Diaconis et. al. suggest this may not be true.

Suppose the coin starts with Heads up ($H$). Then what is the probability that heads wins two out of three tosses? Is it closer or further from $0.5$ than $p$, and by how much? That is, is two-out-of-three more fair than a single coin flip?

There are four ways that heads can win 2 of 3 tosses.

$HHH$

$HHT$

$HTH$

$THH$

To find the probability of each, we need to know not whether each toss is heads or tails, but when the coin is changing state. For example, take the sequence

$HTH$.

The coin starts out $H$, and then we make our first flip and get another $H$. The coin didn’t change state, so this has probability $p$. We flip again and get $T$, a switch. This has probability $q$. The last flip we go back to heads, another switch, and another probability $q$. The final probability for this sequence is $p*q*q = pq^2$.

Here is a mildly-relevant image from the internet. It is the best thing that pops up when google "sexy quarter." This is the middle of the blog post, which is roughly where you are supposed to forcibly insert semi-relevant images without explanation, if I've learned anything from reading blogs.

The probabilities for each of the four sequences are:

$P(HHH) = p^3$

$P(HHT) = p^2q$

$P(HTH) = pq^2$

$P(THH) = q^2p$

GAAH! More $p$‘s than a kindergartener’s underpants. Rather than calculate, let’s simplify using our knowledge that coin tossing is not horrendously unfair, so that $p \approx 0.5$. Specifically, let’s set a small number $\epsilon$ such that

$p = \frac{1}{2} + \epsilon$.

This will let us simplify the calculations because we can ignore anything that has an $\epsilon^2$ in it as a second-order correction. Unless the first-order correction comes out to be zero, this is a good approximation.

We know that

$q = \frac{1}{2} - \epsilon$,

which lets us simplify a bit. First, lay out the ground rules

$\begin{array}{rcl}p^2 &=& \left(\frac{1}{2} + \epsilon\right)^2 \\ &=& \frac{1}{4} + 2*\frac{1}{2}\epsilon + \epsilon^2 \\ &\approx& \frac{1}{4} + \epsilon \end{array}$

This says that when you take a number a little bit bigger than one half and square it, you get something the same little bit bigger than one fourth. Let’s apply the same rule for $q$:

$q^2 \approx \frac{1}{4} - \epsilon$

and when multiplying $p$ and $q$, the over-compensation and under-compensation cancel out to first order, and we have

$p*q \approx \frac{1}{4}$.

The nice thing is that the we can use the binomial theorem to propagate out to higher powers of $p$ and $q$. If we have $p^mq^n$, for example, that is roughly

$p^mq^n \approx \frac{1}{2^{m+n}} + \frac{m-n}{2^{m+n}}*\epsilon$,

which of course is left as an exercise to the reader. It’s not the kind of exercise that will give you washboard abs, but it is the kind that will get you girls.

Returning to the probability for two heads out of three, we can fill in the probabilities like so:

$P(HHH) = p^3 = \frac{1}{8} + \frac{3}{8} \epsilon$

$P(HHT) = p^2q = \frac{1}{8} + \frac{1}{8} \epsilon$

$P(HTH) = pq^2 = \frac{1}{8} - \frac{1}{8} \epsilon$

$P(THH) = pq^2 = \frac{1}{8} - \frac{1}{8} \epsilon$

the sum is

$P(H wins) = \frac{1}{2} + \frac{\epsilon}{4}$

If it’s a little unfair to flip a coin, flipping for best two out of three cuts the bias by a factor of four. Or, in less coherent words, it quarters the quarter’s recording of its core uncordial proclivity.

There’s more interesting stuff here. How much better is it to play three-of-five, or four-of-seven, or $x$ of $2x-1$? Exercises to the very sexy reader.

New Problem: Look Up!

August 7, 2009

I learned a game today. A group of people sit in a circle, looking down. The game leader counts to three, and on three everyone lifts their head and looks at one other person. If the other person is looking back at you, you’re both out. The game continues until there are one or two people left (depending on if your group has an even or odd number). The wonderful part is that no one feels bad about getting knocked out, because it’s impossible not to laugh when you look up to see the person you chose staring right back at you – the power of human eye contact.

The question is: for a given number of players, $n$, and assuming each person chooses who to look at randomly, how many rounds do you expect the game to take before ending?

July 10, 2009

problem

For the sake of brevity, I’m going to use a lot of intuition on this one, and I’m only going to focus on expectation values, even though the question mentioned full probability distributions. I checked my answers against a computer, though, so I guess they’re probably right.

Alice needs to get two consecutive heads to win the game. Suppose she’s got one, but then misses finishing the pattern by getting a tails. Then she has to start all over, waiting until she flips two heads.

On the other hand, suppose Bob has one heads, and needs a tails. He misses by getting heads. That’s not so bad, though, because he’s not starting over. Instead, he’s already half way through his pattern.

Bob is thus more likely to win this game.

Let’s find the expectation value of the number of times Bob must flip before he finishes. First he must get a heads. This takes, on average, two flips. Then he must flip until he gets a tails. This takes two more flips on average, so Bob’s expected number of flips is four.

Alice also expects two tosses to get heads. But once she gets heads, she’ll need a third toss. Half the time, that’s a heads and she’s done. However, half the time she fails and has to start over. So Alice expects to have to go through the whole rigmarole twice. It takes three tosses to go through once, so her expected number of tosses to finish the game is six.

The full probability distributions are more difficult to compute (for me), but a computer simulation tells me that Bob wins about 68% of the time.

To generalize to longer patterns, let’s denote a particular pattern with $n$ flips by $p_n$. Its expected number of flips to finish is $E(p_n)$. Then we’ll say that $p_{n-1}$ is the same pattern without the last flip. In order to finish the pattern $p_n$, you must first finish the pattern $p_{n-1}$. This takes $E(p_{n-1})$ flips on average. Then you’ll either finish the pattern on the next flip, or not.

If you do finish the pattern on the next flip, that’s great. There’s a $1/2$ chance of this, and the length would be $E(p_{n-1})+1$. On the other hand, if you fail by flipping the wrong thing on the last one, there are now two different scenarios. If the first and last sides of the pattern are the same and you failed to finish the pattern, then you must have flipped the opposite side as you started with, and so you’re starting completely over. You’ve done $E(p_{n-1})+1$ flips, and because each time you have a probability $1/2$ of finishing, you expect to go through this process twice. Your probability overall then is $2* \left[E(p_{n-1})+1 \right]$.

On the other hand, if you get almost all the way through but miss the last one and the pattern begins and ends on opposite sides, then when you start over you’re already at least one flip on the way. You might be even further along than that. For example, if you’re trying to get HHT, then you expect to flip $6$ times before getting HH, but once you do, you’ll finish very soon. Even if you miss your target of tails, you must have flipped heads. That means you still have a HH streak over your last two, and you can flip again. You expect to flip twice before finishing the sequence, so the expected number of flips for HHT is eight.

HTT is a different story. The answer works out the same, but the reason is different (as I see it). For HTT, you expect to flip four times to finish the HT pattern. Once you do, if you miss on the last one by getting heads when you wanted tails, you’ve got the first flip of your sequence, but you now need to score a TT. That takes six flips. So the total expected number of flips is $1/2*5 + 1/2*(5+6) = 8$.

The generalized formula is a bit more complicated than I really want to get into though, as far as I can see. Say you flip a coin 32 million times. Then any given 5-flip pattern should appear about one million times in the long sequence. However, some sequences overlap a lot, while others don’t. The ones that overlap a lot, like HHHTHHH, wind up giving further spacing than the ones that don’t overlap, as much, like HTHHTTT. If the patterns overlap, then sometimes the end of one pattern is close to the end of the next, and sometimes far away. Choosing a spot at random in the sequence, you’ll probably wind up in one of the stretches where the ends of the patterns are far away from each other, hence it’ll take a lot of flips to finish the sequence. On the other hand, if the sequences don’t overlap much, then the spread between where they end is pretty much even, and if I pick a spot at random, it’s likely to be a more moderate number of flips before I finish the sequence.

Sorry to be lame and not provide full answers.

New Problem: One More Coin-Flipping Game

July 4, 2009

This problem comes from a TED talk by Peter Donnelly

Alice and Bob are flipping fair coins (in a fair manner). They each flip once per second. Alice flips until she gets two consecutive heads, then stops. Bob flips until he gets a heads followed by a tails, then stops.

Who is more likely to stop first? What is Alice’s expected number of tosses before she stops? What is Bob’s? What are the full probability distributions of coin tosses before stopping for Alice and Bob? What is the probability that they tie?

Can you generalize this scenario to longer patterns?

New Problem: Rosencrantz and Guildenstern Are Dead

November 29, 2008

Suppose you flip a fair coin $n$ times. What is the probability distribution for the longest streak of consecutive like outcomes? That is, let

$P(l) \equiv$ Probability that there exists a streak of $l$ consecutive heads or $l$ consecutive tails in the sequence of $n$ tosses, but no streaks longer than $l$ exist.

Find $P(l)$.

In case it helps, here is a picture of a coin.

PS – The picture doesn’t help, but Sacagawea was pretty hot for a 15-year old. Also, she apparently had a small, secondary head growing out the back of her neck.

October 26, 2008

I’ve done another fantastic job of poorly-defining the problem. I asked for the “best” strategy, which is open to a lot of interpretation. You can play so as the maximize the probability that you get the best possible answer with the digits that come up, or to maximize your expected number at the end of the game, or with some other payoff scheme. I’ll look for an algorithm to maximize your expected number. This means an algorithm such that, if you played the game many times, your average score would be better than any non-equivalent algorithm’s average score with probability that approaches unity as the number of games played approaches infinity. This would roughly correspond to trying to win the game with the greatest possible likelihood, rather than trying to win the grand prize. However, if you were actually playing the game it could in principle be advantageous to tweak the strategy I present below. For example, if the other team adopts the same algorithm, you would always tie. And I hate ties.

Imagine playing the game with two slots and two spins of the wheel. On any given spin, you can get 0 through 9 with equal probability, meaning your expected payoff from a given spin is 4.5. So for this game your strategy is simple. If you get a 0 through 4 on the first roll, you’re likely to do better next time, so drop it in the one’s place. Otherwise, stick it in the tens place.

There are 100 total possible orders of numbers that can come up in this two-turn game. The strategy described above fails only for numbers like 58 and 89 which have the first digit five or greater and the second digit bigger than the first. That’s ten total cases, so in the two-turn game you can play optimally 90% of the time.

The probability distribution for your final outcome is that first digit will be 0 through 4 with probability $\frac{1}{20}$ each, and 5 through 9 with probability $\frac{3}{20}$ each. The expected value of this slot is 5.75. The units place is the same, but the probabilities for those two groups of digits are reversed, and its expected value is 3.25.

Now we understand the game with two plays, we can apply that knowledge to three turns. Suppose you spin the wheel and get a 6. Once you make a decision where to place that 6, you’ll essentially be playing the game with only two slots – a situation we already understand. But since the expected value of the higher slot is 5.75 and 6 is better, we should throw the 6 in the top slot. If you rolled a 4 or 5, it’s between the two expectation values for the slots and should go in the middle. 0 through 3 goes in the one’s place.

Calculating the new expected values for each slot is now more complicated. For the first slot, there’s a $\frac{4}{10}$ chance of filling it with a 6,7,8, or 9 on the first move. If not, it’s the higher slot from a two-slot game. There’s a .6 probability of this happening, and the expected value is 5.75. That makes the expected value for the entire slot .4*7.5 + .6*5.75 = 6.45. For the second slot, a similar calculation yields an expectation value of 4.5 (as it ought to), and for the last slot, 2.55.

For a four-turn game, crank through the same procedure one more time, and again for a five-turn game. You’re aided by a few things. First, there’s a symmetry between high numbers and low numbers, with the axis of symmetry between 4 and 5. That means the expectation value of the middle slot is always 4.5 (if a middle slot exists), and as you go out on either side, complementary slots add to 9.

The expectation values for the slots turn out to be
4-slot game [6.915, 5.285, 3.715, 2.085]
5-slot game [7.2405, 5.8455, 4.5, 3.1545, 1.7595]
You don’t need the last of these to play the game – it just tells you what results you’re likely to get. If you played the game a large number of times employing this algorithm, you would average 78,733.8045 (you would have to play a whole lot of times to get that accurate). I’d pay ten bucks to anyone who wanted to work out what the standard of deviation would be. (combinatorically/analytically, not monte carlo/brute force). I’d pay another ten to see an explicit formula for the case with $n$ slots, rather than the recursive algorithm I’ve got.

So, Nikita’s guess that a 6 should go in the 10,000 spot at any time was a good baseline, but not entirely correct. On the first turn, you should only put a 7, 8, or 9 in the top slot. The second turn is the same as far as that slot goes, but on the third term your standards fall to allow a 6 in there. By the fourth turn, if you still haven’t put something in the first slot you should grab anything 5 or better. If that top slot were still empty on the last turn, you’d just have to take whatever fate handed you.

.