# Estimating an unknown restricted Markov Chain from partial measurements

There is an Markov chain $M$ defined on states $1, ..., N$ with the special property that it only has transitions $p_i$ from $i$ to $i + 1$ , $q_{i + 1}$ from $i + 1$ to $i$, and $r_i = 1 - p_i - q_i$ from $i$ to $i$ (for $i \in [N - 1]$; $p_N = 0$ and $q_1 = 0$ since there is no successor/predecessor state). We know our chain respects this special structure, but we don't know the transition probabilities.

Our data about the process is generated as follows:

1. Start in some known state $n_0 \in [N]$
2. For $k = 0, ... , {t - 1}$:
1. Go to state $n_k$ in $M$
2. Take $n_k$ many steps in $M$
3. Set $n_{k + 1}$ as the current state in $M$
3. Output $n_0,...,n_{t}$

In other words, we only have partial information about our walk through M. But from many of these $n_0,...,n_{t}$ I want to be able to infer the transition probabilities of $M$. How should I go about this? Is there a standard procedure for this? If so, is there an implementation in Matlab (or R)?

• So this is a (finite-state) birth-death chain (with self-loops, which the link doesn't mention, but are common in the literature)? Feb 1 '12 at 17:27
• @cardinal yeah, we are trying to estimate a hidden Moran process, basically. Feb 1 '12 at 17:30
• I'm a little unsure of your description above. In step two, it sounds like you do a fixed number of (unobserved) transitions where the fixed number is the label of the state that you're in? Is that correct? Feb 1 '12 at 17:32
• @cardinal that is exactly correct. After that many transitions, you are a new state which you observe and then repeat. Feb 1 '12 at 17:38
• basically, in step 2.1 I am thinking of $n_k$ as a state and in 2.2 I am treating it as an integer. Feb 1 '12 at 17:39

If you call $A$ the transition matrix of your birth-death chain, with its special structure of only three non-zero terms per row, the probability to observe $n_0,\ldots,n_t$ is $$[A^{n_0}]_{n_0n_1}\,[A^{n_1}]_{n_1n_2}\cdots[A^{n_{t-1}}]_{n_{t-1}n_t}\,.$$ You therefore are able to compute exactly the likelihood associated with your chain. From there, any standard method depending on the likelihood (Bayesian, MLE, &tc.) applies.