Skip to main content
1 of 2
RaphaelB4
  • 4.4k
  • 12
  • 25

The bound proposed by Lucia is correct. I add some detail and I stress that It is an application of "large deviation" theorem which is very very standard.

Set the following independant bernouilli random variable defined as $$X_i=\begin{cases} 0 \text{ with } p=1/2\\ \frac{1}{i} \text{ with } p=1/2\end{cases}$$ Then we have the number of subset is given by $$ 2^n \mathbb{P}(\sum_{i=1}^n X_i \leq 1)$$

And we can then adapte the proof of the well known Cramer theorem. For a lower bound $$\mathbb{P}(\sum_{i=1}^n X_i\leq 1)=\mathbb{P}(e^{-x\sum_{i=1}^n X_i}\leq e^{-x})\leq \frac{\mathbb{E}(e^{-x\sum_{i=1}^n X_i})}{e^{-x}}$$ which give because of the independence of $X_i$ the formula that Lucia have already stated (I didn't know it is called Rankin bound) $$\mathbb{P}(\sum_{i=1}^n {X}_i \leq 1)\leq e^{x} \prod_i^n (e^{-\frac{x}{i}}+1)/2^n$$

There exists $x_0$ which minimise the right part.

Then introduce $$\tilde{X}_i=\begin{cases} 0 \text{ with } p=\frac{1}{1+e^\frac{-x_0}{i}}\\ \frac{1}{i} \text{ with } p=\frac{e^\frac{-x_0}{i}}{1+e^\frac{-x_0}{i}} \end{cases}$$

Remark that $$ \mathbb{E}(\sum_i \tilde{X}_i)=\frac{\mathbb{E}(\sum_i X_i e^{-x_0\sum_{i=1}^n X_i})}{\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i})}=\partial_x [ln(\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i}))]_{x=x_0}$$ But because $x_0$ is a minimum, $\partial_x [ln(\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i}))-ln(e^{-x})]_{x=x_0}=0$ and therefore $\mathbb{E}(\sum_i \tilde{X}_i)=1$. But because of convexity for any $\epsilon>0$ changing $\tilde{X}$ by $\tilde{X}^\epsilon$ by replacing $x_0$ by $x=x_0+\epsilon n$ in the definition give $\mathbb{E}(\sum_i \tilde{X}_i)\leq 1-\delta(\epsilon)$ with $\delta(\epsilon)>0$. We have then that $\mathbb{P}(\sum\tilde{X}^\epsilon_i\leq 1)\geq \delta(\epsilon)$ We can then state the lower bound $$ \delta(\epsilon)\leq \mathbb{E}(1_{\sum(\tilde{X}_i^\epsilon)\leq 1})\leq \frac{\mathbb{E}(1_{\sum X_i \leq 1} e^{-x \sum_i X_i})}{\mathbb{E}(e^{-x \sum_i X_i})} \leq \frac{\mathbb{E}(1_{\sum X_i \leq 1} )e^{-x}}{\mathbb{E}(e^{-x \sum_i X_i})}$$ And to conclude $$ \delta(\epsilon)\frac{\mathbb{E}(e^{-x \sum_i X_i})}{e^{-x}}\leq \mathbb{P}(\sum X_i \leq 1)$$ and therefore $$\lim \frac{1}{n}\log(\frac{\mathbb{E}(e^{-x \sum_i X_i})}{e^{-x}})\leq \lim \frac{1}{n}\log(\mathbb{P}(\sum X_i \leq 1))$$

which is true for any $\epsilon>0$. This is the end of the proof that the bound is tight

RaphaelB4
  • 4.4k
  • 12
  • 25