Expected Value of Game The game is as follows: Start with 1. If you are at $n$, add one with a probability $\frac{1}{n+1}$, otherwise subtract one. End the game if you hit 0.
What is the expected number of rounds that this game lasts? Through empirical data, I have calculated this value to be approximately $2e-1$, but am unsure as to how to prove this result.
 A: Here's a solution that uses basic Markov chain theory.
Let's make the state zero a reflecting boundary i.e, from zero you jump to one with probability one. This is now an irreducible Markov chain.
Direct calculation shows that $\pi_n={n+1\over 2 e\, n!}$ for $n\geq 0$ defines 
the unique invariant probability measure for the chain. Therefore, by general Markov chain
theory, the expected number of steps to return to zero starting at zero is 
$$\mathbb{E}_0(T_0)={1\over \pi_0}= 2e.$$
On the other hand, first step analysis gives 
$$\mathbb{E}_0(T_0)=1+\mathbb{E}_1(T_0),$$ so that 
$$\mathbb{E}_1(T_0)=2e-1.$$
A: (not a solution as yet)
Let $[n]$ denote the expected number of rounds it takes to end the game when we have a value of $n$.
By linearity of expectation, we have
$[0] = 0$
$[1] = 1 + \frac{1}{2} [2] + \frac{1}{2} [ 0] $
$[2] = 1 + \frac{1}{3} [ 3] + \frac{2}{3} [ 1]$
$\vdots $
$[n] = 1 + \frac{1}{n+1} [n+1] + \frac{n}{n+1} [n-1]$
Letting $[1] = \alpha$, we can calculate that
$\begin{array} {l|l}
[1] & \alpha\\ 
[2] & 2 \alpha - 2 \\
[3] & 4 \alpha - 9 \\
[4] & 10 \alpha - 34 \\
[5] & 34 \alpha - 139 \\
\vdots & \vdots
\end{array}$
Let $[n] = f_n \alpha - g_n $. Then, since $[n] \geq 0$, this tells us that $\alpha \geq \frac{g_n}{f_n}$.
Claim: $f_n, g_n$ grow very fast (to be quantified).
(I think we'd have to figure out the sequences.)
We have $f_{n+1} = (n+1) f_n - n f_{n-1}$ and $g_{n+1} = (n+1) g_n - n g_{n-1}+ (n+1)$.
$f_n$ is A003422, known as the left factorials, and given by $f_n = \sum_{i=1}^n i!$.
Claim: $\frac{g_n}{f_n}$ is an increasing sequence, that is bounded above.
(No idea why, but if we can solve the recurrence, that might follow.)
Claim: $\alpha = \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$.
We already have $ \alpha \geq \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$. If $\alpha > \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$, then we will have $[n+1] - [n] > 2 $ for large $n$, which doesn't make sense.
A: I set up an Excel sheet to relax an assumed distribution.  If $f(n)$ is the expected time starting at $n$, the recursion is $f(n)=1+\frac 1{n+1}(nf(n-1)+f(n+1))$.  It does seem to converge to $f(1)=2e-1$.  If we accept that, we can calculate higher ones, getting $$\begin {array}{r|l}\\  n&f(n)\\ \hline 0&0\\1&2e-1\\2&4e-4\\3&8e-13\\4&20e-44\\5&68e-173\\6&308e-824\\7&1748e-4737\\8&11828e-32136  \end{array}$$  These fit well with the relaxation.  $f(8)$ is within $10^{-6}$.  Neither $2,4,8,20,68$ nor $1,4,13,44,173$ is in OEIS.  But I don't know how to justify $f(1)$ either.  As $n$ gets large, I would expect the value to increase by $1$ for each step in $n$, as you step downward almost surely.  If one solved the recurrence and showed that it converges to $1$ that could get you there.
A: This is nowhere near a complete solution - I only do some numerical examples for small values here.

Let $k$ be the number of rounds that the game lasts, and let $P(k = m)$ be the probability that the game lasts $m$ rounds. The expected value $E(k)$ of how long the game lasts is 
$$E(k) = \displaystyle\sum\limits_{m=1}^{\infty} \left(m \cdot P(k=m)\right) = P(k=1) + 2 \cdot P(k=2) + 3 \cdot P(k=3) + \cdots$$
The probability that $k$ is any even number is $0$, because the parity of $n$ changes with every turn.
The probability that the game ends in the first round is $$P(k=1) = 1-\frac{1}{2}=\frac{1}{2}$$
For the game to end on the third round, we need a "win" (a step up) followed by two "losses" (steps down):
$$P(k=3) = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2}$$
For the game to end on the fifth round, we need WLWLL or WWLLL (where W denotes an increase by one and L denotes a decrease by one):
$$P(k=5) = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{3}{4} \cdot \frac{2}{3} \cdot \frac{1}{2}$$
On the seventh round, we'd need WWWLLLL, WWLWLLL, WWLLWLL, WLWWLLL, or WLWLWLL. Given the tediousness of this calculation, I'll stop here.

I'm not sure how to find a general formula for $P(k=m)$ for $m$ odd, let alone find $E(k)$. 
This is related to the Gambler's ruin problem and random walks.
