Proof of Gaussian Smoothing of a Finitely Supported Probability Mass Function: Density Bounds and Control of the Directional Score Integral by the Move Information

Preliminaries. Finite sums. Let $f\ge0$ be defined on a set containing the finite set $\mathsf{S}$. For finite $F\subseteq\mathsf{S}$ one has $\sum_{x\in F}f(x)\le\sum_{x\in\mathsf{S}}f(x)$ (ordinary finite sums over nonempty finite index sets in the sense of Sum over a Finite Index Set, with the empty-sum convention; the cases $F=\emptyset$ and $F=\mathsf{S}$ being immediate, otherwise split $\mathsf{S}=F\cup(\mathsf{S}\setminus F)$ by claim 3 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set and drop the nonnegative second part), so the sum over $\mathsf{S}$ of $f$ is the ordinary finite sum $\sum_{x\in\mathsf{S}}f(x)$, the least upper bound being attained at $F=\mathsf{S}$; the same holds for sums over subsets of $\mathsf{S}$. Moreover, if $f$ is defined on $\mathbb{R}^m$ and vanishes off $\mathsf{S}$, then $\sum_{x\in F}f(x)=\sum_{x\in F\cap\mathsf{S}}f(x)$ for every finite $F\subseteq\mathbb{R}^m$ (claim 4 of the same lemma when $F\cap\mathsf{S}\ne\emptyset$; if $F\cap\mathsf{S}=\emptyset$, every term of the left-hand sum vanishes, so it is $0$: by Sum over a Finite Index Set it is a sum over $[n]$ of zeros along an enumeration, which is $0$ by Finite Sum Notation in a Field; this is the empty-sum convention for the right-hand side), so the sum of $f$ over $\mathbb{R}^m$ equals its sum over $\mathsf{S}$. Applied to $p$, which vanishes off its support, this gives $\sum_{x\in\mathsf{S}}p(x)=1$ as an ordinary finite sum; in particular $\mathsf{S}\ne\emptyset$, $\pi_j\in[0,1]$, and $\mathsf{J}(p;a,w)=\sum_{x\in\mathsf{S}}p(x)\rho_w(x)^{2}$ is a finite nonnegative real number. Finite sums are compared termwise and bounded by the sum of absolute values via Comparison and Absolute Value Bounds for Finite Sums of Real Numbers; a sum over a nonempty finite index set is by Sum over a Finite Index Set a sum over $[n]$ along a bijection, so these apply to sums over $\mathsf{S}$ and its nonempty subsets as well. Sums over a nonempty finite index set are additive and homogeneous by claims 3 and 4 of Properties of a Sum over a Finite Index Set, are reindexed along a bijection between index sets by claim 2 there, and finite double sums may be interchanged by claim 5 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set. A nonnegative real $t$ has a unique nonnegative square root $\sqrt t$ by Existence and Uniqueness of the Nonnegative Square Root; $\sqrt{st}=\sqrt s\sqrt t$ for $s,t\ge0$ (the right side is nonnegative with square $st$), $\sqrt{\exp\kappa}=\exp(\kappa/2)$ by claims 1 and 2 of Basic Properties of the Exponential Function ($\exp(\kappa/2)$ is positive with square $\exp\kappa$), and $t\mapsto\sqrt t$ is increasing on $[0,\infty)$ (if $s<t$ but $\sqrt s\ge\sqrt t$, squaring would give $s\ge t$). Throughout we use the notation, conventions and claims of The Gaussian Smoothing Weight: Normalization, Derivatives, Exponential Tilting, Moments, and First-Order Remainder, which we call the weight lemma; sequential continuity is preserved by finite sums, products and quotients with nonvanishing denominator, by Arithmetic of Limits of Real Sequences, and by translation of the argument, since $d(\theta^k-x,\theta-x)=d(\theta^k,\theta)$ by the definition of the Euclidean distance; every sequentially continuous function is measurable by claims 3(a) and 5 of The Borel Sigma-Algebra of a Euclidean Space as a Product, and Measurability of Projections, Sequentially Continuous Maps, and Open and Closed Sets. Integrals of nonnegative functions are handled with claim 1 of Linearity and Monotonicity of the Lebesgue Integral (linearity, monotonicity), integrable functions with claim 2 there and Integrable Function and the Lebesgue Integral, and translations of integrands with claim 2 of Translation and Reflection Invariance of Lebesgue Measure on $\mathbb{R}^n$: for measurable $f\ge0$ and $x\in\mathbb{R}^m$, $\int f(\theta-x)\,d\lambda_m(\theta)=\int f\,d\lambda_m$.

