Transcript Review of Probability

Stochastic Methods
A Review (Mostly)
Relationship between Heuristic and
Stochastic Methods
 Heuristic
and stochastic methods
useful where
– Problem does not have an exact solution
– Full state space is too costly to search
 In
addition, stochastic methods are
useful when
– One samples an information base
– Causal models are learned from the
data
Problem Areas
 Diagnostic
reasoning
 Natural language understanding
 Speech recognition
 Planning and scheduling
 Learning
Pascal
 Developed
probabilistic techniques to
develop a mathematical foundation
for gambling
 You might remember that Pascal
abjured mathematics when in 1657
his niece was cured of a painful
infection while being in the proximity
of nuns who kissed a thorn from
Christ’s crown.
Sets







Set
– A set is an unordered collection of elements
Cardinality
– Number of elements in a set
– For a set A, its cardinality is denoted: |A|
Universe
– The domain of interest
– Denoted U
Complement of a set A
– The set of all elements from U that are not part of A
– Denoted
A
Subset
– Set A is a subset of set B iff every element of A is also a an element of B
– Denoted: A  B
Union
– The union of sets of A and
B is the set of all elements of either set
– Denoted:
A B
Intersectcion
– The intersection of sets A and B is the set of all elements that are elements
of both sets
– Denoted:
A B
Rules for Sets

AC  A  C  AC
Addition rule
– This can be generalized for N sets

Multiplication Principle
– If we have two sets, A and B, the number
of unique ways the elements can be
combined is |A| x |B|

Cartesian Product of two set, A and B:
𝐴𝑋𝐵=
𝑎, 𝑏
𝑎𝜖𝐴 ∧ (𝑏𝜖𝐵)}
Permutations and Combinations

Permutation of elements is a unique
sequence of elements in that set
– The permutation of n elements taken r at a
time, duplicates not allowed
 nPr
= n!/(n-r)!
– The permutation of n objects taken r at a time,
duplicates allowed
 nr

Combination of a set of n elements is any
subset that can be formed
– The combination of n elements taken r at a
time
 nCr
= n!/((n-r)! r!)
Elements of Probability Theory

Elementary Event
– An occurrence that cannot be made up of other
events

Event, E
– Set of elementary events (e.g., two rolls of two
fair dice)

Sample Space, S
– The set of all possible outcomes of an event E
– E.g. 2 … 12 for dice example

Probability, p
– The ratio of the cardinality of E to that of S
– p(E) = |E| / |S| and
p( E )  1  p( E )
Union
Given that:
| A  B || A |  | B |  | A  B |
Then
p( A  B) | A  B | / | S |
| A | / | S |  | B | / | S |  | A  B | / | S |
 p ( A)  p( B)  p( A  B)
Intersection and Conditional
Probability
Suppose we have the following tulip
table, telling us whether the tulip
bulbs we have are red or yellow and
bloom in April or May
April(A) May(M) Totals
Red (R)
5
8
13
Yellow (y)
3
4
7
Totals
8
12
20
Let S designate the sample space.
Then |S| = 20
If one bulb is selected at random, the probability that the
bulb will be red is: P(R) = 13/20
Now, we want to know the probability of grabbing a red bulb
given that it blooms in April.
P(R|A) = 5/8
=
=
|𝑅∩𝐴|
|𝐴|
|𝑅 ∩𝐴|
|𝐴|
|𝑆|
|𝑆|
= 𝑝(𝑅 ∩ 𝐴)/𝑝(𝐴)
Conditional Probability
In general:
For any two events, with p(B) > 0, the
conditional probability of A given that B
has occurred is:
P(A|B) = P(A  B)/P(B)

Independence
Two events are independent if the occurrence
of one of them does not affect the probability
of occurrence of the other
 More formally, two events A and B are
independent if:

– p(A|B) = p(A) provided that p(B) > 0
– p(B|A) = p(B) provided that p(A) > 0
Theorem
(intersection/independence)
A and B are independent if and only if
P(A  B) = p(A) * p(B)
Proof (if A and B are independent then …)
We know: p(A  B) = p(A|B) * p(B).
are independent, p(A|B) = p(A)
So,
P(A  B) = p(A) * p(B)
Since A and B
Proof (if p(A  B) = p(A) * p(B) then …)
We know that p(A  B) = p(A|B) * p(B).
So, p(A) = P(A|B)
So A is independent of B. The reverse can easily be
demonstrated.
Example 1

What is the probability of rolling a 7 or an 11 using
two fair dice?
– Sample space is the cardinality of the cartesian
product of the set of values from each die: namely,
36
– The subset of the cartesian product that can produce
7 is:
A ={(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)}
– The subset of the cartesian product that can produce
11 is:
B = {(5,6),(6,5)}
– |E| = |A| + |B|
– p(E)=8/36 = .2222
– Another way is to use the probability of the union of
sets
– P(A U B) = p(A) + p(B) – p(A  B) = 6/36 + 2/36 – 0
= .2222
Example 2


What is the probability of being dealt a four-of-akind hand in a five card poker hand?
S is the set of all five card hands. So,
|S| =
52C5
= 2,598,960
E is the set of all four-of-a-kind hands
 T is the set of card types
 W is the set of ways to pick four of the same type
 R is the set of all ways to pick 1 card from the
remaining 48
 So
|E| = |T| * |W| * |R|
|E| = 13C1 * 4C4 * 48C1 = 13 * 1 * 48 = 624
 So, p(E) = |E|/|S| ≈ .00024

Example 3

Recall (by the intersection/independence theorem) two
events are independent if and only
p( A  B)  p( A) * p( B)












Consider a situation where bit strings of length 4 are
randomly generated.
Let A = the event of the bit strings containing an even
number of 1s.
Let B = the event of the bit strings ending in 0.
Are A and B independent?
|S| = 24 = 16
A = {1111,1100,1010,1001,0110,0101,0011,0000}
|A| = 8
B = {1110,1100,1010,1000,0010,0100,0110,0000}
|B| = 8
P(A  B) = |A  B|/|S| = 4/16 = .25
P(A) * p(B) = 8/16 * 8/16 = .25
So A and B are independent