What is the expected value of this coin flipping game?

Question

A casino offers the following game:

You flip a fair coin repeatedly and record the results on slips of paper, one result per slip. At any time you may decide to stop, at which time one of the slips is chosen uniformly at random. You win \$1 if the chosen slip says "Heads".

How much should you be willing to pay to play this game, and what is your strategy?

---

I heard this puzzle several years ago, I do not know the solution.

Answer 1

I would like to throw another possible answer into the mix.

My strategy would be to say stop whenever heads is in the majority.

I cannot prove that this is optimal, nor can I figure out exactly what this converges to. However, I think it's like this.

1. You will only call it on odd turns (say after $i$ turns)
2. If you're going down the binomial tree, there will be some number of the nodes in the $i$th row where there are $(i+1)/2$ heads (these will be where you'll say "stop").
3. The expected value of these will be $n\cdot 2^{-i}\cdot\frac{(i+1)/2}{i}$, where $i$ is the row number, and $n$ is the number of nodes with the correct value.
4. Then (I think) that $n=(2n)!/(n!(n+1)!)$ (I brute forced the first few and searched on OEIS)

With further brute forcing this converged as follows: \begin{eqnarray} 1 && 0.5 \\ 3 && 0.5833333333333334\\ 5 && 0.6208333333333333\\ 7 && 0.643154761904762\\ 9 && 0.6583457341269842\\ 11 && 0.6695318136724387\\ 13 && 0.6782081958839772\\ 15 && 0.6851906177589772\\ 17 && 0.690966518207047\\ 19 && 0.6958473229716441\\ 21 && 0.7000424908764525\\ 23 && 0.703698753813252\\ 25 && 0.7069223589691968\\ 27 && 0.7097923778046177\\ 29 && 0.7123690326457777\\ \end{eqnarray}

