0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ Thanks! Should that last line read $P(S = 0) \le \dotsi$? $\endgroup$ Commented Mar 8, 2016 at 22:42
  • $\begingroup$ Corrected... thanks. $\endgroup$ Commented Mar 9, 2016 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .