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.
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.$$
(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.
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.
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.
