The following question is from a Jane Street interview.
You are given a 100-sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? (There is no limit on the number of rolls.)
P.S. I think the question assumes that we are rational.
Best Answer
Let $v$ denote the expected value of the game. If you roll some $x\in\{1,\ldots,100\}$, you have two options:
You choose one of these two options based on whichever provides you with a higher gain. Therefore, if you spun $x$, your payoff is $\max\{x,v-1\}$.
Now, the expected value of the game, $v$, is given as the expected value of these payoffs: \begin{align*} v=\frac{1}{100}\sum_{x=1}^{100}\max\{x,v-1\}\tag{$\star$}, \end{align*} since each $x$ has a probability of $1/100$ and given a roll of $x$, your payoff is exactly $\max\{x,v-1\}$. This equation is not straightforward to solve. The right-hand side sums up those $x$ values for which $x>v-1$, and for all such values of $x$ that $x\leq v-1$, you add $v-1$ to the sum. This pair of summations gives you $v$. The problem is that you don't know where to separate the two summations, since the threshold value based on $v-1$ is exactly what you need to compute. This threshold value can be guessed using a numerical computation, based on which one can confirm the value of $v$ rigorously. This turns out to be $v=87\frac{5}{14}$.
Incidentally, this solution also reveals that you should keep rolling the dice for a $1 fee as long as you roll 86 or less, and accept any amount 87 or more.
ADDED$\phantom{-}$In response to a comment, let me add further details on the computation. Solving for the equation ($\star$) is complicated by the possibility that the solution may not be an integer (indeed, ultimately it is not). As explained above, however, ($\star$) can be rewritten in the following way: \begin{align*} v=\frac{1}{100}\left[\sum_{x=1}^{\lfloor v\rfloor-1}(v-1)+\sum_{x=\lfloor v\rfloor}^{100}x\right],\tag{$\star\star$} \end{align*} where $\lfloor\cdot\rfloor$ is the floor function (rounding down to the nearest integer; for example: $\lfloor1\mathord.356\rfloor=1$; $\lfloor23\mathord.999\rfloor=23$; $\lfloor24\rfloor=24$). Now let’s pretend for a moment that $v$ is an integer, so that we can obtain the following equation: \begin{align*} v=\frac{1}{100}\left[\sum_{x=1}^{v-1}(v-1)+\sum_{x=v}^{100}x\right]. \end{align*} It is algebraically tedious yet conceptually not difficult to show that this is a quadratic equation with roots \begin{align*} v\in\left\{\frac{203\pm3\sqrt{89}}{2}\right\}. \end{align*} The larger root exceeds $100$, so we can disregard it, and the smaller root is approximately $87\mathord.349$. Of course, this is not a solution to ($\star\star$) (remember, we pretended that the solution was an integer, and the result of $87\mathord.349$ does not conform to that assumption), but this should give us a pretty good idea about the approximate value of $v$. In particular, this helps us formulate the conjecture that $\lfloor v\rfloor=87$. Upon substituting this conjectured value of $\lfloor v\rfloor$ back into ($\star\star$), we now have the exact solution $v=87\frac{5}{14}$, which also confirms that our heuristic conjecture that $\lfloor v\rfloor=87$ was correct.