How to calculate the probability of the next value in a Random Sequence

Question

Assuming that $X$ is the next value in a finite length random sequence, e.g. $$ abbcccaaccbacccabbacababaccccbacabcbacacX $$what would be the $2$-letter most likely to correspond to the value of $X$

1. ($a$ and $b$)
2. ($a$ and $c$)
3. ($b$ and $c$)

What I'm looking for is a formula with which to meet the $2$ letters that are more likely to be the next letter in the sequence

Answer 1

It would really help to know something about the process that generated the sequence. There are many possibilities, but here are two ways to look at it:

If we assume each letter appears independently of any other, so that this is just a sequence of draws from a simple probability distribution, then we can estimate the probabilities based on the frequency of each letter occurring.

$fr(a) = 13 \\ fr(b) = 10 \\ fr(c) = 17$

Dividing those frequencies by the total number of letters, 40, gives us the estimated probabilities:

$Pr(a) = \frac{13}{40} = 0.325 \\ Pr(b) = \frac{10}{40} = 0.25 \\ Pr(c) = \frac{17}{40} = 0.425$

Then, since the probabilities of each letter are independent, we can see that:

$Pr(ab) = Pr(a)Pr(b) = 0.08125 \\ Pr(ac) = Pr(a)Pr(c) = 0.138125 \\ Pr(bc) = Pr(b)Pr(c) = 0.10625$

This is assuming that the letters appear in that order, if order doesn't matter, double each of those probabilities. Then of these options, "ac" is the most likely, followed by "bc", with "ab" the least. The probabilities don't add to 1 because there are three possibilities missed - those of one letter appearing doubled.

Alternatively, we could assume that this is generated by a nice simple Markov chain model where the probability of a given letter depends only on the letter before it. We can estimate those probabilities based on how often a given letter appears after another one. In that case, we have (using the shorthand of $Pr(X|Y)$ meaning the probability that X appears given that the last letter was Y):

$Pr(a|a) = 0.0769 \\ Pr(b|a) = 0.3846 \\ Pr(c|a) = 0.5385 \\ Pr(a|b) = 0.6 \\ Pr(b|b) = 0.2 \\ Pr(c|b) = 0.2 \\ Pr(a|c) = 0.3125 \\ Pr(b|c) = 0.1875 \\ Pr(c|c) = 0.5$

So this time, using the fact that we're running off a previous "c", let's look at the probabilities of the various combinations working off the fact that $Pr(XY|Z) = Pr(X|Z)Pr(Y|X)$:

$\begin{array}{l l l} Pr(aa|c) = 0.024 & Pr(ab|c) = 0.120 & Pr(ac|c) = 0.168 \\ Pr(ba|c) = 0.113 & Pr(bb|c) = 0.038 & Pr(bc|c) = 0.038 \\ Pr(ca|c) = 0.156 & Pr(cb|c) = 0.094 & Pr(cc|c) = 0.250 \end{array}$

If we collapse the probabilities for ab & ba, and so forth, we get:

$Pr(ab) = 0.233 \\ Pr(ac) = 0.324 \\ Pr(bc) = 0.132$

So again, ac is more likely than ab, which is more likely than ac, although the specific probabilities did change a little.

That said, the transition probabilities were calculated on not much data, and you definitely wouldn't want to try to infer some more complicated Markov process based on the small length of the sequence. Even what I've put here has a pretty big margin of error involved.

Answer 2

I notice that b never follows ac. Therefore, I would think that b would be the least likely to follow ac.