Когда сумма независимых марковских цепей - марковская цепь?

[Slumber]

Меня интересует вопрос, когда будет марковской цепь $Z(t) = |X_1(t) - X_2(t)|$, если $X_1(t)$ и $X_2(t)$ - две независимые дискретные цепи Маркова (желательно неоднородные).

Не могу найти ничего существенного по поводу марковости сумм независимых марковских цепей (в интернете встречается контрпример с зависимыми цепями). Есть довольно обширная область markovian functions of a markov chain, но там какие-то сложные условия.

Нашел такую оговорку в Stoyanov J. - Counterexamples in Probability (2ed., Wiley, 1997) - стр.229 книги (258 в djvu):

Цитата:

... 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.

(Ссылка на ихтику http://ihtik.lib.ru/2012.03_ihtik_mathematic/2012.03_ihtik_mathematic_6389.rar).

В это довольно тяжело поверить, все-таки хотелось бы где-то увидеть доказательство или хотя бы утверждение еще раз, т.к. я могу что-то неправильно понимать.

Буду очень благодарен за любые советы или литературу по этому вопросу.

[Slumber]

Допустим, я хочу доказать, что сумма двух независимых марковских цепей - снова марковская цепь. вот ход моих рассуждений:


Пусть $Y(n) = X_1(n)+X_2(n)$. Тогда


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

\centerline{$=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)=}$

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

$\centerline{=/\text{X'ы независимы}/ = \sum_{j+k=i_{n+1}}P(X_1(n+1)=j \ | \ \cdot)\cdot P(X_2(n+1)=k \ | \ \cdot) = }$

$\centerline{ /\text{Марковское свойство+(??) } / = \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)=}$

$\centerline{=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)}$.

Здесь я не могу обосновать, например, шаги (?) и (??) .

-- 18.07.2015, 17:31 --

Upd: ничего хорошего, уже нашли мне контрпример:
http://math.stackexchange.com/questions/1365430/when-the-sum-of-independent-markov-chains-is-a-markov-chain/1365588#1365588

[Slumber]

Я продолжу здесь.
Я стараюсь взять то, что мне подходит из доказательства Теоремы 1 из этой статьи: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tdm&paperid=44&option_lang=rus
(Только у меня не конечная группа, а целые числа).

Пусть у меня есть две дискретные цепи Маркова $\gamma^{(1)}$ и $\gamma^{(2)}$; Суммарная цепь $\Gamma = \{\gamma_1,\gamma_2,...\}$, где $\gamma_j = \gamma_j^{(1)}+\gamma_j^{(2)}$.
Тогда, согласно теореме 6.3.2 у Кемени, Спелл ("Конечные цепи Маркова") об укрупнении состояний марковской цепи, $\Gamma$ будет цепью Маркова тогда и только тогда, когда

$$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$$

Для любых $g_1,g_2,g=g_1+g_2,h \in E$ - пространства состояний новой цепи $\Gamma$ , $p(g,h)$ - ее переходные вероятности.
Уравнения Колмогорова-Чепмена(?) позволяют переписать это в виде:
Для любых фиксированных $h,g_i,\sigma_i \in E, \ i=1,2 : \ g_1+g_2=\sigma_1+\sigma_2 $ справедливы равенства

$$\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)$$

Где суммирование проводится по всем $h_1,h_2 \in E: \ h_1+h_2=h$; $p^{(i)}$-вероятности перехода соответствующих цепей.

Я беру самый простой приходящий на ум пример суммы двух цепей, являющихся суммами независимых случайных величин с распределением $P(X_j^{(1)} = 1)=p, \ P(X_j^{(1)}=-1)=1-p, \ \gamma^{(1)} = \sum_j X^{(1)}_j $, и расписать вероятность $p(x,x)$ для цепи $\Gamma$:
Пусть $g=h=x$, зафиксируем $g_1=1, \ g_2=x-1; \sigma_1=2, \sigma_2=x-2$ и расписываем вероятность перехода, ненулевые слагаемые

$$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)$$

Выходит так: в общем случае, программа для каждой вероятности $p(g,h)$ должна перебрать для каждого разложения $g=g_1+g_2$ все другие его разложения $g=\sigma_1+\sigma_2$ (можно разделить на 2 благодаря симметричности), и в каждом случае этих разложений - все разложения $h=h_1+h_2$. (Невесело).

Буду очень благодарен за любые советы и комментарии. Хотелось бы придумать пару красивых примеров хотя бы.

[Slumber]

Моя попытка воплощения алгоритма в виде программы C++ (спойлер):

(Оффтоп)

#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[x][y];
    }
  }

  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;
}

Программа подтверждает марковость цепи, являющейся суммой двух цепей с $X_n = X \ \forall n, \ P(X=0)=P(X=1)=0.5$:

(Оффтоп)

0.5  0.5  
0.5  0.5  

0.5  0.5  
0.5  0.5  


exit code: 1

И подтверждает не-марковость этого примера:http://math.stackexchange.com/questions/1365430/when-the-sum-of-independent-markov-chains-is-a-markov-chain

(Оффтоп)

0.5  0.5  0  
0.5  0.5  0  
0  0  0  

0.25  0.25  0  
0.75  0.5  0.75  
0  0.25  0.25  


exit code: 0

В файл output.txt пишется подробный лог проверки соотношений.

Структура рабочих файлов chain1.txt и chain2.txt: в первой строке - через пробел минимальное и максимальное значения для цепи (например, $-1$ и $1$), дальше - матрица, разделенная пробелами. Если одна из матриц меньше, она справа и снизу забивается нулями.
Размерность матриц нужно еще указать константой $n$ в начале программы.

В первом случае, const int n =2:
Chain1.txt и Chain2.txt:

(Оффтоп)

0 1
0.5 0.5
0.5 0.5

Во втором случае, 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