(CS) For real numbers $\alpha_1,\dots,\alpha_r$ and $\beta_1,\dots,\beta_r>0$,

by Cauchy-Schwarz Inequality for the Euclidean Dot Product applied in $\mathbb{R}^{r}$ to the vectors with coordinates $\alpha_k/\sqrt{\beta_k}$ and $\sqrt{\beta_k}$. Equivalently, $(\sum_k\alpha_k)^{2}/\sum_k\beta_k\le\sum_k\alpha_k^{2}/\beta_k$.

Step 1: claim 1. Each summand $\theta\mapsto p(x)\varphi_\eta(\theta-x)$ is sequentially continuous and positive, and is at most $p(x)c_\eta$ by claim 1 of the weight lemma; hence $q$ is sequentially continuous, measurable, and $0<q\le c_\eta\sum_{x}p(x)=c_\eta$. By linearity and the translation identity of claim 1 of the weight lemma, $\int q\,d\lambda_m=\sum_xp(x)\int\varphi_\eta(\theta-x)\,d\lambda_m(\theta)=\sum_xp(x)=1$.

Fix $i$ and $\theta\in\mathbb{R}^m$. For $x\in\mathsf{S}$ the translate $\tau_x(\theta')=\varphi_\eta(\theta'-x)$ has, at $\theta$, exactly the same difference quotients in the $i$th variable as $\varphi_\eta$ has at $\theta-x$, namely $\bigl(\varphi_\eta(\theta-x+he_i)-\varphi_\eta(\theta-x)\bigr)/h$, where $e_i$ denotes the point of $\mathbb{R}^m$ with $i$th coordinate $1$ and all other coordinates $0$; so by the definition of the partial derivative and claim 2 of the weight lemma, $\partial_i\tau_x(\theta)$ exists and equals $\partial_i\varphi_\eta(\theta-x)$. In the notation of Slice Function and the Partial Derivative (with $U=\mathbb{R}^m$, admissible radius $1$), the slice function of $q$ at $\theta$ in the $i$th variable is $s\mapsto\sum_xp(x)\tau_x(\theta[s])$, a finite linear combination of the slice functions of the $\tau_x$, each of which is differentiable at $\theta_i$ with derivative $\partial_i\tau_x(\theta)$ by claim 2 of that lemma. By the sum and constant-multiple rules (claim 2 of Sum, Constant Multiple, and Product Rules for One-Dimensional Derivatives) the slice function of $q$ is differentiable at $\theta_i$ with derivative $\sum_xp(x)\partial_i\varphi_\eta(\theta-x)$, and claim 2 of Slice Function and the Partial Derivative gives the formula for $\partial_iq(\theta)$. It is sequentially continuous as a finite sum of translates of the sequentially continuous $\partial_i\varphi_\eta$, and $|\partial_iq|\le\sum_xp(x)\,c_\eta(2\eta)^{-1/2}=c_\eta(2\eta)^{-1/2}$ by claim 2 of the weight lemma.

For the integral bound, apply (CS) at each $\theta$ with $\alpha_x=p(x)\partial_i\varphi_\eta(\theta-x)$ and $\beta_x=p(x)\varphi_\eta(\theta-x)>0$ ($x\in\mathsf{S}$), noting $\sum_x\beta_x=q(\theta)$:

