4
$\begingroup$

Let $B(p)$ denote the Bernoulli distribution over $\{0,1\}$ and $B(p)^n$ the corresponding product distribution over $\{0,1\}^n$. For $n>1$ and $0<x<1$, define $$P_n(x):=B(\frac12+\frac x2)^n$$ and $$Q_n(x):=B(\frac12-\frac x2)^n.$$ I can show $ ||P_n(x)-Q_n(x)||_1 \le 2.1\sqrt{n}x$ using Pinsker's inequality.

Conjecture: $$ ||P_n(x)-Q_n(x)||_1 \le \sqrt{3n}x.$$

$\endgroup$
1
  • 1
    $\begingroup$ An observation (which maybe you already know): let $S_n$ be the sum of the coordinates. A point has higher probability under $P_n$ if $S_n>n/2$, higher probability under $Q_n$ if $S_n<n/2$, and the same if $S_n=n/2$. So the total variation distance between $P_n$ and $Q_n$ is $P_n(S_n>n/2)-Q_n(S_n>n/2)$ (or, by symmetry, $2P_n(S_n>n/2)-1$). $\endgroup$ Apr 6, 2016 at 3:16

1 Answer 1

6
$\begingroup$

Looking at [Pinsker's inequality], I am assuming that the left-hand side of the conjectured inequality is understood as the the total variation norm of the signed measure $P_n(x) - Q_n(x)$, which equals \begin{equation} s(y):=s_n(y):=2\sum_{j=0}^m\binom nj\big[\big(\tfrac12 + y\big)^{n - j} \big(\tfrac12 - y\big)^j - \big(\tfrac12 - y\big)^{n - j} \big(\tfrac12 + y\big)^j\big], \end{equation} where \begin{equation} m:=\lfloor n/2\rfloor,\quad y:=x/2\in[0,1/2). \end{equation} Using identities $(n-j)\binom nj=n\binom{n-1}j$ and $j\binom nj=n\binom{n-1}{j-1}$, we have \begin{equation} \tfrac1{2n}\,s'(y):=\sum_{j=0}^m\binom{n-1}j\big[\big(\tfrac12 + y\big)^{n - j-1} \big(\tfrac12 - y\big)^j + \big(\tfrac12 - y\big)^{n - j-1} \big(\tfrac12 + y\big)^j\big] \end{equation} \begin{equation} -\sum_{j=1}^m\binom{n-1}{j-1}[\big(\tfrac12 + y\big)^{n - j} \big(\tfrac12 - y\big)^{j-1} + \big(\tfrac12 - y\big)^{n - j} \big(\tfrac12 + y\big)^{j-1}\big]. \end{equation} Making in the second sum the substitution $j=k+1$ and then replacing there $k$ back by $j$, we have \begin{equation} \tfrac1{2n}\,s'(y)\Big/\binom{n-1}m=\big(\tfrac12 + y\big)^{n - m-1} \big(\tfrac12 - y\big)^m + \big(\tfrac12 - y\big)^{n - m-1} \big(\tfrac12 + y\big)^m =2^{2-n}(1-4y^2)^{n-m-1}, \end{equation} which is non-increasing in $y\in[0,1/2)$ for $n=1,2,\dots$. So, $s$ is concave.

Moreover, \begin{equation} s'_n(0)=n2^{3-n}\binom{n-1}{\lfloor n/2\rfloor}\le 2A\sqrt n \tag{*} \end{equation} for some universal real constant $A>0$. It should be easy to see that one can take ($A=2$ for $n=1$ and) $A=\sqrt3$ for $n=2,3,\dots$.

Since $s(0)=0$ and $s$ is concave, it will then follow that for $n=2,3,\dots$ $$\|P_n(x) - Q_n(x)\|=s(y)\le2Ay\sqrt n=\sqrt{3n}\,x,$$ as desired (actually, for all $x\in[0,1]$).

Addendum: To verify $(*)$, let \begin{equation} r_n:=s'_n(0)/(2\sqrt n). \end{equation} We need to show that $r_n\le\sqrt3$ for $n=2,3,\dots$. For $m=1,2,\dots$, \begin{equation} \frac{r_{2m+2}}{r_{2m}}=\sqrt{\frac{4m^2+4m+1}{4m^2+4m}}>1, \end{equation} so that $r_{2m}$ increases in $m$, and $r_{2m}\to2\sqrt{2/\pi}$ as $m\to\infty$. So, $r_{2m}<2\sqrt{2/\pi}<\sqrt3$ for all $m=1,2,\dots$. Similarly, in the "odd" case, for $m=2,3,\dots$ \begin{equation} \frac{r_{2m+3}}{r_{2m+1}}=\sqrt{1-\frac{6 m^3+11 m^2-8 m-4}{4(2m+1)(m^2-1)^2}}<1, \end{equation} so that $r_{2m+1}$ decreases in $m\ge2$. It remains to note that $(r_1,r_3,r_5)=(\sqrt4, \sqrt3, \sqrt{45/16})$, so that $r_1>r_3>r_5$.

$\endgroup$
3
  • $\begingroup$ I have added the addendum to verify that $s'_n(0)\le 2\sqrt{3n}$ for $n=2,3,\dots$. $\endgroup$ Apr 6, 2016 at 4:06
  • $\begingroup$ Beautiful, @Iosif Pinelis! $\endgroup$ Apr 6, 2016 at 4:52
  • $\begingroup$ I have simplified a bit the demonstration that $s$ is concave. $\endgroup$ Apr 6, 2016 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.