Proof of Move Score and Move Information of the Multinomial Probability Mass Function

Conventions. Throughout, $p_n=p_{n,\bar S}$ and $\mathsf{K}_n$ are as in Multinomial Probability Mass Function, and $\tilde w$, $Q(\tilde w)$, $L$, $c$ are as in the statement; recall $\tilde w_\gamma=w_\gamma$ for $\gamma\in\Gamma$ and $\sum_{\gamma=1}^{l}\tilde w_\gamma=0$. The objects of Step 0 depend on the trial number $n$; whenever a step fixes $n$, they are the objects constructed for that $n$.

Step 0: a probabilistic representation. Fix $n\in\mathbb{N}$. Define $\nu:\mathcal{B}(\mathbb{R})\to[0,1]$ on the Borel sets of the real line by $\nu(B)=\sum_{\gamma=1}^{l}\bar S_\gamma\mathbf{1}_B(\gamma)$, where $\mathbf{1}_B$ is the indicator of $B$. Then $\nu(\emptyset)=0$, $\nu(\mathbb{R})=\sum_\gamma\bar S_\gamma=1$, and $\nu$ is countably additive, because each point $\gamma$ lies in exactly one set of a pairwise disjoint family; so $\nu$ is a probability measure. Put $A_\gamma=\{\gamma\}$ for $1\le\gamma\le l-1$ and $A_l=\mathbb{R}\setminus\{1,\dots,l-1\}$; these are pairwise disjoint Borel sets with union $\mathbb{R}$ (a singleton $\{\gamma\}=\bigcap_{j\in\mathbb{N}}(\gamma-1/j,\gamma+1/j)$ is a countable intersection of open intervals), and $\nu(A_\gamma)=\bar S_\gamma$ for every $\gamma\in\{1,\dots,l\}$. By Existence of Independent and Identically Distributed Sequences there are a probability space $(\Omega,\mathcal{F},P)$ and an independent sequence $V_1,V_2,\dots$ of random variables on it, each with distribution $\nu$. For the cell counts $S_\gamma=\sum_{i=1}^{n}\mathbf{1}_{\{V_i\in A_\gamma\}}$ formed from $V_1,\dots,V_n$, Multinomial Distribution of Cell Counts for Independent Identically Distributed Points gives $P\bigl(\bigcap_{\gamma}\{S_\gamma=k_\gamma\}\bigr)=\frac{n!}{k_1!\cdots k_l!}\prod_\gamma\bar S_\gamma^{k_\gamma}$, which by Multinomial Probability Mass Function is $p_n(k)$; that is, for every $k\in\mathsf{K}_n$,

$$P(M=k)=p_n(k),\qquad M=(S_1,\dots,S_l),\quad\{M=k\}=\bigcap_{\gamma=1}^{l}\{S_\gamma=k_\gamma\}.$$

Since the $A_\gamma$ are disjoint with union $\mathbb{R}$, each $V_i(\omega)$ lies in exactly one cell, so $\sum_\gamma S_\gamma(\omega)=n$ and $M(\omega)\in\mathsf{K}_n$ for every $\omega$. The set $\mathsf{K}_n\subseteq\{0,\dots,n\}^{l}$ is finite, and the events $\{M=k\}$, $k\in\mathsf{K}_n$, partition $\Omega$; hence, by finite additivity of $P$, for every function $h:\mathsf{K}_n\to\mathbb{R}$ the random variable $h(M)=\sum_{k\in\mathsf{K}_n}h(k)\mathbf{1}_{\{M=k\}}$ is a finite linear combination of indicators of events, its expectation exists, and by Simple Function and Its Integral and claim 2 of Linearity and Monotonicity of the Lebesgue Integral,

$$\mathbb{E}[h(M)]=\sum_{k\in\mathsf{K}_n}p_n(k)\,h(k).\tag{R}$$

