## Local view of setting p*n out of n bits to 1

For p a constant in (0,1) and n going to infinity such that pn is an integer, consider the distribution on n bits that selects a random subset of pn bits, sets those to 1, and sets the others to 0. What is the largest k = k(n,p) so that the induced distribution on any k bits is 1/10 close in total variation distance (a.k.a. statistical distance) to the distribution that sets each bit to 1 independently with probability p? For every p I would like to know k up to a sublinear (i.e. o(n)) additive term. (For starters, p = 1/8 is good too.) Does anybody know of a place where this is worked out?

Thanks! Emanuele

-

You want $\frac15 = \sum_t |P_1(count=t) - P_2(count=t)|$.

where $P_1$ has a binomial distribution and $P_2$ is hypergeometric.

The difference between these distributions is shown in this Mathematica demonstration.

I believe both are reasonably well approximated by normal distributions. Both have mean $pk$. The variance for the binomial distribution is $kp(1-p)$, while it is $\frac{n-k}{n-1}*k(p)(1-p)$ for the hypergeometric distribution.

So, the value of k should be so that the normal distributions $N(0,1)$ and $N(0,\sqrt{\frac{n-k}{n-1}})$ have total variation distance $\frac1{10}$. That should be at about $k=(1-c)n$ where $N(0,1)$ and $N(0,\sqrt{c})$ are $\frac1{10}$ apart. Numerically, it seems that $c$ should be about 0.6605 so $\sqrt{c}$ should be about 0.8127. $k = 0.3395n$.

It appears this is not sensitive to the value of $p$.

-
Thanks, does the normal approximation to the hypergeometric hold with negligible error even for such large k? – Emanuele Viola Jan 18 2010 at 0:41
Yes: dartmouth.edu/~chance/teaching_aids/… The difficulty in using a normal approximation occurs when p is near 0 or 1 or k is near n. This has also been studied stat.tamu.edu/~cha/sub-gaussian-jspi-07.pdf but the first reference is the relevant one. – Douglas Zare Jan 18 2010 at 1:59
Thanks for the references! But the error bound is not clear to me even at a high level: already in Berry–Esseen's bound the pointwise error is about $1/\sqrt{n}$, which won't allow to sum over $k = \Theta(n)$ points. Perhaps one can combine this with a tail bound, but it seems it won't be easy to get an estimate on k up to an additive o(n), right? – Emanuele Viola Jan 18 2010 at 17:03
As the second reference indicates, the Berry-Esseen error estimate for the normal approximation is about as good for the hypergeometric as for the binomial distribution. You don't need a pointwise error bound. You can use Berry-Esseen on the three intervals, where the middle one is where $P_2 \gt P_1$, or in fact, you can just use it on the middle interval. The total variation distance is double the sum of $P_2-P_1$ over that interval. – Douglas Zare Jan 18 2010 at 17:56

Hi Emanuele. Short answer: take a look at Theorem 3.2 in this paper by Diaconis and Holmes:

http://www-stat.stanford.edu/~susan/papers/steinbirthdeath.pdf

as well as its reference to Diaconis and Freedman (1981). It seems the optimal k is known to be $\Theta(n)$, independent of $p$.

I have some questions for you though: Your choice of 1/10 seems a bit "arbitrary", which makes me curious to know whether you really want the correct value of k up to o(n)... I think changing 1/10 to 1/20, say, would change k by a linear amount. So if the answer is k = cn, you really want to know how c depends on 1/10?

Another question: Perhaps another way to attack this problem is to identify the event A on which the hypergeometric and binomial random variables have the most differing probabilities. Is it possible to compute this exactly, or at least decide whether it is an event of the form $A = {u : a \leq u \leq b}$?

-