7
$\begingroup$

I have two distributions that I suspect are close in statistical (variational) distance i.e. $\sum_{x} \| D_1(x) - D_2(x) \|$ is small.

The first distribution is $N$ coin-flips of iid coins with probability $p$ of coming up heads.

For the second distribution, I first pick $F$ locations uniformly randomly out of the $N$ and set them to heads. For the remaining locations, I flip iid coins with bias $p' = \frac{pN - F}{N- F}$. (The rationale for the adjusted probability is so that the expected number of heads match up in both situations.)

How close are these distributions in statistical distance? Is there an easy bound one can place? Here I'm thinking of $p = N^{-1/10}$ and $F \le N^{1/100}$.

My progress

Let's note that both distributions are permutation symmetric so the statistical distance between the two distributions is equivalent to the statistical distance between random variables $X$ and $Y$ where

$X \sim \textrm{Binomial}(N, p)$ and $Y \sim F + \textrm{Binomial}(N-F, p')$.

The intuition as to why these random variables should have similar distribution is that as $N \rightarrow \infty$, the distributions approach normal distributions which are both centered at $pN$ but $X$ concentrates faster than $Y$.

$\endgroup$
3
  • $\begingroup$ You might want to specify what you mean by "statistical (variational) distance" $\endgroup$
    – Snoop
    Oct 15, 2022 at 14:58
  • $\begingroup$ @Snoop en.m.wikipedia.org/wiki/… $\endgroup$
    – Clement C.
    Oct 15, 2022 at 20:54
  • $\begingroup$ I haven't worked through the details but as a starting point you might like to calculate the probability of getting exactly $F-1$ heads in each case. $\endgroup$
    – JCW
    Oct 16, 2022 at 8:20

1 Answer 1

1
$\begingroup$

Hopefully, I didn't make too many mistakes in the asymptotic bounds in the end... but this should work and give something (not necessarily the best bound, but something).


This may be overkill, but let $$ \sigma_1^2 := Np(1-p), \qquad \sigma^2_2 := (N-F)p'(1-p'), \qquad \mu_1=\mu_2 := Np $$ Then, using the triangle inequality and comparison between Poisson Binomial Distributions (of which both your distributions are a special case: one being binomial, and the other being a PBD with only two distinct values of $p_i$, namely $1$ and $p'$) and "translated Poisson distributions" from Lemmas 1 and 2 of [DDS12], we get $$\begin{align*} \mathrm{TV}(X,Y) &\leq \mathrm{TV}(X,🐟_X)+\mathrm{TV}(Y,🐠_Y) +\mathrm{TV}(🐟_X,🐠_Y) \\ &\leq \frac{2+\sqrt{Np^3(1-p)}}{\sigma^2_1}+\frac{2+\sqrt{(N-F)p'^3(1-p')}}{\sigma^2_2}+\frac{1+|\sigma^2_1-\sigma^2_2|}{\sigma^2_1} \end{align*}$$ denoting by $🐟_X$ and $🐠_Y$ the two translated Poisson with parameters $\mu_1,\sigma_1$ and $\mu_2,\sigma_2$, respectively (see [DDS12] for the definition).

In the setting of parameters you consider ($F \ll N$, $p \ll 1/F$, etc.), the first two terms are $$ \frac{2+\sqrt{Np^3(1-p)}}{\sigma^2_1}+\frac{2+\sqrt{(N-F)p'^3(1-p')}}{\sigma^2_2} \leq \frac{2+\sqrt{Np^3}}{\sigma^2_1}+\frac{2+\sqrt{N p^3}}{\sigma^2_2} = O\left(\sqrt{\frac{p}{N}}\right) $$ while the third is $$ \frac{1+|\sigma^2_1-\sigma^2_2|}{\sigma^2_1} \leq O\left( \frac{F}{Np}\right) $$ (not being too careful with the constants, gratefully using the $O(\cdot)$ notation, but that should be correct), So you should get some bound of the form $$ \mathrm{TV}(X,Y) = O\left(\sqrt{\frac{p}{N}}+\frac{F}{Np}\right) = O\left(\frac{1}{N^{11/20}}\right) $$ the last bound for the specific setting $p=1/N^{1/10}$ and $F\leq N^{1/100}$ you mentioned.


[DDS12] Learning Poisson Binomial Distributions. Daskalakis, Diakonikolas, and Servedio, STOC'12. https://arxiv.org/abs/1107.2702

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .