How to find the expected number of steps to reach the end of a Markov chain where the probability of advancing depends on the distance from the end?

Question

So for some context, this is to figure out the expected number of rounds a game will take given the number of equally skilled players. The way it works is as follows: Let $N$ be the number of players. Initially everyone is 'in', though all players participate in each round regardless of whether or not they are 'in' or 'out'. After each round, the last-placing 'in' player is now 'out'. Additionally, if an 'out' player finishes first for the round, they become 'in' again. The game ends when exactly one player is 'in'.

This is my attempt at formulating the problem:

Let $E(n)$ be the expected number of rounds to complete the game given $n$ 'in' players at the start of the round. Since the first round can only eliminate a player, $E(N) = 1 + E(N-1)$. Trivially, $E(1)=0$.

For values of $n$ in between, there will be one fewer 'in' player if an 'in' player is first, or the same number if an 'out' player is first (since an 'in' player will now be 'out', and the 'out' player that finished first will become 'in' again). For $1<n<N$:

$$E(n) = \dfrac{n}{N}\left(1 + E(n-1)\right) + \dfrac{N-n}{n}\left(1+E(n)\right)$$

From here, I'm not really sure what to do next. Other examples I looked at seemed to mostly be for random walks (where it's possible to go forward or backwards in state), whereas here the number of 'in' players will never increase, only stay the same or decrease. Additionally, they also seemed to generally have a fixed probability at each state (i.e. go forwards or backwards with probability 1/2 regardless of position). Plus they were often solving an example with a specific $N$ value that was small enough to do by hand.

The closest I found was this one. Here they seem to get to the point of setting up a similar recurrence, but I'm still unsure how to solve it given an $N$ value.

Answer 1

When there are $n$ 'in' players, the probability for the number of 'in' players to decrease is $p_n=\frac nN$. The expected number of attempts until an experiment with success probability $p$ succeeds is $\frac1p$. Thus the expected number of rounds is

$$ \sum_{n=2}^N\frac1{p_n}=\sum_{n=2}^N\frac Nn=N\sum_{n=2}^N\frac1n=N(H_N-1)\;, $$

where $H_N$ is the $N$-th harmonic number.

Answer 2

Edit : As clarified by exchange to Jorikis answer, my answer below may accidentally answer the wrong question - where an in player gets out only if finishing last.

---

The situation of the state of $n$ among $N$ players being "in" is described by the set of integers in $[0,2^N-1]$ with $n$ binary digits equal to $1$. Let the significance of the bits encode position.

If so, we can enumerate the finish positions and read out winner and loser from first and last binary digit in this number.

As the span of $\Delta n$ always will lie in $\{-1,0,1\}$, we will get a tridiagonal matrix $\bf P$ containing transition probabilities where the last state or column will be set to all zeros to avoid counting the finishing state more than once.

The expected value will be the series

$$[0 \cdots 0 1]\sum_{k=1}^\infty k{\bf P}^k {\bf v_0} $$

where the starting state vector ${\bf v_0} = [1 0 \cdots 0]^T$

This is as closed form as I can manage to get it. If we investigate $\bf P$:s algebraic properties further with eigenspaces or canonical transformations maybe we can do better finding some more satisfying closed form expression.