Transcript Event - Rice University

Probability and Independence
Krishna.V.Palem
Kenneth and Audrey Kennedy Professor of Computing
Department of Computer Science, Rice University
1
Probability
The classical definition of probability
Pierre Simon Laplace
The probability of an event is the ratio of the number of cases favorable to it, to the
number of all cases possible when nothing leads us to expect that any one of these cases
should occur more than any other, which renders them, for us, equally possible.
Let us elaborate…
Consider an event space
Event 1
Event 2
Event 3
Event 4
2
Favorable events
If there is no reason
believe that one event
is more likely to occur
than another
Probability
of favorable
events
No. of favorable
events
Total no. of events
Generalizing Probability
Consider another event space
Event 1
Event 2
Event 3
Let us assume that each event is differently likely
to occur
Let us represent as
a list of magnitude of
“likeliness”
Event 4
3
Event
Likeliness
Event 1
p1
Event 2
p2
Event 3
p3
Event 4
p4
Generalizing Probability (Contd.)
4
Event
Likeliness
Event 1
p1
Event 2
p2
Event 3
p3
Event 4
p4
For example,
Event
Probabilities
Event 1
0.5
Event 2
0.3
Event 3
0.1
Event 4
0.1
Let us look at these values.
If these values have the following properties
1. All pi are in the range [0,1]
2. The sum of all pi = 1.
then these values are called the probabilities of these
events.
Satisfies both the conditions
This means that event 1 occurs
1 out of 4 times … etc.
Specification
Consider the event space
Event 1
Event 2
Event 3
Event 4
Event
Probabilities
Event 1
p1
Event 2
p2
Event 3
p3
Event 4
p4
Both these together
5
Complete specification of
the behavior of the
experiment
Now we have this relationship
Event
Probabilities
Event 1
p1
Event 2
p2
Event 3
p3
Event 4
p4
This can be defined concisely as a
function whose independent variable
represents the event
The dependent variable is the value
of the probability
Let the variable ‘x’ represent the event
6
x
Event
1
Event 1
2
Event 2
3
Event 3
4
Event 4
Probability (Event i)
p( x  i)  pi
Here ‘x’ is called a random variable.
Where i={1,2,3,4}
Analysis of the event space of a
coin toss
 Can you list the event space of an experiment where an
unbiased coin is being tossed ?
Event H
Event T
 To complete the specification we need the probabilities of
these events.
7
Event
Probabilities
Event H
½
EventT
½
The method of union of events
Joint Event space of
two coins
Event HH
Event HT
Event TH
Event TT
Event
Probability
Event HH
1/4
Event HT
1/4
Event TH
1/4
From the previous definition,
Event TT
1/4
Probability of the outcome = 2/4
= 1/2
Consider the outcome
Heads in both the coins “OR”
Tails in both the coins
Another way of representing the same probability is
Probability of (Heads in both the coins “OR” Tails in both the coins)
= Probability (Heads in both the coins) + Probability(Tails in both the coins)
8
Why do you think that the “OR” of two events is translated to a + for their probabilities ?
Mutually Exclusive events and outcomes
Joint Event space of
two coins
Two events are said to be mutually exclusive if
Event HH
Event HT
Event TH
Event TT
(i) Given one event as the outcome of the experiment
it is assumed that all other outcomes are discarded.
For example, if Event HH is the outcome of the experiment
then Event TT “cannot” the outcome of the experiment
Let us consider another example,
Joint Event space of two coins
The event space of the two coins can also be represented like this because it
covers all possible events
First coin is H
First coin is T
Second coin is H
Second coin is T
9
But these two events are not mutually exclusive because if the event
that the first coin is H occurs then the event that the second coin is
H can also occur
Hence these events are “not” mutually exclusive
The method of union of events
Joint Event space of
two coins
Event HH
Event HT
Event TH
Event TT
The method of union of events states that
“ If two events are mutually exclusive then the probability
that either of them will occur is the sum of probabilities of the
two events”
Let us play the experiment ∞ times
Outcomes
HH HT TH TT HH HH TT HH HT TH HT TH TH …. ∞
(HH , HH, HH) + (TT,TT,TT,….)
Relative Frequency =
All Outcomes
All Outcomes
For infinite trials
10
For infinite trials
1/4
+
1/4
= 1/2
The method of union of events
Consider an event space
Favorable events
Recall
Event 1
Event 3
Event 2
….. Etc.
Probability
of favorable
events
No. of favorable
events
Total no. of events
Event 4
Given all the above events are mutually exclusive
11
Event
Probabilities
Event 1
p1
Event 2
p2
Event 3
p3
Event 4
p4
….Etc.
Probability
of favorable
events
p2  p4  ...... Etc.
The method of union of events
Let us consider the case of two dice
Joint Event Space of Die 1 & 2
Event 11
Event 12
Event 21
Event 23
….. Etc.
Are these events mutually exclusive ?
Using method of union of events, calculate the following
(i) Probability that the first DIE and the second
die rolled a ‘3’ OR both the DICE rolled a ‘6’
A) P(Event 33 OR Event 66) = 1/36 + 1/36 = 1/18
(ii) Probability that 3 and 4 were rolled be either one of them
12
A) P(Event 34 OR Event 43) = 1/36 + 1/36 = 1/18
Mini-exercise 1 – Snakes and
Ladders(S&L)
 Calculate the probability of landing in square 6 OR square 8
