Proof of The Poisson Removal Ratio for Moves of Several Points: Move Score, Mean, Exact Second Moment, Move Information, and Pointwise Bounds

Preliminaries. By Factorial of a Natural Number, $k!=k\,(k-1)!$ for $k\ge1$, and for $k\ge\mathsf{m}$, $k!/(k-\mathsf{m})!=\prod_{i=1}^{\mathsf{m}}(k-\mathsf{m}+i)$ (induction on $\mathsf{m}$, peeling the top factor). Hence for $k\ge\mathsf{m}$, $p_\mu(k-\mathsf{m})/p_\mu(k)=\mu^{k-\mathsf{m}}k!/((k-\mathsf{m})!\,\mu^{k})=\prod_{i=1}^{\mathsf{m}}(k-\mathsf{m}+i)/\mu$, and for $k<\mathsf{m}$ the numerator $p_\mu(k-\mathsf{m})$ vanishes ($k-\mathsf{m}\notin\mathbb{N}_0$), which justifies the two displayed forms of $\varrho$. Sums of nonnegative functions over $\mathbb{N}_0$ are least upper bounds of finite partial sums (Sum of a Nonnegative Function over an Arbitrary Set); a reindexing $k\mapsto k-\mathsf{m}$ along the bijection from $\{k\ge\mathsf{m}\}$ onto $\mathbb{N}_0$ maps finite subsets onto finite subsets and preserves finite sums (claim 2 of Properties of a Sum over a Finite Index Set), hence preserves the sum over the set; and terms equal to $0$ may be dropped, since every finite partial sum over $F\subseteq\mathbb{N}_0$ equals the partial sum over $F\cap\{k\ge\mathsf{m}\}$ (claims 3 and 4 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set), so the two families of finite partial sums, and hence their least upper bounds, coincide. Let $(\Omega,\mathcal{F},P)$ be a probability space carrying a random variable $K$ with the Poisson distribution with parameter $\mu$ (it exists by Existence of Independent Sequences with Prescribed Distributions); for every measurable $g:\mathbb{R}\to[0,\infty)$, claim 1 of Series Formula, Exponential Moments, and Chernoff Tail Bounds for the Poisson Distribution gives $\mathbb{E}[g(K)]=\sum_{k\in\mathbb{N}_0}p_\mu(k)g(k)$, and for every natural number $j\ge1$, claim (a) of Factorial Moments and Moments of Every Order of the Poisson Distribution gives that the falling factorial $K^{\underline{j}}=\prod_{q=0}^{j-1}(K-q)$ is integrable with $\mathbb{E}[K^{\underline{j}}]=\mu^{j}$; put $k^{\underline{0}}=1$. Note that $k^{\underline{j}}\ge0$ for all $k\in\mathbb{N}_0$ (for $k<j$ a factor vanishes), so the series formula applies to it, and $k^{\underline{j+1}}=k^{\underline{j}}(k-j)$.

Step 1: claim 1. By Move Score of a Discrete Probability Mass Function, $\rho_{p_\mu,a,w}(k)=w_1(1-p_\mu(k-\mathsf{m})/p_\mu(k))=w_1(1-\varrho(k))$ on the support $\mathbb{N}_0$; and $k+\mathsf{m}\in\mathbb{N}_0$ trivially.

Step 2: claim 2. Dropping the vanishing terms $k<\mathsf{m}$ and reindexing, $\sum_{k\in\mathbb{N}_0}p_\mu(k)\varrho(k)=\sum_{k\ge\mathsf{m}}p_\mu(k-\mathsf{m})=\sum_{n\in\mathbb{N}_0}p_\mu(n)=1$, the last equality because $p_\mu$ is a probability mass function with support $\mathbb{N}_0$.

Step 3: claim 3. (a) A falling-factorial expansion. For natural numbers $\ell\ge0$ and $0\le j\le\ell$ put $c_{\ell,j}=(\ell!)^{2}/\bigl((j!)^{2}(\ell-j)!\bigr)$, and $c_{\ell,j}=0$ for $j<0$ or $j>\ell$. We claim that for every $\ell\ge0$ and every $n\in\mathbb{N}_0$,

$$\prod_{i=1}^{\ell}(n+i)=\sum_{j=0}^{\ell}c_{\ell,j}\,n^{\underline{j}} .\tag{3.1}$$

