forked from emsbach/probability-and-computing-solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathexercise01.07.tex
137 lines (134 loc) · 6.93 KB
/
exercise01.07.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
\paragraph{Exercise 1.7}
\begin{enumerate}
\item[(a)] \textbf{Lemma 1.3} (\textcolor{WildStrawberry}{Inclusion-exclusion
principle}): Let $E_1,...,E_n$ be any $n$ events. Then
\[
\pr\left(\bigcup_{i=1}^n E_i\right)
= \sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + \sum_{i<j<k}\pr(E_i \cap E_j \cap E_k) - ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l} \pr\left(\bigcap_{r=1}^lE_{i_r}\right)+ ... .
\]
\textit{Proof}. We want to show the Inclusion-exclusion principle by induction
over $n \in \mathbb{N}$, where $n \geq 2$. \\
For the base case (IB) assume that $n = 2$. According to Lemma 1.1, one has
\begin{align*}
\pr\left(E_1 \cup E_2 \right)
&= \pr(E_1) + \pr(E_2) - \pr\left(E_1 \cap E_2 \right) \\
&= \sum_{i=1}^2 \pr(E_i) - \sum_{i<j}\pr\left(E_1 \cap E_2 \right).
\end{align*}
Let $n \geq 2$, so that the Inclusion-exclusion principle holds for $n$
(induction hypothesis, IH). We have to show, that the Inclusion-exclusion
principle then also hold for $n+1$.
\begin{align*}
\pr\left(\bigcup_{i=1}^{n+1} E_i\right)
&= \pr\left(\left(\bigcup_{i=1}^{n} E_i\right) \cup E_{n+1}\right) \\
&=_{\text{Lemma 1.1}} \pr\left(\bigcup_{i=1}^{n} E_i\right) + \pr(E_{n+1}) -
\pr\left(\left(\bigcup_{i=1}^{n} E_i\right) \cap E_{n+1}\right) \\
&= \pr\left(\bigcup_{i=1}^{n} E_i\right) + \pr(E_{n+1}) -
\pr\left(\bigcup_{i=1}^{n} \left(E_i \cap E_{n+1}\right)\right) \\
&=_{IH} \pr(E_{n+1}) +
\left(
\sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + ... + (-1)^{n+1}
\sum_{i_1<i_2< ... <i_n} \pr\left(\bigcap_{r=1}^n E_{i_r}\right)
\right) \\
&\ \ - \Bigg(
\sum_{i=1}^n \pr\left(E_i \cap E_{n+1}\right) -
\sum_{i<j} \pr\left((E_i \cap E_{n+1}) \cap (E_j \cap E_{n+1})\right)
+ ... \\
&\quad \quad \quad+ (-1)^{n+1} \sum_{i_1<i_2< ... <i_n} \pr\left(\bigcap_{r=1}^n
\left(E_{i_r} \cap E_{n+1}\right)\right)
\Bigg) \\
&= \sum_{i=1}^{n+1} \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + ... +
(-1)^{n+1} \sum_{i_1<i_2< ... <i_n} \pr\left(\bigcap_{r=1}^n E_{i_r}\right) \\
&\ \ - \Bigg(
\sum_{i=1}^n \pr\left(E_i \cap E_{n+1}\right) - \sum_{i<j}\pr\left(E_i
\cap E_j \cap E_{n+1}\right) + ...
+ (-1)^{n+1} \sum_{i_1<i_2< ... <i_n} \pr\left(\bigcap_{r=1}^n
\left(E_{i_r} \cap E_{n+1}\right)\right)
\Bigg) \\
&= \sum_{i=1}^{n+1} \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + ... + (-1)^{n+2}
\sum_{i_1<i_2< ... <i_{n+1}} \pr\left(\bigcap_{r=1}^{n+1}E_{i_r}\right).
\end{align*}
Hence, the Inclusion-exclusion principle applies.
\item[(b)] \textbf{Lemma 1.8}: Let $E_1,...,E_n$ be any $n$ events and $l \in
\mathbb{N}$, so that $l$ is odd. Then
\[
\pr\left(\bigcup_{i=1}^n E_i\right)
\leq \sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + \sum_{i<j<k}\pr(E_i \cap E_j \cap E_k) - ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l} \pr\left(\bigcap_{r=1}^lE_{i_r}\right).
\]
\textit{Proof}. Let $l \in \mathbb{N}$, so that $3 \leq l \leq n$ and $l$ is odd. According to Lemma 1.3 one has,
\begin{align*}
\begin{tabular}{l}
$\pr\left(\bigcup_{i=1}^n E_i\right) -
\left(
(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right) + ... +
(-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right)
\right)$ \\
$\ \ = \sum_{i=1}^n \pr(E_i) + ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l}
\pr\left(\bigcap_{r=1}^lE_{i_r}\right).$
\end{tabular}
\end{align*}
Therefore, we have to show that
\[
(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
+ ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \leq 0.
\]
Since $l$ is odd,
\begin{align*}
&(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right) + ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \\
= &-\sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
+ ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right).
\end{align*}
Furthermore, for any $1 \leq k < n$ holds,
\[
\sum_{i_1<i_2< ... <i_k} \pr\left(\bigcap_{r=1}^k E_{i_r}\right)
\geq \sum_{i_1<i_2< ... <i_{k+1}} \pr\left(\bigcap_{r=1}^{k+1} E_{i_r}\right).
\]
Hence, for any pair $(k,k+1)$, there $l+1 \leq k < n$ and $k$ is even, holds
\begin{align*}
\ &(-1)^{k+1} \sum_{i_1<i_2< ... <i_{k}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right) + (-1)^{k+2} \pr\left( \bigcap_{r=1}^{k+1} E_{i} \right) \\
= &-\sum_{i_1<i_2< ... <i_k} \pr\left( \bigcap_{r=1}^{l+1} E_{i_r} \right) + \pr\left(\bigcap_{r=1}^{k+1} E_{i}\right) \\
\leq &\ 0.
\end{align*}
Therefore,
\[
(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
+ ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \leq 0,
\]
and
\[
\pr\left(\bigcup_{i=1}^n E_i\right)
\leq \sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + \sum_{i<j<k}\pr(E_i \cap E_j \cap E_k) - ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l} \pr\left(\bigcap_{r=1}^lE_{i_r}\right).
\]
\item[(c)] \textbf{Lemma 1.9}: Let $E_1,...,E_n$ be any $n$ events and $l \in
\mathbb{N}$, so that $l$ is even. Then
\[
\pr\left(\bigcup_{i=1}^n E_i\right)
\geq \sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + \sum_{i<j<k}\pr(E_i \cap E_j \cap E_k) - ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l} \pr\left(\bigcap_{r=1}^lE_{i_r}\right).
\]
\textit{Proof}. Let $l \in \mathbb{N}$, so that $2 \leq l \leq n$ and $l$ is even. Similarly to exercise 1.7b) we want now to show that
\[
(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
+ ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \geq 0.
\]
Since $l$ is even,
\begin{align*}
&(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right) + ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \\
= &\sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
- ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right).
\end{align*}
For any pair $(k,k+1)$, there $l+1 \leq k < n$ and $k$ is odd, holds
\begin{align*}
\ &(-1)^{k+1} \sum_{i_1<i_2< ... <i_{k}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right) + (-1)^{k+2} \pr\left( \bigcap_{r=1}^{k+1} E_{i} \right) \\
= &\sum_{i_1<i_2< ... <i_k} \pr\left( \bigcap_{r=1}^{l+1} E_{i_r} \right) - \pr\left(\bigcap_{r=1}^{k+1} E_{i}\right) \\
\geq &\ 0.
\end{align*}
Therefore,
\[
(-1)^{l+2} \sum_{i_1<i_2< ... <i_{l+1}} \pr\left(\bigcap_{r=1}^{l+1} E_{i_r}\right)
+ ... + (-1)^{n+1} \pr\left(\bigcap_{i=1}^n E_{i}\right) \geq 0,
\]
and
\[
\pr\left(\bigcup_{i=1}^n E_i\right)
\geq \sum_{i=1}^n \pr(E_i) - \sum_{i<j}\pr(E_i \cap E_j) + \sum_{i<j<k}\pr(E_i \cap E_j \cap E_k) - ... + (-1)^{l+1} \sum_{i_1<i_2< ... <i_l} \pr\left(\bigcap_{r=1}^lE_{i_r}\right).
\]
\end{enumerate}