7
$\begingroup$

Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where \begin{equation} Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}. \end{equation} To make things easier, we bring symmetry and avoid the boundry issues by letting $K=\frac{N}{2}$ and $n<K$. For an odd $n$, we know by symmetry \begin{equation} Pr(X~even)=Pr(X~odd). \end{equation} For an even $n$, my conjecture is that \begin{equation} \vert Pr(X~even)-Pr(X~odd) \vert \leq \frac{\binom{N}{n/2}}{\binom{N}{n}}. \end{equation} I ran some simulations and the result shows that it should be true, but I have not been able to prove it so far. Could someone help me with that?

If this question is answered, a subsequent question is the case where $K$ is roughly $\frac{N}{2}$ but not exact. A corresponding condition is $\vert K-\frac{N}{2}\vert \leq c N$, for a constant $0<c<0.5$. We still assume $n<min (K, N-K)$ to avoid boundary issues. The conjecture is still the same in this case.

I try not to be greedy and will be much satisfied if only the first question is answered. Many thanks in advance!

$\endgroup$
7
$\begingroup$

In the case $N=2K$ the sum can be evaluated in closed form using generating functions, and satisfies the desired inequality.

In general, multiply by ${N \choose n} t^k z^n$ and sum over both $k \leq K$ and $n \leq N$ to get $$ G_{N,K}(t,z) = (1+tz)^K (1+z)^{N-K} $$ (by writing $n=k+m$ and factoring into a product of two binomial sums). The desired alternating sum is then ${N \choose n}^{-1}$ times the $z^n$ coefficient of $G_{N,K}(-1,z) = (1-z)^K (1+z)^{N-K}$. When $K=N-K$, this simplifies to $(1-z^2)^K$, so the coefficient is zero for $n$ odd (as you noted by an antisymmetry argument) and $(-1)^n {K \choose n/2}$ for $n$ even. In particular the absolute value is less than $N \choose n/2$ as desired (and by a factor of about $2^{n/2}$). For general $K,N$, you can bound or estimate the $z^n$ coefficient using stationary-phase techniques.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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