Prove that something is a Markov chain

Question

Let $\xi_0, \xi_1, \xi_2, ...$be independent, identically distributed, integer valued random variables. Define $Y_n$ = max{$\xi_i: 0 \leq i \leq n$}. Show that $(Y_{n)n\geq0}$ is a Markov chain and find it's transition matrix.

First time user here.

I just got into Markov's chains and is continuously struggling with this type of question. I understand that we have to prove this using the Markov property by showing that $P(Y_{n+1} = \xi_{n+1} | Y_n = \xi_n, ..., Y_0=\xi_0) = P(Y_{n+1} = \xi_{n+1}|Y_n = \xi_n)$. My thought is to first show that $P(Y_{n+1} = \xi_{n+1} | Y_n = \xi_n, ..., Y_0=\xi_0) = P(Y_{n+1} = \xi_{n+1})$ by independence, but I don't now how to proceed from here on.

Also, will the transition matrix be $P_{ij} = {1/n}$?

Help is much appreciated.

Answer 1

The shortest approach might be to note that $$ Y_{n+1}=\max\{\xi_{n+1},Y_n\}, $$ in particular, $Y_{n+1}$ is $\sigma(\xi_{n+1},Y_n)$-measurable. Since $\xi_{n+1}$ is independent of $(Y_k)_{0\leqslant k\leqslant n}$, this shows that $(Y_n)_{n\geqslant0}$ is a Markov chain.

The transition probabilities are $$ P_{ij}=P(Y_{n+1}=j\mid Y_{n}=i)=P(\max\{\xi_0,i\}=j), $$ thus, $$ P_{ii}=P(\xi_0\leqslant i),\qquad P_{ij}=P(\xi_0=j)\ (j\gt i),\qquad P_{ij}=0\ (j\lt i). $$

Answer 2

You are correct in saying you want to prove the Markov property.

First, the $ \xi_i $ are random variables. So a statement like $ \mathbb{P}(Y_{n+1} = \xi_{n+1}) = \ ... $ does not quite make sense here if the $ \xi_i $ are to be random variables and not the values assumed by the random variables.

Here's a hint, replace the $ \xi_i $ in your formulation of the Markov property with lower case letters, to represent the integer values assumed by the random variables $ \xi_i $. E.g. something along the lines of $\mathbb{P}(Y_{n+1} = a_{n+1}) \ ... $ That might help you make sense of things a bit better, I hope.