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

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