100-sided die probability The question is as follows: 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 number of rolls.
The EV for a 100-sided die roll is 50.5, but the fact that you can pay a dollar for an extra roll complicates things. Not quite sure how to proceed.
 A: Hint:
If your value now is $X_t$, what is the marginal value of the roll?
If you roll $R \sim \mathcal{U}[1,100]$, then if $R > X_t+1$ you gained and if $R \leq X_t+1$, you either lost or became indifferent. So what is the marginal value?
A: If the expected value of this game is $a$, then at a die roll of $X$ you have the choice of either collecting $X$ or paying a dollar and restart, which gives you an expected value of $a-1$.
To maximize the expected value, you should take $X$ if $X> a-1$ and start over if $X\le a-1$ (it does not really matter what we do when $X=a-1$).
We obtain therefore
$$ a = \frac1{100}\left(\lfloor a-1\rfloor\cdot a+\sum_{k=\lfloor a-1\rfloor+1}^{100}k\right)
=\frac1{100}\left(\lfloor a-1\rfloor\cdot a+\frac{100\cdot101}{2}-\frac{\lfloor a-1\rfloor \cdot\lfloor a\rfloor}{2}\right).
$$
I find numerically (didn't do much code checking, but the results are somewhat plausible)
$$a\approx87.3571 $$
which seems to be exactly (and of course the true result must be rational)
$$a=87\frac{5}{14}.$$
But I'm sure you can do the justification after the fact, i.e. show that the strategy that consists in continuing until you roll at least $87$ gives you $87\frac{5}{14}$ as expected value.
For your convenience, here is the PARI one-liner:

solve(a=1,100,sum(k=1,100,max(a-1,k))/100-a)


If an extra roll costs two dollars instead of one, the result would be
$$a=82\frac12$$
instead, and with a cost of only $0.1$ dollars it would be
$$a=96\frac1{10}.$$
A: A different approach, more complicated, is this:
Suppose that we can play a game as many times as we wish, $G$ is the possible gain in each game and every time we play we pay a fixed amount $c$. Moreover, we can just retire the gain of the last played game. Further suppose that we set a threshold $T$ such that we stop playing if $G\geqslant T$, otherwise we play again.
Then the expected gain, for given $T$, is $\operatorname{E}[G_S]$ where $S$ is the time where the game stops, then we have that
$$
\operatorname{E}[G_S]=\int_{\mathbb{R} }\operatorname{E}[G_S|S=t]F_S(dt)=\sum_{k\geqslant 1}\operatorname{E}[G_S|S=k]\Pr [S=k]
$$
because playing countable number of games we assume a discrete time. Now observe that
$$
\operatorname{E}[G_S|S=k]=\operatorname{E}[G|G\geqslant T]-ck,\quad \Pr[S=k]=q^{k-1}p\\\text{ for }\quad  q:=1-p,\quad  p:=\Pr [G\geqslant T]
$$
Therefore
$$
\begin{align*}
\operatorname{E}[G_S]&=\sum_{k\geqslant 1}\operatorname{E}[G|S=k]\Pr [S=k]\\
&=p\sum_{k\geqslant 1}(\operatorname{E}[G|G\geqslant T]-ck)q^{k-1}\\
&=p\left(\frac{\operatorname{E}[G|G\geqslant T]}{1-q}-\frac{c}{(1-q)^2}\right)\\
&=\operatorname{E}[G|G\geqslant T]-\frac{c}{p}\\
&=\frac{\operatorname{E}[G \mathbf{1}_{\{G\geqslant T\}}]-c}{\Pr [G\geqslant T]}
\end{align*}
$$
What will be the optimal value for $T$ if $G\sim \operatorname{Unif}(\{1,\ldots ,n\})$? In this case we want to maximize
$$
\operatorname{E}[G_S]=\frac1{2}\cdot \frac{(n+1-2c)n-T^2+T}{n+1-T},\quad T\in\{1,\ldots ,n\}
$$
For $c=1$ and $n=100$ we get that $T=87$ maximizes the expected gain, giving $\operatorname{E}[G_S]\approx 86.3$.
