Interview problem: Chow-Robbins game

Problem:

(1) Let's play a game. You toss a fair coin repeatedly. You can stop whenever you want before reaching 100 times. The payoff is the proportion of heads once stopped or reaching 100 times. What is the expected payoff according to the best strategy?

(2) There are a random number of pencils and we two take turns to take the pencils. Each time you or me can take 1 or 2 pencils and whoever get the last one loses. Would you like to play first? 

(3) Dicing problem: 

(a) Toss a dice. You can get face value in dollars or you can choose to try again twice. What is the expected payoff according to the best strategy?

(b) If you can get the maximum face values of two tosses, compare this payoff with that in (a) without calculation.

(c) What if you can try again at most 50 times? Estimate the number to the 3 decimal.

(d) What if you can try again for infinite times but each toss will cost you 1 dollar. The first toss is free.    

Solution:

(1) This Chow-Robbins game. Let $V(n, h)$ be the expected payoff after we stopped after $n$ number of tosses with $h$ number of heads.  We have $V(100, h)=h/100$ for $0\leq h \leq 100$ and $$V(n, h)=\max\left(\frac{h}{n}, \frac{V(n+1, h+1)+V(n+1, h)}{2}\right)\,.$$ Finally return $V(0, 0)$.

What if the game is not forced to stop at $100$ times and we can toss as many times as we want? 

Clearly, we cannot play infinitely as the law of large numbers limits the payoff to 1/2. The expected payoff is around $0.793$ as shown in this paper.

(2) Let $p(n)$ be the first player's winning probability when there are $n$ pencils at the start. We have $p(1)=0$, $p(2)=1$ and \begin{equation}p(n)=\max\{1-p(n-1), 1-p(n-2)\}\,.\end{equation} By induction, we can prove that $p(n)=0$ if $n \% 3 == 1$, otherwise $p(n)=1$. Since $n$ is random, the first player winning probability is 2/3.

(3) The payoff in (b) is larger than that in (a) since there is no rollback in game (a). 

Let $f(n)$ be the expected payoff when we can toss at most $n$ times, $f(1)=(1+2+3+4+5+6)/6=3.5$. For $f(n+1)$, the strategy is to try again if the face value is less than $f(n)$, otherwise take the face value. So \begin{equation}f(n+1) = \frac{1}{6}\sum_{i=1}^6\max\left[i, f(n)\right]\,.\end{equation} For question (a), we simply calculate $f(2)=(3.5 + 3.5 + 3.5 + 4+5+6) / 6=4.25$.

For question (c), we continue to calculate $f(3)=4.67$, $f(4)=4.94$ and $f(5)=5.13>5$. Therefore, for $n\geq 5$, we have $f(n+1) =\frac{5}{6} f(n) + 1$, and thus $f(n)=\left[f(5)-6\right]\left(\frac{5}{6}\right)^{n-5}+6$. Finally, $f(50)\approx 5.999$.

(d) The payoff of the last trial is $3.5$. Since the first trial is free, we can toss at most 4 times. Let $f(n)$ be the expected profit before the $n$-th toss, $f(4)=3.5-3=0.5$, and \begin{equation} f(n)=\frac{1}{6}\sum_{i=1}^6 \max\left[i-(n-1), f(n+1)\right]\,.\end{equation} As a result, $f(3)=(0.5+0.5+1+2+3+4)/6=1.83$, $f(2)=(1.83 + 1.83 + 2+3+4+5)/6=2.94$, and finally $f(1)=(2.94+2.94+3+4+5+6)/6=3.98$.