Maximum value on a set of die rolls --- how to prove that this is a Markov chain? Suppose we have a sequence of rolls of a fair die.  Suppose we let $X_n$ be the $n$th outcome and let $Z_n=\max(X_1,...,X_n)$ be the maximum outcome in the first $n$ rolls.  For example, if I roll a die $n=2$ times and I get outcomes $X_1=5$ and $X_2=3$ then I have $Z_n=\max(5,3)=5$.
Is the process $Z^{*}=\{Z(n)|n \in \mathbb{N}\}$ a Markov Chain?

This is as far as I could go.  I know that $Z_{n+1}=\max(Z_n,X_{n+1})$ since $Z_n=\max(X_1,...,X_n)$, but I couldn't prove that:
$$P(Z_{n+1}|Z_n)=P(Z_{n+1}|Z_1,...,Z_n).$$
Do I really need to prove that to for it to be a Markov Chain?  Or is it enough to prove that there is some structure of dependence (by which I mean that $Z_{n+1}$ depends only from $Z_n$)?

To prove that $$P(Z_{n+1}|Z_n)=P(Z_{n+1}|Z_1,...,Z_n)$$ you can use induction. If you can

*

*prove that it holds for $n=0$
and


*assuming it is true for some $n$ and prove that it holds for $n+1$
induction shows that it holds for any $n$.
Since
\begin{align}
P(Z_{2}=z| Z_1 = z_1) = \begin{cases}
0 & & & \text{if } z < z_1 \\[10pt]
z/k & & & \text{if } z = z_1 \\[10pt]
1/k & & & \text{if } z > z_1 \\[10pt]
\end{cases}
\end{align}
and
\begin{align}
P(Z_{n+1}=z| Z_1 = z_1, ... ,Z_n = z_n) &= \begin{cases}
0 & & & \text{if } z < z_n \\[10pt]
z/k & & & \text{if } z = z_n \\[10pt]
1/k & & & \text{if } z > z_n \\[10pt]
\end{cases}\\[14pt]
&=P(Z_{n+1}=z| Z_n = z_n) \\
\end{align}
induction shows that $P(Z_{n+1}|Z_1,...,Z_n)=P(Z_{n+1}|Z_n)$.
