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

  • 2
    $\begingroup$ I'm not sure approximating the Binomials will give you the best result. It looks like their TVD is approximately $\delta n$ whereas the Normal approximation gives a constant times $\delta\sqrt{n}$, which is not as good. To get a lower bound you will need to work the TVD out to $O(\delta^2)$, but that looks straightforward. It looks like you can also obtain exact formulas in terms of incomplete Beta functions. $\endgroup$ – whuber Jul 5 '17 at 22:04
  • $\begingroup$ Thanks, I will try to lower bound the total variation directly. $\endgroup$ – vkonton Jul 5 '17 at 22:15
  • 1
    $\begingroup$ @vkonton, what size $n$ values are you interested in? $\endgroup$ – Lucas Roberts May 30 '18 at 15:33
  • 1
    $\begingroup$ Because the TVD between these binomials can be computed and even expressed exactly for small $n$ or sufficiently small $\delta,$ the best possible lower bound would be the TVD itself. Please explain, then, what the locus of intended application of this bound is and, if possible, provide criteria for us to compare different bounds. $\endgroup$ – whuber Jun 18 '19 at 13:51

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

| cite | improve this answer | |
  • 1
    $\begingroup$ Since I cannot add a comment - the solution provided by Lucas Roberts seems incorrect: 1. An error occurs going from the 3th to the 4th equation. The fraction $(1+2\delta)/(1-2\delta)$ should read $(1-2\delta)/(1+2\delta)$. 2. According to the wikipedia page on Markov's inequality, the stated version of Markov's inequality only seems valid if $g(X)$ is monotonically increasing. If we correct according to my first point, then the considered $g$ will not be monotonically increasing. $\endgroup$ – smapers Jun 17 '19 at 19:57
  • $\begingroup$ @smapers Thanks for spotting the typo, I think you are correct about the sign error, which incidentally propogates through a couple other lines-I'll fix that part soon. For the Markov inequality there is a proof which requires non-decreasing function $g(\cdot)$. However, I think all you need for the use here is that the $g(\cdot)$ function is non-negative. For example splitting the non-negative function $g(\cdot)$ around a single point and both (partial) expectations are non-negative so dropping 1 of the 2 summands would give you an inequality. $\endgroup$ – Lucas Roberts Jun 18 '19 at 11:28
  • $\begingroup$ @smapers I updated the derivation in the post to reflect the changes in typo you spotted, thanks! $\endgroup$ – Lucas Roberts Oct 26 '19 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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