An apparently easy game of chance

Question

The game begins with $n$ coins.

• Every round we pay 1 dollar, toss all the $n$ coins, and remove the $T$ coins which landed in Tail.
• Then we start over with the remainder $n-T$ coins until there are no more coins.
• You receive a prize $P$ when the Game ends (All coins landed Tails in any of the throws)

The excercise is to find the fair price of the final prize $P$ given $n$ (price in which in long term both players do not lose or earn any money from playing)

For n = 1 I thought on:

Coin toss	Probability	Total paid
T	$1/2$	1
HT	$1/4$	2
HHT	$1/8$	3
HHHT	$1/16$	4
HHHHT	$1/32$	5
HHHHHT	$1/64$	6
...	...	...

With $P(n=1) = \sum_{n=1}^{\infty}(\frac{n}{2^n}) = 2$

So the Fair Prize of this game for $n=1$ is 2 dollars.

How can it be calculated for a higher amount of initial coins? lets say $n=2$ or $n=16$.

My thoughts until now are, for 2 coins, in the first toss:

Coin results	probability	thoughts
(HH)	1/4	which I don't know how to proceed, because is recurrent, as with the 1 coin example
(HT)	1/4	the price of one coin
(TH)	1/4	same, price of one coin
(TT)	1/4	we finish the game, so you receive the prize.

Any thoughts?

Clues on how to push this to higher dimensions?

Answer 1

Let $X$ be the amount of rounds at the end of the game.

Then $$P(X\le x) = \left(1- a^x\right)^n$$

for $a=\frac12$ (this is the same approach as @lulu's comment). Hence

$$P(X>x)= 1-P(X\le x) = \sum_{j=1}^{n} (-1)^{j+1} \binom{n}{j} a^{xj}$$

We are interested in $E[X]$, which is

$$\begin{align} E[X] &= \sum_{x=0}^\infty P(X>x)\\ &= \sum_{j=1}^{n} (-1)^{j+1} \binom{n}{j}\sum_{x=0}^\infty a^{xj} \\ &= \sum_{j=1}^{n} (-1)^{j+1} \binom{n}{j} \frac{1}{1-a^j} \\ \end{align} $$

I'm not sure if this can be further simplified.

PS: It seems not https://oeis.org/A158466 From the papers quoted there one can get some asymptotics.

A semiempirical approximation $E[X]\approx \log_2(n) +1.336 + {0.664}\frac{1}{n}$, quite precise for the full range $1\le n \le \infty$