5
$\begingroup$

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?

  • 0
    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.2011-11-28

1 Answers 1

8

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

  • 3
    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?)2011-11-30