I'm doing an exercise in randomized algorithms which is equivalent to the following:

Suppose we have pairwise independent events $X_1,\dotsc,X_n$ so that $$\mathbb{P}[X_i] = 1 - \frac{1}{\alpha n}$$ for each $i$, where $0 < \alpha < 1$, $\alpha n \ge 1$. Use the Chebyshev inequality to show that $$\mathbb{P}\left(\bigcap_{1 \le i \le n} X_i\right) \le \alpha$$

The following approach seems natural but gets stuck:

Let $\chi_1,\dotsc,\chi_n$ be the indicator variables corresponding to $X_1,\dotsc,X_n$. Then the event $\bigcap_i X_i$ occurs precisely when $\sum_{1 \le i \le n} \chi_i \ge n$. We have $E\left[\sum_i \chi_i\right] = n - \frac{1}{\alpha}$, so by Chebyshev's inequality, we have \begin{align} \mathbb{P}\left(\bigcap_i X_i\right) &= \mathbb{P}\left[\sum_i \chi_i \ge E\left[\sum_i \chi_i\right]+ \frac{1}{\alpha} \right] \\ &< \frac{E\left[\sum_i \chi_i\right]}{\alpha^{-2}} \\ &= \alpha^2(n - \alpha^{-1}) = \alpha(\alpha n - 1) \end{align} At this point it seems that I'm stuck, since $\alpha(\alpha n - 1) \le \alpha$ only happens if $\alpha n \le 2$. I don't see a way to get anywhere by splitting into cases based on whether $\alpha n \le 2$. What's the best way to proceed from here?


Let random variable $T_i$ be the indicator for event $X_i^c$ (the complement of $X_i$). Thus $\mathbb P\left(\bigcap_i X_i\right) = \mathbb P\left(\sum_i T_i = 0\right)$. Now $T_i$ has mean $\mu = 1/(\alpha n)$ and variance $ 1/(\alpha n) - 1/(\alpha n)^2$, and since the $X_i$ are pairwise independent the covariance of $T_i$ and $T_j$ is $0$ if $i \ne j$. Thus $S = \sum_i T_i$ has mean $\mathbb ES = 1/\alpha$ and variance $\sigma^2 = 1/\alpha - 1/(\alpha^2 n)$.

Now $$P(S = 0) \le P(|S - \mathbb ES| \ge 1/\alpha)$$ so Chebyshev says $$P(S = 0) \le \dfrac{\sigma^2}{1/\alpha^2} = \dfrac{\alpha n - 1}{n} < \alpha$$

  • $\begingroup$ Thanks! Should that last line read $P(S = 0) \le \dotsi$? $\endgroup$ – Sebastian Conybeare Mar 8 '16 at 22:42
  • $\begingroup$ Corrected... thanks. $\endgroup$ – Robert Israel Mar 9 '16 at 0:30

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.