11
$\begingroup$

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.

$\endgroup$

4 Answers 4

21
$\begingroup$

Let $v$ denote the expected value of the game. If you roll some $x\in\{1,\ldots,100\}$, you have two options:

  • Keep the $x$ dollars.
  • Pay the \$$1$ continuation fee and spin the dice once again. The expected value of the next roll is $v$. Thus, the net expected value of this option turns out to be $v-1$ dollars.

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.

$\endgroup$
2
  • $\begingroup$ I like the way this is written, but you cannot solve anything with it apart from using a computer?, while with the other method on this post you can solve it by hand, right? $\endgroup$
    – JimSi
    May 30, 2018 at 9:48
  • $\begingroup$ @JimSi Good point, I added further details on how to tackle this problem without a computer. $\endgroup$
    – triple_sec
    May 30, 2018 at 18:15
8
$\begingroup$

The expected value $G$ of the game is $87\frac{5}{14}\approx 87.357....$. For a proof you can consider the following recurrence $$ G = \frac{101-b}{100} \frac{\frac{1}{2} 100 \times 101 - \frac{1}{2} b (b-1)}{101-b} + \frac{b-1}{100}(G-1) $$ with a fixed $b\in\{1,\ldots,100\}$ which is the value you want to roll at least to stop the game. Solving the recurrence for $G$ yields $$ G = \frac{b^2+b-10102}{2(b-101)} $$ and differentiation with respect to $b$ yields $$ \frac{d}{d b}G =\frac{1}{2}-\frac{100}{(b-101)^2} $$ with roots $$ b=101\pm 10\sqrt{2}. $$ Only the smaller root is in the desired intervall and yields a maximum. Plug $86=\lfloor b\rfloor$ and $87=\lceil b\rceil$ into $G$ and take the maximum to get the result.

$\endgroup$
3
  • $\begingroup$ +1 for the derivation. Note that $b$ is discrete and an integer, so $b = 101- 10\sqrt{2}$ is not valid, but instead we have $b=87$, giving us a slightly different value of $G$. $\endgroup$
    – Calvin Lin
    Aug 12, 2013 at 19:36
  • $\begingroup$ agreed. I edit the solution accordingly. $\endgroup$ Aug 13, 2013 at 5:10
  • $\begingroup$ Thanks heaps! It makes total sense. $\endgroup$
    – 90b56587
    Aug 14, 2013 at 1:08
2
$\begingroup$

All answers are correct, but maybe I can phrase it in a less complex manner. Say you in advance determine a value V, where if you roll V or some amount greater than V, you will stop the game. What is your expectation here? Given that you have rolled V or higher, you are uniformly likely to have rolled any value between V and 100. The expectation of this roll is 0.5*(V+100).

But how much did you pay to get to this point? On average, when an event occurs with probability p, where p is bounded between 0 and 1, then in expectation it takes 1/p independent trials to realize this event. The probability of rolling V or higher is (101-V)/100, so on average it will take 100/(101-v) rolls to achieve this outcome. Your expectation is gain - loss, which equals 0.5*(V+100) - 100/(101-V).

It is simple to see that by taking the derivative with respect to V and setting equal to zero, we can get the V that maximizes expectation. Assuming your opponent is perfectly rational, this is the only bid they will accept to play the game. As it turns out, we can solve the equation to get V equals approximately 87.

$\endgroup$
1
$\begingroup$

Here’s an approach like Uwe’s that avoids solving a recurrence and with some other things explained.

First note that there is no reason to change your strategy at any point. Dice have no memory, so the value of the “rest of the game” is the same as the value of the complete game. So the best strategy is to play until the result is at least $b$ for some fixed $b$.

For a single roll result $X$, the probability of $X\geq b$ is $\dfrac{100-b+1}{100}$, and (intuitively and actually) the expected length of the game is the reciprocal of that probability, or $\dfrac{100}{100-b+1}$ rolls. You paid \$1 per roll, so you paid a total of $\dfrac{100}{100-b+1}$ dollars. You won between \$$b$ and \$$100$, so the expected payout is the average of the integers from $b$ to $100$, or $50+\dfrac b2$, dollars. (The average of a sequence of consecutive integers is always the average of the smallest and largest ones.)

So the expected value of the game is $50+\dfrac b2-\dfrac{100}{100-b+1}$. This is sort of a tilted branch of a hyperbola, and it should be pretty clear without graphing that it has a unique maximum, so you can compute values one by one and zero in on the maximum of \$$86\frac5{14}$ when $b=87$.

$\endgroup$
2
  • $\begingroup$ Can you clarify why there's no reason to change your strategy? I don't follow your reasoning. $\endgroup$ Apr 25, 2023 at 18:42
  • $\begingroup$ Looking again, I (and others?) think I missed the fact that you don't pay for the first roll, so the expected value should be one dollar more, but the minimum will be at the same value of $b$. As far as your question goes, there is an implicit (perhaps wrong!) assumption that being "rational" means trying to maximize expected value. If you have other criteria, such as complete unwillingness to lose more than, say, \$5, then yes, you should change your plan if you have already lost $5. But the best strategy (for highest future winnings, ignoring money spent) can't depend on the previous rolls. $\endgroup$
    – Steve Kass
    Apr 26, 2023 at 18:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .