2
$\begingroup$

Professor X gives the following homework problem from Mathematics For Computer Science (note: this is not from a course at CUHK, as the link might suggest):

Prove the following probabilistic inequality, referred to as the Union Bound. Let $A_1,A_2,...A_n,...$ be events. Then $$Pr\left[\bigcup\limits_{n\in N} A_n\right] \leq \sum\limits_{n \in N}Pr[A_n].$$ Hint: Replace the $A_n$'s by pairwise disjoint events and use the Sum Rule.

However, Professor X instructs his students to follow a different hint instead of the one given in the original problem. He writes:

Better hint: use induction; no need for the Sum Rule.

I don't see how induction works here. I presume he means that, for the induction, one should use a proposition something like the following,

$$P(k): Pr\left[\bigcup\limits_{n=1}^{k} A_n\right] \leq \sum\limits_{n=1}^{k} Pr[A_n]$$

then argue that $P(1)$ holds as a base case, and that $P(k)\rightarrow P(k+1)$, which implies that $P(n)$ holds for any $n\in N$ by the principle of mathematical induction.

This argument would be insufficient, however. We are not trying to prove that $P(n)$ holds for any $n \in N$. Rather, we are trying to establish $P(\infty)$:

$$Pr\left[\bigcup\limits_{n=1}^{\infty} A_n \right] \leq \sum\limits_{n=1}^{\infty}Pr[A_n].$$ Since induction cannot establish $P(\infty)$, induction is insufficient to prove the result.

Do others agree? Have I correctly interpreted the notation of the original problem as equivalent to $P(\infty)$? Is there some other inductive hypothesis that would make induction a valid approach for this?

Note: transfinite induction is not available in this course -- not that I'm sure it would help anyway.

$\endgroup$
  • 4
    $\begingroup$ I believe you're right that induction by itself does not establish the infinite-union statement. However, if the induction is carried out, note that you get $$Pr\left[\bigcup\limits_{n=1}^{k} A_n\right] \leq \sum\limits_{n=1}^{k} Pr[A_n] \leq \sum\limits_{n=1}^{\infty}Pr[A_n]$$ for every $k\in\Bbb N$; and then you can take the limit as $k\to\infty$ (the right-hand side no longer depends on $k$). $\endgroup$ – Greg Martin Oct 6 '16 at 6:19
  • 1
    $\begingroup$ Professor X's hint is allright, I fail to see what there is to "challenge" here. $\endgroup$ – Did Oct 6 '16 at 6:48
  • $\begingroup$ @Did, you believe the hint is ok because the strategy I've outlined does in fact establish the result, or because some other (unspecified) induction strategy establishes the result? $\endgroup$ – Chad Oct 6 '16 at 6:54
  • $\begingroup$ I know the hint is allright and I object to your choice of words and to the attitude towards X's indications that it seems to reveal. @Greg's comment precisely describes a complete proof based on X's excellent indication. $\endgroup$ – Did Oct 6 '16 at 6:56
  • $\begingroup$ @Did Thanks for clarifying. No bad attitude intended - just trying to understand. $\endgroup$ – Chad Oct 6 '16 at 7:04
1
$\begingroup$

I disagree with the comments and agree with your claim that proof by induction is insufficient here (and in fact I have penalized students in the past for attempting to argue this way). As Greg Martin points out, induction allows you to deduce $$ Pr\left[\bigcup_{n=1}^kA_n\right]\le\sum_{n=1}^kPr[A_n]\le\sum_{n=1}^\infty Pr[A_n]. $$ To deduce the result from here, we need to know that $Pr\left[\bigcup_{n=1}^kA_n\right]\to Pr\left[\bigcup_{n\in\mathbb N}A_n\right]$ as $k\to\infty$. But this is not immediate, and the typical way to prove this is to use the original hint, i.e. replace the $A_n$'s with pairwise disjoint events and use countable additivity. Therefore you have gained nothing by using induction.

$\endgroup$
  • $\begingroup$ do you mean as $k\rightarrow \infty$? $\endgroup$ – Chad Oct 6 '16 at 17:38
  • $\begingroup$ Yes, thank you. I will edit. $\endgroup$ – Jason Oct 6 '16 at 17:45
  • $\begingroup$ thanks. I was also wondering about this intermediate step. I'll do some more digging and see whether it follows from other propositions already proven in the text. $\endgroup$ – Chad Oct 6 '16 at 17:53

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.