Step 1: claim 1. Every $p_n(k)$ is nonnegative, and positive exactly on $\mathsf{K}_n$ because all $\bar S_\gamma>0$. Taking $h\equiv1$ in (R), $\sum_{k\in\mathsf{K}_n}p_n(k)=P(\Omega)=1$; in particular $p_n\le1$. For a finite set $F\subseteq\mathbb{R}^l$, $\sum_{x\in F}p_n(x)=\sum_{x\in F\cap\mathsf{K}_n}p_n(x)\le\sum_{k\in\mathsf{K}_n}p_n(k)=1$ by claims 4 and 3 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set (terms vanishing off $F\cap\mathsf{K}_n$; the omitted terms over $\mathsf{K}_n\setminus F$ are nonnegative; the trivial cases of empty index sets are handled by the empty-sum convention), with equality for $F=\mathsf{K}_n$; so $1$ is the least upper bound of the finite sub-sums, and the sum of $p_n$ over $\mathbb{R}^l$ equals $1$. Thus $p_n$ is a discrete probability mass function with $\{p_n>0\}=\mathsf{K}_n$, a finite set (a subset of $\{0,\dots,n\}^{l}$); in particular this holds for $n=N$. In the same way, for any $\mathsf{A}\subseteq\mathsf{K}_n$ and any $u:\mathsf{K}_n\to[0,\infty)$, the sum of $x\mapsto p_n(x)u(x)$ over $\mathsf{A}$ in the sense of Sum of a Nonnegative Function over an Arbitrary Set is the ordinary finite sum $\sum_{k\in\mathsf{A}}p_n(k)u(k)$ (the finite sub-sums are bounded by it, and it is itself a finite sub-sum).

Step 2: claim 2. Let $k\in\mathsf{K}_N$ and $\gamma\in\Gamma$. Then $k-a_\gamma=k-\delta_\gamma+\delta_\sigma$ has coordinates $k_\gamma-1$, $k_\sigma+1$ and $k_{\gamma'}$ ($\gamma'\ne\gamma,\sigma$), summing to $N$. If $k_\gamma\ge1$, then $k-a_\gamma\in\mathsf{K}_N$ and, by Factorial of a Natural Number, $k_\gamma!=k_\gamma\,(k_\gamma-1)!$ and $(k_\sigma+1)!=(k_\sigma+1)\,k_\sigma!$, so

$$\frac{p_N(k-a_\gamma)}{p_N(k)}=\frac{k_\gamma!\,k_\sigma!}{(k_\gamma-1)!\,(k_\sigma+1)!}\cdot\frac{\bar S_\sigma}{\bar S_\gamma}=\frac{k_\gamma\,\bar S_\sigma}{(k_\sigma+1)\,\bar S_\gamma}.$$

If $k_\gamma=0$, then $k-a_\gamma$ has the negative coordinate $-1$, so $k-a_\gamma\notin\mathsf{K}_N$, $p_N(k-a_\gamma)=0$, and the displayed formula holds as well (both sides vanish). Hence, by Move Score of a Discrete Probability Mass Function and $\sum_{\gamma\in\Gamma}w_\gamma=-\tilde w_\sigma$,

$$\rho_{p_N,a,w}(k)=\sum_{\gamma\in\Gamma}w_\gamma\Bigl(1-\frac{k_\gamma\bar S_\sigma}{(k_\sigma+1)\bar S_\gamma}\Bigr)=-\tilde w_\sigma-\frac{\bar S_\sigma}{k_\sigma+1}\Bigl(L(k)-\frac{\tilde w_\sigma k_\sigma}{\bar S_\sigma}\Bigr)=-\frac{\bar S_\sigma}{k_\sigma+1}L(k)-\tilde w_\sigma\Bigl(1-\frac{k_\sigma}{k_\sigma+1}\Bigr),$$

and $\tilde w_\sigma/(k_\sigma+1)=\bar S_\sigma c/(k_\sigma+1)$ gives the claim.

Step 3: claim 3. For $k\in\mathsf{K}_N$ and $\gamma\in\Gamma$, the point $k+a_\gamma=k+\delta_\gamma-\delta_\sigma$ has coordinate sum $N$ and nonnegative coordinates except possibly $k_\sigma-1$; so $k+a_\gamma\in\mathsf{K}_N$ if and only if $k_\sigma\ge1$, which is the first assertion. For the second, take $n=N$ in Step 0. Since $S_\sigma$ takes values in $\mathbb{N}_0$, $\{S_\sigma=0\}$ is the disjoint union of the events $\{M=k\}$ over $k\in\mathsf{K}_N$ with $k_\sigma=0$, so $\sum_{k\in\mathsf{K}_N,\,k_\sigma=0}p_N(k)=P(S_\sigma=0)$. Moreover $\{S_\sigma=0\}=\bigcap_{i=1}^{N}\{V_i\in\mathbb{R}\setminus A_\sigma\}$, and $\mathbb{R}\setminus A_\sigma$ is a Borel set, so by the independence of $V_1,\dots,V_N$ (Independence of Events and of Random Variables) and $P(V_i\in\mathbb{R}\setminus A_\sigma)=\nu(\mathbb{R}\setminus A_\sigma)=1-\bar S_\sigma$,

$$P(S_\sigma=0)=\prod_{i=1}^{N}(1-\bar S_\sigma)=(1-\bar S_\sigma)^{N}.$$

