# 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$ ?

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