# When the sum of independent Markov chains is a Markov chain?

I try to find as much as possible cases, when the chain $Z(t) = |X_1(t)-X_2(t)|$ is Markov, where $X_1(t)$ and $X_2(t)$ are independent, discrete-time and space, preferably non-homogeneous Markov chains. I started to search for the sum of independent Markov chains and I found this statement in Stoyanov J. - Counterexamples in Probability (2ed., Wiley, 1997)(p.229, one can google it and find in google books):

... the sum of two Markov processes need not be a Markov process. Note, however, that that the sum of two independent Markov processes preserves this property.

That seems very strange to me and I wish to find the proof or at least the statement elsewhere.

EDIT: The way of thinking how it may look like for a sum of two independent Markov chains (If I want to prove that the sum of two independent Markov chains is again a Markov chain):

Let $Y(n) = X_1(n)+X_2(n)$. Then

$P(Y(n+1) = i_{n+1} \ | \ Y(n) = i_n, ..., Y(0)=i_0) =$

$= P(X_1(n+1)+X_2(n+1)=i_{n+1}\ | \ X_1(n)+X_2(n)=i_n,...,X_1(0)+X_2(0)=i_0)=$

$=/ (?) / = \sum_{j+k=i_{n+1}}P(X_1(n+1)=j,X_2(n+1)=k \ | \ \cdot)=$

