What is the value of this other coin flipping game?

Question

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?

Answer 1

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{equation}\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}\end{equation}

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{equation}\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}\end{equation}

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

\begin{equation}\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}\end{equation}

It follows that: \begin{equation}\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}\end{equation}

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

\begin{equation}\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}\end{equation}

where $e(i_2,i_3)$ is

\begin{equation}\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}\end{equation}

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

Similarly,

\begin{equation}\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}\end{equation}

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

\begin{equation}\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}\end{equation}

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.

Answer 2

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

Answer 3

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!