Induction on $\ell$: for $\ell=0$ both sides equal $1$. Assume (3.1) for $\ell$. Since $(n+\ell+1)\,n^{\underline{j}}=n^{\underline{j}}(n-j)+(j+\ell+1)n^{\underline{j}}=n^{\underline{j+1}}+(j+\ell+1)n^{\underline{j}}$, and shifting the summation index in the first resulting sum by one (Invariance of Finite Sums and Products under Reindexing by a Permutation after extending the range with the vanishing coefficients $c_{\ell,-1}=c_{\ell,\ell+1}=0$),

$$\prod_{i=1}^{\ell+1}(n+i)=(n+\ell+1)\sum_{j=0}^{\ell}c_{\ell,j}n^{\underline{j}}=\sum_{j=0}^{\ell+1}\bigl(c_{\ell,j-1}+(j+\ell+1)c_{\ell,j}\bigr)n^{\underline{j}} .$$

For $1\le j\le\ell$, using $(\ell+1-j)!=(\ell+1-j)(\ell-j)!$ and $(j!)^{2}=j^{2}((j-1)!)^{2}$,

$$c_{\ell,j-1}+(j+\ell+1)c_{\ell,j}=\frac{(\ell!)^{2}}{(j!)^{2}(\ell+1-j)!}\bigl(j^{2}+(j+\ell+1)(\ell+1-j)\bigr)=\frac{(\ell!)^{2}(\ell+1)^{2}}{(j!)^{2}(\ell+1-j)!}=c_{\ell+1,j};$$

for $j=0$ the left side is $(\ell+1)c_{\ell,0}=(\ell+1)\,\ell!=(\ell+1)!=c_{\ell+1,0}$, and for $j=\ell+1$ it is $c_{\ell,\ell}=1=c_{\ell+1,\ell+1}$. This proves (3.1) for $\ell+1$. Below we use (3.1) with $\ell=\mathsf{m}$.

(b) The second moment. Dropping the vanishing terms and reindexing $k=n+\mathsf{m}$,

$$\sum_{k\in\mathbb{N}_0}p_\mu(k)\varrho(k)^{2}=\sum_{k\ge\mathsf{m}}\frac{p_\mu(k-\mathsf{m})^{2}}{p_\mu(k)}=\sum_{n\in\mathbb{N}_0}p_\mu(n)\frac{p_\mu(n)}{p_\mu(n+\mathsf{m})}=\sum_{n\in\mathbb{N}_0}p_\mu(n)\frac{(n+\mathsf{m})!}{n!\,\mu^{\mathsf{m}}}=\mu^{-\mathsf{m}}\,\mathbb{E}\Bigl[\prod_{i=1}^{\mathsf{m}}(K+i)\Bigr],$$

by the series formula applied to the nonnegative function $g(k)=\prod_{i=1}^{\mathsf{m}}(k+i)$ (extended by $0$ off $\mathbb{N}_0$; measurable as it is a polynomial on the Borel set $\mathbb{N}_0$). By (3.1), $\prod_{i\le\mathsf{m}}(K+i)=\sum_{j\le\mathsf{m}}c_{\mathsf{m},j}K^{\underline{j}}$ on the event $\{K\in\mathbb{N}_0\}$, which has probability $1$; integrable random variables agreeing off a null event have equal expectations (their difference vanishes off a null set, so its integral is $0$ by Lebesgue Integral of a Nonnegative Measurable Function and Simple Function and Its Integral). Hence, by linearity of the expectation (Linearity and Monotonicity of the Lebesgue Integral, all summands being integrable) and the factorial moments,

$$\mathbb{E}\Bigl[\prod_{i=1}^{\mathsf{m}}(K+i)\Bigr]=\sum_{j=0}^{\mathsf{m}}c_{\mathsf{m},j}\mu^{j},\qquad\text{so}\qquad \sum_kp_\mu(k)\varrho(k)^{2}=\sum_{j=0}^{\mathsf{m}}c_{\mathsf{m},j}\mu^{j-\mathsf{m}}=\sum_{i=0}^{\mathsf{m}}c_{\mathsf{m},\mathsf{m}-i}\mu^{-i},$$

substituting $i=\mathsf{m}-j$ (a permutation of the index set, Invariance of Finite Sums and Products under Reindexing by a Permutation), and $c_{\mathsf{m},\mathsf{m}-i}=(\mathsf{m}!)^{2}/\bigl(((\mathsf{m}-i)!)^{2}i!\bigr)=\binom{\mathsf{m}}{i}^{2}i!$. This is the displayed formula.

