How to calculate chain probabilities Consider a machine that produce sequential letters, like so;
A -> X -> T -> U -> ...
I will be using this notation in this question:
P(U) -> denotes probability of a letter being U.
P(U(t)|X(t-1)) -> denotes probability of a letter being U at time t, given that at at time t-1, letter was X. In other words, probability of letter U following letter X
P(U(t)|X(t-2)) -> denotes probability of a letter being U at time t, given that at at time t-2, letter was X. In other words, probability of letter U following letter X and some other character.
How can I calculate next character being U after observing this sequence A -> X -> T given that we know P(U), P(U(t)|T(t-1)), P(U(t)|X(t-2)), P(U(t)|A(t-3)) from historical data.
For example, assume I sampled 1 million characters coming out of this machine, and I have calculated that %5 percent of all the character were letter U. I have also observed that whenever I have observed letter T there is an 80% probability that U will be the next letter. Moreoever, I have also observed that there is there is 0.05% probability that whenever I  see letter X, two letters later I will observe the letter U.
My question is, if I keep running the machine, and observe X and then T, what is the probability that I will observe U next. Moreover, how can I generalize this calculation, so that I can check last 5 or 10 letters the calculate the probability of next character being U
 A: You are stating you have empirically computed $P(X_t | X_{t-i}), 1 \leq i \leq 3$ and need $P(X_t | X_{t-1}, X_{t-2}, X_{t-3})$ where $X_t$ is the letter appearing at time $t$.
By the conditional probability definition:
$$P(X_t | X_{t-1}, X_{t-2}, X_{t-3}) = \frac{P(X_t, X_{t-1}, X_{t-2}, X_{t-3})}{P(X_{t-1} | X_{t-2}, X_{t-3}) P(X_{t-2}|X_{t-3}) P(X_{t-3}) }$$
First, you don't know every $P(X_t, X_{t-1}, X_{t-2}, X_{t-3})$. But you can approximate using a kind of Laplace smoothing, ie, initially giving every case one dummy sample to prevent zero probabilities, and then count all the data you have. Even so, they grow exponentially like @combo refers for the translation of the Higher-Order Markov Chain, and some memory tricks might be needed.
Second, you could simplify and consider that $P(X_{t-1} | X_{t-2}, X_{t-3}) \approx P(X_{t-1} | X_{t-2})$ or do a similar smoothing as before for $P(X_{t-1}, X_{t-2}, X_{t-3})$.
Anyway, let's not forget these are simplifications. They might not work in your application.
