Past exam of the probability course of the University of Oxford / 2014 / 1 / c

Write $S_{n+1}=S_n+X_{n+1}$. The new random variable $X_{n+1}$ is independent of the entire history generated by $X_1,\dots ,X_n$, hence of $(S_1,\dots ,S_n)$. This is a Markov chain obtained from independent innovations: conditional on the past, only the current sum enters the next state. Its time-homogeneous transition probabilities areEvery jump is a positive integer, and each row sums to one by the probability mass function from part (b).

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