Let $(\xi_n)_{n \in \mathbb{N}}$ be a sequence of i. i. d. random variables with $\xi_n \sim (1-p)\delta_{-1}+p \delta_1$ and

$$\eta_n= \underset{k \in \{1, \dots ,n\}}{\max} \displaystyle\sum_{i=1}^k \xi_i - \underset{j \in \{1, \dots ,n\}}{\min} \displaystyle\sum_{i=1}^j \xi_i, \ \ \ \ \ \ \ \ \ \ \ \ \eta_0=0.$$

Our goal is to investigate whether $(\eta_n)_{n \in \mathbb{N}}$ is a Markov chain. We got the hint that we shall draw a picture concerning this topic. Our problem (and so our question) is that we don't get what the interpretation of $(\eta_n)$ is. When calculating the first parts, we don't get something relevant about the Markov-chain-question.

  • $\begingroup$ At each time, either the maximum goes up by 1, the minimum goes down by 1, or neither. So $\eta$ either goes 1 to the right or stays where it is. What is the probability that $\eta$ moves? Does it depend only on the current value of $\eta$ or do you need to know the current position of the whole walk too? $\endgroup$ – Ian Apr 18 '18 at 14:17
  • $\begingroup$ The problem is that we can't get the propability that $\eta$ moves. From $\xi_n$ we don't get whether the max changes or not. If we would have the probability, we could decide about Markov. $\endgroup$ – Jan Apr 18 '18 at 14:21
  • $\begingroup$ The point is that in a non-Markov process, if you know $X_n$, it is not good enough to compute the distribution of $X_{n+1}$. Here for instance, consider $\eta_n=2$ and see if you need more information to determine the probability that $\eta_{n+1}=2$ again. $\endgroup$ – Ian Apr 18 '18 at 14:31
  • $\begingroup$ If $\eta_n=2$ and $\eta_{n+1}=2$ this would be the probability for the case that max and min don't move. We don't get a formula for this. Can you help us with P$(\eta_{n+1}=2| \eta_n=2)$? $\endgroup$ – Jan Apr 18 '18 at 14:41
  • $\begingroup$ Suppose the current min is 0, the current max is 2. Compare "the current position is 1" vs "the current position is 2". $\endgroup$ – Ian Apr 18 '18 at 14:53

If $\eta_n$ is to be Markov, then you should be able to deduce the full distribution of $\eta_{n+1}$ knowing only the value of $\eta_n$. Knowing the older values of $\eta$ should not change the distribution.

Somehow you expect this to not be the case, because if $\sum_{i=1}^n \xi_i$ is currently on the "frontier" i.e. currently equal to either its running min or its running max, then $\eta_{n+1}=\eta_n+1$ is possible. Otherwise it is not. To turn this into a proof that $\eta$ is not Markov, you need to be able to extract information about whether $\sum_{i=1}^n \xi_i$ is on the frontier using information about $\eta$. One way to see this is that if $\eta_n>\eta_{n-1}$ then $\sum_{i=1}^n \xi_i$ is on the frontier. As a result, you should be able to choose $n$ and $M$ such that

$$P(\eta_{n+1}=M \mid \eta_n=M-1,\eta_{n-1}=M-2)>P(\eta_{n+1}=M \mid \eta_n=M-1).$$

Note that this is true even though the RHS is hard to compute exactly.


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.