in the following scaled-down version of snakes and ladders
(no snake or ladder)?
Instructions for Mini-Exercise 1
 We will start at square 1
 Roll the die 50 times and record the
squares that you land in
 Calculate the chance of landing in
square 6 OR square 8
 Note that favorable events could
be derived both from landing
on square 6 OR on square 8
13
7
8
9
6
5
4
1
2
3
The method of intersection of events
Event Space of coin 2
Event Space of coin 1
Event
H
T
P
½
½
Event H
Event H
Event T
Event T
Joint Event space of
two coins
Consider this joint experiment
again
Event HH
Event HT
Event TH
Event TT
Event
P
H
2/3
T
1/3
All the events are not
equally likely
What is the probability of the outcome of the experiment having HEAD in the first die and TAIL in the
second die ?
14
Cannot use the earlier definition of
Favorable events
Total number of events
The method of intersection of events
Event Space of coin 2
Event Space of coin 1
Event
H
T
P
½
½
Event H
Event H
Event T
Event T
Joint Event space of
two coins
Event
P
H
2/3
T
1/3
H in coin 1 = ½ of the time
Consider this joint experiment
again
Event HH
Event HT
Event TH
Event TT
T in coin 2
= 1/3 of this = ½ * 1/3
= 1/6 of the time
What is the probability of the outcome of the experiment having HEAD in the first coin and TAIL in the
second coin ?
= Probability of first coin having HEAD * Probability of second coin having TAIL = ½ * 1/3 = 1/6
15
The method of intersection of events
Event Space of coin 2
Event Space of coin 1
Event
H
T
P
½
½
Event H
Event H
Event T
Event T
Joint Event space of
two coins
Event
P
H
2/3
T
1/3
Event HH
Event HT
Event TH
Event TT
The method of intersection of events says “The probability of a joint event is equal to the
product of probability of elementary events”
16
The method of intersection of events
Let us consider the case of two dice
Table of probabilities of the outcomes
Outcom
e
Die 1
Die 2
1
1/12
1/3
2
1/12
1/3
3
1/12
1/12
4
1/12
1/12
5
1/3
1/12
6
1/3
1/12
Using method of intersection of events,
Calculate the following
(i) Probability that the first die rolled a ‘1’ and the second
die rolled a ‘4’
A) P(Event 14) = P(Event 1) * P(Event 4)
= 1/12
*
1/12 = 1/144
(ii) Probability that the first die rolled a ‘6’ and the second
die rolled a ‘6’
17
A) P(Event 66) = P(Event 6) * P(Event 6)
= 1/3
*
1/12 = 1/36
Mini-exercise 2 – Snakes and
Ladders(S&L)
 Calculate the probability of landing in square 2 AND square 8
in the following scaled-down version of snakes and ladders
(no snake or ladder)?
Instructions for Mini-Exercise 2
7
8
9
 We will start at square 1
 Roll the die for 50 times and record
6
5
4
1
2
3
the squares that you land in
 Calculate the chance of landing in
square 6 AND 8 in one cycle
 In this case, favorable events
requires that both events occur
 A cycle is completed when you go
from square 9 to square 1
18
Building a model
 An important component of this course (including exercises
and projects) would be building models, and these games are
an example.
 An example of a model would be
4
5
1/6
1/6
6
19
4
5
1/6
Solution:
Probability of reaching 6 via 5 = 1/6
Probability of reaching 6 via 4 = 1/6
Total probability of reaching 6 from 4 OR 5 = 1/6 + 1/6 = 1/3
20
1/6
6
You are at square 4 and want to compute the probability of reaching square 6
4
1/6
This can happen in two ways
(i) You roll a 1 and reach 5 and then roll a 1 again
(ii) You roll a 2 and reach 6
5
1/6
1/6
6
As we know the probabilities of the rolls we can calculate the probability of reaching 6 from 4
Solution:
Probability of reaching 6 via 5 = (1/6 * 1/6 )
Probability of reaching 6 directly = 1/6
21
Total probability of reaching 6 from 4 = 7/36
Mini-Exercise 3
 Can you build a model for the snakes and ladder game till
