 Solution

Now $M_{n+1}=\max (M_n,X_{n+1})$. Again $X_{n+1}$ is independent of the whole previous history, so the recursion is a Markov chain obtained from independent innovations. To remain at $s$, the new observation must be at most $s$; to jump to $t>s$, it must equal $t$. Thus the transition probabilities areThe upper tail sums to $1/(s+1)$, complementing the holding probability $s/(s+1)$.