(c) The move information and its bounds. By Move Information of a Discrete Probability Mass Function and claim 1, $\mathsf{J}(p_\mu;a,w)=\sum_kp_\mu(k)w_1^{2}(1-\varrho(k))^{2}=w_1^{2}\sum_kp_\mu(k)\bigl(1-2\varrho(k)+\varrho(k)^{2}\bigr)$. The three sums $\sum_kp_\mu(k)$, $\sum_kp_\mu(k)\varrho(k)$ and $\sum_kp_\mu(k)\varrho(k)^{2}$ are finite ($1$, $1$ by claim 2, and the finite sum of (b)), so by linearity (the sums being the integrals with respect to the counting measure of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions, claims 3 and 4(c), on which claim 2 of Linearity and Monotonicity of the Lebesgue Integral applies), $\mathsf{J}(p_\mu;a,w)/w_1^{2}=1-2+\sum_{i=0}^{\mathsf{m}}\binom{\mathsf{m}}{i}^{2}i!\mu^{-i}=\sum_{i=1}^{\mathsf{m}}\binom{\mathsf{m}}{i}^{2}i!\mu^{-i}$, the $i=0$ term being $1$; for $w_1=0$ the move score vanishes and so does the move information. The $i=1$ term is $\mathsf{m}^{2}/\mu$ and the others are nonnegative, giving the lower bound. For the upper bound, $\binom{\mathsf{m}}{i}^{2}i!=\frac{1}{i!}\Bigl(\frac{\mathsf{m}!}{(\mathsf{m}-i)!}\Bigr)^{2}\le\frac{\mathsf{m}^{2i}}{i!}$, since $\mathsf{m}!/(\mathsf{m}-i)!=\prod_{q=0}^{i-1}(\mathsf{m}-q)\le\mathsf{m}^{i}$ (claim 5 of Properties of Finite Products); and for $i\ge2$, $i!\ge2\,(i-2)!$, so with $x=\mathsf{m}^{2}/\mu$, $\sum_{i=2}^{\mathsf{m}}\frac{x^{i}}{i!}\le\frac{x^{2}}{2}\sum_{i=2}^{\mathsf{m}}\frac{x^{i-2}}{(i-2)!}\le\frac{x^{2}}{2}\exp(x)$ by the series for $\exp$ (The Real Exponential Function), all terms being nonnegative. Adding the $i=1$ term gives the upper bound.

Step 4: claim 4. For $k\ge\mathsf{m}$, each factor satisfies $0\le(k-\mathsf{m}+i)/\mu\le k/\mu$, so $\varrho(k)\le(k/\mu)^{\mathsf{m}}$ by claim 5 of Properties of Finite Products; for $k<\mathsf{m}$, $\varrho(k)=0\le(k/\mu)^{\mathsf{m}}$. Now let $x\ge0$ with $\mathsf{m}(x+\mathsf{m})\le\mu$ and let $k\ge\mu-x$. Then $k\ge\mathsf{m}(x+\mathsf{m})-x\ge\mathsf{m}^{2}\ge\mathsf{m}$ (as $\mathsf{m}x\ge x$), so every factor satisfies $(k-\mathsf{m}+i)/\mu\ge(k-\mathsf{m})/\mu\ge(\mu-x-\mathsf{m})/\mu=1-\delta$ with $\delta=(x+\mathsf{m})/\mu\in[0,1]$ (as $\mathsf{m}\ge1$ gives $x+\mathsf{m}\le\mathsf{m}(x+\mathsf{m})\le\mu$), hence $\varrho(k)\ge(1-\delta)^{\mathsf{m}}$ by claim 5 of Properties of Finite Products. Finally $(1-\delta)^{m}\ge1-m\delta$ for every natural number $m$ and $\delta\in[0,1]$, by induction: it holds for $m=1$, and multiplying $(1-\delta)^{m}\ge1-m\delta$ by $1-\delta\ge0$ gives $(1-\delta)^{m+1}\ge(1-m\delta)(1-\delta)=1-(m+1)\delta+m\delta^{2}\ge1-(m+1)\delta$. With $m=\mathsf{m}$ this yields $\varrho(k)\ge1-\mathsf{m}(x+\mathsf{m})/\mu$. $\blacksquare$