Finite Bernoulli fluctuations and matching exponential rates

The total weight is ${\prod }_{i=1}^n(p+(1-p))=1$, so the stipulated weights form a finite probability law. Summing over all coordinates except $i$ gives $P(X_i=1)=p$ and $P(X_i=0)=1-p$; the product factorization also gives independence. For $0\le k\le n$ put $c_{n,k}:=\mathrm{\#}\{S\subseteq \{1,\dots ,n\}:\mathrm{\mid }S\mathrm{\mid }=k\}$. The set of coordinates with value $1$ gives a bijection between outcomes with $K=k$ and such subsets, so $P(K=k)=c_{n,k}{p}^k(1-p{)}^{n-k}$. By [F4] and [F12], $\mathbb{E}{X}_i=p$ and $\mathrm{Var}(X_i)=\mathbb{E}[(X_i-p{)}^2]=p(1-p)$. For $i\mathrm{\ne }j$, the product weights factor the finite sum, giving $\mathbb{E}[(X_i-p)(X_j-p)]=\mathbb{E}(X_i-p)\mathbb{E}(X_j-p)=0$. Expanding $K$ and $(K-np{)}^2$ therefore yields $\mathbb{E}K=np$ and $\mathrm{Var}(K)=np(1-p)$.

The finite-sum definition [F5] and product weights give $M_K(s)={\sum }_{x\in {\mathrm{\Omega }}_n}{P}_p(x)e^{s{\sum }_i{x}_i}={\prod }_{i=1}^n((1-p)+p{e}^s)=(1-p+p{e}^s{)}^n\mathrm{.}$ This is a finite factorization, so no limiting interchange is involved.

On $0<a<1$, differentiating the displayed expression for $D$ with [F9] gives $D(p\mathrm{\parallel }p)=0$, ${\mathrm{\partial }}_{a}D(a\mathrm{\parallel }p){\mathrm{\mid }}_{a=p}=0$, and ${\mathrm{\partial }}_a^{2}D(a\mathrm{\parallel }p)=1\mathrm{/}[a(1-a)]\ge 4$, since $a(1-a)\le 1\mathrm{/}4$. Let $G(a)=D(a\mathrm{\parallel }p)-2(a-p{)}^2$. Then $G(p)=G^{\mathrm{\prime }}(p)=0$ and $G^{\mathrm{\prime }\mathrm{\prime }}\ge 0$. For $a>p$, the mean value theorem applied first to $G^{\mathrm{\prime }}$ and then to $G$ gives $G^{\mathrm{\prime }}(a)\ge 0$ and $G(a)\ge 0$; for $a<p$, the same two applications give $G^{\mathrm{\prime }}(a)\le 0$ and again $G(a)\ge 0$. Thus $D(a\mathrm{\parallel }p)\ge 2(a-p{)}^2$ for interior $a$. At $a\downarrow 0$, the only noncontinuous-looking term is $a\log a=-\log (1\mathrm{/}a)\mathrm{/}(1\mathrm{/}a)$, which tends to zero by [F11]; at $a\uparrow 1$ the analogous term is $(1-a)\log (1-a)$. The remaining factors are continuous, so the endpoint extensions preserve the inequality.

Fix $1\le k\le n-1$ and let $a=k\mathrm{/}n$. For $0\le j\le n$ put $q_j=c_{n,j}{a}^j(1-a{)}^{n-j}$. These are the count probabilities under the finite product weights with parameter $a$; their sum is $1$ by factoring the total weight as $(a+(1-a){)}^n$. For each $0\le j<n$, count pairs $(S,T)$ with $S\subset T\subseteq \{1,\dots ,n\}$, $\mathrm{\mid }S\mathrm{\mid }=j$, and $\mathrm{\mid }T\mathrm{\mid }=j+1$. Choosing $S$ first gives $c_{n,j}(n-j)$ pairs, while choosing $T$ first gives $c_{n,j+1}(j+1)$; hence $c_{n,j+1}\mathrm{/}{c}_{n,j}=(n-j)\mathrm{/}(j+1)$. Therefore $\frac{q_{j+1}}{q_j}=\frac{n-j}{j+1}\frac{a}{1-a}\mathrm{.}$ The factor $(n-j)\mathrm{/}(j+1)$ decreases strictly with $j$, since $(n-j-1)(j+1)<(n-j)(j+2)$ for $j<n-1$. At $j=k-1$ the ratio is $(n-k+1)\mathrm{/}(n-k)>1$, and at $j=k$ it is $k\mathrm{/}(k+1)<1$. Thus the sequence increases through $q_k$ and decreases after it, so $q_k$ is the largest of its $n+1$ masses. Their sum is $1$, whence $1\mathrm{/}(n+1)\le q_k\le 1$.

Pointwise on ${\mathrm{\Omega }}_n$, ${\mathbf{1}}_{\{\mathrm{\mid }\bar{X}-p\mathrm{\mid }\ge \epsilon \}}\le (\bar{X}-p{)}^2\mathrm{/}{\epsilon }^2$. Summing this inequality with the finite weights and using step 1.1 gives the first probability bound.

Suppose first $p<a<1$ and put $s=\log \text{\hspace{0.17em}⁣}(a(1-p)\mathrm{/}(p(1-a)))>0$. On $\{K\ge na\}$, $e^{sK}\ge e^{sna}$, so the finite expectation of the nonnegative random variable $e^{sK}$ is at least $e^{sna}{P}_p(K\ge na)$. By step 1.2, $P_p(K\ge na)\le e^{-sna}(1-p+p{e}^s{)}^n=e^{-nD(a\mathrm{\parallel }p)},$ where $e^s=a(1-p)\mathrm{/}(p(1-a))$, $1-p+p{e}^s=(1-p)\mathrm{/}(1-a)$, and [F7]–[F8] simplify the logarithm. If $0<a<p$, the same value of $s$ is negative; on $\{K\le na\}$ one again has $e^{sK}\ge e^{sna}$, and the same substitution yields $P_p(K\le na)\le e^{-nD(a\mathrm{\parallel }p)}$. This proves both exponential tail bounds without using a general concentration theorem as a premise.

Direct division of the two point probabilities, using the same subset count $c_{n,k}$ from step 1.1, gives $\frac{P_p(K=k)}{q_k}={\left(\frac{p}{a}\right)}^k{\left(\frac{1-p}{1-a}\right)}^{n-k}\mathrm{.}$ Since $k=na$ and $n-k=n(1-a)$, [F7]–[F8] give the logarithm of this ratio as $na\log (p\mathrm{/}a)+n(1-a)\log ((1-p)\mathrm{/}(1-a))=-nD(a\mathrm{\parallel }p)$, so the ratio is $e^{-nD(a\mathrm{\parallel }p)}$. Combining with step 2.1 proves the claimed bounds for $1\le k\le n-1$. For $k=0$ and $k=n$, direct evaluation gives $P_p(K=0)=(1-p{)}^n=e^{-nD(0\mathrm{\parallel }p)}$ and $P_p(K=n)=p^n=e^{-nD(1\mathrm{\parallel }p)}$, which satisfy the same inequalities.

If $0<\epsilon <1$, split the deviation event into the upper threshold $a_{+}=p+\epsilon$ and lower threshold $a_{-}=p-\epsilon$. For an interior threshold apply step 2.3 and then step 1.3; at $a_{+}=1$ or $a_{-}=0$ use the exact endpoint probability $p^n$ or $(1-p{)}^n$ and the endpoint case of step 1.3; a threshold outside $[0,1]$ gives an empty event. Each nonempty tail is at most $e^{-2n{\epsilon }^2}$, so their sum is at most $2e^{-2n{\epsilon }^2}$. If $\epsilon \ge 1$, the deviation event is empty because $0\le \bar{X}\le 1$ and $0<p<1$.

If $k_n\mathrm{/}n\to a\in (0,1)$, then $D(k_n\mathrm{/}n\mathrm{\parallel }p)\to D(a\mathrm{\parallel }p)$ by continuity on $(0,1)$. Taking logarithms of step 3.1 and dividing by $n$ bounds $n^{-1}\log P_p(K=k_n)$ between $-D(k_n\mathrm{/}n\mathrm{\parallel }p)-\log (n+1)\mathrm{/}n$ and $-D(k_n\mathrm{/}n\mathrm{\parallel }p)$. By [F11], $\log (n+1)\mathrm{/}n\to 0$, so the squeeze theorem gives the stated rate. These probabilities remain conditional on the explicitly stipulated product law; no finite sample or measurement is asserted.