# When the sum of Markov chains is a Markov chain: “dumb” algorithm

Suppose I have two (independent) discrete-time and space, preferably non-homogeneous Markov chains $\Gamma^{(i)}=\{\gamma_1^{(i)},\gamma_2^{(i)},...\}, \ i=1,2$ and I want to find a way to check when the sum $\Gamma=\{\gamma_1,\gamma_2,..\}, \ \text{where} \ \gamma_j= \gamma_j^{(1)}+\gamma_j^{(2)}, \ j=1,2,...$, is a Markov chain.

I have found an article in Russian (unfortunately, I couldn't find an English publication) link where the conditions were derived for the chains defined on a finite additive group. I think that the part of the proof of Theorem 1 fits general case with a (finite) Markov chain on $\mathbb{Z}$.

I have added the translation of the beginning of the article containing Theorem 1 and corresponding definitions at the bottom of the question.

My idea (just a copy of the part of the Theorem 1 proof) looks as follows:

According to the Theorem 6.3.2 from Kemeny,Snell: Finite Markov Chains (lumpability) sequence $\Gamma$ will be a Markov chain if and only if

$$P\{ \gamma_{j+1} = \gamma_{j+1}^{(1)}+\gamma_{j+1}^{(2)} = h, \ | \ \gamma_j^{(1)}=g_1, \gamma_j^{(2)}=g_2 \}=p(g,h), \ g=g_1+g_2$$

For every $g_1,g_2,g=g_1+g_2,h \in E$ - state space of the new chain $\Gamma$ , $p(g,h)$ - it's transition probabilities.

(?) Chapman-Kolmogorov equations (?) allow us to write:

For every fixed $h,g_i,\sigma_i \in E, \ i=1,2 : \ g_1+g_2=\sigma_1+\sigma_2$

holds:

$$\sum p^{(1)}(g_1,h_1)p^{(2)}(g_2,h_2)=\sum p^{(1)}(\sigma_1,h_1)p^{(2)}(\sigma_2,h_2)$$

where the sum is taken over all the $h_1,h_2 \in E: \ h_1+h_2=h$; $p^{(i)}$ are the transition probabilities of the chains $\Gamma^{(i)}$.

Let's take a look how it will look like for the simple case of two Markov chains that are sums of i.i.d. random variables with distribution

$$P(X_j^{(1)} = 1)=p, \ P(X_j^{(1)}=-1)=1-p, \ \gamma^{(1)}_k = \sum_{j=1}^k X^{(1)}_j.$$

Let's take this "decomposition" of transition probability $p(x,x)$ for some state $x$ of the result chain $\Gamma$, let $g=h=x$ and $g_1=1, \ g_2=x-1; \sigma_1=2, \sigma_2=x-2$ and write non-zero parts of the sums above:

$$p^{(1)}(1,0)p^{(2)}(x-1,x)+p^{(1)}(1,2)p^{(2)}(x-1,x-2)=p^{(1)}(2,1)p^{(2)}(x-2,x-1)+p^{(1)}(2,3)p^{(2)}(x-2,x-3)$$ $$(1-p)p + p(1-p) = (1-p)p + p(1-p)$$

Thus, in general case, the program will: for every possible transition probability $p(g,h)$ of the resulting chain $\Gamma$, pass all possible pairs of different sums $g=g_1+g_2$ and $g=\sigma_1+\sigma_2$, for every pair passing all possible sums $h=h_1+h_2$.

(Well, it will be very hard for a big chain, but at least something).

So, the question is:

• is it correct;

• why exactly (2) is equal to (3) in the theorem below;

• which classes of Markov chains can be used here: I think it is possible to take non-homogeneous and dependent chains;

• are there any improvements, maybe for some specific chains?

(I apologize for any unspotted mistakes in this big post)

Part of the article:

Let $\Gamma^{(i)}=\{\gamma_1^{(i)},\gamma_2^{(i)},...\},i=1,...,s$

be independent realizations of simple homogeneous Markov chains on a finite additive group $G$ with transition probability matrices

$\pi^{(i)}=\|p^{(i)}(g,h)\|,g,h \in G,i=1,2,..,s.$ Let's define $\Gamma=\{\gamma_1,\gamma_2,..\}$, where $\gamma_j=\sum_{i=1}^s \gamma_j^{(i)},j=1,2,...$ We are interested in conditions when $\Gamma$ is a simple homogeneous Markov chain with some matrix of transition probabilities

$$\pi=\|p(g,h) \|,g,h \in G$$ that does not depend on initial distribution of chains $\Gamma^{(i)}$ (i.e. on distribution of variables $\gamma_1^{(i)},i=1,2,...,s$).

Every line of the matrix $\pi^{(i)}=\|p^{(i)}(g,h)\|$ corresponds to the some element (which we will call a characteristic function of the line) of a group algebra $DG$:

$$p^{(i)}(g) = \sum_{h \in G}p^{(i)}(g,h)\cdot h,$$ where $D$ is a field of real or rational numbers (definition of a group algebra was taken from Curtis, Reiner: Representation Theory of Finite Groups and Associative Algebras).

Theorem 1. Elements of a sequence $\Gamma$ form a simple homogeneous Markov chain with a some transition matrix $\pi=\|p(g,h) \|$ that does not depend on an initial distribution of chains $\Gamma^{(i)}$ when and only when in algebra $DG$ for any elements $g_i,\sigma_i,i=1,..,s$ of a group $G$ such that

$$\sum_{i=1}^s g_i = \sum_{i=1}^s \sigma_i,$$ holds

$$\prod_{i=1}^s p^{(i)}(g_i)=\prod_{i=1}^s p^{(i)}(\sigma_i).\tag{1}$$ If equality (1) holds then $p(g)=\sum_{h \in G}p(g,h)\cdot h$, and $p^{(i)}(g_i)$ are connected in $DG$ in the following way:

$$p(g)=\prod_{i=1}^s p^{(i)}(g_i),\ \sum_{i=1}^s g_i = g.$$

Proof According to the Theorem 6.3.2 from Kemeny,Snell: Finite Markov Chains (combining states) sequence $\Gamma$ will be a Markov chain if and only if

$$P\{\sum_{i=1}^s \gamma_{j+1}^{(i)}=h | \gamma_j^{(1)}=g_1,...,\gamma_j^{(s)}=g_s \} = p(g,h)\tag{2}$$ for every

$$g_1,...,g_s,h \in G, \ g = \sum_{i=1}^s g_i, \ j=1,2,...$$ Conditions (2) are equal to:

for every fixed $h,g_i,\sigma_i \in G, \ i=1,2,...,s, \ \sum_{i=1}^s g_i = \sum_{i=1}^s \sigma_i$, holds

$$\sum p^{(1)}(g_1,h_1)...p^{(s)}(g_s,h_s)=\sum p^{(1)}(\sigma_1,h_1)...p^{(s)}(\sigma_s,h_s),\tag{3}$$ where the sum is taken over all

$$h_1,...,h_s \in G, \ \sum_{i=1}^s h_i = h.$$ But the thing in the left (right) part of the equality (3) is the coefficient before $h \in G$ of the element $\prod_{i=1}^s p^{(i)}(g_i)$(or $\prod_{i=1}^s p^{(i)}(\sigma_i)$) of the group algebra $DG$, which finishes the proof.

EDIT: I tried to write some program for this; it seems to work for the following examples:

-sum of two identical chains $X_n=X \ \forall n, \ P(X=0)=P(X=1)=0.5$ (is Markov);

The code:

#include "math.h"
#include "iostream"
#include "fstream"

using namespace std;

const int n = 3; //dimensions of the matrix

typedef struct prob_matrix{
double data[n][n]; //if the matrices have different dimensions,
//we fill space with 0
int minvalue;
//states of the chain, i.e. matrix 3x3 may represent
//a chain with state space {-1,0,1}
int maxvalue;
};

int x, y;
ifstream in(filename);

if (!in) {
cout << "Cannot open file.\n";
return;
}

in >> mat.minvalue;
in >> mat.maxvalue;

for (y = 0; y < n; y++) {
for (x = 0; x < n; x++) {
in >> mat.data[y][x];
}
}

in.close();

}

