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



Local view of setting p*n out of n bits to 1
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](http://demonstrations.wolfram.com/BinomialApproximationToAHypergeometricRandomVariable/).


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


