How to estimate transition probabilities in markov model for a given string of observations?

Question

I have strings of observations of states. How would I estimate transition probabilities if I want to model the source of the symbols in my string as a Markov model of some order? I would prefer the method to be general and simple to express in terms of matrices but other approaches will also be welcome.

Answer 1

Let's consider first order k=1. You can create a frequency table for the symbols following each particular symbol in your string and the probabilities in this tables could be estimations of the true transitional probabilities. For ex. if I have the symbol A occuring 100 times in the given string and the symbols next to A are: B-exactly 40 times, C-30 times and D- 30 times, then an estimation for the transitional probabilities is $\hat{P}(A\to B) = 0.4$, $\hat{P}(A\to C) = 0.3$,$\hat{P}(A\to D) = 0.3$. This will be the MLE given the data.

If the order is $k=2,3,\ldots$, you may create similar tables for every pair, triple, etc. of symbols occuring consecutively in the string.