Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|improve this question
So this is a (finite-state) birth-death chain (with self-loops, which the link doesn't mention, but are common in the literature)? – cardinal Feb 1 '12 at 17:27
@cardinal yeah, we are trying to estimate a hidden Moran process, basically. – Artem Kaznatcheev 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? – cardinal 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. – Artem Kaznatcheev 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. – Artem Kaznatcheev 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.

share|improve this answer

Your Answer


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.