So the solution is bigger than this, at least (there's some value to most of the other nodes, so even if you called it here, you could get something more).

If someone good at sequences could figure out this sum: \begin{equation}\sum_{n=0}^{\infty}\frac{(2n)!}{n!(n+1)!}\cdot\frac{n+1}{2n+1}\cdot\frac{1}{2^{2n+1}}\end{equation} you'd have the answer to what this strategy would give you. Someone else may be able to find a better strategy of course.

Taking the sum to 200 gives (approximately) 0.7654966208975894

Answer 2

The number of heads will equal the number of tails infinitely many times, so at any point, you can give up trying to be clever and just wait until the proportion is 1/2, then take that.

Let's first suppose that the player is impatient, meaning that for a particular number $N$, they will give up after $N$ turns, either claiming the current ratio if it is at least 1/2 or waiting for it to reach 1/2 if not. Let $f_N(h,t)$ most amount of money such an impatient player could expect to win, if they already have gotten $h$ heads and $t$ tails. Using the boundary conditions $f_N(h,N-h)=\max(\frac{h}N,\frac12)$ and the recursive formula $$ f_N(h,t)=\max\left(\tfrac12 f_N(h+1,t)+\tfrac12 f_N(h,t+1),\tfrac{h}{h+t}\right) $$ we can use a computer to compute $f_N(0,0)$, which is the initial value of the game.

People have done exactly this, and found that for large values of $N$, $f_N(0,0)\approx0.79$. This means there are definitely strategies which win slightly more that $79$ cents on average, though no one is sure if any more can be attained.

Answer 3

You can get at least a 50% chance of success very easily, always stop after the first flip. You can do a bit better by only stopping if you get "Heads" and continuing for a while if you get tails. It seems reasonable to me that you could get a 75% win ratio by saying "if I get tails, keep flipping until the heads and tails even out", which by the law of large numbers should eventually happen.

But there isn't anything really special about for 50% if you're willing to keep flipping forever. If you waited until by a fluke of probability there was eventually a 60% ratio, you could do better. By waiting an extremely large amount of time, you could get the ratio as large as you wanted, since (even though the probability would continually drop) there is no penalty for playing for an excessively long time. So, you can get arbitrarily close to 100%, although you will never reach it unless you got lucky on the first flip.

So, any cost between \$0 and \$0.99 will favor the better, while a cost of $1 will barely favor the house.

Answer 4

I'm sure someone will come up with a better answer, but as a simple benchmark:

Given that your coin is fair (equal chance of heads and tails), and that time has no value in this problem, I would follow the strategy of ending as soon as you get your first heads.

If your first toss is heads ($\frac{1}{2}$ chance), then you win \$1 with a perfect probability. If you throw a tails then heads, ($\frac{1}{4}$ chance), then you have a $\frac{1}{2}$ chance of winning \$1.

We can use this set up to find the expected winnings each time as:
$\sum_{n=1}^\infty \frac{1}{n}*\frac{1}{2^n}$ or $\sum_{n=1}^\infty \frac{1}{n2^n}$. This holds true because the chance of winning after $n$ flips following this strategy is $\frac{1}{n}$ and the chance of getting a heads on the $n^{th}$ flip is $\frac{1}{2^n}$.

Eventually, we get that we expect to win \$.69 (really $ln(2)$ or $0.6931472$), so paying \$.69 or less should lead to a profit as we play enough games.

Answer 5

You should not pay more than $0.50 to play this game. Here is why.

Each flip brings the odds of your slip draw closer to 50:50 odds. Yes you may hit heads on your first flip at which point, you take the casino for their dollar. This will only happen 50% of the time. The other 50% of the time you will get a tails which forces you to keep on flipping to try for a better chance than 0% on your paper slip drawing.

Say at some point you get 4 heads and 3 tails. That is a ~ 57% chance of winning that dollar (i.e. 4 heads / 7 slips). The longer you go the closer you get to 50:50 odds. Paying any more than $0.50 may win you money in the early stages, but only 50% of the time. The other 50% of the time you keep flipping to play catchup with the tails you have accumulated bringing you ever closer to the 50:50 odds you get from just flipping the coin in the first place :D

Reponse To Comments:

Someone asked if you can get above 50% by continuing to flip. You will most definitely get more heads, and for a short time may even have greater than 50% odds, but your best odds happen with early flips. The trick to this puzzle is you have to realize that the times when you are above 50% win rate only happens 50% of the time you play this game with the casino.

Take for example that I flip heads on my first flip. I have a 50% chance of doing that and it will give me a 100% chance on my win rate during the dollar draw. My real odds end up being 50% for the flip time 100% for the draw or 0.5 * 1 = 0.5 or 50% because the other 50% of the time I will hit a tails and have a 0% chance of winning the draw and have to keep flipping or forfeit my bet.

You can't do better than 100% chance of winning, so the other 50% of the time you either lose your entire bet or you keep flipping to get an advantage of 50% or greater. The kicker is as you keep flipping, 50% of the time you will dig the hole deeper (i.e. get more tails). The more you flip, the closer the odds converge to 50:50 because you can't outpace the tails you have accumulated and even when you do get a streak of heads going, you are equally likely and definitely will hit an equal streak of tails whether it be this round of betting or some future round since the coin flip is 50:50.

So even though I may have more heads (at some point in time), the ratio of heads to tails will always converge on 50:50.

3 heads / 4 flips = 75%

6 heads / 10 flips = 60%

30 heads / 55 flips = 54.5%

....

1000 heads / 1900 flips = 52.6%

1000 heads is a lot of heads, but 1000 when compared to 900 tails is a smaller advantage than when you compare 6 heads out of 10 flips.

And I know someone out there is thinking, well I would just stop at the 75% and play (3/4), but remember that is just a rate at which you CAN win a dollar. The other 25% of the draw will lose your bet. Even worse, in a future round of betting you ABSOLUTELY WILL come across a game where you have 3 tails and 1 head giving you only a 25% to win the draw and 75% chance to lose. In this scenario, you can either play catch-up with the the tails, which can take you deeper into the tail territory or in the best case even you out to the 50% win rate or you can choose to submit to a win rate lower than 50% in which case you negate any winnings you had in previous rounds of betting.

In the long run you will never come out above a 50% win rate and should not pay more than $0.50 to play.

Answer 6

Well, let's work out the probability tree and see what pops up:

      1      0
    x    .5     0
  x    .66  .33     0
x    .75    .5  .25   0

If you get a heads, you just end the game and take your money.
If you have all tails, you keep on flipping.
At the first .5, you have an even chance of winning/losing if you stay.
Say you go on. The two 50% chances have offsetting chances, expected payout is still 50/50.
Say you go another layer. Expected winnings is still 50/50.

Now, say you go TTH. At that point, your chances are .33. If you go again, your cumulative chance actually goes up to .375.

So, it seems like flip until you have even heads/tails chance, or greater.

So, 50% H (1), 25% TH (.50), 6.25% TTHH (.50).
That looks like an infinite series where each term is 1/4 of the last, so the formula would be :
$.5 + .125 * \frac{1}{1-.25} = \frac{2}{3}$