# Laplace smoothing parameter choice for Markov chain transitions

Let $Y_{t}$ be the state of the process at time $t$, ${\bf P}$ be the transition matrix then:

$${\bf P}_{ij} = P(Y_{t} = j | Y_{t-1} = i)$$

Since this is a Markov chain, this probability depends only on $Y_{t-1}$, so it can be estimated by the sample proportion. Let $n_{ik}$ be the number of times that the process moved from state $i$ to $k$. Then,

$$\displaystyle\hat{{\bf P}}_{ij} = \dfrac{ n_{ij} }{ \sum_{k=1}^{m} n_{ik} }$$

where $m$ is the number of possible states ($m=5$ in this case). The denominator, $\sum_{k=1}^{m} n_{ik}$, is the total number of movements out of state $i$. Estimating the entries in this way actually corresponds to the maximum likelihood estimator of the transition matrix, viewing the outcomes as multinomial, conditioned on $Y_{t-1}$.

However if the observed Markov chain was too small a sparse matrix may arise, suggesting some transitions are impossible:

\begin{align} \widehat{P}_{\text{personal care}}=&\begin{pmatrix} 0& 0 & 0& 1.00& 0\\ 0& 0 & 0.22& 0.44& 0.33\\ 0& 0.19& 0.57& 0.10& 0.14\\ 0.03& 0.19& 0.09& 0.50& 0.19\\ 0& 0.06& 0.13& 0.56& 0.25\\ \end{pmatrix} \end{align}

This is unlikely and so Laplace smoothing could be used to replace mle:

$$\hat{{\bf P}}_{ij} = \frac{ n_{ij}+ \alpha}{ \sum_{k=1}^{m} n_{ik} +n_{ij}\alpha},$$ where $\alpha$ is some smoothing parameter. What criteria can I use to choose $\alpha$?

• I first thought of cross-validation, but I fear that the resulting choice for $\alpha$ would be zero, since $\alpha > 0$ biases the estimate towards the uniform distribution. Commented Jul 17, 2013 at 11:52
• As an alternative to Laplace smoothing, would you consider a Bayesian approach, with a choice of prior that puts some non-null probability on all transitions? Commented Jul 17, 2013 at 11:55
• I am happy to consider this. Why do you think it would improve the estimate in this case?
– HCAI
Commented Jul 17, 2013 at 11:58
• I'm not sure that it will improve the estimate (we would need to define in which sense I guess), but it would lead to non-zero transition probabilities unless the data contain enough evidence to shrink some of them to zero. Also, it would allow to differenciate the probabilities for non-observed transitions, which doesn't seem to be the case for the Laplace smoothing. Commented Jul 17, 2013 at 12:17
• I see your train of thought. Do you have a reference for this or an example perhaps?
– HCAI
Commented Jul 17, 2013 at 12:21