# Lower bound on the sum of pmf squared of a hypergeometric distribution

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!

• 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. Sep 4 '18 at 18:15
• 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)$. Sep 4 '18 at 19:02
• @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. Sep 5 '18 at 5:24
• @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? Sep 5 '18 at 5:27
• 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)$. Sep 5 '18 at 7:58

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 $$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},$$ whence $$\sum_x p_X(x)^2\ll\frac1{\sqrt n}\, \sum_x p_X(x)=\frac1{\sqrt n}.$$ So, in view of the reasoning in your question, the lower bound $\frac1{\sqrt n}$ is optimal up to a constant factor.
• Thanks for the response, $O(\frac{1}{\sqrt n})$ being tight implies I need a different approach for my bigger problem. Sep 5 '18 at 5:53