Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If you flip a coin until you decide to stop and you want to maximize the ratio of heads to total flips, what is that expected ratio?

Assuming that you want to maximize the ratio, meaning whether you flip again or not depends on the chances of whether you will risk more than you gain, I have gotten that:

  • if the probability is 50/50 (same number of heads and tails so far), you flip again
  • if there are more tails than heads you flip again
  • if you have more heads then tails you don't flip

How do you put this into an equation form to solve for expected ratio?

Thanks

share|improve this question
    
similar to ruin theory, have you tried to model this as a stochastic process? –  yiyi May 3 '12 at 1:40
    
Sorry, I have no knowledge of stochastic processes. My personal math knowledge is quite shallow :(. Is that what it takes to solve this? I saw it as an interview question for an entry level position (and not graduate level education) so I didn't expect that high of mathematical knowledge to be needed. –  Matt May 3 '12 at 1:42
    
However, if you have a solution, I would love to learn how it works. –  Matt May 3 '12 at 1:46
1  
If the coin is fair, there is probability $1$ of equalizing, not by CLT, not by Law of Large Numbers, but because in a random walk in one dimension, equal probability of left and right, there is probability $1$ of return to the origin. –  André Nicolas May 3 '12 at 2:34
1  
If the player is behind or tied, then with probability $1$ there will be equalization, indeed with probability $1$ the player will ultimately be $1$ ahead. Standard but not easy theorem about random walk in one dimension. For ratio, $1$ ahead is better than $1$ behind or tied, no matter how long it takes. –  André Nicolas May 3 '12 at 2:48

1 Answer 1

up vote 7 down vote accepted

Your bullet points amount to saying that you're going to flip the coin until the number of heads exceeds the number of tails. Suppose that this happens on the $n$-th flip; then after $n-1$ flips you must have had equal numbers of heads and tails, so $n=2m+1$ for some $m$, you now have $m+1$ heads, and the ratio of heads to flips is $\frac{m+1}{2m+1}$. If $p_n$ is the probability of stopping after the $(2n+1)$-st flip, the expected ratio of heads to flips is $$\sum_{n\ge 0}\frac{p_n(n+1)}{2n+1}\;.$$ Thus, the first step is to determine the $p_n$.

Clearly $p_0=\frac12$: we stop after $1$ toss if and only if we get a head. If we stop after $2n+1$ tosses, where $n>0$, the last toss must be a head, half of the first $2n$ tosses must be heads, and for $k=1,2,\dots,2n$ the first $k$ tosses must not include more heads than tails. The problem of counting such sequences is well-known: these are Dyck words of length $2n$, and there are $C_n$ of them, where $$C_n=\frac1{n+1}\binom{2n}n$$ is the $n$-th Catalan number. Each of those $C_n$ sequences occurs with probability $\left(\frac12\right)^{2n}$, and each is followed by a head with probability $\frac12$, so $$p_n=C_n\left(\frac12\right)^{2n}\cdot\frac12\;,$$ and the expected ratio is $$\frac12\sum_{n\ge 0}C_n\left(\frac12\right)^{2n}\frac{n+1}{2n+1}=\frac12\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}n\;.$$

Very conveniently, the Taylor series for $\arcsin x$ is $$\arcsin x=\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}nx^{n+1}\;,$$ valid for $|x|\le 1$, so the expected ratio is $$\frac12\sum_{n\ge 0}\frac1{4^n(2n+1)}\binom{2n}n=\frac12\arcsin 1\approx 0.7854\;.$$

Added: I should emphasize that this calculation applies only to the stated strategy. As others have noted, that strategy is known not to be optimal, though it's quite a good one, especially for being so simple.

share|improve this answer
2  
This is a beautiful answer with a beautiful result. Only to prevent misunderstandings I want to point out that it determines the expected ratio of the given strategy; it doesn't prove that this is the optimal strategy, and in fact the essentially duplicate question linked to by Sam in a comment under the question says that the optimal strategy is unknown. –  joriki May 3 '12 at 5:13
    
@joriki: Thanks, and thanks for emphasizing that point; I probably should have made it clearer that I was working only with the given strategy. –  Brian M. Scott May 3 '12 at 5:16
    
The paper I linked to under the question gives the bounds $$0.79295301268091 \lt V (0, 0) \lt 0.79295559864361$$ for the value of the game at the beginning, so this strategy is surprisingly close to optimal. –  joriki May 3 '12 at 5:36
    
This is awesome. Thanks! –  Matt May 3 '12 at 5:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.