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

  • $\begingroup$ I take it you have these data for all possible $t$, not just a specific $t$. (If you do not, it looks like your question would be unanswerable.) Put a little more abstractly it asks, "how can I calculate a probability given that I have three ways to find its value from historical data?" As such, it sounds like you already have three answers. Are you asking how to combine them if they disagree with each other? If so, you need to describe those historical data and how you used them to estimate the conditional probabilities. If not, you need to clarify your question. $\endgroup$
    – whuber
    Sep 6 '17 at 14:50
  • $\begingroup$ @whuber I have add an example, is it clear now? $\endgroup$
    – yasar
    Sep 6 '17 at 16:45
  • $\begingroup$ Do you assume that $P(U(t)\mid X(t-1)) = P(U(\tau) \mid X(\tau-1))$ for $t\neq\tau$, or does the value of $t$ matter? If only the delay matters (which I assume, since this has a markov process tag), then you can write this as a standard markov process with state expanded to include recent history. Note the complexity increases exponentially in your history length. $\endgroup$
    – combo
    Sep 7 '17 at 6:51
  • $\begingroup$ @combo I am assuming probabilities doesn't change over time, as you suggest $\endgroup$
    – yasar
    Sep 7 '17 at 10:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.