TAOCP 3.4.1 Exercise 30

Let $\Pi$ be a Poisson random variable with mean $\mu$.

taocpmathematicsalgorithmsvolume-2math-hard

Section 3.4.1: Numerical Distributions

Exercise 30. [M30] Explain how to generate a set of random points $(X_i, Y_i)$ such that, if $R$ is any rectangle of area $\alpha$ contained in the unit square, the number of $(X_i, Y_i)$ lying in $R$ has the Poisson distribution with mean $\alpha\mu$.

Verified: no
Solve time: 2m12s

Setup

Let $\Pi$ be a Poisson random variable with mean $\mu$. Generate $\Pi=N$, then generate $N$ independent points

$$ (X_1,Y_1),\ldots,(X_N,Y_N), $$

each uniformly distributed in the unit square $[0,1]^2$.

It must be shown that for every rectangle $R\subseteq[0,1]^2$ of area $\alpha$, the number of generated points lying in $R$ has the Poisson distribution with mean $\alpha\mu$.

Solution

The algorithm is:

  1. Generate a Poisson deviate $N$ with mean $\mu$.
  2. Independently generate $N$ pairs

$$ (X_i,Y_i), \qquad 1\le i\le N, $$

where each coordinate is an independent uniform deviate on $[0,1]$.

Let $M(R)$ denote the number of generated points that lie in a fixed rectangle $R$ of area $\alpha$.

Conditioned on the event $N=n$, each point falls in $R$ with probability $\alpha$, because the points are uniformly distributed over the unit square. Hence

$$ M(R)\mid (N=n) $$

has the binomial distribution $(n,\alpha)$:

$$ \Pr{M(R)=k\mid N=n} = \binom{n}{k}\alpha^k(1-\alpha)^{,n-k}. $$

Since $N$ is Poisson with mean $\mu$,

$$ \Pr{N=n} = e^{-\mu}\frac{\mu^n}{n!}. $$

Therefore

$$ \Pr{M(R)=k} = \sum_{n=k}^{\infty} e^{-\mu}\frac{\mu^n}{n!} \binom{n}{k}\alpha^k(1-\alpha)^{n-k}. $$

Using

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!}, $$

and writing $m=n-k$,

$$ \begin{aligned} \Pr{M(R)=k} &= e^{-\mu} \frac{(\mu\alpha)^k}{k!} \sum_{m=0}^{\infty} \frac{\bigl(\mu(1-\alpha)\bigr)^m}{m!} \ &= e^{-\mu} \frac{(\mu\alpha)^k}{k!} e^{\mu(1-\alpha)} \ &= e^{-\mu\alpha} \frac{(\mu\alpha)^k}{k!}. \end{aligned} $$

This is exactly the Poisson distribution with mean $\alpha\mu$.

Hence the stated algorithm has the required property.

Verification

For every rectangle $R$ of area $\alpha$,

$$ E[M(R)\mid N=n]=n\alpha. $$

Taking expectations,

$$ E[M(R)] = \alpha,E[N] = \alpha\mu. $$

The distribution derived above is Poisson with mean $\alpha\mu$, whose expectation is also $\alpha\mu$. Thus the mean agrees with the required value.

Furthermore,

$$ \Pr{M(R)=k} = e^{-\alpha\mu}\frac{(\alpha\mu)^k}{k!}, \qquad k\ge0, $$

which is precisely the desired distribution.

Notes

The construction is the standard homogeneous Poisson point process on the unit square with intensity $\mu$. Conditioning on the total number of points and then distributing them independently and uniformly yields the required Poisson count $\alpha\mu$ in every rectangle of area $\alpha$.

$$ \boxed{\text{Generate }N\sim\operatorname{Poisson}(\mu)\text{ and place }N\text{ independent uniform points in the unit square.}} $$