2

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain?

My attempt: Consider the case, $P(Y_{n+1}=3|Y_n=1)=\frac{1}{6}$ if the current maximum is bigger than 3, but $P(Y_{n+1}=3|Y_n=1)=0$ if the current maximum is 2.

<p>So we require the additional information of knowing the current maximum.</p>

But my tutor said we should explicitly come up with a concrete case where $Y_3$ depends on $Y_2$, $Y_1$ to violate the definition of Markov Chain.

How do I go about doing that?

Yellow Skies
  • 1,710

2 Answers2

2

I assume that $Y_1$ is defined to be just the value of the first throw. Let $X_i$ denote the outcome of the $i$'th throw. Then $$ P(Y_3 = 3| Y_2 = 2, Y_1 = 3) = P(X_3 = 4,5,6) = \frac{2}{6}, $$ since $X_1 = 3$ and $X_2 = 2$. So to get the second highest number to be a 3, we need to throw a number higher than a three. However $$ P(Y_3 = 3| Y_2 = 2, Y_1 = 4) = P(X_3 = 3) = \frac{1}{6}, $$ since $X_1 = 4$ and $X_2 = 2$. So to get the second highest number to be a 3, we need to throw exactly that three.

So $Y_3$ is dependent on $Y_1$ and thus $\{Y_n\}$ is not a Markov chain.

Marc
  • 6,861
1

First, with your definition, $Y_1$ is not defined. I will answer starting the chain at $Y_2$

If your "roll" is a heads or tail, calculate $P(Y_{n+1}=0|Y_{n}=0)$ and show that it depends of $n$

leonbloy
  • 63,430
Sylvain Biehler
  • 478