<s>[INST] Expected number of steps until game stops A game starts with some $N$ and a player chooses randomly an integer in range $\left[0,N-1\right]$:

*

*If the chosen number, let's denote it by $K$, is $0$ the game stops, otherwise we move to the next round, but shrink the range to $\left[0,K-1\right]$.

*What is the expected number of rounds the game will be played before it's $\mbox{stopped}~?$.

I have tried writing it as a Markov chain with the transition matrix of the form:
\begin{bmatrix}
 0 & \frac{1}{N} & \frac{1}{N} & ... & \frac{1}{N} \\
 0 & 0 & \frac{1}{N-1} & ... & \frac{1}{N-1} \\
 & & ... \\
 0 & 0 & 0 & ... & 1 \\
 0 & 0 & 0 &... & 1 \\
\end{bmatrix}
that gives for, say, $N=3$
\begin{align}
Q & = 
\begin{bmatrix}
 0 & \frac13 & \frac13 \\
 0 & 0 & \frac12 \\
 0 & 0 & 0
\end{bmatrix}, \quad N=(I-Q) = \begin{bmatrix}
 1 & \frac23 & \frac23 \\
 1 & 1 & \frac12 \\
 1 & 1 & 1
\end{bmatrix},
\\[3mm] N^{-1} & = \begin{bmatrix}
 3 & 0 & -2 \\
 -3 & 2 & 1 \\
 0 & -2 & 2
\end{bmatrix}
\end{align}
that would result in 1 expected step to reach 0, however it does not look right and computing same expectation manually gives
\begin{align*} 
E_3 &= \frac13 \cdot 1 + \frac13 (E_2 + 1) + \frac13 (E_1 + 1) \\
    &= 1 + \frac13\frac32 + \frac13 = \frac{11}{6}
\end{align*}
Could you please tell me what I am missing or if there is a better approach to solving this?
 [/INST] Your $N$ matrix should be
$$N = (I-Q) = 
\begin{bmatrix}
1 & -1/3 & -1/3 \\
0 & 1 & -1/2 \\
0 & 0 & 1
\end{bmatrix}.$$
Remember, $I$ is the identity matrix, not the all $1$s matrix. The inverse of this is
$$(I-Q)^{-1} =
\begin{bmatrix}
1 & 1/3 & 1/2 \\
0 & 1 & 1/2 \\
0 & 0 & 1
\end{bmatrix},$$
and the sum of the first row is $11/6$ as you found.
Another way to do this is to solve the recurrence relation for $E_N$.
$$E_N = \frac{1}{N}+\frac{1}{N}\sum_{i=1}^{N-1}(1+E_i) = 1+ \frac{1}{N}\sum_{i=1}^{N-1}E_i.$$
This can be solved by substituting $S_N = \sum_{i=1}^N E_i$, solving the recurrence relation for $S_N$, and then finally finding $E_N = S_N - S_{N-1}$. This leads to an answer of $E_N = 1 + \sum_{i=1}^N \frac{1}{i}$ if you go through all the work.
</s>