void PrintMatrix(prob_matrix& mat) {
for(unsigned d = 0; d < n; ++d)
{
for(unsigned c = 0; c < n; ++c)
cout << mat.data[d][c]<<"  ";
cout<<endl;
}
cout<<endl;
}

int main(){

prob_matrix chain1;

prob_matrix chain2;

PrintMatrix(chain1);
PrintMatrix(chain2);

bool errorflag = 1;

ofstream outputfile;
outputfile.open("output.txt");
//begin loop
//as long as both chains are finite with max state =n,
//the result chain has it's max state =2n
//state space E = [-2n;2*n]

for (int g=-2*n; g<=2*n;++g){
//looping all possible transition probabilities p(g,h)
for (int h=-2*n;h<=2*n;h++){// on E: from -2n to 2n

outputfile<<"g="<<g<<" "<<"h="<<h<<endl;
for (int g1=chain1.minvalue; g1<=chain1.maxvalue;g1++){
//partitioning g = g1+g2 on [-2*n.2*n]; not optimal, just for demonstration
int g2=g-g1;           //state space for chain1
if (g2>=chain2.minvalue && g2<=chain2.maxvalue) {//state space for chain2
outputfile<<"--(g1+g2)"<<g1<<"+"<<g2<<"="<<g<<endl;

for (int s1=chain1.minvalue; s1<=chain1.maxvalue;s1++){
//partitioning g = s1+s2 on [-2*n,2*n]
int s2=g-s1;
if (s2>=chain2.minvalue && s2<=chain2.maxvalue){
outputfile<<"----(s1+s2)"<<s1<<"+"<<s2<<"="<<g<<endl;
double sum1=0;
double sum2=0;
double temp1;
double temp2;

for(int h1=chain1.minvalue;h1<=chain1.maxvalue;h1++){
//partitioning h=h+h2; h1 from state space of chain1
int h2=h-h1;
if (h2>=chain2.minvalue && h2<=chain2.maxvalue){
//h2 from state space of chain2
outputfile<<"------(h1+h2)"<<h1<<"+"<<h2<<"="<<h<<endl;
temp1 = (chain1.data[g1-chain1.minvalue][h1-chain1.minvalue])*(chain2.data[g2-chain2.minvalue][h2-chain2.minvalue]);
//state-minvalue = matrix coordinates
temp2 = (chain1.data[s1-chain1.minvalue][h1-chain1.minvalue])*(chain2.data[s2-chain2.minvalue][h2-chain2.minvalue]);
sum1=sum1+temp1;
sum2=sum2+temp2;

}
}
outputfile<<sum1<<" = "<<sum2<<endl;
if (sum1!=sum2) {outputfile<<"mismatch"<<endl;errorflag=0;}

}

}

}

}

}
}
outputfile<<endl<<"exit code: "<<errorflag<<endl;
outputfile.close();
cout<<endl<<"exit code: "<<errorflag<<endl;

return 0;
}


