0

Let $\{\xi_n\}$ be independent, identically distributed, random variables. Define $S_k = \sum\limits_{i=0}^k \xi_i $ and $\eta_k = \max(S_0, ..., S_k)$. How to prove or disprove that $\{ \eta_k\}$ is a Markov process?

I have a feeling that $\{ \eta_k\}$ is not a Markov process, but don't know how to rigorously prove it.

My attempt

I think it is sufficient to show that assuming $\xi \sim U_{[-1/2 ; 1/2]}$ the following is true: $$ P\left(\eta_3 > \frac{1}{2} ~~\Big|~~ \eta_2 = \frac{1}{2} , \eta_1 = \frac{1}{2} \right)\neq P\left(\eta_3 > \frac{1}{2} ~~\Big|~~ \eta_2 = \frac{1}{2} \right) $$

The left part of the above is $$ P\left(\eta_3 > \frac{1}{2} ~~\Big|~~ \eta_2 = \frac{1}{2} , \eta_1 = \frac{1}{2} \right) = P\left(\xi_3 > -\xi_2 ~\Big|~ \xi_1 = \frac{1}{2}, \xi_2 < 0\right) $$ The right part is $$ P\left(\eta_3 > \frac{1}{2} ~~\Big|~~ \eta_2 = \frac{1}{2} \right) = P\left(\xi_3 > -\xi_2 ~\Big|~ \xi_1 = \frac{1}{2}, \xi_2 < 0\right) + P\left(\xi_3 > 0 ~\Big|~ \xi_1 + \xi_2 = \frac{1}{2}, \xi_1 < \frac{1}{2} \right) $$ And the problem is to prove that the last term $P\left(\xi_3 > 0 ~\Big|~ \xi_1 + \xi_2 = \frac{1}{2}, \xi_1 < \frac{1}{2} \right) $ is non zero

And it really seems, that it is non zero, because $\{\xi_3 > 0\}$ and $ \{\xi_1 + \xi_2 = \frac{1}{2}\}$ are independent.

Am i right ?

Community
  • 1
xolodec
  • 103
  • "I have a feeling that it is not Markov process, but don't know how to rigorously prove it." A common approach then is to find a counterexample. Did you do anything in this direction? – Did Oct 30 '15 at 08:47
  • If I could find one, i wouldn't post such a question here. – xolodec Oct 30 '15 at 08:48
  • I did not say "find", I said "do anything in this direction". Do you understand the difference? – Did Oct 30 '15 at 08:50
  • I dont think my attempt is right, but i posted it, as you suggested – xolodec Oct 30 '15 at 09:30
  • The decomposition of the RHS is not correct. You write $P(A\mid B\cup C)$ with $B\cap C=\varnothing$ as $P(A\mid B)+P(A\mid C)$ while $$P(A\mid B\cup C)=\frac{P(A\cap B)+P(A\cap C)}{P(B)+P(C)}=\frac{P(A\mid B)P(B)+P(A\mid C)P(C)}{P(B)+P(C)}.$$ Correcting this step while keeping the same approach should lead you to a full solution. (Note that increments uniform on an interval may not have been the simplest choice and that $\pm1$ increments often work well in these situations.) – Did Oct 30 '15 at 09:52
  • Am i right that assuming $$ P(A\mid B\cup C)=\frac{P(A\cap B)+P(A\cap C)}{P(B)+P(C)}=\frac{P(A\mid B)P(B)+P(A\mid C)P(C)}{P(B)+P(C)} $$ the probability of $B$ is equal to $$P(B) = P({ \xi_1 = 1/2, \xi_2 < 0 }) = 0 $$ so that $$ P(A|B+C) = P(A|C)$$ – xolodec Oct 30 '15 at 12:56

1 Answers1

0

Let $ p(x) = \mathbb{I}(x \in [-1/2;~ 1/2]) $, or equivalently $ \xi \sim U_{\left[-\frac{1}{2}; ~\frac{1}{2}\right]} $.

Consider probabilities: \begin{equation} \begin{gathered} P\left( \eta_3 > 0 ~\Big|~ \eta_1 = \dfrac{1}{2}, \eta_2 = \dfrac{1}{2} \right) = P\left( \xi_3 > -\xi_2 ~\Big|~ \xi_1 = \dfrac{1}{2},~ \xi_2 < 0 \right) = \\ = \int_{-1/2}^{0} \int_{-x_2}^{1/2} dx_3 dx_2 = \dfrac{1}{8} \end{gathered} \end{equation} \begin{equation} \begin{gathered} P\left( \eta_3 > 0 ~\Big|~ \eta_2 = \dfrac{1}{2} \right) = P\left( \eta_3 > 0 ~\Big|~ \underbrace{\left\{ \xi_1 = \dfrac{1}{2},~ \xi_2 < 0 \right\}}_{B} \cup \underbrace{\left\{ \xi_1 + \xi_2 = \dfrac{1}{2} \right\}}_{C} \right) \end{gathered} \end{equation} Note that $ P(B \cap C) = 0 $, so \begin{equation} \begin{gathered} P( \eta_3 > 0 ~|~ B \cup C ) = \dfrac{P(\eta_3 > 0 ~|~ B) P(B) + P(\eta_3 > 0 ~|~ C) P(C)}{P(B) + P(C)} = \\ = P(\eta_3 > 0 ~|~ C) = P\left(\xi_3 > 0 ~\big|~ \left\{ \xi_1 + \xi_2 = \frac{1}{2} \right\} \right) = \dfrac{1}{2} \end{gathered} \end{equation} So we have proved, that Markov property is not fulfilled for such a sequence. \begin{equation} P\left( \eta_3 > 0 ~\Big|~ \eta_1 = \dfrac{1}{2}, \eta_2 = \dfrac{1}{2} \right) \neq P\left( \eta_3 > 0 ~\Big|~ \eta_2 = \dfrac{1}{2} \right) \end{equation}

xolodec
  • 103