The Poisson, Exponential, and Uniform

Three distributions, all connected

September 20, 2018

Until recently, I had trouble remembering the pdf of the Poisson distribution. The expression

\dfrac{e^{-\lambda} \lambda^n}{n!}

didn’t make much sense to me. I knew the Poisson could be derived as the limit of the binomial distribution, but that didn’t help my memory much.

Here’s an alternative method of deriving the Poisson’s pdf that I personally find much more intuitive. Suppose we have a Poisson process with parameter \lambda , and let the hits of this process occur at t_1, t_2, … Define d_i as the wait time between hits:

d_i=\begin{cases} t_1, & i = 1,\\ t_i - t_{i-1}, & i > 1 \end{cases}

And note that t_i=\sum_{j=1}^i d_j . It’s well known that d_i \sim Exponential(\lambda) . The pdf of the Poisson at n is equal to the probability of getting exactly n hits in the first unit of time. We both need the n th point to be within the first unit of time, and the n+1 th to be after the first unit of time. Writing this out as math and using d_i we get:

P(t_n\le1, t_{n+1}>1) = P\left(\sum_{i=1}^n d_i\le1, d_{n+1}+t_n>1\right)

We can compute this by integrating over all combinations of d_i ( 1\le i\le n ; d_{n+1} to be considered later) that satisfy \sum_{i=1}^n d_i\le1 . For each combination, we compute the likelihood of those d_i being drawn and of drawing a d_{n+1} that satisfies d_{n+1}>1-t_n=1-\sum_{i=1}^n d_i .

\begin{eqnarray*} \int\limits_{u_1+u_2+\cdots+u_n\le1} & P(d_{n+1}>1 - t_n)\prod_{i=1}^n P(d_i=u_i) \\ = \int\limits_{u_1+u_2+\cdots+u_n\le1} & \exp(-\lambda(1-t_n))\prod_{i=1}^n \lambda e^{-\lambda u_i} \\ = \int\limits_{u_1+u_2+\cdots+u_n\le1} & \exp(-\lambda(1-t_n))\lambda^n \exp(-\lambda \sum_{i=1}^n u_i) \\ = \int\limits_{u_1+u_2+\cdots+u_n\le1} & \lambda^n e^{-\lambda} \end{eqnarray*}

So in fact we’ve been integrating a constant this whole time. All that’s left to do now is compute \int\limits_{u_1+u_2+\cdots+u_n\le1} 1 dV which corresponds to the volume of an n -dimensional simplex. The answer is guessable (a 2D simplex has area half; 3D, a sixth; n dimensions, probably 1/n! ) but it can also be derived by looking at the problem back in t_i space rather than d_i space. A valid set of d_i leads to 0\le t_1\le t_2\le \cdots\le t_n\le 1 ; each t_i is in the range [0, 1] and they must be in ascending order. Consider the unit n -dimensional hypercube where each point corresponds to a choice of t_i satisfying t_i\in [0,1] . We’d expect 1/n! of the volume of our hypercube to be occupied by t_i arranged in ascending order because are n! ways to arrange n items, and by symmetry they’re equally likely. The hypercube itself has volume 1 so our integral evaluates to 1/n! .

Putting everything together, we get e^{-\lambda}\lambda^n/n! as desired. I guess the TL;DR is that the Poisson’s pdf can be thought of as “the exponential distribution, evaluated at 1/n , raised to the n th power, divided by n!

More abstractly…

It’s tempting to conclude from our constant integrand that spacing points according to an exponential distribution leads to a uniform distribution of points. This clearly isn’t true though, because uniform distributions are on bounded intervals while the exponential distribution isn’t. The following procedure, however, will generate points following a uniform distribution:

  • Start at zero
  • Repeat n times:
    • Get a sample x from Exponential(\lambda)
    • Move right by x
    • If we’re right of 1, clear everything and restart the procedure
    • Place a point on the current position
  • Get a sample x from Exponential(\lambda)
  • Move right by x
  • If we’re not right of 1, clear everything and restart the procedure

In fact, we can show that the actual distribution of x (the exponential, conditioned on the procedure not restarting) matches the distribution of space between samples:

P(x_1=a | \text{things worked})=\dfrac{\int\limits_{a+u_2+\cdots+u_n\le1} P(x_1=a, x_2=u_2, … x_n=u_n)P(x_{n+1}>1-\sum_{i=1}^n x_i)}{\int\limits_{u_1+\cdots+u_n\le1} P(x_1=u_1, … x_n=u_n)P(x_{n+1}>1-\sum_{i=1}^n x_i)}

Where the top integral is over u_2,…,u_n and the bottom is over u_1,…,u_n . As shown earlier, the integrand for either integral is (the same) constant, so our expression simplifies to a ratio of volumes. We know the volume of the simplex defined by u_1+\cdots+u_n\le1 is 1/n! . The shape defined by a+u_2+\cdots+u_n\le1 is also a simplex, but in n-1 dimensions and scaled down by a factor of 1-a . So, its volume is (1-a)^{n-1}/(n-1)! . Dividing the two, we get


which is exactly what the distribution should be.