There's a footnote in Jurafsky & Martin (2008, p.89) pointing out that, without an end-symbol, an n-gram model would not be "a true probability distribution". Even after seeking the paper they've referenced, I could not get the point. Here is the example and the footnote:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

About the end-symbol, </s>, the authors say:

"We need the end-symbol to make the bigram grammar a true probability distribution. Without an end-symbol, the sentence probabilities for all sentences of a given length would sum to one, and the probability of the whole language would be infinite."

Could someone help me to interpret the quoted part above? Or, does anybody know about some resource that could help me understand what is the need for an end-symbol in n-gram models?

  • 1
    My understanding is that a sequence n-1 may occur more frequently at the end of sentences, but your model won't take this into account unless you use </s>.
    – fenceop
    Feb 24, 2015 at 16:18
  • This is the intuitive way to implement ngrams. I played with them a few times for markov chains when I was younger, without formal stuff like this to tell me what to do. It was obvious to have a special start and end token. Did you try another way to implement it? Is it as simple? Feb 24, 2015 at 17:02
  • I agree with both of you. That's really intuitive. But let's suppose you have a bad text, with just a few periods (some people seem to replace them by commas). In such a context, it would not be easy to mark sentence endings with end-symbols. Then is it right to infer from the book that probabilities would just blow up and the use of n-grams would become invalid?
    – mcrisc
    Feb 24, 2015 at 19:17
  • Ah well now you're talking about a real problem! I think many people implement punctuation in various ways. I tried one token per symbol and one token per run of symbols, where symbol means neither a letter nor whitespace. The terms you should read up on are "sentence segmentation" and "sentence splitting". Segmentation is also a general problem at every level of spoken and written NLP. Feb 25, 2015 at 3:43
  • You've thrown some light on the problem. I think my mistake was not considering that n-grams should be counted in the context of sentence boundaries. So, my real problem is finding those boundaries. Thanks for your help!
    – mcrisc
    Feb 25, 2015 at 15:11

3 Answers 3


Without loss of generality, let's consider a bigram model (looking at two words at a time), without a beginning or end marker. Let's also assume our language has at least one sentence of length two, at least one sentence of length three, and at least one sentence of length four.

What's the probability of seeing the sentence "I am", with nothing before or after it? In our model, it would be $P("I") \times P("am"|"I")$: the odds of seeing "I", times the odds of seeing "am" when you've already seen "I".

Now, what's the probability of seeing any sentence of length two in this model? We can see it should be $\sum_v \sum_w P(v) \times P(w|v)$: same as above, but summing over all possible words instead of just "I" and "am".

But this is the same as $\sum_v P(v) \sum_w P(w|v) = \sum_v P(v) \times 1$, by laws of probability. And we know that $\sum_v P(v) = 1$. Therefore the probability of having a sentence of length two is 1.

And this is a problem. Because we know that there are also sentences that are not length two. You can repeat this proof with length three, and find that the probability of having a sentence of length three is also 1. And same for four, and so on…

But we want the probability of seeing a sentence to be 1, because that's how probability works, which means the probability of seeing a sentence of length two (and the probability of seeing a sentence with length three, and…) has to be less than 1.

It turns out, adding a sentence-end marker fixes this. Because now when we're taking that sum over $v$ and $w$, we can specify that $w="</s>"$, and the sum becomes $\sum_v P(v,"</s>")$, which is significantly less than 1. I won't prove it here, but you can go through some tedious probability math to show that adding beginning and ending markers makes the probability distribution valid (the probability of seeing a sentence at all is now 1).

