What is the value of this other coin flipping game?

This is variation of this question: What is the value of this coin flipping game?

Imagine that you can play the game in a casino - you are flipping a fair coin. If you get tails, the game continues and the money you can win is doubled. If you get heads, the game ends.

Money you can win at the start: $\$1$The casino has$\$1,000,000$ to pay you.

You can play this game only $1000$ times.

Examples:

1. If you get heads in the first round, you get $\$1$and the game ends. 2. If you get tails twice and then heads, you get$\$4$ ($1\times 2 \times 2$) and the game ends.

Question:

How much you would pay for this game?

• This seems you always win game to me, because if you play 1 dollars, even u get head or toss, you get 1D back? u dont lose? if you play with 2 dollars you get still 1 dollars back instead of 2 dollars? – Oray Feb 15 '16 at 11:34
• Not if the question is 'how much would you pay'. You're assuming a dollar is used as 'cost' to play a game, but the one dollar is your starting capital. Ironically, the casino would need a cost of over one dollar (to avoid the guaranteed 'draw or win' for the player), but then the 'one dollar starting money' doesn't make any sense. – Tim Couwelier Feb 15 '16 at 12:05
• @TimCouwelier I made an edit to make it more clear. Feel free to edit my question if you know a better formulation. – matousc Feb 15 '16 at 12:18
• I misunderstand the question then, 1000 times means if you get head, you can play again like 1000 times I guess? – Oray Feb 15 '16 at 12:44
• the tricky part for me is the restriction to 1E6 win in total. which basically hindered me to do this analytically. If it was one million per game things would be very easy – Bort Feb 15 '16 at 13:30

Let $J_n$ be the random variable whose value is the payout of the $n$-th game. For $n=1$, we can easily calculate the expectation.

$$\begin{split} \mathbb{E}(J_1)&= \left(\sum_{1 \leq i \leq 20} \hphantom{.}\underbrace{\hphantom{..}2^{-i}\hphantom{..}}_{\mathbb{P}(J_1 = 2^{i-1})}\cdot 2^{i-1}\right) &+\sum_{i>20}2^{-i}\cdot 10^6\\ &=\hphantom{...........}10&+2^{-20}\cdot 10^6 \end{split}$$

Notice that if we get $21$ or more tails, we receive $10^6$ because $2^{i-1}>10^6$ for all $i\geq 21$. Also, the first summation limit is $20 = \lceil \log_2\left(10^6\right)\rceil$.

Now, precisely because of the total payout limit of $10^6$, the result of $J_{n+1}$ depends on the results of all $J_k$ with $1 \leq k \leq n$. How, then, do we calculate the expectation of $J_{n+1}$'s? For that, we use the fundamental result that $\mathbb{E}(X) = \mathbb{E}(\mathbb{E}(X|Y))$. Thus, for instance:

$$\begin{split} \mathbb{E}(J_2)&=\mathbb{E}(\mathbb{E}(J_2|J_1))\\ &=\left(\sum_{1\leq n \leq 20}\mathbb{E}\left(J_2|J_1=2^{n-1}\right)\cdot\mathbb{P}\left(J_1=2^{n-1}\right)\right)+\underbrace{\mathbb{E}\left(J_2|J_1=10^6\right)}_0\cdot \mathbb{P}\left(J_1=10^6\right)\\ &=\sum_{1\leq n\leq20}2^{-n} \cdot \mathbb{E}\left(J_2|J_1=2^{n-1}\right) \end{split}$$

We first calculate $\mathbb{E}\left(J_2|J_1=2^{n-1}\right)$. We can write it as:

$$\begin{split} &\left( \sum_{\displaystyle 1\leq m \leq \lceil \log_2\left(10^6 -2^{n-1}\right)\rceil } 2^{-m} \cdot 2^{m-1} \right) \\ + &\vphantom{.^{^{^{^{^{^{.}}}}}}}\hphantom{...}\sum_{\displaystyle m > \lceil \log_2 \left( 10^6 - 2^{n-1} \right) \rceil} 2^{-m} \cdot \left(10^6-2^{n-1} \right) \\ =&\hphantom{..}\frac12\cdot \lceil \log_2\left(10^6 -2^{n-1}\right)\rceil+2^{^{\displaystyle -\lceil \log_2\left(10^6 -2^{n-1}\right)\rceil \vphantom{^{^{^{^{^{.}}}}}}}}\cdot \left(10^6-2^{n-1}\right) \end{split}$$

