Maximum value on a set of die rolls --- how to prove that this is a Markov chain?

Question

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$)?

Answer 1

Yes, this is a Markov chain. In general, in order to show that the process is a Markov chain, you will need to show that the transition probability depends on the "history" of the chain only through its most recent value. In the present case it is relatively simple to derive the exact form for the transition probabilities, so this can be done directly.

Your question does not specify how many sides your die has, so I am going to proceed for the general case where we have a fair die with $k \in \mathbb{N}$ sides. Outcome of the rolls are represented by the sequence $X_1,X_2,X_3,... \sim \text{IID U} \{ 1,...,k \}$ and $Z_n \equiv \max (X_1,...,X_n)$ is the maximum outcome in the first $n$ rolls. We can write the latter quantity in its recursive form as $Z_{n+1} = \max (Z_n, X_{n+1})$, which gives the inverse-relationship:

$$\begin{matrix} X_{n+1} \leqslant Z_n \quad & & & \text{if } Z_{n+1} = Z_n, \\[6pt] X_{n+1} = Z_{n+1} & & & \text{if } Z_{n+1} > Z_n. \\[6pt] \end{matrix}$$

Using the independence of the underlying sequence of uniform values, it is simple to establish that $X_{n+1} \ \bot \ (Z_1,...,Z_n)$, so for all $z=1,...,k$ we have the following transition probabilities:

$$\begin{align} T_{n+1}(z|\mathbf{z}_n) &\equiv \mathbb{P}(Z_{n+1}=z| Z_1 = z_1,...,Z_n = z_n) \\[14pt] &= \begin{cases} 0 & & & \text{if } z < z_n \\[10pt] \mathbb{P}(X_{n+1} \leqslant z| Z_1 = z_1,...,Z_n = z_n) & & & \text{if } z = z_n \\[10pt] \mathbb{P}(X_{n+1} = z| Z_1 = z_1,...,Z_n = z_n) & & & \text{if } z > z_n \\[10pt] \end{cases} \\[14pt] &= \begin{cases} 0 & & & \text{if } z < z_n \\[10pt] \mathbb{P}(X_{n+1} \leqslant z) & & & \text{if } z = z_n \\[10pt] \mathbb{P}(X_{n+1} = z) & & & \text{if } z > z_n \\[10pt] \end{cases} \\[14pt] &= \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] &= \frac{1}{k} \cdot \mathbb{I}(z > z_n) + \frac{z}{k} \cdot \mathbb{I}(z = z_n). \\[6pt] \end{align}$$

Since this transition probability depends on the history $\mathbf{z}_n$ only through the value $z_n$, you have a Markov chain.

Answer 2

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

1. prove that it holds for $n=0$

and

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