Expected number of iterations while counter is less than a random number Imagine you have a die with sides numbered from m to n, where $m \le n$.
Lets say you follow this procedure:
Roll the die and take as many steps as shown on the die.
It seems obvious that the expected number of steps you would take is $\frac{m+n}2$
For a normal die, $m=1$ and $n=6$. Your expected number of steps is $\frac{1+6}2=\frac72=3.5$
Take a more complicated procedure:
Roll the die and if the number shown is greater than the number of steps you've taken, take another step and if its less than or equal, you stop.
Programming equivalent is  

What is the expected number of loops of 'for (int i=0; i< Random(m,n); ++i)'?

I've taken an attempt at coming up with a formula for this. Let me explain my logic while working through a small sample where $m=0$ and $n=2$:
The expected number of steps is the sum of (each of number of possible steps multiplied by their probability).


*

*The probability of taking $0$ steps is the probability of rolling a $0$ on your first roll, which is $\frac13$

*The probability of taking $1$ step is the probability of rolling a $1$ or $2$ on your first roll, which is $\frac23$, and also, as pointed out, also the probability of NOT rolling a $2$ on the next roll, which is $\frac23$. The total for this is $\frac23\cdot\frac23$

*The probability of taking $2$ steps is the probability of rolling a $1$ or $2$ on your first roll and rolling a $2$ on your second roll. This is $\frac23\cdot\frac13$  


Summing them together, you have $0\cdot\frac13+1\cdot\frac23\cdot\frac23+2\cdot\frac23\cdot\frac13=\frac89$
Here is the formula I've come up with working backwards from examples I've tried. Note, this formula now fails due to the change in my step #2 above:
$$\sum_{i=1}^ni\frac{\frac{n!}{(n-i)!}}{(n-m+1)^i}$$  
Is this correct? Is there a more clean formula? Does this problem have a name?
 A: For simplicity, let's assume that the faces on your die run from $\{0,\dots, n\}$.  the $m$ doesn't change much...it just means that you automatically get to take $m$ steps before the proper game starts.  Let $P(r)$ be the probability of throwing an $r$ and let $\phi_k$ be the probability that you get to take exactly $k$ steps.
In order to move exactly $0$ steps you need to throw a $0$ initially so $$\phi_0=P(0)=\frac 1{n+1}$$.
In order to move exactly $1$ step you need the first throw to be anything greater than a $0$ and you need the second roll to be $≤ 1$.  Thus $$\phi_1=P(>0)\times P(≤1)=\frac n{n+1} \times \frac 2{n+1}$$
In order to move exactly $k$ steps you need the first throw to be anything greater than a $0$ and you need the second roll to be $>1$ and so on  Thus $$\phi_k=P(>0)\times P(>1)\times \dots \times P(≤k)=\frac n{n+1} \times \frac {n-1}{n+1}\times \dots \times \frac {k+1}{n+1}$$
Combining all this (and trusting that there have been no errors) we see that the expected number of steps is $$E=\sum_{k=0}^n \frac {k(k+1)\,n!}{(n+1)^{k+1}(n-k)!}$$
I don't see any way to simplify this, though that doesn't mean there isn't a way.
