0
$\begingroup$

An interesting combinatorial identity is the Vandermonde convolution identity:

$$ \sum_k {n\choose k}{m\choose s-k} = {n+m \choose s},$$

which can be proved by considering the coefficients in $(x+1)^{n+m} = (x+1)^n (x+1)^m$. I am interested in the behavior of the summands: which summands among them contribute the most?.

More specifically, I'd like to look at the behavior of the function

$$ F(k) = \frac{{n\choose k}{m\choose s-k}}{{n+m \choose s}}. $$

In a specific probabilistic problem, intuition suggests that $F(k)$ peaks near $k$, with $\frac{n}{n+m} = \frac{k}{s}$. Indeed, in the limit case $s = n+m$, $k$ had better be $n$ for the value to survive. However, I'm not satisfied with the limit case.

Given that $F$ does peak around $k = k^* := \frac{ns}{n+m}$, I want to know how much it peaks. Thus the following question:

Find the smallest possible non-negative integer $\epsilon$ such that

$$ \sum_{k \in [k^*-\epsilon, k^*+\epsilon]} F(k) > 90\%.$$

The answer $\epsilon$ depends on $n, m, s$, and "$90\%$".

$\endgroup$

1 Answer 1

2
$\begingroup$

$\newcommand\ep{\epsilon}$

Of course, there is no simple explicit expression for the smallest $\ep$. However, one can give upper bounds on or approximations of this $\ep$. Indeed, $F$ is the probability mass function of a random variable, say $X$, with the hypergeometric distribution with parameters $n,m,s$. So, by a Hoeffding inequality, for $\ep\in[0,k^*]$ $$S(\ep):=\sum_{k\in[k^*-\ep,k^*+\ep]}F(k)=P(|X-k^*|\le\ep) \ge1-2e^{-2\ep^2/s}.$$ Solving now the equation $1-2e^{-2\ep^2/s}=0.90$ for $\ep>0$, we get a desired upper bound on the smallest $\ep$ such that $S(\ep)\ge0.90$.

If $s$ is much smaller than $\min(n,m)$ and if $\frac n{n+m}$ is not close to $0$ or $1$, then one can use a normal approximation to hypergeometric distribution.

$\endgroup$
8
  • $\begingroup$ Thank you! I have no background in statistics, and thought it's quite hard to analyze the entity I gave. Turned out it's just the hypergeometric distribution (textbook-level).. $\endgroup$
    – Student
    Apr 15, 2020 at 17:30
  • $\begingroup$ To my surprise.. this estimate does not depend on $n+m$.. a direct corollary is that no matter how large the black box it, to understand it (to some extent), you only need to sample a little bit (say 50) of them!!! $\endgroup$
    – Student
    Apr 15, 2020 at 18:14
  • $\begingroup$ An edit has been submitted suggesting that your $\epsilon^2/s$'s are supposed to be $\epsilon^2 s$. Is that correct? $\endgroup$
    – LSpice
    Apr 15, 2020 at 20:18
  • 1
    $\begingroup$ @Student : (i) "this estimate does not depend on $n+m$": (ii) "your "$\epsilon^2/s$'s are supposed to be "$\epsilon^2s$'s"; (iii) "why the Hoeffding inequality can be applied onto hypergeometric distributions?" First, concerning (iii): this inequality by Hoeffding holds because, by Theorem 4 in his paper at en.wikipedia.org/wiki/Hypergeometric_distribution#cite_note-3 , the sampling without replacement is convex-dominated by the sampling with replacement. I have now replaced the link to Hoeffding by a hopefully better one. $\endgroup$ Apr 15, 2020 at 23:40
  • 1
    $\begingroup$ Previous comment continued: Now concerning (ii): The original expression in the answer was correct. A quick check of that is as follows: take $\epsilon\asymp\sqrt s\asymp$(standard deviation of $X$). Then the bound should be $\asymp1$, which it was and now again is. I have reversed your edits. $\endgroup$ Apr 15, 2020 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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