# Problem with condtional probability in Markov chain

Suppose we have a sequence of independent binomial random variables $\xi \in B(1,p)$. We build a new sequence $\eta_n = 2 \xi_{n+1} + \xi_n$. Will it be a Markov chain?

My thoughts. Lets consider conditional probability:

$$\mathbb{P}\big(\eta_n = x_n \big\vert \eta_{n-1} = x_{n-1}, \eta_{n-2} = x_{n-2}, \dots \big) =$$$$= \mathbb{P}\big(2 \xi_{n+1} + \xi_n = x_n \big\vert 2 \xi_n + \xi_{n-1} = x_{n-1}, 2 \xi_{n-1} + \xi_{n-2} = x_{n-2}, \dots \big)$$

And we see that according to independence of $\xi$, $\eta_n$ doesn't depend on the subsequence $\{\eta_{i}, i\ge n-2\}$. But $\eta_{n-1}$ does. Should we consider somehow such dependence in the conditional part of probability?

• Hint: The key fact is that $\eta_n$ determines $\xi_{n+1}$ since $(\xi_{n+1}=1)=(\eta_n\geqslant2)$ hence $\eta_{n+1}=g(\eta_n)+2\xi_{n+2}$ for some measurable function $g$ where $\xi_{n+2}$ is independent of $(\eta_k)_{k\le n}$, which implies the Markov property. Actually, $(\eta_n)$ is simply reading the sequence of bits $(\xi_n)$ two at a time. – Did Oct 25 '15 at 8:08
• @Did, thank you for this approach. it's quite helpful for understanding – Andrei Kulunchakov Oct 25 '15 at 8:10