Step 4: second and fourth moments. Let $n\in\mathbb{N}$ and use the objects of Step 0. Put $\beta=\max_{\gamma\in\{1,\dots,l\}}|\tilde w_\gamma|/\bar S_\gamma$.

(a) Let $g=\sum_{\gamma=1}^{l}\frac{\tilde w_\gamma}{\bar S_\gamma}\mathbf{1}_{A_\gamma}$ and $Y_i=g(V_i)$. Then $g$ is Borel measurable (a finite linear combination of indicators of Borel sets, each measurable by claim 1 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions, and sums and scalar multiples of measurable real functions are measurable by claim 2 there) and bounded by $\beta$ (the $A_\gamma$ are disjoint, so at each point at most one indicator is nonzero), and $L(M)=\sum_\gamma\frac{\tilde w_\gamma}{\bar S_\gamma}S_\gamma=\sum_{i=1}^{n}Y_i$. By claim 2 of Joint Distribution, Expectations, and Block Independence for Independent Random Variables (with $r=1$), $\mathbb{E}[Y_i]=\int g\,d\nu=\sum_\gamma\frac{\tilde w_\gamma}{\bar S_\gamma}\bar S_\gamma=\sum_\gamma \tilde w_\gamma=0$ and, since $g^{2}=\sum_\gamma\frac{\tilde w_\gamma^{2}}{\bar S_\gamma^{2}}\mathbf{1}_{A_\gamma}$ by disjointness, $\mathbb{E}[Y_i^{2}]=\sum_\gamma\frac{\tilde w_\gamma^{2}}{\bar S_\gamma^{2}}\bar S_\gamma=Q(\tilde w)$; here integrals of simple functions against $\nu$ are computed by Simple Function and Its Integral and linearity. For $i\ne j$, $Y_i$ and $Y_j$ are independent by claim 3 of Joint Distribution, Expectations, and Block Independence for Independent Random Variables, so $\mathbb{E}[Y_iY_j]=\mathbb{E}[Y_i]\mathbb{E}[Y_j]=0$ by Expectation of a Product of Independent Random Variables. Expanding the square and using linearity of the expectation (claim 2 of Linearity and Monotonicity of the Lebesgue Integral; all variables are bounded, hence integrable),

$$\mathbb{E}\bigl[L(M)^{2}\bigr]=\sum_{i=1}^{n}\mathbb{E}[Y_i^{2}]+\sum_{i\ne j}\mathbb{E}[Y_iY_j]=n\,Q(\tilde w),\qquad\mathbb{E}\bigl[(L(M)-c)^{2}\bigr]=n\,Q(\tilde w)-2c\cdot0+c^{2}=n\,Q(\tilde w)+c^{2}.\tag{M2}$$

(b) Let $h_\sigma=\mathbf{1}_{A_\sigma}-\bar S_\sigma$, a Borel measurable function on $\mathbb{R}$ (the indicator of a Borel set minus a constant, measurable by claims 1 and 2 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions), and $X_i=h_\sigma(V_i)$, so that $S_\sigma-n\bar S_\sigma=\sum_{i=1}^{n}X_i$, $|X_i|\le1$, $\mathbb{E}[X_i]=\bar S_\sigma-\bar S_\sigma=0$ and $\mathbb{E}[X_i^{2}]\le1$, $\mathbb{E}[X_i^{4}]\le1$. Expanding,

$$\mathbb{E}\Bigl[\Bigl(\sum_{i=1}^{n}X_i\Bigr)^{4}\Bigr]=\sum_{(i_1,i_2,i_3,i_4)\in\{1,\dots,n\}^{4}}\mathbb{E}[X_{i_1}X_{i_2}X_{i_3}X_{i_4}].$$

Fix a multi-index and suppose some index value $i$ occurs exactly once in it. Let $J=\{j_1<\dots<j_q\}$ be the set of the other index values (nonempty, disjoint from $I=\{i\}$, $1\le q\le3$), and let $m_r$ be the multiplicity of $j_r$ in the multi-index; the product of the remaining three factors is $\psi(V_{j_1},\dots,V_{j_q})$ for the function $\psi:\mathbb{R}^{q}\to\mathbb{R}$, $\psi(x_1,\dots,x_q)=\prod_{r=1}^{q}h_\sigma(x_r)^{m_r}$, which is jointly Borel in the sense of Joint Distribution, Expectations, and Block Independence for Independent Random Variables: coordinate projections are jointly Borel and compositions with the Borel function $h_\sigma$ remain so by claim 4 of Joint Distribution, Expectations, and Block Independence for Independent Random Variables, and finite products of measurable real functions are measurable by Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions. By claim 3 of Joint Distribution, Expectations, and Block Independence for Independent Random Variables (with the blocks $I$ and $J$), $X_i$ and $\psi(V_{j_1},\dots,V_{j_q})$ are independent bounded random variables, so by Expectation of a Product of Independent Random Variables the term equals $\mathbb{E}[X_i]\cdot\mathbb{E}[\psi(V_{j_1},\dots,V_{j_q})]=0$. The remaining multi-indices are those in which every value occurs at least twice: either all four entries coincide ($n$ multi-indices, each term $\mathbb{E}[X_i^{4}]\le1$), or the entries take exactly two values, each twice ($3n(n-1)$ multi-indices: three ways to pair the four positions, $n(n-1)$ ordered choices of the two values; each term is $\mathbb{E}[X_i^{2}X_j^{2}]=\mathbb{E}[X_i^{2}]\mathbb{E}[X_j^{2}]\le1$ by the same independence and product argument). Hence

