Solved – Lower Bound on the Total Variation Distance between two Binomials

approximationbinomial distributiondistancenormal-approximation

Let $X= B(n,1/2)$, $Y=B(n,1/2 + \delta)$, for a small $\delta >0$
be two Binomial Distributions.

Question 1.

I am looking for a lower bound on the Total Variation Distance
the two Binomials $X,Y$.

My attempt at deriving a lower bound is the following:
Since $X, Y$ have huge variance we can approximate each of them
very well with a discretized Normal and then lower bound the total variation distance of the two Normals. My problem here is that I
am not sure how to go from discretized Normals to continuous Normals.

Question 2.

Having two discretized normals as defined in this paper which are
in Total Variation distance $\epsilon$ then is it true that the continuous
Normals with the same mean and variance are also in total variation distance at most $\epsilon$ ?

Best Answer

The approach that seems most straightforward is to rewrite this problem in terms of an expectation and then bound the expectation. Start w/ $||X -Y||_{TV}=\sum_{x=0}^n |P(x)-P(y)|$ and rewrite the r.h.s.

$$\sum_{x=0}^n |{n\choose x}2^{-n}-{n\choose x}(1/2+\delta)^x (1/2-\delta)^{n-x}| = \sum_{x=0}^n {n\choose x}2^{-n}|1-2^{n}(1/2+\delta)^x (1/2-\delta)^{n-x}|$$ and then rewrite again by multiplying through the $2^n$ factor inside the absolute value,

$$\sum_{x=0}^n {n\choose x}2^{-n}|1-2^{n}(1/2+\delta)^x (1/2-\delta)^{n-x}|=\sum_{x=0}^n {n\choose x}2^{-n}\left|1-(1-2\delta)^{n}\left[\frac{(1+2\delta)}{(1-2\delta)}\right]^x\right|.$$

Now rewrite the last expression (r.h.s) as an expectation of $X\sim binom(n, 1/2)$ via:

$$\sum_{x=0}^n {n\choose x}2^{-n}\left|1-(1-2\delta)^{n}\left[\frac{(1+2\delta)}{(1-2\delta)}\right]^x\right|=\mathbb{E}_X\left|1-(1-2\delta)^{n}\exp[Xk]\right|,$$ where $k=log\left(\frac{(1+2\delta)}{(1-2\delta)} \right)>0.$

Now use whichever bound you want to use, e.g. the argument of Markov's inequality yields as one step $\Pr(g(X) \geq g(a))g(a) \leq \mathbb{E}(g(X)),$ provided $g(X)\geq 0, \forall X$, for all $a \geq 0$, a conservative choice is $a=\lfloor np\rfloor$. Now, $\Pr(g(X) \geq 0)=1$, and $g(\lfloor np\rfloor)=|1-(1-2\delta)^{n}\exp{\left[\lfloor np\rfloor k \right]}| \geq |1-(1-2\delta)^{n}(-1-\lfloor np\rfloor k) |$. Where $n \geq 1 $ and $n \in \mathbb{Z}_+$. Provided $\delta < \frac{1}{2}$ the $g(0)$ function goes to 1 as $n\to \infty$.

Related Question