# Estimate transition matrix from many short Markov chains

I have a situation where data from the following process is observed:

For $i = 1, \dots, n$ let $(X_{i,1}, \dots, X_{i,m_i})$ be a sequence of $m_i$ random variables coming from a discrete-space Markov chain with $N \times N$ transition matrix $P$. For simplicity's sake I'll assume that each $X_{ij} \in \{1, \dots, N\}$. For $i \neq i'$ assume that the chains $(X_{i,1}, \dots, X_{i,m_i})$ and $(X_{i',1}, \dots, X_{i',m_{i'}})$ are independent of each other and both have the same transition matrix $P$. In general $m_i \neq m_{i'}$.

A big complication: $m_i$ is really small. The largest $m_i$ is 9, the smallest is 3, and about 95% of the $m_i = 5$. I have around 50 of these chains (i.e. $n = 50$).

For a single chain the MLE $\hat P_i$ of $P$ is easy to compute: it's just the proportions of times that each transition was observed.

My question: how to get a single estimate of $P$ from these $\hat P_i$? Each $\hat P_i$ estimates the same thing, and due to differences in $m_i$ some do better than others. But because each $m_i$ is small, none of them do very well. There are lots of 0's and 1's which I don't think reflect reality. What should I do here?

• I wonder whether there is any useful information in the starting states of each chain. (For instance, if these mini-chains are random segments selected from a single larger chain, the distribution of starting states might reflect a stationary distribution.) Could you tell us how those starting states were determined? – whuber May 11 '16 at 22:17
• @whuber Thanks for the comment. Each chain corresponds to a totally separate process which was started and stopped; I don't know much about why the initial values for each chain happened to be what they are, but they are certainly random. Overall, I really expected this to be a well-studied problem with a tidy answer. I'm surprised that that doesn't seem to be the case. – alfalfa May 12 '16 at 1:47
• Your problem appears to be no different than estimating the transition probabilities in a single chain. – whuber May 12 '16 at 4:44
• According to all the information you have provided, the answer is of course. You have observed three independent transitions from the $0$ state, governed by its Binomial distribution, and four independent transitions from the $1$ state, governed by its (possibly different) Binomial distribution. That reduces the question to estimating Binomial probabilities. Why should it matter that the transitions occurred within different chains? – whuber May 12 '16 at 13:41
• That makes a lot of sense. Thank you. I guess I was just overthinking it. – alfalfa May 13 '16 at 3:22

Basically, because these chains are independent and have the same transition matrix $P$, I can just count the number of instances of each possible transition and get the MLE of $P$ from that. It doesn't matter that these counts come from different Markov chains.