Laplace's law of succession

This is Laplace's first attempt to estimate probabilities of events occurring consecutively in a sequence. Its goal is to estimate the probability of an event occurring $n+1$ times in succession given that the event occurred $n$ times in succession.

The law can be found using the following reasoning :

Suppose that we have $N+1$ coins that we label from $0$ to $N$. Each coin has a different probability of landing on the head. The coin $i$ lands on the head with a probability of $i/N$. We assume that the coins can be chosen with an uniform probability. We can then choose a coin and toss it again and again.

So the probability that the first $n$ toss are all heads for this particular coin is given by :

$$P(n\: heads\vert coin=i)=\left(\frac{i}{N}\right)^n$$

So, the probability of observing $n$ tosses in a raw in this experiment is :

$$F_{N,n}=P(n\: heads)=\sum_{i=0}^NP(coin=i)\cdot P(n\: heads\vert coin=i)=\frac{1}{N+1}\sum_{i=0}^N\left(\frac{i}{N}\right)^n$$

Furthermore :

$$P(n+1\: heads\vert n\: heads)\cdot P(n\: heads) = P(n\: heads\vert n+1\: heads)\cdot P(n+1\: heads)$$

If the first $n+1$ toss are all heads, the first $n$ toss are all heads too, so

$$P(n\: heads\vert n+1\: heads)=1$$

and

$$P(n+1\: heads\vert n\: heads)=\frac{F_{N,n+1}}{F_{N,n}}$$

We want this to be true in general and not only for a finite number of possible probabilities $\left\{\frac{i}{N}\right\}_i$. In order to do that, we have to take an infinite number of coins with probabilities describing the possible range of probabilities $\left[0,1\right]$. The probability we are looking for becomes :

$$P(n+1\: heads\vert n\: heads)=\lim_{N \to \infty} \frac{F_{N,n+1}}{F_{N,n}}$$

The properties of integrals give us :

$$\lim_{N \to \infty} F_{N,n}=\int_0^1x^n\:dx=\left[\frac{x^{n+1}}{n+1}\right]_0^1=\frac{1}{n+1}$$

So we can express the solution with this simple formula :

$$P(n+1\: heads\vert n\: heads)=\frac{n+1}{n+2}$$

This is a particular case of the Laplace's law of succession in order to give the reader a feeling of the demonstration. The important property of the demonstration that we have to notice is that we used an uniform probability for the coin at the beginning of the demonstration. That mean that a uniform prior is required to apply the formula. In practice we do not know the distribution of the priors. Furthermore, the priors may depend on the context, so we certainly cannot compute them and thus we have to make a choice. It has also be proved (see [34] for instance) that the Laplace's formula is more general and gives the same result with other forms of prior probabilities.

In our case, the formula can be extended and we can compute the probability of a sequence $s$ being sampled next given that we observed a sequence of $N_s$ sequences [34] . An estimation of the probability of the sequence $s$ is :

$$P(s)=\frac{n_s+1}{N_s+\vert\Sigma\vert}$$

This way of estimating the probabilities has been originally used by Ron et al. to train variable length Markov model [51].