square 6 ?
 In this game, if we cross square 6 with a die roll we stay at 6
 That means, if you are at square 4 and you roll a 5, then you still stay at 6
22
6
5
4
1
2
3
 Remember the elements of a model
 A node or a circle that indicates a particular square in the game
 An arrow or an edge that indicates the possibility of reaching another square
from the current square
 A label on each arrow that indicates the probability of that transition taking
place
1/6
1
1/6
1/6
1/6
2
1/6
3/6
1/6
4
2/6
1/6
5
3
6
23
This is a partial model of the scaled down snakes and ladder game
1/6
1
1/6
1/6
1/6
2
1/6
3/6
4
2/6
1/6
1/6
1/6
5/6
5
1/6
6/6
6
24
4/6
3
Mini-Exercise - 4
 Using the model of the snakes and ladders, calculate the
following values
 The probability of reaching square 4 from square 1
 The probability of reaching square 5 OR square 6 from square 2
 The probability of reaching square 3 AND square 5 from square
1
25
Let us start with the transition model we built
1/6
1
1/6
1/6
1/6
1/6
3/6
4
2/6
1/6
1/6
1/6
5/6
5
Hint: New edge(s) might be added as an extension
1/6
6/6
6
26
2
4/6
3
6
5
4
1
2
3
Mini-Exercise - 5
 Using the new model of the snakes and ladders with the
snake, calculate the following values
 The probability of reaching square 4 from square 1
 The probability of reaching square 5 OR square 6 from square 2
 The probability of reaching square 3 AND square 5 from square
1
27
Question ?
Say that you are at square 4 at a point in the game
1/6
1
1/6
1/6
1/6
2
1/6
1/6
4
1/6
1/6
1/6
1/6
1/6
5
1/6
1/6
3
1/6
6
28
You roll a die and you reach 6
What can we do to get that
information ?
What if we place some sort of a
token at each square we land ?
1/6
1
1/6
And then we reached square 4
1/6
1/6
1/6
Let us say that we land at square 2
2
1/6
4
1/6
1/6
1/6
Thus after completing the game we
have the additional “information” to
determine where we have been
1/6
1/6
5
1/6
1/6
1/6
6
29
So we leave a token at square 2
3
More information
So basically if we play this game
multiple times, then we need more
tokens (probably with different colors)
to keep track of where we were each
time.
1/6
1
1/6
1/6
1/6
2
Let us say that an all-knowing “Oracle”
tells us that the previous square we
were in was odd and not even.
1/6
1/6
4
1/6
1/6
1/6
1/6
1/6
5
1/6
1/6
1/6
6
30
Do we still need tokens to keep track ?
3
Will we need more tokens or less ?
Answers
We will analyze more precisely the
relationship between two events in
the next class.
1/6
1
1/6
1/6
1/6
2
1/6
1/6
4
1/6
1/6
1/6
1/6
1/6
5
1/6
1/6
1/6
6
31
3
Independence and Dependence
 Till now, we have been looking at events individually.
 But in practice, events are interrelated.
 Some events are dependent on some other event taking place
Let us consider the following example
Let us play a small game. Bob is rolling a die. He asks Alice to guess what he rolled.
1. What is the probability that Bob is correct ?
2. Let us say that the Oracle told Danny that the outcome of the die is an even number or
an odd number. Then what is the probability that Danny is correct ?
32
There is an underlying mathematical concept that can be explicitly stated to calculate
the answer to the question
Consider an experiment.
The outcome of the experiment can be specified in terms of two different event spaces
p
p
p1
p2
p3
Event 1
Event 2
Event 3
…
Event Even
Event Odd
Peven
Podd
…
Knowledge of the outcome of the roll of a die in terms of whether it is an even number or
an odd number allows us to predict the actual outcome more precisely
33
Let us calculate how much it improves our quality of our guess
There is an underlying mathematical concept that can be explicitly stated to calculate
the answer to the question
Consider an experiment.
The outcome of the experiment can be specified in terms of two different event spaces
p
p
p1
p2
p3
Event 1
Event 2
Event 3
…
Event Even
Event Odd
Peven
Podd
…
Knowledge of the outcome of the roll of a die in terms of whether it is an even number or
an odd number allows us to predict the actual outcome more precisely
34
Let us calculate how much it improves our quality of our guess