2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Did Jul 31 '15 at 14:43
  • $\begingroup$ @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. $\endgroup$ – Slowpoke Jul 31 '15 at 14:59
  • $\begingroup$ 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.) $\endgroup$ – Did Jul 31 '15 at 15:02
  • $\begingroup$ @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. $\endgroup$ – Slowpoke Jul 31 '15 at 15:12
  • $\begingroup$ "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. $\endgroup$ – Did Jul 31 '15 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.