# Analyzing Markov chain

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.

• 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? – Ian Apr 18 '18 at 14:17
• 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. – Jan Apr 18 '18 at 14:21
• 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. – Ian Apr 18 '18 at 14:31
• 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)$? – Jan Apr 18 '18 at 14:41
• Suppose the current min is 0, the current max is 2. Compare "the current position is 1" vs "the current position is 2". – 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).$$