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
 A: 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$.
A: 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\}$?
