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$,

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$),

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

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}$,

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,

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$