How can I compare two Markov processes?

Question

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.

Answer 1

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.

Answer 2

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.