Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks, does the normal approximation to the hypergeometric hold with negligible error even for such large k? –  Emanuele Viola Jan 18 '10 at 0:41
1  
Yes: dartmouth.edu/~chance/teaching_aids/books_articles/… 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 '10 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 '10 at 17:03
1  
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 '10 at 17:56
add comment

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

share|improve this answer
    
Thanks a lot for the reference! Indeed that's very relevant. In fact I was hoping to get a tight bound on k as a function of both p and the error (now set to 1/10). The paper by Diaconis and Freedman gets close enough by giving reasonable constants. Maybe doing better than that is painful, so I'll accept your answer. Regarding your other question, I agree that's a possible approach but doesn't look easy to me. –  Emanuele Viola Jan 18 '10 at 22:26
    
@Emanuele: So, you don't actually want k up to o(n), which was what my answer gave? –  Douglas Zare Jan 19 '10 at 11:08
    
@Douglas: Indeed I'd prefer to have k up to o(n), but I was slow at understanding the details of your answer. So you are saying the points where the hypergeometric is larger than the binomial are always an interval (seems like what Ryan was asking too), so we just apply the bound in your second reference to that interval. That makes sense. Is it easy to verify this interval property? –  Emanuele Viola Jan 19 '10 at 19:08
    
Yes, expand the explicit formulas for the binomial and hypergeometric probabilities. Look at the ratio (P_1(t)/P_2(t))/(P_1(t+1)/P_2(t+1)). Cancel almost everything to get a simple quotient of polynomials. Use this near where the ratio P_1(t)/P_2(t) is close to 1. –  Douglas Zare Jan 20 '10 at 17:27
    
I haven't verified if this works (partially because the statement of the Berry–Esseen's bound for the hypergeometric distribution looks a bit scary to me) but I am accepting Douglas' answer because the combination of the observations in the comments should indeed answer my original question. Thanks! –  Emanuele Viola Jan 22 '10 at 23:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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