High order Markov Chain transition probability I'm modelling a time series using high order markov chain and estimate the transition probability of the equivalent first order markov chain.
The problem is that some of transition in the equivalent first order markov chain from state i to state j doesn't occur in the training dataset at all. How to handle this problem and give a estimate on this transition probability?
Thanks a lot!
 A: Without any actual events or a physical model that indicates the transition, I think the best you can do is a reasonable upper bound on the probability.  The probability could, in fact, be zero.
Assuming N opportunities to make the transition, 0 of which made that particular one, then we could assume that the probability of what we saw is has no less than a 50% probability.  In this case: $P[0$ of $N] \ge 0.5, (1-p)^N \ge 0.5, 1-p \ge 0.5^{\frac{1}{N}}$,
$p \le 1 - 0.5^{\frac{1}{N}}$
Note that this upper bound gets small very quickly with large $N$.
For an even greater confidence, one could say that the probability of the observed event is no less than 5% probable, thus:
$p \le 1 - 0.05^{\frac{1}{N}}$
Here, alot more data is needed to get a low upper bound, but you can have pretty high confidence in it.
I'm guessing what you'd really like is a lower bound other than 0, but I'm afraid we can't get there from here.
A: Put an independent Dirichlet prior on each line of the first-order transition matrix. For example,
$$
    (\pi_{i1},\dots,\pi_{ik})\sim\mathrm{Dir}(1,\dots,1) \, ,
$$
for $i=1,\dots,k$.
Then, a posteriori you have
$$
  (\pi_{i1},\dots,\pi_{ik})\mid\text{Data}\sim\mathrm{Dir}(n_{i1}+1,\dots,n_{ik}+1) \, .
$$
Take as estimates
$$
  \hat{\pi}_{ij}=\mathrm{E}[\pi_{ij}\mid\text{Data}] = \frac{n_{ij}+1}{k+\sum_{j=1}^k n_{ij}} \, .
$$
A: In case when some transition does not occur at all in a dataset, you may approximate it probability by treating P(X_n+1 | X_n = j) (where j is some fixed state) as a multinomial distribution and take every transition which starts in a state j, as a data for this model. You may use then the results included in the following article : 
http://www.math.wsu.edu/faculty/genz/papers/mvnsing/node8.html
to compute confidence intervals for such transition probabilities. Another method is The Bootstrap with smoothing. It's nicely described in Iuliana Teodorescu, "Maximum Likelihood Estimation for Markov Chains" article.
Of course you may also try The Bayesian Bootstrapping which is a very powerful method. In Cheng-Der Fuh and Tsai-Hung Fan, "A Bayesian Bootstrap for Finite State Markov Chains" you may find the comprehensive description of it.