$$\mathbb{E}\bigl[(S_\sigma-n\bar S_\sigma)^{4}\bigr]\le n+3n(n-1)\le3n^{2}.$$

Applying Markov's inequality (Markov's and Chebyshev's Inequalities) to the nonnegative random variable $(S_\sigma-n\bar S_\sigma)^{4}$ with $a=(n\bar S_\sigma/2)^{4}$,

$$P\bigl(|S_\sigma-n\bar S_\sigma|\ge n\bar S_\sigma/2\bigr)=P\bigl((S_\sigma-n\bar S_\sigma)^{4}\ge(n\bar S_\sigma/2)^{4}\bigr)\le\frac{3n^{2}\cdot16}{n^{4}\bar S_\sigma^{4}}=\frac{48}{n^{2}\bar S_\sigma^{4}}.\tag{M4}$$

Step 5: claim 4. By Move Information of a Discrete Probability Mass Function, Step 1 (with $\mathsf{A}=\mathsf{K}_N$, the support of $p_N$) and claim 2, $\mathsf{J}(p_N;a,w)=\sum_{k\in\mathsf{K}_N}p_N(k)\frac{\bar S_\sigma^{2}}{(k_\sigma+1)^{2}}(L(k)+c)^{2}$, a finite sum. Put $n=N+2$; from here on, $(\Omega,\mathcal{F},P)$, $V_i$, $S_\gamma$ and $M$ are the objects of Step 0 constructed for this $n$. For $k\in\mathsf{K}_N$ let $k'=k+2\delta_\sigma\in\mathsf{K}_n$; the map $k\mapsto k'$ is a bijection from $\mathsf{K}_N$ onto $\mathsf{K}_n^{\ge2}=\{k'\in\mathsf{K}_n:k'_\sigma\ge2\}$ (with inverse $k'\mapsto k'-2\delta_\sigma$), along which the finite sum over $\mathsf{K}_N$ below is reindexed by claim 2 of Properties of a Sum over a Finite Index Set. Since $n!=(N+1)(N+2)\,N!$ and $(k_\sigma+2)!=(k_\sigma+1)(k_\sigma+2)\,k_\sigma!$, the formula of Multinomial Probability Mass Function gives

$$p_n(k')=\frac{(N+1)(N+2)\,\bar S_\sigma^{2}}{(k_\sigma+1)(k_\sigma+2)}\,p_N(k),\quad\text{i.e.}\quad\frac{\bar S_\sigma^{2}}{(k_\sigma+1)^{2}}p_N(k)=\frac{p_n(k')}{(N+1)(N+2)}\cdot\frac{k_\sigma+2}{k_\sigma+1}=\frac{p_n(k')}{(N+1)(N+2)}\Bigl(1+\frac{1}{k'_\sigma-1}\Bigr),$$

