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
|
Review of Basic Set Theory: 1.2
Sets are represented by capital letters like A, B, C.
Sets can be like {1, 2, 3, ...}, (0, 1), reals, R^k, etc.
Operations
A \cup B - union of A and B, refers to a set such that x \in A \cup B
iff x\in A OR x\in B.
A \cap B - intersection, refers to a set such that x \in A \cup B iff
x\in A AND x\in B.
A \setminus B (written as \) - difference, x\in A \setminus B iff x\in A
and x\not\in B
B^c = \overbar{B} - complement, equivalent to \Omega \setminus B or
C \setminus B, where C or \Omega is the sample space of the problem.
Universe ex: all possible combinations of two coin flips.
Countable union:
+\infty n
U A_i or U
i=1 i=1
Represents union of a list of indexed sets.
Countable intersection is analagous.
UNcountable intersection/union is a union or intersection over an
uncountable set like the reals or (0, 1).
Symmetric difference: (A \union B) \setminus (A \cap B). (think of XOR)
DeMorgan's Laws (and proofs)
(A \cap B)^c = A^c \cup B^c
Let x \in (A\cap B)^c \to x \not\in A \cap B.
If x\in A, x\not\in B \to x\in B^c. If x\in B, x\not\in A \to x\in A^c.
Therefore, x\in A^C \cup B^c.
(The proof the other way is similarly trivial)
(A \cup B)^C = A^C \cap B^c
These laws can be generalized to infinite unions (although not through
induction, which merely proves it for arbitrary large, finite sets).
Prove: Let B be the union of all A^c where A \in C. x\in B iff x \in
(infinite intersection of all A where A \in C)^c
[Proof omitted at present]
Distributive laws
C_1 \cap (C_2 \cup C_3) = (C_1 \cap C_2) \cup (C_1 \cap C_3)
C_1 \cup (C_2 \cap C_3) = (C_1 \cup C_2) \cap (C_1 \cup C_3)
Sample space and probability
Example sample space is n ordered Bernoulli trials [finite]
or (0,1) or (0,1)^2 or R [continuous]
C = { w_1, w_2, ... } where w_i is an elementary event. ??MUST?? be
countable.
If A \subseteq C, A is an event (random event) in C.
Probability set function
Assign to each w_j a number p(w_j) \in [0, 1].
\sum_{j=1}^\infty p(w_j) = 1.
p_j := p(w_j) also known as random weights
P(A) = \sum_{j : w_j \in A} p(w_j) [ the sum can be generalized to integral]
Properties of P(A)
P : subsets of C --> [0, 1]
1) P(C) = 1
2) \forall A \subseteq C, 0 \leq P(A) \leq 1
3) If A_1, A_2 \subseteq C and A_1 \cap A_2 = \empty,
P(A_1 \cup A_2) = P(A_1) + P(A_2)
4) \forall A_1, A_2 \subseteq C,
P(A_1\cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2)
5) \forall A \subseteq C
P(A) + P(A^c) = 1.
6) P(\empty) = 0
7) P(A) is nondecreasing: If A_1 \subseteq A_2 \subseteq C,
P(A_1) \leq P(A_2)
sigma-algebra backed by C is a set which contains C, and is closed under
countable union and complement w.r.t C. (these are not unique, e.g.
{C, \empty} and P(C) are both valid sigma-algebras).
|
