7
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, does the normal approximation to the hypergeometric hold with negligible error even for such large k? $\endgroup$
    – Manu
    Commented Jan 18, 2010 at 0:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Jan 18, 2010 at 1:59
  • $\begingroup$ 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? $\endgroup$
    – Manu
    Commented Jan 18, 2010 at 17:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Jan 18, 2010 at 17:56
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Manu
    Commented Jan 18, 2010 at 22:26
  • $\begingroup$ @Emanuele: So, you don't actually want k up to o(n), which was what my answer gave? $\endgroup$
    – Douglas Zare
    Commented Jan 19, 2010 at 11:08
  • $\begingroup$ @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? $\endgroup$
    – Manu
    Commented Jan 19, 2010 at 19:08
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Jan 20, 2010 at 17:27
  • $\begingroup$ 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! $\endgroup$
    – Manu
    Commented Jan 22, 2010 at 23:37

You must log in to answer this question.

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