$=/\text{X's are independent}/ = \sum_{j+k=i_{n+1}}P(X_1(n+1)=j \ | \ \cdot)\cdot P(X_2(n+1)=k \ | \ \cdot) =$

$= /\text{Markov property + (??) } / = \sum_{j+k=i_{n+1}}P(X_1(n+1)=j \ | \ X_1(n)+X_2(n)=i_n)\cdot P(X_2(n+1)=k \ | \ X_1(n)+X_2(n)=i_n)=$

$=P(X_1(n+1)+X_2(n+1)=i_{n+1} \ | \ X_1(n)+X_2(n)=i_n) = P(Y(n+1)=i_{n+1}\ | \ Y(n)=i_n)$.

Here I am uncertain about (?) and (??) steps.

• Do you want to know whether the sum of two independent Markov chains is a Markov chain or whether the sum of two independent Markov processes is a Markov process? The title of your question suggests the former, but the question itself the latter.
– saz
Commented Jul 18, 2015 at 11:35
• @saz As far as I understand, Markov chain is a sort of discrete-valued Markov process, so if this statement is true about general Markov processes, it should work for Markov chains too. Commented Jul 18, 2015 at 11:49
• @saz I'm interested in the sum of two independent chains. Commented Jul 18, 2015 at 11:58
• A more general framework for the question is whether some function of a Markov chain is still a Markov chain, that is, if $X=(X_n)$ is Markov and $Y_n=G(X_n)$, when is $Y=(Y_n)$ a Markov chain? Your case is when $X=(X^1,X^2)$, which is Markov if $X^1$ and $X^2$ are independent and Markov. This general property is called lumpability, sufficient conditions for lumpability are well known, one meets it naturally when studying hidden Markov models (of great relevance in applications), and gg'ing lumpability markov provides relevant references.
– Did
Commented Oct 27, 2015 at 10:21
• @Did Thank you, we have already met in this question where I have actually used the lumpability (formula (3)) and was checking the condition using a program. Looks like my explanation there was overcomplicated, because I didn't know that lumpability is a rather well-known thing, so I received no answers except yours. Commented Oct 27, 2015 at 12:54

In general, the sum of two independent Markov chains is not a Markov chain.

Let $X$ be a random variable such that $\mathbb{P}(X=0) = \mathbb{P}(X=1) = \frac{1}{2}$ and set $X_n := X$ for all $n \in \mathbb{N}$. Obviously, $(X_n)_{n \in \mathbb{N}}$ is a Markov chain. Moreover, let $(Y_n)_{n \in \mathbb{N}_0}$, $Y_0 := 0$, be a Markov chain independent from $X$ with state space $\{-1,0,1\}$ and transition matrix

$$P := \begin{pmatrix} \frac{1}{4} & \frac{3}{4} & 0 \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ 0 & \frac{3}{4} & \frac{1}{4} \end{pmatrix}.$$

Now set $Z_n := X_n+Y_n$. Then, by the independence of $X$ and $(Y_n)_{n \in \mathbb{N}_0}$, we have

\begin{align*} \mathbb{P}(Z_2 = 0 \mid Z_1 = 1, Z_0 = 1) &= \frac{\mathbb{P}(Z_2 = 0, Z_1 = 1, Z_0 = 1)}{\mathbb{P}(Z_1 =1, Z_0=1)} \\ &=\frac{\mathbb{P}(Y_2 = -1, Y_1 = 0, X= 1)}{\mathbb{P}(Y_1 =0, X=1)} \\ &= \frac{\mathbb{P}(Y_2 = -1, Y_1 = 1)}{\mathbb{P}(Y_1 = 0)} \frac{\mathbb{P}(X=1)}{\mathbb{P}(X=1)} \\ &= \mathbb{P}(Y_2 = -1 \mid Y_1 = 0) = \frac{1}{4}. \end{align*}

On the other hand, a very similar calculation shows that

\begin{align*} \mathbb{P}(Z_2 = 0 \mid Z_1 = 1) &= \frac{\mathbb{P}(Y_2 = -1, Y_1=0) \mathbb{P}(X=1) + \mathbb{P}(Y_2 = 0, Y_1=1) \mathbb{P}(X=0)}{\mathbb{P}(Y_1 = 0) \mathbb{P}(X=1) + \mathbb{P}(Y_1=1) \mathbb{P}(X=0)} \\ &= \frac{5}{12} \neq \frac{1}{4}. \end{align*}

This means that $(Z_n)_{n \in \mathbb{N}_0}$ is not a Markov chain.

• Thank you! However, this brings be to the very beginnig of my search. It is very strange that I can find almost nothing on this question (cases when the sum will be a Markov chain). Commented Jul 18, 2015 at 14:25
• @hcl14 Yeah. Since independence is already a rather strong condition, I guess that there is simply no reasonable condition for the sum being again a Markov chain.
– saz
Commented Jul 18, 2015 at 21:36
• You might be interested in the algorithm and a program I posted here: link Commented Jul 27, 2015 at 8:35

I know this is an old post, but it's the top result on google when one searches for "sum of Markov chains" -- at least it is for me at the time of writing. I just wanted to suggest a much easier and more intuitive solution.

Let $$U$$ and $$V$$ be independent Bernoulli$$(\tfrac12)$$. Let $$X_n = U$$ for all $$n$$. Let $$Y_n = -(-1)^n V$$ for all $$n$$ Let $$Z_n = U - (-1)^n V.$$ In particular, $$U-V = Z_0 = Z_2 = Z_4 = \cdots$$ and also $$U+V = Z_1 = Z_3 = Z_5 = \cdots$$.

Suppose that the 'present' is time $$n = 2$$, and we wish to consider the distribution of $$Z_3$$. Note that $$Z_2 = 0$$ implies $$U = V$$, and so $$Z_1 = Z_3 = 2U$$. Knowing $$Z_1$$ now determines precisely $$Z_3$$. For example, $$P(Z_3 = 2 \mid Z_2 = 0, Z_1 = 2 ) = 1 \neq P(Z_3 = 2 \mid Z_2 = 0, Z_1 = 0).$$ (In particular, if one sees consecutive $$0$$s, then one knows that $$U = V = 0$$.)

• Thank you! I remember also writing some algorithm on that problem which might be interesting for you, but it's a long time since university so I can't tell how correct is it. Commented Nov 1, 2018 at 9:22
• Excellent, thanks. By the way, I had forgotten that you wanted independent Markov chains initially. The solution posted yesterday was for dependent ones. I've changed it -- only very minorly -- just a moment ago to be independent :) Commented Nov 1, 2018 at 9:24