0
$\begingroup$

For positive integers $\ell < m < n$, consider a partition of $[2n]$ into two $n$-element sets $(X,Y)$. How many ways are there to choose an $m$-subset $A \subset [2n]$ such that the size of the intersection $A \cap X$ is at least $\ell$?

I believe this quantity is given by the following sum: $$ S_{\ell,m,n} := \sum_{j=0}^{m-\ell}{n \choose m-j} {n \choose j}. $$

If my reasoning is correct, is there a way to obtain a non-trivial upper bound (i.e. approximation) for $S_{\ell,m,n}$?

$\endgroup$
2
  • 1
    $\begingroup$ I assume you are interested in some asymptotic bounds. If so —- which regime you are in? I.e., what are the relative growth rates of the parameters? $\endgroup$ Jun 9 at 8:50
  • 2
    $\begingroup$ The largest value occurs at $j=m/2$ and close to there it is approximately normal unless $m$ is small or close to $n$. $\endgroup$ Jun 9 at 13:11

1 Answer 1

2
$\begingroup$

I agree with your formula. You choose $j \in \{0,\ldots,m-\ell\}$ (it will be the cardinal of $A \cap Y$, and given such a $j$ you choose independently $j$ elements in $Y$ and $m-j$ elements in $X$.
Here is an upper bound
$$S_{\ell,m,n} \le \sum_{j=0}^{m} {n \choose m-j} {n \choose j} = {2n \choose m}.$$ One obtains the last equality by looking at the coefficient of $X^m$ in the product $(1+X)^n \times (1+X)^n$. My guess is that this bound is sharp when $m/2-\ell >> \sqrt{m}$.

Less trivial bound

The quotient $S_{\ell,m,n}/{2n \choose m}$ is the probability $\mathbf{P}[X \ge \ell]$ where $X$ is a random hypergeometric random variable with parameters $2n$, $n$ and $m$. The law of $X$ is symmetric with regard to $m/2$ and is less spread out than the binomial law with parameters $m$ and $1/2$ (sampling without replacement provides a least dispersion of the number of success).

More precisely, given binomial random variable $Y$ with parameters $m$ and $1/2$, I guess that when $\ell \ge m/2$, $$2\mathbb{P}[X \ge \ell] = \mathbb{P}[|X-m/2| \ge \ell-m/2] \le \mathbb{P}[|Y-m/2| \ge \ell-m/2] = 2\mathbb{P}[Y \ge \ell].$$ Does anyone have a reference or a proof of this fact? Then, Cramer-Chernoff inequalities give nice bounds.

$\endgroup$
2
  • 4
    $\begingroup$ The bound you put is trivial after looking at the question. I assume the OP asks for more interesting ones... $\endgroup$ Jun 9 at 8:48
  • $\begingroup$ @Ilya Bogdanoiv. You are right. Giving a too simple answer can be a way to get more precisions on the nature of the bound wished (is it wanted for $\ell/m$ close to $0$, close to $1/2$, close to $1$ ?). Anyway, I completed my answer to give a less trivial bound when $\ell \ge m/2$. $\endgroup$ Jun 9 at 21:32

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.