It follows that: $$\begin{split} \mathbb{E}(J_2)&=\sum_{1\leq n \leq 20}2^{-n}\left(\frac12\cdot \lceil \log_2\left(10^6 -2^{n-1}\right)\rceil+2^{-\lceil \log_2\left(10^6 -2^{n-1}\right)\rceil }\cdot \left(10^6-2^{n-1}\right) \right)\\ &=\frac{11485739}{1048576}\vphantom{h^{h^{h^{h^{h^{h^{h^{h}}}}}}}} \end{split}$$

We can repeat the process for the next $J_k$, and obtain that:

$$\begin{split} \mathbb{E}(J_3)=\sum_{\displaystyle 1 \leq i_2 \leq \lceil \log_2\left(10^6 \right) \rceil} 2^{-i_2} \cdot \left( \sum_{\displaystyle 1 \leq i_3 \leq \lceil \log_2\left(10^6 - 2^{i_2 - 1} \right) \rceil} 2^{-i_3} \cdot e(i_2,i_3) \right) \end{split}$$

where $e(i_2,i_3)$ is

$$\begin{split} &\frac12 \cdot \lceil \log_2\left(10^6 - 2^{i_2 - 1} -2^{i_3-1}\right) \rceil\\ +\hphantom{..}\vphantom{^{^{^{^{^{^{^{^{^{^{^{^{.}}}}}}}}}}}}} &2^{^{\displaystyle -\lceil \log_2\left(10^6 - 2^{i_2 - 1} -2^{i_3-1}\right) \rceil}}\cdot \left(10^6 - 2^{i_2 - 1} -2^{i_3-1}\right) \end{split}$$

from whence it follows that $\mathbb{E}(J_3)=\frac{24665391590542601}{2251799813685248}$.

Similarly,

$$\begin{split} \mathbb{E}(J_4)=\sum_{\displaystyle 1 \leq i_2 \leq \lceil \log_2\left(10^6 \right) \rceil} 2^{-i_2} \cdot \left( \sum_{\displaystyle 1 \leq i_3 \leq \lceil \log_2\left(10^6 - 2^{i_2 - 1} \right) \rceil} 2^{-i_3} \cdot \\ \left( \sum_{\displaystyle 1 \leq i_4 \leq \lceil \log_2\left(10^6 - 2^{i_2 - 1} - 2^{i_3 - 1} \right) \rceil} 2^{-i_4} \cdot e(i_2,i_3,i_4) \right) \right) \end{split}$$

where $e(i_2,i_3,i_4)$ is

$$\begin{split} &\frac12 \cdot \lceil \log_2\left(10^6 - 2^{i_2 - 1} -2^{i_3-1} - 2^{i_4-1}\right) \rceil\\ +\hphantom{..}\vphantom{^{^{^{^{^{^{^{^{^{^{^{^{.}}}}}}}}}}}}} &2^{^{\displaystyle -\lceil \log_2\left(10^6 - 2^{i_2 - 1} -2^{i_3-1} - 2^{i_4 - 1}\right) \rceil}}\cdot \left(10^6 - 2^{i_2 - 1} -2^{i_3-1} - 2^{i_4 - 1}\right) \end{split}$$

It follows that $\mathbb{E}(J_4) = \frac{808234073895490893065}{73786976294838206464}$.

I believe at this point the pattern should be clear on how to set up the recursion that yields $\mathbb{E}(J_{n+1})$ from previous $J_k$'s. That said, I'm not sure we're any wiser in doing so, and calculations become quickly quite troublesome. Here are the first few approximate values for $\mathbb{E}(J_{k})$:

• $\mathbb{E}(J_{1}) = 10.9536743164062$
• $\mathbb{E}(J_{2}) = 10.9536542892456$
• $\mathbb{E}(J_{3}) = 10.9536342620864$
• $\mathbb{E}(J_{4}) = 10.9536142349288$
• $\mathbb{E}(J_{5}) = 10.9535942077726$
• $\mathbb{E}(J_{6}) = 10.9535741806178$

Unsurprisingly, with each game the expected payout is very slightly smaller than that of the previous game (because the limit payout is reduced from our previous winnings). This also implies that the difference between them is shrinking:

