N-gram language model question
For these 2-word sentences, notice that the original equation for the MLE approximation of the probabilities of the bigram is:
$$P(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)}{\sum_w{C(w_{i-1}w)}} = \frac{C(w_{i-1}w_i)}{C(w_{i-1})}, $$
where the denominator $C(w_{i-1})$ only equals the count of $w_{i-1}$ iff there is an end-symbol $\text{&lt;/s&gt;}$, otherwise the number of times $w_{i-1}$ appears at the end of the sentence has to be subtracted from its count. Therefore, the &quot;count&quot; function you are using in the denominator is wrong, and the true probabilities in your particular corpus are:
$$\begin{equation}
\begin{split}
P(a|a) &amp;= \frac{C(aa)}{C(a)} &amp;= \frac{1}{2} \\
P(b|a) &amp;= \frac{C(ab)}{C(a)} &amp;= \frac{1}{2} \\
P(a|b) &amp;= \frac{C(ba)}{C(b)} &amp;= \frac{1}{2} \\
P(b|b) &amp;= \frac{C(bb)}{C(b)} &amp;= \frac{1}{2} \\
P(a|\text{&lt;s&gt;}) &amp;= \frac{C(\text{&lt;s&gt;}a)}{C(\text{&lt;s&gt;})} = \frac{2}{4} &amp;= \frac{1}{2} \\
P(b|\text{&lt;s&gt;}) &amp;= \frac{C(\text{&lt;s&gt;}b)}{C(\text{&lt;s&gt;})} = \frac{2}{4} &amp;= \frac{1}{2} \\
\end{split}
\end{equation}$$
and now the sum of the probabilities of all possible 2-word sentences with this vocabulary becomes equal to 1:
$$\sum_{w, v\in\{a, b\}^2}P(\text{&lt;s&gt;}wv) = \sum_{w, v\in\{a, b\}^2} P(w|\text{&lt;s&gt;})\cdot P(v|w) = \sum_{w, v\in\{a, b\}^2} \frac{1}{4} = 1 .$$