An unpleasant calculation?

At the end of my previous post I claimed that proving that $\sum_{s=2}^k \frac{{k \choose s} {n-k \choose k-s}}{{n \choose k}} 2^{{s \choose 2}} ,$ tends to $0$ when $n$ tends to infinity and $k=(2-\epsilon)\log_2(n)$ was unpleasant. It appears that I was wrong, and I would like to show here a simple proof that was suggested to me by my colleague Philippe Rigollet.

The key observation is that the term $\frac{{k \choose s} {n-k \choose k-s}}{{n \choose k}}$ is the probability that an hypergeometric random variable $H(k,k,n)$ takes value $s$ . Hypergeometric distributions are nasty, but when $n$ is of larger order than $k$ (which is the case here), they are well approximated by a simple binomial $B(n, k/n)$ . In the present case this suggests the upper bound $\frac{{k \choose s} {n-k \choose k-s}}{{n \choose k}} \leq {k \choose s} \left(\frac{k}{n}\right)^s .$ The latter inequality can be proved formally using the identity ${n-1 \choose k-1} = \frac{k}{n} {n \choose k} .$ Now one can simply use the inequalities $2^{{s \choose 2}} \leq 2^{s \frac{k}{2}},$ and ${k \choose s} \leq k^s$ to obtain that the original unpleasant sum is upper bounded by $\sum_{s=2}^{k} 2^{s (\frac{k}{2} + 2\log_2(k) - \log_2(n) )}$ which clearly tends to $0$ when $n$ tends to infinity and $k=(2-\epsilon)\log_2(n)$ .

This entry was posted in Random graphs. Bookmark the permalink.

One Response to "An unpleasant calculation?"

By Philippe Rigollet January 17, 2013 - 3:58 pm

I’ll try myself at posting my two (extra) cent about this proof with latex on WordPress.

The formula can be written as $E[2^{{X \choose 2}}I(X\ge 2)]$ where $X$ has a hypergeometric distribution with the following parameters: $n$ is the population size, $k$ is the number of success and $k$ is the number of draws. I like to view this distribution as an experiment where one puts $k$ pebbles in $n$ slots at random (with only one pebble per slot) and then $X$ denotes the number of pebbles in the slots numbered $1$ through $k$ . This distribution enjoys a remarkable property, sometimes referred to as negative association: the fact that a pebble is in one of the first $k$ slots decreases the probability that another pebble is in one of these first $k$ slots (indeed one slot is already taken). Let’s see how we can use this property:

First, $E[2^{{X \choose 2}}I(X\ge 2)]= E[2^{{X \choose 2}}]-P(X \le 1)$ . We now show that each term tends to 1.

Let’s begin with the expected value:
$E[2^{{X \choose 2}}]\le E[2^{\frac{X^2}{2}}]\le E[2^{\frac{k}{2}X}]= E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]$ where $Y_i$ indicates if pebble $i$ is in one of the first $k$ slots. Now, negative association becomes useful. It implies that $E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]\le \prod_{i=1}^kE[2^{\frac{k}{2}Y_i}]$ . But each $Y_i$ is a Bernoulli random variable with parameter $k/n$ so that $E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]\le \big((2^{\frac{k}2}-1)\frac{k}n +1\big)^k$ . For $k=(2-\varepsilon)\log_2(n)$ , we find that this quantity tends to 1 and $n \to \infty$ .

We now deal with $P(X \le 1)$ . A sufficient condition for this event to hold is that all the $k$ pebbles are in slots numbered at least $k+1$ . Therefore $P(X \le 1) \ge P(X= 0) =1 -P(X\ge 1)$ . By a union bound $P(X\ge 1) \le k^2/n \to 0$ .

By Philippe Rigollet January 17, 2013 - 3:58 pm

I’ll try myself at posting my two (extra) cent about this proof with latex on WordPress.

The formula can be written as $E[2^{{X \choose 2}}I(X\ge 2)]$ where $X$ has a hypergeometric distribution with the following parameters: $n$ is the population size, $k$ is the number of success and $k$ is the number of draws. I like to view this distribution as an experiment where one puts $k$ pebbles in $n$ slots at random (with only one pebble per slot) and then $X$ denotes the number of pebbles in the slots numbered $1$ through $k$ . This distribution enjoys a remarkable property, sometimes referred to as negative association: the fact that a pebble is in one of the first $k$ slots decreases the probability that another pebble is in one of these first $k$ slots (indeed one slot is already taken). Let’s see how we can use this property:

First, $E[2^{{X \choose 2}}I(X\ge 2)]= E[2^{{X \choose 2}}]-P(X \le 1)$ . We now show that each term tends to 1.

Let’s begin with the expected value:
$E[2^{{X \choose 2}}]\le E[2^{\frac{X^2}{2}}]\le E[2^{\frac{k}{2}X}]= E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]$ where $Y_i$ indicates if pebble $i$ is in one of the first $k$ slots. Now, negative association becomes useful. It implies that $E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]\le \prod_{i=1}^kE[2^{\frac{k}{2}Y_i}]$ . But each $Y_i$ is a Bernoulli random variable with parameter $k/n$ so that $E[2^{\frac{k}{2}\sum_{i=1}^kY_i}]\le \big((2^{\frac{k}2}-1)\frac{k}n +1\big)^k$ . For $k=(2-\varepsilon)\log_2(n)$ , we find that this quantity tends to 1 and $n \to \infty$ .

We now deal with $P(X \le 1)$ . A sufficient condition for this event to hold is that all the $k$ pebbles are in slots numbered at least $k+1$ . Therefore $P(X \le 1) \ge P(X= 0) =1 -P(X\ge 1)$ . By a union bound $P(X\ge 1) \le k^2/n \to 0$ .

An unpleasant calculation?

One Response to "An unpleasant calculation?"

By Philippe Rigollet January 17, 2013 - 3:58 pm

Leave a reply

Archives

Categories

Recent Posts

Subscribe to Blog via Email

Meta

Blogroll