If $\displaystyle X_n$ is the maximum value obtained from the first n throws of a fair die, how would I show that X is a Markov chain, and calculate the transition probabilities $\displaystyle p_{ij}(n)$?
Thanks very much!
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