1
$\begingroup$

I have been struggling sometime now with the following question and I feel like I am stacked.

Let $X_n : n= 0,1,\ldots$ be a sequence of iid discrete random variables with $$P(X_n=j)=a_j>0 \qquad \text{ for } j=0,1,2...$$

Is $Y_n=\min(X_0,X_1,\ldots,X_n)$ a Markov chain?

Any help would be much appreciated.

$\endgroup$
1
$\begingroup$

The sequences $(Y_n)_n$ of the $\min$'s and $(M_n)_n$ of the $\max$'s are Markov Chains. As above, define $$Y_n:=\min\{X_0,X_1,\ldots X_n\}$$ and observe that given the values $Y_0,\ldots Y_n$ the value of $Y_{n+1}$ depends only on the value of $Y_n$ since $$Y_{n+1}=j \iff \min\{X_{n+1}, y_{n}\}=j \iff \begin{cases} y_n>j, X_{n+1}=j \text{ or }\\ y_n=j, X_{n+1}\ge j \end{cases}$$ Therefore the probability of $Y_{n+1}$ depends only on $Y_{n}$, i.e. $$\begin{align*}P(Y_{n+1}=j\mid Y_0=y_0, \ldots, Y_{n}=y_{n})&=P(Y_{n+1}=j|Y_n=y_n)\\\\&=\begin{cases}P(X_n=j)=a_j, & \text{ if } 0\le j<y_n \\ P(X_n\ge j)=\sum_{i\ge j}a_i, & \text{ if } y_n=j\\0, & \text{ if } y_n< j \end{cases}\end{align*}$$ since the minimum cannot increase. Similarly for $\max$ where you should be aware that the maximum cannot decrease.


Necessary for the above result is the fact that the $X_n$ are independent and identically distributed. Otherwise it would not hold.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot! It is clear now! $\endgroup$ – Dimitri C Nov 24 '14 at 15:33
  • $\begingroup$ $Y_{n+1}$=$j$⟺min{$X_{n+1}$,$y_n$}=$j$⟺{$X_n$=$j$,$y_n$>j or // $y_n$=$j$,$X_n$≥$j$ Shouldn't this line be written like this? $Y_{n+1}$=$j$⟺min{$X_{n+1}$,$y_n$}=$j$⟺{$X_{n+1}$=$j$,$y_n$>j or // $y_n$=$j$,$X_{n+1}$≥$j$ $\endgroup$ – Dimitri C Nov 24 '14 at 23:52
  • $\begingroup$ @DimitriC Yes, of course! I will correct immediately. Sharp eye... $\endgroup$ – Jimmy R. Nov 24 '14 at 23:58
  • 1
    $\begingroup$ thanks again Stef. Appreciate it! $\endgroup$ – Dimitri C Nov 24 '14 at 23:59
  • $\begingroup$ You are welcome! Good luck with your course! $\endgroup$ – Jimmy R. Nov 24 '14 at 23:59

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.