Expected Value of a die where you can reroll N times, and take the highest of our rerolls

Question

This is the generalization of the problem where you can reroll a die once, and take the highest of your two rolls.

Knowing 3.5 is the expected value of a die roll,

The computation for that is: $\frac 12 $ chance of getting higher than 3.5, of which there are 3 equally likely options(4,5,6), and a $\frac 12 $ chance of rolling lower, in case we logically choose to use our reroll. The expected value of our reroll, since it is independent of the first roll is simply 3.5. Thus we have $\frac 12 * \frac 13 * (4 + 5 + 6) + \frac 12(3.5) = 4.25 $.

After extending the above computation to more cases and some algebra, I find the Expected value of the Nth reroll to be the following recursive function:

$$E_1 = 3.5$$ $$ E_n = \frac{2*(\rfloor{E_{n-1})*E_{n-1}} - (\rfloor{E_{n-1}})^2 - (\rfloor{E_{n-1}}) + 42}{12}$$

What I need to find is $$\lim_{n\to\infty}E_n$$

How do I compute this?

Answer 1

The intuitive answer is that it is $6$. After $n$ rolls the chance you have rolled at least one $6$ is $1-\left(\frac 56\right)^n$. This converges to $1$, so you are "guaranteed" to have at least one $6$ and keep that.

Answer 2

As a function of $n$ rolls:

Let $p(k)$ denote the probability that your highest roll is
at least $~k~: k \in \{1,2,3,4,5,6\}.$

Then $~\displaystyle p(k) = 1 - \left(\frac{k-1}{6}\right)^n.$

Let $r(k)$ denote the probability that your highest roll is
exactly $~k~: k \in \{1,2,3,4,5,6\}.$

Then, $r(6) = p(6)$ and for $~k \in \{1, 2, 3, 4, 5\},$
$r(k) = p(k) - p(k+1).$

So, the expected value of your highest roll, based on $n$ rolls is

$$\sum_{k=1}^6 \left[k \times r(k)\right].$$

Edit
Just occurred to me:

The shortcut evaluation is to award $1$ point for each event of the highest roll being at least $k$.

Therefore, the alternate computation is

$$\sum_{k=1}^6 p(k).$$