MathB.in - Share Mathematics with LaTeX and Markdown

*A biased coin takes 100 flips on average to get 10 heads in a row. What's the bias?*

To solve this problem, I'll consider a simpler, related scenario. But before that, a lemma.

Lemma: Say you have a biased coin that comes up heads with probability $h$. If you flip the coin until it comes up heads, the expected number of flips is $1/h$. (For example, if the coin comes up heads with probability $0.1$, the expected number of flips is $10$.)

Proof: Let x be the expected number of flips. You must flip at least once in order to know whether to stop. If that flip comes up heads, you are done: you make zero more flips.  Otherwise, it came up tails. Coins have no memory, so the number of flips remaining is the same regardless of how many flips you have made so far. Therefore, when you flip tails, you expect to make x more flips before stopping.

By expected value: $$x = 1 + h·0 + (1-h)·x$$ Solving for $x$ yields: $$\frac{1}{h}$$

Now for the simpler scenario: say we have a biased coin that comes up heads with probability $h$. Let one "trial" be the act of flipping the coin until it comes up tails. Let a "successful trial" be a trial with 10 or more heads. Let a "game" be the act of making trials until you get a successful trial. What's the expected number of flips per game?

I'll consider a series of questions to arrive at the answer.

First, what's the expected number of trials per game? The probability of getting 10 heads in a row is $h^{10}$. That's also the probability of getting a successful trial, so, by the lemma, the expected number of trials is: $$\frac{1}{h^{10}}$$.

Second, what's the expected number of flips per trial? The coin comes up tails with probability $1-h$, so, by the lemma, the expected number of flips per trial is: $$\frac{1}{1-h}$$

Third, what's the expected number of flips per game? It's just the expected number of flips per trial multiplied by the expected number of trials per game, that is: $$\frac{1}{h^{10}(1-h)}$$.

Recall that, in this simpler scenario, a trial doesn't end until we flip tails. Therefore, even after getting 10 heads in a row on the final (successful) trial, we keep flipping until it comes up tails. Call these "extra flips".

What's the expected number of extra flips for a successful trial? Regardless of what's been flipped up to this point, the probability of flipping tails is still $1-h$, so the expected number of extra flips is $$\frac{1}{1-h}$$

Now, the scenario in the original problem is just like the simpler scenario except that *extra flips don't count towards the total*. To adjust for this, I'll subtract the expected number of extra flips from the expected number of flips per game. The expected number of flips in the original scenario is therefore: $$\frac{1}{h^{10}(1-h)} - \frac{1}{1-h}$$

This simplifies to: $$\frac{h^{-10}-1}{1-h}$$.

In the original problem, it is given that the expected number of flips is $100$, i.e. that $(h^{-10}-1)/(1-h) = 100$. We can use binary search to find that $h$ is about $0.71$.

Fri, 05 Jul 2019 00:12 GMT