Poisson approximation by coupling

This paper employs the coupling technique and elementary probability results to establish a general proof for approximating a binomial distribution with a Poisson distribution, offering a more robust alternative to the standard asymptotic convergence approach found in undergraduate texts.

The Gist

Imagine you are trying to predict how many times a rare event will happen. Maybe it's how many times a specific typo appears in a long book, or how many times a bus is late in a month.

In the world of probability, there are two main ways to model these situations:

1. The "Counting" Method (Binomial): You have a fixed number of chances (like 1,000 pages in a book), and each chance has a tiny probability of the event happening. You count the successes.
2. The "Flow" Method (Poisson): You assume the event happens randomly over time or space with an average rate.

For a long time, math textbooks have taught us that if you have a lot of chances and the probability of each is very small, the "Counting" method looks almost exactly like the "Flow" method. They say, "As the number of chances goes to infinity, the two become the same."

The Problem:
The old way of teaching this is like saying, "If you walk far enough, you'll eventually reach the ocean." It's true, but it doesn't tell you how far you are from the water right now. It doesn't give you a safety margin or a guarantee of how close you are at any specific moment.

The New Approach (The Paper's Contribution):
This paper, written by Rinaldo Schinazi, introduces a clever trick called "Coupling." Think of coupling not as a mathematical formula, but as a magic synchronization tool.

The Magic Synchronization (Coupling)

Imagine you have two runners:

• Runner B (Binomial): He runs a race with $n$ steps. At each step, there is a tiny chance he trips.
• Runner L (Poisson): He runs a race where he is expected to trip a total of $np$ times on average.

Usually, we compare them by looking at their final scores from a distance. But Coupling forces them to run side-by-side on the same track, using the same "randomness" (like the same wind or the same uneven pavement) to decide when they trip.

The paper shows that if you force these two runners to use the same random inputs, they will almost always trip at the exact same time.

• If the wind blows, they both trip.
• If the pavement is smooth, they both keep running.

The only time they differ is when the "wind" is just strong enough to trip one but not the other. The paper proves that the expected number of times they will be out of sync is incredibly small.

The "Error" Guarantee

The paper's main result is a simple promise:

"No matter how many steps you take ($n$) or how likely a trip is ($p$), the difference between the probability of the Binomial runner and the Poisson runner is always less than $n \times p^2$."

Think of $p^2$ as the "squared risk." Since $p$ is usually a tiny fraction (like 0.01), $p^2$ is microscopic (0.0001). Even if you multiply that by a large number of steps ($n$), the total error remains very small.

Why This Matters (In Simple Terms)

1. It's a Safety Net: Unlike the old textbooks that only talked about the "limit" (the distant future), this paper gives you a bound. It tells you exactly how wrong you might be right now, even if you only have a few trials.
2. It's Elementary: The author didn't use complex, graduate-level math. He used basic probability concepts (like rolling dice or drawing numbers from a hat) to prove a very strong result.
3. It's General: This logic works not just for simple cases, but can be adapted to more complex scenarios where the "chances" aren't all identical.

The Bottom Line

The paper says: "You can use the simpler Poisson model to approximate the complex Binomial model, and we can prove exactly how close the approximation is using a simple, side-by-side comparison technique."

It turns a vague "they get closer eventually" into a concrete "they are this close, guaranteed."

Technical Summary

Technical Summary: Poisson Approximation by Coupling

Problem Statement
The paper addresses the classical problem of approximating a Binomial random variable $B$ with parameters $(n, p)$ by a Poisson random variable $L$ with parameter $\lambda = np$. While standard undergraduate texts establish the convergence in distribution (showing that $P(B=k) \to P(L=k)$ as $n \to \infty$ and $np \to \lambda$), the author notes that this approach fails to provide a quantitative bound on the approximation error for finite $n$ and $p$. The goal is to derive a rigorous error bound valid for all $n \ge 1$ and $p \in (0, 1)$.

Methodology: Coupling
The paper employs the coupling technique, a probabilistic method attributed to Wolfgang Doeblin in the 1930s. Unlike convergence proofs that rely on asymptotic limits, coupling constructs two random variables on the same probability space to compare them directly.

The proof proceeds in three stages:

1. Elementary Coupling (Bernoulli vs. Poisson): The author constructs a coupling between a single Bernoulli random variable $B$ (parameter $p$) and a Poisson random variable $L$ (parameter $p$) using a single uniform random variable $U \sim \text{Uniform}(0, 1)$.

   • $B$ is defined as $0$ if $U < 1-p$ and $1$ if $U > 1-p$.
   • $L$ is defined based on the cumulative sums of Poisson probabilities ($r_k = e^{-p}p^k/k!$). Specifically, $L=0$ if $U < r_0$, and $L=k$ if $s_{k-1} < U < s_k$ (where $s_k$ is the partial sum of probabilities).
   • The expected absolute difference is calculated as $E|L - B| = 2(e^{-p} - (1-p))$. Using the inequality $2(e^{-p} - (1-p)) \le p^2$, the author establishes that $E|L - B| \le p^2$.

2. Extension to Sums (Binomial vs. Poisson): The construction is extended to $n$ independent uniform random variables $(U_i)_{1 \le i \le n}$.

   • For each $i$, a pair $(L_i, B_i)$ is generated using the method above, where $B_i$ are independent Bernoulli($p$) variables and $L_i$ are independent Poisson($p$) variables.
   • The sums are defined as $B = \sum_{i=1}^n B_i$ (Binomial) and $L = \sum_{i=1}^n L_i$ (Poisson with parameter $np$).
   • By the triangle inequality and linearity of expectation, the expected difference is bounded: $E|L - B| \le \sum_{i=1}^n E|L_i - B_i| \le \sum_{i=1}^n p^2 = np^2$.

3. Error Bound Derivation: The paper utilizes a standard inequality relating the total variation distance to the coupling probability: $|P(L \in D) - P(B \in D)| \le P(L \neq B)$. Since $P(L \neq B) = P(|L-B| \ge 1) \le E|L-B|$, the bound derived in the previous step applies directly to the difference in probabilities.

Key Contributions and Results
The central result is Theorem 1, which states that for any set of positive integers $D$:
$$|P(L \in D) - P(B \in D)| \le np^2$$
where $B \sim \text{Binomial}(n, p)$ and $L \sim \text{Poisson}(np)$.

The paper also notes that this argument can be adapted to the more general case of a sum of independent Bernoulli variables with potentially different parameters $p_i$. In that case, the bound becomes $\sum_{i=1}^n p_i^2$. The author acknowledges that while this bound can be improved using more advanced techniques (yielding bounds of the form $f(\lambda)\sum p_i^2$), the presented proof relies solely on elementary probability results.

Significance and Claims
The paper claims to provide a "much more general result" than standard convergence proofs by offering a uniform error bound valid for all $n$ and $p$, rather than just in the limit. The significance lies in the pedagogical approach:

• Elementary Level: The proof avoids advanced machinery, making the coupling technique accessible to readers with only basic probability knowledge, despite the technique typically being reserved for graduate texts.
• Streamlined Proof: The author aims to simplify and detail the coupling argument found in advanced monographs (specifically referencing [4]), presenting it as a self-contained, elementary demonstration.
• Explicit Bounds: The work emphasizes that coupling provides a concrete measure of approximation error, addressing a limitation of traditional limit-based approaches found in undergraduate literature.