Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you have an alphabet with two words, a,b and a long string of these letters. You measure the probability of finding an $a$ or $b$ to be $p(a)=3/4$ and $p(b)=1/4$. You expect that the probabilities for finding letter pairs should be $$ \begin{align} p'(aa) &= p(a)^2 &= 9/16 \\ p'(ab) &= p(a)p(b) &= 3/16 \\ p'(ba) &= p(b)p(a) &= 3/16 \\ p'(bb) &= p(b)^2 &= 1/16 \\ \end{align} $$

but instead you find them to be something different, say for example $$ \begin{align} p(aa) &= 19/32 \\ p(ab) &= 5/32 \\ p(ba) &= 5/32 \\ p(bb) &= 3/32 \\ \end{align} $$

which implies there is some correlation between the letters. Given 1-gram $p(x_1)$ and 2-gram $p(x_1x_2)$ what are the 3-gram $p(x_1x_2x_3)$ probabilities? In general, what are the n-gram probabilities $p(x_1\ldots x_n)$ given the previous n-1 measurements?

My confusion stems from the fact that I'm not sure how to put the different levels together, i.e. if the expected $p'(abb)$ simply $p(ab) p(bb)$ doesn't this discard the information from $p(a), p(b)$? Likewise for the n-gram, does using only the (n-1)-gram information throw something away?

Edit: The comments indicate a few things that may prevent an answer. For one, instead of saying "we expect", this should be "we expect if the distribution was uniform". The question of the underlying distribution is clearly important for an exact answer. However, what can we say about the 3-grams given the information about the 2 and 1-grams?

share|improve this question
It depends on what your system is. It could depend on the last letter, the last two, etc. –  Narut Sereewattanawoot May 10 '13 at 21:39
Your sentence beginning "You expect that the probabilities...." is forcing me to make the assumption that letter choices are made independently which you tell me is not supported by the facts. Similarly, given 1-gram and 2-gram probabilities does not allow for the computation of 3-gram probabilities unless one makes the unrealistic assumption that the 2-gram choice is independent of the previous 1-gram choice. Yes, lots of things are thrown away when you proceed along the lines you have thought of. Read Shannon's paper A Mathematical Theory of Communication for a nice description of the issues –  Dilip Sarwate May 10 '13 at 21:40
@DilipSarwate Thanks for the reference, it looks excellent ... I've never seen a paper with so many citations! I've updated the question to hopefully make it more tractable. –  Hooked May 11 '13 at 2:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.