P.S. If you find the LaTeX source fragments annoying to read, vote here to get proper rendering support on this site!

  • Am I reading you well that after adding <sentence_start> and <sentence_end> tokens the sum of probabilities for all possible sentences generated from given corpus (given n-grams) magically becomes 1? Can you point to a proof of this magic? Sep 25, 2019 at 19:29
  • @SergeyBushmanov I'll look for one; the proof isn't too hard (I had to write it all out once for an exam) but it's also really tedious with a lot of intermediate values.
    – Draconis
    Sep 25, 2019 at 19:45
  • Well, if you say adding <eos> tag is enough to make probability distribution well behaving and it's provable that's enough. Thank you! Though, having a link to proof may still be useful. Many thanks again for taking your time! Sep 25, 2019 at 20:04
  • @SergeyBushmanov Intuitive explanation: without an <eos> tag, there's no distinction between "the probability of seeing two words next to each other" and "the probability of seeing a two-word sentence". The <eos> tag lets you distinguish the two, which is good, because the sum of "the probability of seeing an N-word sentence" for all N should be 1, but the sum of "the probability of seeing N words next to each other" for all N should be significantly higher than that (because the probability of seeing one word, ever, at all, should be extremely high—and that's just the N=1 case!).
    – Draconis
    Sep 25, 2019 at 20:37
  • Interesting problem here! I'll write the proof myself. Hope you can double-check it if you have time @Draconis May 25, 2023 at 18:54

It turns out Bigram will give a true probability distribution

The previous version of the textbook shows its reference for this statement (you can search it online)

"Chen and Goodman (1998) We need the end-symbol to make the bigram grammar a true probability distribution. Without an end-symbol, the sentence probabilities for all sentences of a given length would sum to one, and the probability of the whole language would be infinite.”

I found the paper Chen and Goodman (1998).

enter image description here

bi-gram is just an approximation of n-gram.

If you work on the exercise from the book 3.5, by appending </s>:

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

P(a | <s>) = 0.25
P(a | a) = 0.25
p(</s> | a) = 0.5

# you get a tree
      a             b
   a  b </s>     a  b </s>

P(L=1) = 0.5, P(L=2) = 0.25 ... P(L = N) = P(L=N-1) / 2

The sum of all P(L) will be 1.

helpful deck: https://courses.grainger.illinois.edu/cs447/fa2020/Slides/Lecture03.pdf enter image description here enter image description here


This is my own proof for this problem. Hope it helps someone who are struggling with this problem himself.

The problem:

Why do we need the end-of-sentence(eos) marker at all?

It boils down to this interesting definition of "what is a sentence"?

  1. Without a eos marker: We're compelled to this definition:

A sentence of length n is a word sequence of length n.

As @Draconis pointed out, there's no real difference between a n-long word sequence and a n-long sentence! This is what causes the problem here. The sum of probability of all sentence of length n is equals to 1, which is something we don't want because we want the model to output something more useful: the probability of a n-long sentence in the sample space of all sentences(arbitrary length), not in the sample space of sentences of length n.

  1. With a eos marker(game-changer): We have the new definition of a sentence:

A sentence of length n is a word sequence of length (n + 1) with the last word being eos

Problem solved! The sum of probability of all sentence of length 2 is now:

$\sum_v \sum_w P(v,w,eos) <= \sum_v \sum_w \sum_t P(vwt) = 1$. So are sentence of length n

What's left is to prove: $sum_u P(u,eos) = 1$ for all u is the word sequence of a sentence.

sum_u P(u, eos) = sum_u(P(?, eos) * P(u | eos)) = P(?, eos) * sum_u P(u |eos). I claim that sum_u P(u | eos) = 1 / P(?, eos).

Indeed, we denote:

number of word occurrences(including duplicates) as C_w.
number of word sequence (u, eos) as C(u, eos)
number of word sequence that ends with eos as C(?, eos)

Now, P(?, eos) = C(?, eos) / C_w. Furthemore:

Sum_u P(u | eos) = sum_u C(u, eos) / C(?, eos) = (sum_u C(u, eos)) / C(?, eos) = C_w / C(?, eos) = 1 / P(eos). Q.E.D

  • Assuming P(eos) < 1, then 1 / P(eos) > 1, which violates the probability axiom since sum_u(P(u|eos)) should be 1.
    – Izana
    Aug 21, 2023 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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