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

$$\Bigl(\sum_{k=1}^{r}\alpha_k\Bigr)^{2}\le\Bigl(\sum_{k=1}^{r}\beta_k\Bigr)\Bigl(\sum_{k=1}^{r}\frac{\alpha_k^{2}}{\beta_k}\Bigr),$$

by The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ 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)$:

$$\frac{(\partial_iq(\theta))^{2}}{q(\theta)}\le\sum_{x\in\mathsf{S}}p(x)\frac{\partial_i\varphi_\eta(\theta-x)^{2}}{\varphi_\eta(\theta-x)}=\sum_{x\in\mathsf{S}}p(x)\,Z_{e_i}(\theta-x)^{2}\varphi_\eta(\theta-x),$$

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,

$$\int\frac{(\partial_iq)^{2}}{q}\,d\lambda_m\le\sum_{x\in\mathsf{S}}p(x)\int Z_{e_i}^{2}\varphi_\eta\,d\lambda_m=\sum_{x\in\mathsf{S}}p(x)\,\kappa_{e_i}=\frac1\eta.$$

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

$$\partial_uq(\theta)=\sum_{x\in\mathsf{S}}p(x)\sum_{i=1}^{m}u_i\,\partial_i\varphi_\eta(\theta-x)=\sum_{j=1}^{n}w_j\sum_{x\in\mathsf{S}}p(x)\sum_{i=1}^{m}(a_j)_i\,\partial_i\varphi_\eta(\theta-x),$$

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

$$\partial_uq(\theta)=B(\theta)+\sum_{j=1}^{n}w_j\sum_{x\in\mathsf{S}}p(x)\bigl(\varphi_\eta(\theta-x)-\varphi_\eta(\theta-x-a_j)\bigr),\qquad B(\theta)=\sum_{j=1}^{n}w_jB_j(\theta),\quad B_j(\theta)=\sum_{x\in\mathsf{S}}p(x)R_{a_j}(\theta-x).$$

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

$$T_j(\theta)=\sum_{x\in\mathsf{S}_j^{\mathrm{out}}}p(x)\,\varphi_\eta(\theta-x-a_j)\ge0.$$

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

$$\sum_{x\in\mathsf{S}}p(x)\varphi_\eta(\theta-x-a_j)=\sum_{x\in\mathsf{S}_j^{\mathrm{in}}}p(x)\varphi_\eta\bigl(\theta-(x+a_j)\bigr)+T_j(\theta)=\sum_{y\in\mathsf{S}}p(y-a_j)\varphi_\eta(\theta-y)+T_j(\theta).$$

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

$$\partial_uq=A_1-\sum_{j=1}^{n}w_jT_j+\sum_{j=1}^{n}w_jB_j,\qquad A_1(\theta)=\sum_{y\in\mathsf{S}}p(y)\rho_w(y)\varphi_\eta(\theta-y).$$

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

$$\frac{T_j(\theta)^{2}}{q(\theta)}\le\frac{T_j(\theta)^{2}}{\sum_{x\in\mathsf{S}_j^{\mathrm{out}}}\beta_x}\le\sum_{x\in\mathsf{S}_j^{\mathrm{out}}}p(x)\frac{\varphi_\eta(\theta-x-a_j)^{2}}{\varphi_\eta(\theta-x)}.$$

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

$$\Bigl(\int\frac{(\partial_uq)^{2}}{q}\,d\lambda_m\Bigr)^{1/2}=\lVert F_{\partial_uq}\rVert_2\le\lVert F_{A_1}\rVert_2+\sum_{j=1}^{n}|w_j|\,\lVert F_{T_j}\rVert_2+\sum_{j=1}^{n}|w_j|\,\lVert F_{B_j}\rVert_2,$$

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