Usage: files Chain1.txt and Chain2.txt contain matrices and min and max states of the chain (e.g. -1 and 1); If matrices have different dimensions, they are filled with 0's at right and bottom; In the code:

const int n = 2;


two identical chains:

0 1
0.5 0.5
0.5 0.5


Output:

0.5  0.5
0.5  0.5

0.5  0.5
0.5  0.5

exit code: 1


From the counterexample above:

const int n = 3;


Chain1.txt:

0 1
0.5 0.5 0
0.5 0.5 0
0 0 0


Chain2.txt:

-1 1
0.25 0.75 0
0.25 0.5 0.25
0 0.75 0.25


Output:

0.5  0.5  0
0.5  0.5  0
0  0  0

0.25  0.75  0
0.25  0.5  0.25
0  0.75  0.25

exit code: 0


File output.txt contains full log of calculations.

• Indeed the sum of two independent Markov chains may not be a Markov chain, but when each Markov chain is a sum of independent increments, then their sum is again Markov and again a sum of independent increments. If the increments of the two chains at time $n$ have distributions $p_n$ and $q_n$ respectively, then the increments of their sum have distribution $p_n\ast q_n$ at time $n$ (convolution). I have the feeling that this simple observation answers every part of your question but I might be mistaken. – Did Jul 31 '15 at 14:43
• @Did Yes, that's one of the cases, when the sum will be a Markov chain. Another one: when the chains are just different realizations of a random variable, e.g. $(X_n) \equiv X$ for all $\forall n$. The problem is to find more cases. – Slowpoke Jul 31 '15 at 14:59
• The problem as you stated it was to determine the sums of independent sums of independent increments which were Markov chains. The answer is: all of them. Now if you have a different problem in mind, please be specific. (Note that the "other" case you describe in your comment is actually a special case of independent sums of independent increments.) – Did Jul 31 '15 at 15:02
• @Did No, in this question I ask about a chain $\Gamma$ which is a sum of two chains $\Gamma^{(1)}$ and $\Gamma^{(2)}$ that can have any nature (but we have their transition matrices). The value of the chain $\Gamma$ at time $n$ obtained by adding the values of two chains: $\gamma_n = \gamma^{(1)}_n +\gamma^{(2)}_n$. For example, let $(X_n)$ take values $-1$ and $0$ with transition matrix \begin{matrix} 0.25 & 0.75 \\ 0.75 & 0.25 \end{matrix} and $(Y_n)$ take values $0$ and $1$ with the same transition probabilities. The program tells me that $(X_n+Y_n)$ is a Markov chain. – Slowpoke Jul 31 '15 at 15:12
• "No", applying to which part of what I said exactly? Yes there are sporadic cases when X+Y is Markov, such as the highly symmetrical one in your comment. I do not think one can expect general criteria though. For a more general framework, the notion of lumpability might help, since your question amounts to determine when the function X+Y of the Markov chain (X,Y), is still Markov. – Did Jul 31 '15 at 16:17