# Peculiar form of the chain rule of probability

I was reading a textbook (equation 4.3) on n-gram models and came across this form of the chain rule of probability: \begin{align*} P(X_1 = x_1, \ldots, X_n = x_n) &= P(X_1=x_1) \cdot P(X_2=x_2 \mid X_1=x_1) \cdot \\ &\quad \cdot P(X_3=x_3 \mid X_1^2=x_1^2) \cdots P(X_n=x_n \mid X_1^{n-1}=x_1^{n-1}) \end{align*}

Here the random variable $X$ is the $i$-th word in some sentence. This is for n-gram models. So $P(X_1=x_1,\ldots, X_n-x_n)$ is the probability of a certain sentence $(x_1,\ldots, x_n)$ with $n$ words.

Does anyone know why you can condition on $X_1$ to the power of $1$, $2$, or etc? How is it the same as this form: \begin{align*} P(X_1=x_1, \ldots, X_n=x_n) &= P(X_1=x_1) \cdot P(X_2=x_2 \mid X_1=x_1) \cdot \\ &\quad \cdot P(X_3=x_3 \mid X_2=x_2, X_1=x_1) \cdot \\ &\quad \cdots P(X_n \mid X_{n-1}=x_{n-1},\ldots, X_1=x_1) \end{align*}

I tried googling and I seem to only find the latter form.

I am fairly certain that the source you linked to is using $X_1^k$ as shorthand for $X_1,\dots,X_k$ (sort of like $(X_i)_{i=1}^k$). This seems reasonable because they later go on to say they'll approximate $P(w_n \mid w_1^{n-1})$ by $P(w_n \mid w_{n-1})$. They then define the $N$-gram model, which looks $N-1$ words in the past, by the approximation $P(w_n \mid w_1^{n-1} ) \approx P(w_n \mid w_{n-N+1}^{n-1})$. If this is intended to condition on the previous $N-1$ words, then $w_{n-N+1}^{n-1}$ should indeed be shorthand for $w_{n-N+1},\dots,w_{n-1}$.

• Yes, that's exactly it: $x_1^n$ stands for $(x_1, ..., x_n)$. – Marcelo Ventura Jun 10 '16 at 5:15
• Also, "approximate $P(w_n \mid w_1^{n-1})$ by $P(w_n \mid w_{n-1})$" means they assume that Markovian loss of memory applies as a good approximation. – Marcelo Ventura Jun 10 '16 at 5:17

It appears to be an annoying shortened notation -- one which should never be used without a clearly highlighted explanation because it can easily be confusing.   I hate those.

The relevant introduction is buried in paragraph 3, on page 3.

For this reason, we’ll need to introduce cleverer ways of estimating the probability of a word $w$ given a history $h$, or the probability of an entire word sequence $W$.   Let’s start with a little formalizing of notation. To represent the probability of a particular random variable $X_i$ taking on the value “the”, or $P(X_i =$“the”$)$, we will use the simplification $P($the$)$.   We’ll represent a sequence of $N$ words either as $w_1 \ldots w_n$ or $w^n_1$.   For the joint probability of each word in a sequence having a particular value $P(X = w_1,Y = w_2,Z = w_3, \ldots, W = w_n)$ we’ll use $P(w_1,w_ 2, \ldots ,w_n)$.

$\ddot\frown$