where we used claim 2 of the weight lemma, $\partial_i\varphi_\eta(z)^{2}/\varphi_\eta(z)=(z_i/\eta)^{2}\varphi_\eta(z)$, and the notation $Z_{e_i}(z)=e_i\cdot z/\eta=z_i/\eta$ of claim 3 there (with the dot product), with $\kappa_{e_i}=\lVert e_i\rVert^{2}/\eta=1/\eta$. Integrating, using monotonicity, linearity, translation invariance and claim 4 of the weight lemma,

Step 2: claim 2. Since $2|st|\le s^{2}+t^{2}$ for real $s,t$, we have $|\partial_iq\,\partial_kq|/q\le\tfrac12\bigl((\partial_iq)^{2}+(\partial_kq)^{2}\bigr)/q$ pointwise; the right side has finite integral by claim 1, and the left side is sequentially continuous (as $q>0$), hence measurable. So $\partial_iq\,\partial_kq/q$ is integrable and $J(q)_{ik}$ is a real number. Pointwise, $(\partial_vq)^{2}/q=\sum_{i,k}v_iv_k\,\partial_iq\,\partial_kq/q$ by expanding the square, and linearity of the integral for integrable functions gives the displayed identity.

Step 3: claim 3.

The mean-square norm with respect to $q$. By claim 3 of Image Measures, Measures with Densities, and Change of Variables, $\nu(E)=\int\mathbf{1}_Eq\,d\lambda_m$ ($E\in\mathcal{B}(\mathbb{R}^m)$, with $\mathbf{1}_E$ the indicator of $E$) is a measure on $(\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m))$ with $\nu(\mathbb{R}^m)=\int q\,d\lambda_m=1$, so $(\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m),\nu)$ is a probability space, whose random variables are the measurable functions $\mathbb{R}^m\to\mathbb{R}$; and for every measurable $F:\mathbb{R}^m\to\mathbb{R}$ the same claim gives $\int F^{2}\,d\nu=\int F^{2}q\,d\lambda_m$. For a sequentially continuous $A:\mathbb{R}^m\to\mathbb{R}$ put $F_A=A/q$, again sequentially continuous; then the expectation of $F_A^{2}$ under $\nu$ is $\int A^{2}/q\,d\lambda_m$. Whenever this is finite, $F_A$ is square-integrable with mean-square norm $\lVert F_A\rVert_2=(\int A^{2}/q\,d\lambda_m)^{1/2}$, and for two such functions $A,A'$ the triangle inequality (claim 2 of Cauchy-Schwarz and Triangle Inequalities for the Mean-Square Norm) gives $\lVert F_{A+A'}\rVert_2\le\lVert F_A\rVert_2+\lVert F_{A'}\rVert_2$, since $F_{A+A'}=F_A+F_{A'}$; moreover $\lVert F_{cA}\rVert_2=|c|\lVert F_A\rVert_2$ for real $c$, by linearity of the integral.

Decomposition of $\partial_uq$. Fix $\theta$. By claim 1 and $u=\sum_jw_ja_j$,

where $(a_j)_i$ is the $i$th coordinate of $a_j$. By the definition of $R_{a_j}$ in claim 5 of the weight lemma, $\sum_i(a_j)_i\partial_i\varphi_\eta(z)=R_{a_j}(z)+\varphi_\eta(z)-\varphi_\eta(z-a_j)$. Hence

Fix $j$ and put $\mathsf{S}_j^{\mathrm{out}}=\{x\in\mathsf{S}:x+a_j\notin\mathsf{S}\}$ and $\mathsf{S}_j^{\mathrm{in}}=\mathsf{S}\setminus\mathsf{S}_j^{\mathrm{out}}$, so that $\pi_j=\sum_{x\in\mathsf{S}_j^{\mathrm{out}}}p(x)$, and define

Splitting the sum over $\mathsf{S}=\mathsf{S}_j^{\mathrm{in}}\cup\mathsf{S}_j^{\mathrm{out}}$ (claim 3 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set; if one part is empty there is nothing to split), reindexing the sum over $\mathsf{S}_j^{\mathrm{in}}$ along the bijection $x\mapsto x+a_j$ from $\mathsf{S}_j^{\mathrm{in}}$ onto $\{y\in\mathsf{S}:y-a_j\in\mathsf{S}\}$ (claim 2 of Properties of a Sum over a Finite Index Set), and using $p(y-a_j)=0$ for $y\in\mathsf{S}$ with $y-a_j\notin\mathsf{S}$ (claim 4 of the peeling lemma; if $\mathsf{S}_j^{\mathrm{in}}=\emptyset$, every term of the sum over $y\in\mathsf{S}$ below vanishes and both sides are $T_j(\theta)$), we get

Consequently $\sum_xp(x)\bigl(\varphi_\eta(\theta-x)-\varphi_\eta(\theta-x-a_j)\bigr)=\sum_{y\in\mathsf{S}}\bigl(p(y)-p(y-a_j)\bigr)\varphi_\eta(\theta-y)-T_j(\theta)$, and since $p(y)-p(y-a_j)=p(y)\bigl(1-p(y-a_j)/p(y)\bigr)$ for $y\in\mathsf{S}$, summing over $j$ with the weights and using the definition of the move score yields

All functions here are finite sums of translates of sequentially continuous functions, hence sequentially continuous.

Three bounds. (i) Applying (CS) at each $\theta$ with $\alpha_y=p(y)\rho_w(y)\varphi_\eta(\theta-y)$ and $\beta_y=p(y)\varphi_\eta(\theta-y)$ over $y\in\mathsf{S}$, where $\sum_y\beta_y=q(\theta)$, gives $A_1(\theta)^{2}/q(\theta)\le\sum_yp(y)\rho_w(y)^{2}\varphi_\eta(\theta-y)$; integrating with translation invariance, $\int A_1^{2}/q\,d\lambda_m\le\sum_yp(y)\rho_w(y)^{2}=\mathsf{J}(p;a,w)$, by Move Information of a Discrete Probability Mass Function and the preliminaries.

(ii) If $\mathsf{S}_j^{\mathrm{out}}=\emptyset$ then $T_j=0$. Otherwise apply (CS) over $x\in\mathsf{S}_j^{\mathrm{out}}$ with $\alpha_x=p(x)\varphi_\eta(\theta-x-a_j)$ and $\beta_x=p(x)\varphi_\eta(\theta-x)$; since $\sum_{x\in\mathsf{S}_j^{\mathrm{out}}}\beta_x\le q(\theta)$,

Integrating, with translation by $x$ and claim 3 of the weight lemma ($\int\varphi_\eta(z-a_j)^{2}/\varphi_\eta(z)\,d\lambda_m(z)=\exp(\kappa_j)$), $\int T_j^{2}/q\,d\lambda_m\le\pi_j\exp(\kappa_j)$.

(iii) Applying (CS) with $\alpha_x=p(x)R_{a_j}(\theta-x)$ and $\beta_x=p(x)\varphi_\eta(\theta-x)$ over $x\in\mathsf{S}$ gives $B_j(\theta)^{2}/q(\theta)\le\sum_xp(x)R_{a_j}(\theta-x)^{2}/\varphi_\eta(\theta-x)$, and integrating with translation and claim 5 of the weight lemma, $\int B_j^{2}/q\,d\lambda_m\le\sum_xp(x)\bigl(\exp(\kappa_j)-1-\kappa_j\bigr)=\exp(\kappa_j)-1-\kappa_j$.

Conclusion. By (i)-(iii), $F_{A_1}$, $F_{T_j}$ and $F_{B_j}$ are square-integrable under $\nu$, and so is $F_{\partial_uq}=F_{A_1}-\sum_jw_jF_{T_j}+\sum_jw_jF_{B_j}$ (sums and multiples of square-integrable random variables are square-integrable by Square-Integrable Random Variables and the Mean-Square Inner Product). Repeated application of the triangle inequality and of $\lVert F_{cA}\rVert_2=|c|\lVert F_A\rVert_2$ gives

and inserting the bounds (i)-(iii) for the three norms (the square root being increasing on $[0,\infty)$) yields the claim. $\blacksquare$