Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a matrice A. It is model probability matrice for some process (Markov chain).
Then, I have estimated matrice B.
I have to somehow compare these two matrices to tell whether process that gave matrice B in result matches model matrice A. How can I do this? I would like to have some parameter to change a tollerancy for difference.
I need at least three different methods so I can compare their results.

Those matrices are stochastic matrices. Their size is n x n.

I don't know how to put this. I have two series of observations of state. One is a "model" and for other I need to decide if it matches the "model".

From two different series of state observations I estimate "model" matrice A and matrice B. Then I need to check if process that resulted in matrix B is the same process that gave model matrice A.

Please, see my new question How can I compare two Markov processes?

share|improve this question
    
It depends on the "results" that you want to match. Usually for finite-horizon properties you should work with $$\|A-B\| = \sup\limits_{i,j}|a_{ij}-b_{ij}|$$ while for the infinite-horizon and structural properties you should also compare structures of matrices $A$ and $B$, e.g. that $a_{ij}>0 \Leftrightarrow b_{ij}>0$. Anyway, you would benefit if you be more specific about results you need to match. –  Ilya Nov 28 '11 at 10:37
add comment

1 Answer

up vote 5 down vote accepted

In other words, you want to know whether the process that you observed and which gave rise to $B$ could correspond to a path of the Markov chain with transition matrix $A$, or not. A canonical way to answer this question is to compute the likelihood of the sequence of observations described by $B$ with respect to the model $A$. For Markov chains, this is $$ L=\prod_{x,y}A(x,y)^{N(x,y)}, $$ where the product is over every states $x$ and $y$ and $N(x,y)$ is the number of times one observed a transition from $x$ to $y$. Presumably, $B$ corresponds to $B(x,y)=N(x,y)/N(x)$, where $N(x)$ is the number of times one observed a visit to $x$.

If indeed the observed sequence was generated by the model $A$, $N(x,y)=nm(x)A(x,y)+o(n)$ for every $x$ and $y$, where $n$ is the length of the sequene and $m$ is the so-called stationary distribution of the Markov chain. Hence, $$ \log L_A=n\cdot\Lambda_A+o(n),\quad \Lambda_A= \sum_{x,y}m(x)A(x,y)\log A(x,y). $$ Furthermore, the discrepancy between $B$ and $A$ under the hypothesis that the sequence was generated by $A$ is described by a central limit theorem, that is, for every $x$ and $y$, $$ N(x,y)=nm(x)A(x,y)+\sqrt{n}Z_{x,y}+o(\sqrt{n}), $$ for a given centered gaussian family $(Z_{x,y})$ whose covariance matrix depends on $A$ and can be computed explicitly. Hence the approximate $p$-value of the observed sequence is $$ \mathrm P(Z\approx (N-nm\cdot A)/\sqrt{n}). $$ Assuming the covariance matrix of $Z$ is $C$, one gets an approximate $p$-value of $\mathrm e^{-K/2n}$, with $$ K=(N-nm\cdot A)^*C^{-1}(N-nm\cdot A). $$ One can also consider the likelihood $L$ and note that $$ L=L_A^n\cdot L_{B\mid A},\qquad L_{B\mid A}=\prod_{x,y}A(x,y)^{N(x,y)-nm(x)A(x,y)}, $$ and use $L_{B\mid A}$ to estimate the discrepancy between the observed sequence, described by $(N(x,y))$, and the model, described by $A$.

share|improve this answer
    
I'm not a mathematician. I just need an equation and a book/article it came from to cite ;) –  Jan Ajan Nov 29 '11 at 13:41
    
I am a mathematician and I hate it when people just need an equation and a book/article to cite. –  Did Nov 30 '11 at 7:57
    
Sorry for that. Nobody is expected to know and understand everything. –  Jan Ajan Nov 30 '11 at 8:03
    
If I were a mathematician, I would solve this problem myself without anyone's help. –  Jan Ajan Nov 30 '11 at 8:16
1  
Not my point. Read what I wrote. (As a mathematician, I also hate it when people pretend that I wrote things I did not. Terribly boring and old fashioned, isn't it?) –  Did Nov 30 '11 at 10:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.