# Explain motivation behind recurrence of $100$-sided dice problem

The following question is asked in another MSE post. For completeness, I restate the question below.

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.

I do not understand the solution provided by @Uwe Stroinski. In particular,

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.

I do not understand the rationale behind first term, that is, $$\frac{101-b}{100} \frac{\frac{1}{2} 100 \times 101 - \frac{1}{2} b (b-1)}{101-b}.$$ I understand that the second term is for re-rolling, that is why the expectation is reduced by $$1$$ with the probability of getting a reroll.

But I totally have no idea where the first term comes from.

• We can simplify the expression: $$\frac{b+(b+1) + ... + 100}{101-b} = \frac{(1/2)(100)(101)-(1/2)b(b-1)}{101-b} = \frac{b+100}{2}$$ which is $E[Roll|Roll\geq b]$. Jan 13, 2020 at 4:07
• @Michael Yes. We can simplify the expression till $\frac{b+100}{2}.$ But I do not know how to make sense of the non-simplify expression. Jan 13, 2020 at 4:08
• The first term is the probability of rolling at least $b$ times the expected payoff from the first roll that is $\ge b$. The second piece of that product is unnecessarily complicated, though, since that expected payoff is clearly $(100 + b)/2$ -- the roll is uniformly distributed between $100$ and $b$. Jan 13, 2020 at 4:09
• Oh, your question was about the non-simplified expression. The sum $b + (b+1) + (b+2) + \ldots + 99 + 100$ is equal to the sum $1 + 2 + \ldots + 99 + 100$ minus the sum $1 + 2 + \ldots + (b-2) + (b-1)$. Jan 13, 2020 at 4:10
• @mjqxxxx: I think that should be an answer rather than a comment. There's not much more to say. Jan 13, 2020 at 7:30

The first term is (the probability of rolling at least $$b$$) times (the expected payoff from the first roll that is $$\ge b$$). The expected payoff from a roll that is uniformly random from $$b$$ and $$100$$, inclusive, is clearly just $$(b+100)/2$$, and indeed the second piece of the product reduces to this expression. The way it's written, though, comes from a more elaborate calculation of the expected payoff: $$\frac{\sum_{i=b}^{100}i}{\sum_{i=b}^{100}1}=\frac{\sum_{i=1}^{100}i - \sum_{i=1}^{b-1}i}{\sum_{i=1}^{100}1 - \sum_{i=1}^{b-1}1}=\frac{\frac{1}{2}101\cdot 100-\frac{1}{2}b\cdot(b-1)}{100-(b-1)}.$$