X_n is a markov chain because the next maximum is determined by the next throw of the die...which is independent of any of the previous throws.

the best way to look at it is that the given the present, the future is independent of the past.

for the one step case, it's pretty easy to see that the transition probs are;

p_ii = i/6

p_ij = 0 for j < i

p_ij = 1/6 for j > i

hence p_ii(n) = (i/6)^n and p_ij(n) = 0 for j < i.

for j > i;

let A_j = {at least one j in the next n throws and no number greater than j is thrown}

lt B_j = {no number greater than j is thrown}

Then A_j = B_j \ B_j-1

so

P(A_j) = P(B_j) - P(B_j-1) = (j/6)^n - (j-1/6)^n

which is p_ij(n) for j > i.

rushed through the steps a bit there but hopefully that makes some sense...

raheel88