16
$\begingroup$

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

  • 0
    similar to ruin theory, have you tried to model this as a stochastic process?2012-05-03
  • 0
    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.2012-05-03
  • 0
    However, if you have a solution, I would love to learn how it works.2012-05-03
  • 0
    Oh, then I guess they wanted to know if you knew how to come up with expected value. E(x) = $\frac{\sigma x_i}{N}$ where N is the total number of values. I would guess the person that wrote this question didn't have a high level of mathematical knowledge. But, its a good question for Math geeks. hehe2012-05-03
  • 0
    Hmmm, well the more you flip, the closer the ratio will be to 0.5. Therefore, you would want to stop flipping as soon as you had a heads ratio of > 0.5.2012-05-03
  • 0
    @JoelCornett That is true because of the Law of Large numbers; however, that doesn't deal with the halting caused by N(tails) > N(Heads).2012-05-03
  • 0
    @MaoYiyi: Wouldn't you necessarily keep playing (flipping) if N(tails)>N(Heads), as you're trying to maximize the ration of heads to tails and the central limit theorem guarantees you that at some point N(heads)=N(tails)?2012-05-03
  • 0
    In other words, N(tails)>N(heads) is not a stopping condition.2012-05-03
  • 0
    @JoelCornett sorry, wrote the 3rd condition backwards. N(Head) > N(tails) is a halt. I also agree with you that the Law of Large Numbers, means that over time N(heads) = N(tails); however, on the next flip will still decide. The point I am trying to make (not argue) is that the stopping criteria effect E(trails) of this question.2012-05-03
  • 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.2012-05-03
  • 0
    @AndréNicolas: You're assuming that the player will keep playing until that happens, which is _not_ the case because the player is seeking to maximize his or her ratio.2012-05-03
  • 0
    Not sure if this will help, but the the expected ratio (of heads to total tosses) after the next toss is $\frac{2a+1}{2b+2}$ if $a$ is the number of heads and $b$ is the number of total tosses.2012-05-03
  • 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.2012-05-03
  • 1
    Unless I've misunderstood your setup, this is an *extremely* difficult problem for various cases of the first few outcomes. See the discussion here: http://math.stackexchange.com/questions/6195/why-is-this-coin-flipping-probability-problem-unsolved2012-05-03
  • 0
    Wow ok. Sorry about this question then. Seemed pretty doable just based on how simple the question is. My bad. Thanks for the link.2012-05-03
  • 0
    Note that the page that the question Sam linked to links to links to [an arXiv paper](http://arxiv.org/abs/1201.0626v1) with new results on this game. Note also that while the optimal strategy is not completely known, it is known that the strategy you propose is not optimal. I've voted to close this question as a duplicate of the other one.2012-05-03

1 Answers 1

14

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.

  • 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.2012-05-03
  • 0
    @joriki: Thanks, and thanks for emphasizing that point; I probably should have made it clearer that I was working only with the given strategy.2012-05-03
  • 0
    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.2012-05-03
  • 0
    This is awesome. Thanks!2012-05-03