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
\begin{equation} \prod_{i=1}^s p^{(i)}(g_i)=\prod_{i=1}^s p^{(i)}(\sigma_i).\tag{1} \end{equation} 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
\begin{equation} 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} \end{equation} 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
\begin{equation} \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} \end{equation} 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);
-counterexample from my previous question;
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;
};
//Loading matrices from file;
void LoadMatrix(prob_matrix& mat,char* filename) {
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(){
//loading data
prob_matrix chain1;
LoadMatrix(chain1,"Chain1.txt");
prob_matrix chain2;
LoadMatrix(chain2,"Chain2.txt");
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.