• $\mathbb{E}(J_{1}) - \mathbb{E}(J_{2}) = 0.0000200271606$
• $\mathbb{E}(J_{2}) - \mathbb{E}(J_{3}) = 0.0000200271592$
• $\mathbb{E}(J_{3}) - \mathbb{E}(J_{4}) = 0.0000200271576$
• $\mathbb{E}(J_{4}) - \mathbb{E}(J_{5}) = 0.0000200271562$
• $\mathbb{E}(J_{5}) - \mathbb{E}(J_{6}) = 0.0000200271548$

So we could write

$$\mathbb{E}(J_k) = \mathbb{E}(J_1) - \left( \sum_{1 \leq i \leq k-1}\mathbb{E}(J_i) - \mathbb{E}(J_{i+1}) \right) > \mathbb{E}(J_1) - (k-1) \cdot \big( \mathbb{E}(J_1) - \mathbb{E}(J_2) \big)$$

We thus have the following rough estimate for all $k \geq 2$:

$$\mathbb{E}(J_1) - (k-1) \cdot \left( \mathbb{E}(J_1) - \mathbb{E}(J_2) \right) < \mathbb{E}(J_k) < \mathbb{E}(J_1)$$

Accordingly, for instance, $10.9336671829668 < \mathbb{E}(J_{1000}) < 10.9536743164062$. It is clear, I believe, that even over the course of the one thousand games, the effect is minuscule.

For the total expected payout $\mathbb{E}(\sum_{1 \leq k \leq 1000} J_k) = \sum_{1 \leq k \leq 1000} \mathbb{E}(J_k)$, we thus have the following estimates:

$$10943.6707496865 < \mathbb{E}\left(\sum J_k\right) < 10953.6743164062$$

Hence, $\mathbb{E}\left(\sum J_k\right) \simeq 10948.6725330464$, give or take $5$ dollars (an error of about $0.0457$%).

Therefore, if we're paying $10.94$ dollars or less per game, we should expect profit over the course of a thousand games. However, if we're paying $10.96$ or more per game, we should expect loss. For $10.95$ we're not quite sure, but since our upped bound is so lazy and yet 'barely' above $10950$, I'd hazard you're slightly in the loss here.

So yeah, up to $10.94$ dollars.

The expected value of this game goes to infinity as below;

$E(x)=0.5(1)+0.5(0.5\times 2+0.5(0.5\times 4+0.5(...))))$

In other words,

$E(x)=0.5(2^x)+0.5(E(x+1))$

or

$E(x)=\infty$

Since you can play 1000 times at most;

$E(x)=0.5x = 500$

if there were $2^{1000}$$but they have a million. so you can play the game getting tails all the time in a row 21 times at most. So you need to pay; \sum_{n=0}^{20} (0.5^x(2^x-y))=0 (for n=20, 2^n is assumed to be a million) y=10.48 \$$ • Correct me if I'm wrong - but are you calculating the end value of your 'coin stack', or, what the OP is asking for, 'how much would you pay to play a game'. It looks like you're doing the first, but then you answer is besides the point... – Tim Couwelier Feb 15 '16 at 12:02 • well, the expected value for this represents the value you are going to win in this game statistically. Because the value you are going to win increases exponentially after some rolls. In reality I would not play this game with 500 dollars but you have a chance to win 2^1000 if you can roll 1000 times tails. – Oray Feb 15 '16 at 12:15 Oray's answer is close but there are some inconsistencies. It starts out by saying the expected value of the game is infinity (which it clearly is not) but then calculates an expected value that is finite (which is close to correct but not quite). The payout is as follows for the sequence of tails(T)/heads(H): • H; pay = 1; p = 1/2 • TH; pay = 2; p = 1/4 • TTH; pay = 4; p = 1/8 • TTTH; pay = 8; p = 1/16 • etc • TT(19 tails)H; pay = 2^19; p = 2^(-20) • TTT(20 tails); pay = 10^6; p = 2^(-20) Note that the probability of the last (20 tails or more) is 2^(-20) and not 2^(-21). So the expected value is the sum of the payouts times the corresponding probabilities Sum[2^k * 2^-(k+1),{k,0,19}] + 10^6 * 2^(-20) and gives approximately E[x] =$10.95 This is the expected amount you would win over a large number of plays. How much you would be willing to pay to play, however, has a subjective component that is different for everyone. I would want to make a profit so I certainly wouldn't pay more than 10 dollars!