# How can I compare two Markov processes?

There is a discrete-time irreductible Markov process with $r$ possible states. $k$ observations were performed. At each observation a state of process was determined.

$T_0 = \lbrace 0,1,\dots ,k-1\rbrace$
$T_1 = \lbrace 1,2,\dots ,k-1\rbrace$

$n_i(t) = 1$ means that process was in state $i$ at time $t$, ($t \in T_0$),
$n_i(t) = 0$ otherwise,
$v_{ij}(t) = 1$ means that process changed from state $i$ to state $j$ between time $t-1$ and $t$, ($t \in T_1$), $v_{ij}(t) = 0$ otherwise.

I estimate probability of transition from state $i$ to state $j$ as

$\hat{p}_{ij} = \frac{\displaystyle\sum_{t \in T_1}v_{ij}(t)}{\displaystyle\sum\limits_{t \in T_1}n_i(t-1)}$

First question:
How many observations do I need to properly estimate transition matrix? If $p_{ij}$ is an ideal estimation, I don't want relative error between $\hat{p}_{ij}$ and $p_{ij}$ ( $\frac{|\hat{p}_{ij}-p_{ij}|}{p_{ij}}$ ) to be more than $\varepsilon = 0.01$ with probability $P \ge 0.99$.
I need this in form $k=k(r,\varepsilon, P)$.
I know that the number will be large but this does not matter. I just want to know the number.
For my purposes $r$ will be between 7 and 15, $\forall_i p_{ii} \neq 1$.
If there would be a state $i$ that was never entered or was entered at the last step (what could be written as $\sum\limits_{t \in T_1}n_i(t-1)=0$), I will just simply exclude that state from further calculations.

Second question:
I have first transition matrix $A$. That matrix describes "model" process and was estimated with sufficient number of observations. Then, second process was observed and new matrix $B$ was estimated (with sufficient number of observations).
How can I decide if second process matches "model" process? I want this method to have an "error factor" (I don't know how to name it) witch changeable value $\varphi$. I need 3 or 4 of those methods for comparison.

-
Jan, to bump your question back to the front page, so that it might come to more people's attention, you can make a trivial edit to the text (e.g. add some spaces, change one word, etc.). I have done this for you. If bumping it a few times doesn't help, another approach to attract attention and answers to your question would be to place a bounty on it, but unfortunately to do so requires 75 points. –  Zev Chonoles Nov 29 '11 at 16:46

There are a variety of observations here for the first question - too long for a comment:

1. The Markov process needs to be irreducible; otherwise you probably will not observe some of the possible transitions from some state.

2. With a finite number of observations you can never be certain of the accuracy of your estimates, as there will be a positive probability that the error is greater than any target you set yourself. The best you will be able to do is say that with a certain probability your errors are less than your target error.

3. When you say relative error, do you mean $\frac{|\hat{p}_{ij}-p_{ij}|}{p_{ij}}$ or ${|\hat{p}_{ij}-p_{ij}|}$? The former will mean you need more observations especially if some of the $p_{ij}$ are small.

4. The number of observations needed will depend on how common each state is, and if some states are rare then more observations will be needed.

5. The number of observations needed will depend on how common it is for states not to change, and if many observations involve states not changing then more observations will be needed.

The end result is likely to be a large number of observations, which depends on the detail of the process.

-
I edited my question do provide answers to some of your questions. –  Jan Ajan Nov 30 '11 at 7:43

You cannot tell the accuracy of your estimate without knowing the true value, but you can construct confidence intervals and tell the precision of your point estimate $\hat{p}_{ij}$. For example, see this paper for details. Having the Fisher information matrix and equipped with asymptotic normality, you may test hypothesis for the sample mean as usual.

-
Thanks for this paper. There is still question 2 to answer ;). –  Jan Ajan Dec 1 '11 at 8:39