The expectation of a Dice game Let's assume there is a $n$ faces fair dice with face value as $1, 2,...,n-1, n$. Player return would be the value of throwing result, i.e. if player throw once and the result face is $m$, then player will get $m$ as return. If don't like the result of throw, player can give up the return of that throw and throw $1$ more time. Player will only choose re-throw when expect return would be greater than current result. Let's assume player could do such re-throw for up to $k$ times. Then what is player's expect return of this game?
I have been trying to do the backward induction but had hard time to come up with a generalized solution.
The expect return of $k^{th}$ throw is $\frac{(1+2+...+n-1+n)}{n}=\frac{(n+1)}{2}$. Player would only re-throw at $(k-1)^{th}$ if result $<\frac{n+1}{2}$. Then expect return at $({k-1})^{th}=\frac{(n+1)}{2}\frac{1}{n}(\frac{n+1}{2}-1+1)+\frac{(\frac{(n+1)}{2}+...+n)}{n}$
. Then use the same logic to calculate $(k-2)^{th}$ ...
So if the expect return at $t^{th}$ throw is $E_t$, then $E_{t-1}=\frac{E_t*\lfloor{E_t}\rfloor}{n}+\frac{(\lceil{E_t}\rceil+n)(n-\lceil{E_t}\rceil+1)}{2n}$
Does anybody have an idea?
 A: Let $X_1,X_2,\dots$ be the face values for the individual throws, and let $Y_1,Y_2,\dots$ be the current returns after the throws.
Let $\overline x=E[X_1]=E[X_i]=\frac{1}{n}\binom{n+1}{2}=\frac{n+1}{2}$ be the expected face value, which is the expected return of a single throw.
Let's first consider fixed $k$ to get a feeling for what's going on.
For $k=0$, we can only throw once, so we have $Y_1=X_1$ and $E[Y_1]=\overline x$.
For $k=1$, the player rethrows if the expected return of the second throw is greater than the current return, i.e. if $\overline x=E[X_2]>Y_1$. So, the distribution of $Y_2$ is $P(Y_2=y)=P(Y_1=y)+P(Y_1<\overline x)P(X_2=y)=(1+P(X_1<\overline x))\frac{1}{n}$ for $y\ge\overline x$, obtained by not rethrowing or rethrowing, and $P(Y_2=y)=P(Y_1<\overline x)P(X_2=y)=P(X_1<\overline x)\frac{1}{n}$.
In particular, this gives $P(Y_2<\overline x)=P(X_1<\overline x)^2$ and, using the largest integer $x=\lceil\overline x\rceil-1=\max\mathbb Z_{<\overline x}$ below $\overline x$ ($\lceil a\rceil$ is $a$ rounded up) and $P(X_1\le x)=\frac{x}{n}$ further
\begin{align*}
E[Y_2]&=\sum_{y=1}^{x}\frac{1}{n}P(X_1\le x)y+\sum_{y=x+1}^n\frac{1}{n}(1+P(X_1\le x))y\\
&=\frac{x}{n^2}\binom{x+1}{2}+\left(\binom{n+1}{2}-\binom{x+1}{2}\right)\left(\frac{1}{n}+\frac{x}{n^2}\right).
\end{align*}
For $k=2$, we get $P(Y_3=y)=P(Y_2=y)+P(Y_2<y)P(X_3=y)=(1+P(X_1<\overline x)+P(X_1<\overline x)^2)\frac{1}{n}$ for $y\ge\overline x$, and $P(Y_3=y)=P(Y_2<\overline x)P(X_3=y)=P(X_1<\overline x)^2\frac{1}{n}$, so
$P(Y_3<\overline x)=P(X_1<\overline x)^3$.
So, for any $k$ rethrows we have $k+1$ throws and $P(Y_{k+1}=y)=\frac{1}{n}\sum_{i=0}^kP(X_1<\overline x)^i$ for $y\ge\overline x$, and $P(Y_{k+1}=y)=P(X_1<\overline x)^k\frac{1}{n}$ for $y<\overline x$.
As a sanity check, notice that
$$P(Y_{k+1}\ge\overline x)=P(X_1\ge\overline x)\sum_{i=0}^kP(X_1<\overline x)^i=(1-P(X_1<\overline x))\sum_{i=0}^kP(X_1<\overline x)^i=1-P(X_1<\overline x)^{k+1}$$
and that $P(Y_{k+1}<\overline x)=P(X_1<\overline x)^{k+1}$, so $P(Y_{k+1}<\overline x)+P(Y_{k+1}\ge\overline x)=1$ and this is, maybe surprisingly, indeed a probability distribution. So, now we cn write down the expectation
$$E[Y_{k+1}]=\sum_{y=1}^nP(Y_{k+1}=y)y=\sum_{y=1}^{x}\frac{1}{n}P(X_1\le x)^ky+\sum_{y=x+1}^n\frac{1}{n}\frac{1-P(X_1\le x)^{k+1}}{1-P(X_1\le x)}y,$$
where we used the geometric series $\sum_{i=0}^ka^i=\frac{1-a^{k+1}}{1-a}$. Computing the sums and using $P(X_1\le x)=\frac{x}{n}$ gives
\begin{align*}
E[Y_{k+1}]&=\frac{x^k}{n^{k+1}}\binom{x+1}{2}+\frac{1}{n^{k+1}}\frac{n^{k+1}-x^{k+1}}{n-x}\left(\binom{n+1}{2}-\binom{x+1}{2}\right).
\end{align*}
