Chapter 1 Flashcards
Set
A collection of some items
Ordering does not matter
Notion: A = {1, 2}
Subset
Set A is a subset of set B if every element of A is also an element of B. We write A⊂B, where “⊂” indicates “subset.”
Superset
B is a superset of A, or B ⊃ A, if every element of A is also in B
Universal set
the set of all things that we could possibly consider in the context
we are studying. (denoted by S)
Venn diagram
any set is depicted by a closed region, its drawn like a circle where the elements of A are within the circle of A and if elements are in both A and B the circles overlap
Union
a set containing all elements that are in A or in B
{1,2} ∪ {2,3} = {1,2,3}
Intersection
denoted by A ∩ B, consists of all elements thatare both in A and B
{1,2} ∩ {2,3} = {2}
Complement
The complement of a set A, denoted by Ac or
¯
A, is the set of all elements that are in the universal set S but are not in A
difference (subtraction)
The set A − B consists of elements that are in A but not in B
if A = {1,2,3} and B = {3,5}, then A−B={1,2}
A −B = A ∩ Bc
mutually exclusive or disjoint
Two sets A and B are mutually exclusive or disjoint if they do not have any shared elements; i.e., their intersection is the empty set,
A ∩ B = ∅.
More generally, several
sets are called disjoint if they are pairwise disjoint, i.e., no two of them share a common elements
Partition
a collection of nonempty sets A1,A2,⋯ is a partition of a set A if they are disjoint and their union is
A
De Morgan’s law
(keep in mind the c is the complement)
For any sets A1, A2, ⋯ ,An, we have:
(A1 ∪ A2 ∪ A3 ∪ ⋯ An)c =Ac1 ∩ Ac2 ∩ Ac3 ⋯ ∩ Acn
(A1 ∩A2 ∩A3 ∩⋯An)c =Ac1 ∪ Ac2 ∪ Ac3 ⋯ ∪ Acn
Distributive law
For any sets A, B, and C we have
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
cartesian product
A Cartesian product of two sets A and B, written as A × B, is the set containing ordered pairs from A and B. That is, if C = A ×B, then each element of C is of the form (x,y) , where x ∈ A and y ∈ B:
A×B={(x,y)|x ∈ A and y ∈ B}.
For example, if A = {1,2,3} and B = {H,T}, then A×B={(1,H),(1,T),(2,H),(2,T),(3,H),(3,T)}.
Note that here the pairs are ordered, so for example, (1,H) ≠ (H,1). Thus A × B is not the same as
B ×A
multiplication principle
If you have two finite sets A and B, where A has M elements and B has N elements, then A ×B has M ×N elements.
cardinality
the size of a set
The cardinality of a set is denoted by |A|
In a finite set the cardinality is how many elements it contains
inclusion-exclusion principle (also counts for probability)
- |A ∪ B| = |A|+|B|−|A∩B|,
- |A ∪ B∪C| =|A|+|B|+|C| −|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|
countable vs uncountable set (2 types of infinite set)
you can list the elements of a countable set A, i.e., you can write
A = {a1,a2,⋯}, but you cannot list the elements in an uncountable
set.
definition countable (and uncountable)
Set A is called countable if one of the following is true:
a. if it is a finite set, ∣A∣<∞ ; or
b. it can be put in one-to-one correspondence with natural numbers N, in which case the set is said to be countably infinite.
A set is called uncountable if it is not countable.
guidelines to remember is a set is countable or uncountable
- N,Z,Q, and any of their subsets are countable.
- Any set containing an interval on the real line such as [a,b],(a,b],[a,b), or (a,b), where a<b is uncountable.
- Any subset of a countable set is countable.
- Any superset of an uncountable set is uncountable.
- If A1,A2,… is a list of countable sets, then the set UiAi = A1∪A2∪A3… is also countable
- if A and B are countable, then A x B is also countable
domain and co-domain in functions
A function f is a rule that takes an input from a specific set, called the domain, and produces an output from another set, called co-domain. Thus, a function maps elements from the domain set to elements in the co-domain with the property that each input is mapped to exactly one output.
If A is the domain and B is the co-domain for the function f, we use the following notation:
f : A→B.
range
the set containing all the possible values of f(x). Thus, the range of a function is always a subset of its co-domain.
random experiment
a process by which we observe
something uncertain (you do not know what the result is gonna be)
outcome
a result of a random experiment
sample space
The set of all possible
outcomes (the universal set of a random experiment)
trial
a particular performance of a random experiment
When we repeat a random experiment several times, we call each one of them a trial.
event
an eventis a collection of possible outcomes. In other words, an event is a subset of the sample
space to which we assign a probability
probability
We assign a probability measure P(A) to an event A. This is a value between 0 and 1 that shows how likely the event is.
axioms of probability theory
- For any event A, P(A) >= 0
- Probability of the sample space S is P(S) = 1
- If A1,A2,A3,… are disjoint events, then P(A1 ∪ A2 ∪ A3, ⋯) = P(A1)+P(A2)+P(A3)+⋯
discrete vs continuous sample set
in discrete probability models we can compute the probability of events by adding all the corresponding outcomes, while in continuous probability models we need to use integration instead of summation
conditional probability
it’s the probability of an event occurring given that another event has already occurred. It is denoted as P(A|B), which reads as “the probability of event A given event B”
conditional probability formula
P(A|B) = (P(A ∩ B) / (P(B)), when P(B) > 0
also written as:
P(A∩B) = P(A)P(B|A) = P(B)P(A|B)
chain rule for conditional probability
P(A1 ∩ A2 ∩ … ∩ An) = P(A1)P(A2|A1)P(A3|A2,A1)⋯P(An|An−1An−2⋯A1)
independence
Two events are independent if one does not convey any information about the other
Two events A and B are independent if P(A ∩ B) = P(A)P(B)
Three events A, B and C are independent if all of the following conditions hold:
P(A∩B)=P(A)P(B),
P(A∩C)=P(A)P(C),
P(B∩C)=P(B)P(C),
P(A∩B∩C)=P(A)P(B)P(C).
independence when it comes to other operations (complements, unions etc)
If A and B are independent then:
- A and Bc are independent,
- Ac and B are independent,
- Ac and Bc are independent
If A1,A2,⋯,An are independent then:
P(A1∪A2∪⋯∪An) = 1−(1−P(A1))(1−P(A2))⋯(1−P(An))
Consider two events A and B, with P(A) ≠ 0 and P(B) ≠ 0. If A and B are disjoint, then they are not independent.
the law of total probability
If B1,B2,B3,⋯ is a partition of the sample space S, then for any event A we have
P(A) =∑i P(A∩Bi) =∑i P(A|Bi)P(Bi).
Because:
P(A) =P(A∩B)+P(A∩Bc)
and using the definition of conditional probability,
P(A ∩ B) = P(A|B)P(B)
, we can write
P(A) =P(A|B)P(B)+P(A|Bc)P(Bc).
Bayes’ Rule
- For any two events A and B, where P(A) ≠ 0, we have
P(B|A) = P(A|B)P(B) / P(A)
- If B1, B2, B3, … form a partition of the sample S, and A is any event with P(A) ≠ 0, we have
P(Bj|A) = (P(A|Bj)P(Bj)) / (∑iP(A|Bi)P(Bi))
conditional independence
if A and B are conditionally independent given C, then
P(A|B,C) = P(A|C)
