I roll a fair die with $n>1$ sides until the most recent roll is smaller than the previous one. Let $E\_n$ be the expected number of rolls. Do we have $\lim\_{n\to\infty} E\_n < \infty$? If not, what about $\lim\_{n\to\infty} E\_n/n$ and $\lim\_{n\to\infty} E\_n/\log(n)$?



Throwing a fair die until most recent roll is smaller than previous one
By doing casework on the second to last roll $m$, one has $$E\_n = \sum\_{k=2}^\infty k p\_k^{(n)},$$ where $$p\_k^{(n)} = \sum\_{m=1}^n n^{-(k-1)}{m+k-3 \choose k-2}\frac{m-1}{n}.$$ Note, for any fixed $k$, $$\lim\_{n \to \infty} p\_k^{(n)} = \frac{k-1}{k!}.$$ Therefore, by an easy dominated convergence argument, one has $$\lim\_{n \to \infty} E\_n = \sum\_{k=2}^\infty k\frac{k-1}{k!} = e.$$


