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](https://arxiv.org/abs/1311.5939)) 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!



Lower bound on the sum of pmf squared of a hypergeometric distribution
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. 