using $k_\sigma+1=k'_\sigma-1\ge1$. Also $L(k')=L(k)+2\tilde w_\sigma/\bar S_\sigma=L(k)+2c$, so $L(k)+c=L(k')-c$. Therefore

$$\mathsf{J}(p_N;a,w)=\frac{1}{(N+1)(N+2)}\sum_{k'\in\mathsf{K}_n^{\ge2}}p_n(k')\Bigl(1+\frac{1}{k'_\sigma-1}\Bigr)(L(k')-c)^{2}\le\frac{\Sigma_1+\Sigma_2}{(N+1)(N+2)},$$

where, all terms being nonnegative,

$$\Sigma_1=\sum_{k'\in\mathsf{K}_n}p_n(k')(L(k')-c)^{2},\qquad\Sigma_2=\sum_{k'\in\mathsf{K}_n^{\ge2}}p_n(k')\frac{(L(k')-c)^{2}}{k'_\sigma-1}.$$

By (R) and (M2) (with this $n$), $\Sigma_1=\mathbb{E}[(L(M)-c)^{2}]=nQ(\tilde w)+c^{2}$.

To bound $\Sigma_2$, split $\mathsf{K}_n^{\ge2}$ into $E=\{k'\in\mathsf{K}_n^{\ge2}:k'_\sigma-1\ge n\bar S_\sigma/4\}$ and its complement $E^{c}$ in $\mathsf{K}_n^{\ge2}$. On $E$, $1/(k'_\sigma-1)\le4/(n\bar S_\sigma)$, so the part of $\Sigma_2$ over $E$ is at most $\frac{4}{n\bar S_\sigma}\Sigma_1=\frac{4Q(\tilde w)}{\bar S_\sigma}+\frac{4c^{2}}{n\bar S_\sigma}$. If $n\bar S_\sigma<4$ then $E^{c}=\emptyset$, because $k'_\sigma\ge2$ gives $k'_\sigma-1\ge1>n\bar S_\sigma/4$. Otherwise $n\bar S_\sigma\ge4$, and every $k'\in E^{c}$ satisfies $k'_\sigma<1+n\bar S_\sigma/4$, hence $n\bar S_\sigma-k'_\sigma>\tfrac34n\bar S_\sigma-1\ge\tfrac12n\bar S_\sigma$; so $E^{c}\subseteq\{k'\in\mathsf{K}_n:|k'_\sigma-n\bar S_\sigma|\ge n\bar S_\sigma/2\}$. On $\mathsf{K}_n$ we have $|L(k')|\le\sum_\gamma\frac{|\tilde w_\gamma|}{\bar S_\gamma}k'_\gamma\le\beta n$ and $|c|\le\beta$, so $(L(k')-c)^{2}\le(\beta n+\beta)^{2}\le4n^{2}\beta^{2}$, while $1/(k'_\sigma-1)\le1$. Hence, by (R) applied to the indicator of the event $\{|S_\sigma-n\bar S_\sigma|\ge n\bar S_\sigma/2\}$ and (M4), the part of $\Sigma_2$ over $E^{c}$ is at most

$$4n^{2}\beta^{2}\sum_{k'\in\mathsf{K}_n,\ |k'_\sigma-n\bar S_\sigma|\ge n\bar S_\sigma/2}p_n(k')=4n^{2}\beta^{2}\,P\bigl(|S_\sigma-n\bar S_\sigma|\ge n\bar S_\sigma/2\bigr)\le\frac{192\,\beta^{2}}{\bar S_\sigma^{4}}.$$

Collecting, and using $\frac{nQ(\tilde w)}{(N+1)(N+2)}=\frac{Q(\tilde w)}{N+1}$,

$$\mathsf{J}(p_N;a,w)\le\frac{Q(\tilde w)}{N+1}+\frac{1}{(N+1)(N+2)}\Bigl(c^{2}+\frac{4Q(\tilde w)}{\bar S_\sigma}+\frac{4c^{2}}{n\bar S_\sigma}+\frac{192\beta^{2}}{\bar S_\sigma^{4}}\Bigr).$$

Finally, $c^{2}=\frac{\tilde w_\sigma^{2}}{\bar S_\sigma}\cdot\frac{1}{\bar S_\sigma}\le\frac{Q(\tilde w)}{s_{\min}}$, $\frac{4Q(\tilde w)}{\bar S_\sigma}\le\frac{4Q(\tilde w)}{s_{\min}}$, $\frac{4c^{2}}{n\bar S_\sigma}\le\frac{4Q(\tilde w)}{s_{\min}^{2}}$ (as $n\ge1$), and $\beta^{2}=\max_{\gamma\in\{1,\dots,l\}}\Bigl(\frac{\tilde w_\gamma^{2}}{\bar S_\gamma}\cdot\frac{1}{\bar S_\gamma}\Bigr)\le\frac{Q(\tilde w)}{s_{\min}}$ (each term $\tilde w_\gamma^{2}/\bar S_\gamma$ is at most the sum $Q(\tilde w)$), so $\frac{192\beta^{2}}{\bar S_\sigma^{4}}\le\frac{192\,Q(\tilde w)}{s_{\min}^{5}}$. Since $0<s_{\min}\le1$ (each $\bar S_\gamma>0$ by hypothesis, and $\bar S_\gamma\le\sum_{\gamma'=1}^{l}\bar S_{\gamma'}=1$ as the other summands are nonnegative), each of the four terms is at most its bound with $s_{\min}^{5}$ in the denominator, and $1+4+4+192=201$. $\blacksquare$