TAOCP 1.2.10 Exercise 1
From (4) with $k=0$ and using $p_{n-1,-1}=0$ from (5), p_{n0}=\frac{1}{n}p_{n-1,-1}+\frac{n-1}{n}p_{n-1,0}=\frac{n-1}{n}p_{n-1,0}.
Section 1.2.10: Analysis of an Algorithm
Exercise 1. [10] Determine the value of $p_{n0}$ from Eqs. (4) and (5) and interpret this result from the standpoint of Algorithm M.
Verified: yes
Solve time: 40s
From (4) with $k=0$ and using $p_{n-1,-1}=0$ from (5),
$$ p_{n0}=\frac{1}{n}p_{n-1,-1}+\frac{n-1}{n}p_{n-1,0}=\frac{n-1}{n}p_{n-1,0}. $$
From (5), $p_{10}=1$. Iteration yields
$$ p_{n0}=\prod_{j=2}^{n}\frac{j-1}{j} =\frac{1}{n}. $$
The event $A=0$ occurs exactly when no new maximum is encountered in steps M2 through M5, which forces $X[1]=\max{X[1],\dots,X[n]}$. Under the uniform permutation model, this means $X[1]=n$, and there are $(n-1)!$ such permutations among $n!$ total, giving probability $1/n$.
Thus,
\boxed{p_{n0}=\frac{1}{n}}. $$∎