18
$\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

$\endgroup$
16
  • $\begingroup$ similar to ruin theory, have you tried to model this as a stochastic process? $\endgroup$
    – yiyi
    May 3, 2012 at 1:40
  • $\begingroup$ 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. $\endgroup$
    – Matt
    May 3, 2012 at 1:42
  • 1
    $\begingroup$ 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. $\endgroup$ May 3, 2012 at 2:34
  • 1
    $\begingroup$ 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. $\endgroup$ May 3, 2012 at 2:48
  • 1
    $\begingroup$ Unless I've misunderstood your setup, this is an extremely difficult problem for various cases of the first few outcomes. See the discussion here: math.stackexchange.com/questions/6195/… $\endgroup$
    – Alex R.
    May 3, 2012 at 2:50

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – joriki
    May 3, 2012 at 5:13
  • $\begingroup$ @joriki: Thanks, and thanks for emphasizing that point; I probably should have made it clearer that I was working only with the given strategy. $\endgroup$ May 3, 2012 at 5:16
  • $\begingroup$ 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. $\endgroup$
    – joriki
    May 3, 2012 at 5:36
  • $\begingroup$ This is awesome. Thanks! $\endgroup$
    – Matt
    May 3, 2012 at 5:51
  • $\begingroup$ Isn't this identical to "the country where people keep on having kids until they get a boy" questions or the gambler's ruin? Should the answer not be 0.5? $\endgroup$ Jun 23, 2020 at 7:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .