# N-gram language model question

I have this question I found regarding n-gram modelling in the Speech and language processing text book:

Suppose we didn't use the end symbol </s>. Train an unsmoothed bigram grammar on the following corpus without using the end-symbol </s>.

<s> a b
<s> b b
<s> b a
<s> a a

Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2 word sentences over the alphabet {a, b} is 1.0 and the sum of the probability of all possible 3 word sentences over the alphabet {a, b} is also 1.0.

Note: <s> means beginning of sentence.
</s> means end of sentence.


My attempt was:

Two word sentences:
P(a | b) = count(b a) / count(b) = 1 / 4
P(b | a) = count(a b) / count(a) = 1 / 4
P(a | a) = count(a a) / count(a) = 1 / 4
P(b | b) = count(b b) / count(b) = 1 / 4


sum = 1

but when I get to 3 word sentences:

P(a | a, a) = count(a a a) / count(a) = 1 / 64

Now, you get 8 three word sentences which sums to 8 / 64

This is where I am getting lost. I need some pointing in the right direction.

in the Trigram model:

$$P(w_k|w_1, . . . ,w_{k−1}) =P(w_k|w_{k−2},w_{k−1})$$

hence, the Probability of sentence $$w_1....w_N$$ is as follows:

$$\prod_{k=1}^N {P(w_k|w_{k−2}w_{k−1})}$$

and $$P(w_3|w_2,w_1) = \cfrac{count(w_3,w_2,w_1)}{count(w_2,w_1)}$$

in words: you must divide $$count(w_3,w_2,w_1)$$ by the number of times $$(w_2,w_1)$$ appeared one after the other, and not separately. Then it should sum to $$1$$.

I m not sure, but I think this will help you. Here we use the tri-gram model, because the bi-gram model is not used for 3 words, and the answer is not the same as the bi-gram model for this corpus. $$P(a|a,b) = 0/1 = 0$$ $$P(b|b,a) = 0/1 =0$$

Similarly, all combinations of $$\{a,b\}$$ have a zero answer.