7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ What is side index of a "threw"? dice? Can you include an example? More concretely, suppose that the top face shows a $3$. What is the side index? The four numbers showing on the four other sides visible? (On a standard die with $3$ on top, the bottom face is a $4 = 7-3$.....) $\endgroup$ Oct 3, 2021 at 22:52
  • 1
    $\begingroup$ In order to prove $P(Z_{n+1}|Z_n) = P(Z_{n+1}|Z_1, \dots, Z_n)$, start by thinking about the relationship between $Z_n$ and $\max (Z_1, \dots, Z_n)$. $\endgroup$
    – jbowman
    Oct 3, 2021 at 22:55
  • $\begingroup$ @DilipSarwate I made it more clear. $\endgroup$ Oct 3, 2021 at 22:59
  • $\begingroup$ You need to prove the whole thing, but doing so is trivial if you can prove it for the base case and then for $n+1$. Induction takes you the rest of the way. $\endgroup$ Oct 4, 2021 at 11:14

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Sorry but Should transition probability not take as $T_{n+1}(z|\mathbf{z}_n)$ rather than $T_{n+1}(z|\mathbf{x}_n)$? $\endgroup$ Oct 3, 2021 at 23:52
  • 1
    $\begingroup$ @DaviAmerico: Well spotted --- edited. $\endgroup$
    – Ben
    Oct 4, 2021 at 0:00
  • 1
    $\begingroup$ If you look at the explicit formulas for the probabilities, you can see that there are no values $z_1...z_{n-1}$ used anywhere, only $z_n$. $\endgroup$ Oct 4, 2021 at 11:26
  • $\begingroup$ Yeah I know but I didn't mean that, I dont know how to put what my doubt is but I'm trying. You have used these two events : $X_{n+1}\leq Z_n$ and $X_{n+1}=Z_{n+1}$ to get the distribution of $Z_{n+1}$ (so far everithing is pretty ok) but these two events give you the distribution of $Z_{n+1}|Z_1,...,Z_n$ not $Z_{n+1}$ I didn't get the why of it. $\endgroup$ Oct 4, 2021 at 21:46
  • $\begingroup$ I have updated the answer to show this aspect more explicitly. $\endgroup$
    – Ben
    Oct 4, 2021 at 22:39
3
$\begingroup$

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

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

$\endgroup$
1
  • $\begingroup$ I'm getting a probability as $(k-z)/k$ in event ($z>z_n$) since we'll $k-z$ choices for $z>z_n$ $\endgroup$ Oct 4, 2021 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.