3
$\begingroup$

I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant literature.

Consider a random variable $X$ distributed hypergeometrically with parameters $(n,m,i)$, i.e.,

$$p_X(x)=\frac{{i \choose x}{n-i \choose m-x}}{{n \choose m}},$$ where $\max(0,m+i-n)\leq x \leq \min(i,m)$.

The simple question I am asking is are there any good lower bounds for $$\sum_x (p_X(x))^2$$ as a function of $n$ specifically (a bound which holds for a given $n$ and which is not dependent on $i,m$)? Note: the summation is over the entire support of $X$, i.e., $\max(0,m+i-n)\leq x \leq \min(i,m)$.

My attempt and observations:

Using tail bounds (see 1) for the hypergeometric distribution gives $$\sum_{x:|x-\mathbb E X|\leq\sqrt n}p_X(x)\geq 1-2e^{-2}=c.$$ Now we can use Cauchy-Schwarz to get something along the lines of: \begin{align*} \sum_x p_X(x)^2 &\geq \sum_{x:|x-\mathbb E X|\leq\sqrt n}p_X(x)^2\\ &\geq \frac{1}{2\sqrt n} c^2=\frac{c'}{\sqrt n}. \end{align*}

This bound turns out to be weak for my purposes. I also computed the quantity for $n\in \{3,4,5,...,1000\}$ and for all relevant $i,m$ and it looks like $\sum_x p_X(x)^2 \geq \frac{1}{\log^2 n}$. This solves my problem if it is indeed true for all $n$.

Any help/leads would be appreciated. Thanks!

$\endgroup$
6
  • $\begingroup$ Hi and welcome to MO. In the expression you're interested in, what are summing on - $n$ i.i.d samples denoted by $x$? Maybe $x_i$ where $i=1,\ldots, n$ then. Perhaps it'd be easier if you specify it in the question itself. $\endgroup$
    – Amir Sagiv
    Sep 4, 2018 at 18:15
  • $\begingroup$ By "as a function of $n$ specifically" do you mean for fixed $m$ and $i$? But then it's easy to see $p_X(0) = 1 + O(1/n)$. $\endgroup$ Sep 4, 2018 at 19:02
  • $\begingroup$ @AmirSagiv Thanks! The summation is over the support set of the random variable $X$, I've edited the question to make it clear. Basically, $\sum_x p(x)=1$, but I want a lower bound for $\sum_x p(x)^2$ for this particular distribution. If the distribution was instead uniform, $1/n$ would be a lower bound. Hope that makes it clear. $\endgroup$
    – User93
    Sep 5, 2018 at 5:24
  • $\begingroup$ @RobertIsrael, I mean a bound that holds for worst case $i,m$. Of course, $1/m$ or $1/i$ are valid lower bounds, so in that case I would just take $1/n$ to be the lower bound since $i,m \leq n$. The idea is that I observe the summation to be at least as big as $1/\log^2 n$ and I want to see if that is indeed true. $p_X(0)$ being $1+O(1/n)$ is true only for constant $i,m$, correct? $\endgroup$
    – User93
    Sep 5, 2018 at 5:27
  • 1
    $\begingroup$ I mean that, for fixed $m$ and $i$, $p_X(0)$ is a rational function of $n$ with numerator and denominator both monic polynomials in $n$ of degree $m$, so $p_X(0) = 1 + O(1/n)$. $\endgroup$ Sep 5, 2018 at 7:58

1 Answer 1

3
$\begingroup$

Suppose that $i=n-i=m$ (so that $n=2m$) and $m$ is even; I suppose that such $i$ and $m$ you consider relevant. Then \begin{equation} p_X(x)=\binom mx^2\Big/ \binom{2m}m\le\binom m{m/2}^2\Big/ \binom{2m}m \asymp\frac{(2^m/\sqrt m)^2}{2^{2m}/\sqrt m}=\frac1{\sqrt m}\asymp\frac1{\sqrt n}, \end{equation} whence \begin{equation} \sum_x p_X(x)^2\ll\frac1{\sqrt n}\, \sum_x p_X(x)=\frac1{\sqrt n}. \end{equation} So, in view of the reasoning in your question, the lower bound $\frac1{\sqrt n}$ is optimal up to a constant factor.

$\endgroup$
1
  • $\begingroup$ Thanks for the response, $O(\frac{1}{\sqrt n})$ being tight implies I need a different approach for my bigger problem. $\endgroup$
    – User93
    Sep 5, 2018 at 5:53

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.