Transcript Blue screen

PROBABILITY AND STATISTICS
FOR ENGINEERING
Probability Theory
Hossein Sameti
Department of Computer Engineering
Sharif University of Technology
Probability And Statistics
Source: http://ocw.mit.edu
Sharif University of Technology
2
PROBABILITY THEORY
1.Basics
Random Phenomena, Experiments
 Study of random phenomena
 Different outcomes
 Outcomes that have certain underlying patterns about them
 Experiment
- repeatable conditions
 Certain elementary events Ei occur in different but completely
uncertain ways.
 probability of the event Ei : P(Ei )>=0
7/21/2015
Sharif University of Technology
4
Probability Definitions
 Laplace’s Classical Definition
- without actual experimentation
- provided all these outcomes are equally likely.
Example
• a box with n white and m red balls
elementary outcomes: {white , red}
Probability of “selecting a white ball”:
• P  a given num ber is divisible by a prim e p  
7/21/2015
1
p
Sharif University of Technology
5
Probability Definitions
 Relative Frequency Definition
- The probability of an event A is defined as
- nA is the number of occurrences of A
- n is the total number of trials
7/21/2015
Sharif University of Technology
6
Probability Definitions
Example
1. The probability that a given number is divisible by a prime p:
7/21/2015
Sharif University of Technology
7
Counting - Remark
 General Product Rule
if an operation consists of k steps each of which can be performed in ni ways
(i = 1, 2, …, k), then the entire operation can be performed in ni ways.
Example
- Number of PINs
- Number of elements in a Cartesian product
- Number of PINs without repetition
- Number of Input/Output tables for a circuit with n input signals
- Number of iterations in nested loops
7/21/2015
Sharif University of Technology
8
Permutations and Combinations - Remark
 If order matters choose k from n:
- Permutations :
 If order doesn't matter choose k from n:
- Combinations :
Example
A fair coin is tossed 7 times. What is the
probability of obtaining 3 heads? What is
the probability of obtaining at most 3
heads?
7/21/2015
Sharif University of Technology
9
Example: The Birthday Problem
 Suppose you have a class of 23 students. Would you think it likely or
unlikely that at least two students will have the same birthday?
 It turns out that the probability of at least two of 23 people having the
same birthday is about 0.5 (50%).
7/21/2015
Sharif University of Technology
10
Axioms of Probability- Basics
 The axiomatic approach to probability, due to Kolmogorov,
developed through a set of axioms
 The totality of all events known a priori, constitutes a set Ω, the set
of all experimental outcomes.
7/21/2015
Sharif University of Technology
11
Axioms of Probability- Basics
 A and B are subsets of Ω .
A
A
B
A B
7/21/2015
B
A
A B
A
A
Sharif University of Technology
12
Mutually Exclusiveness and Partitions
 A and B are said to be mutually exclusive if
A B  ,
 A partition of  is a collection of mutually exclusive(ME) subsets of
 such that their union is .
A1
A
B
A2
Ai
Aj
An
A B 
7/21/2015
Sharif University of Technology
13
De-Morgan’s Laws
A B  A B;
A
B
A B
7/21/2015
A
B
A B
A B  A B
A
B
A
B
A B
Sharif University of Technology
14
Events
 Often it is meaningful to talk about at least some of the subsets of 
as events
 we must have mechanism to compute their probabilities.
Example
Tossing two coins simultaneously:
A: The event of “Head has occurred at least once” .
7/21/2015
Sharif University of Technology
15
Events and Set Operators
 “Does an outcome belong to A or B”
 “Does an outcome belong to A and B”
 “Does an outcome fall outside A”?
 These sets also qualify as events.
 We shall formalize this using the notion of a Field.
7/21/2015
Sharif University of Technology
16
Fields
 A collection of subsets of a nonempty set  forms a field F if
(i)
F
(ii)
If A  F , then
(iii)
If A  F
and
A F
B  F , then
A  B  F.
 Using (i) - (iii), it is easy to show that the following also belong to F.
7/21/2015
Sharif University of Technology
17
Fields
If
then
 We shall reserve the term event only to members of F.
 Assuming that the probability P(Ei ) of elementary outcomes Ei of Ω are
apriori defined.
 The three axioms of probability defined below can be used to assign
probabilities to more ‘complicated’ events.
7/21/2015
Sharif University of Technology
18
Axioms of Probability
 For any event A, we assign a number P(A), called the probability of
the event A.
 Conclusions:
7/21/2015
Sharif University of Technology
19
Probability of Union of to Non-ME Sets
A
AB
A B
7/21/2015
Sharif University of Technology
20
Union of Events
 Is Union of denumerably infinite collection of
pairwise disjoint events Ai an event?
 If so, what is P(A ) ?
 We cannot use third probability axiom to
compute P(A), since it only deals with two
(or a finite number) of M.E. events.
7/21/2015
Sharif University of Technology
21
An Example for Intuitive Understanding
 in an experiment, where the same coin is tossed indefinitely define:
A = “head eventually appears”.
 Our intuitive experience surely tells us that A is an event.
If
An  head appears for the 1st time
on the n th toss

 {t , t , t ,  , t , h }
 

n 1
We have:
 Extension of previous notions must be done based on our intuition as
new axioms.
7/21/2015
Sharif University of Technology
22
σ-Field (Definition):
 A field F is a σ-field if in addition to the
three mentioned conditions, we have the
following:
- For every sequence of pairwise disjoint
events belonging to F, their union also
belongs to F
7/21/2015
Sharif University of Technology
23
Extending the Axioms of Probability
 If Ai s are pairwise mutually exclusive
 from experience we know that if we keep
tossing a coin, eventually, a head must
show up:
P ( A)  1.

 But:
A 

An ,
n 1
 Using the fourth probability axiom we
have:
 

P ( A)  P 
  An 
 
 n 1

7/21/2015
Sharif University of Technology


P ( An ).
n 1
24
Reasonablity
 In previously mentioned coin tossing experiment:
 So the fourth axiom seems reasonable.
7/21/2015
Sharif University of Technology
25
Summary: Probability Models
 The triplet (, F, P)
-  is a nonempty set of elementary events
-F
is a -field of subsets of .
- P is a probability measure on the sets in F subject to the four
axioms
 The probability of more complicated events must follow this
framework by deduction.
7/21/2015
Sharif University of Technology
26
Conditional Probability
 In N independent trials, suppose NA, NB, NAB denote the number of times
events A, B and AB occur respectively.
 According to the frequency interpretation of probability, for large N,
P ( A) 
NA
, P(B) 
NB
N
, P ( AB ) 
N AB
N
.
N
 Among the NA occurrences of A, only NAB of them are also found among the
NB occurrences of B.
 Thus the following is a measure of “the event A given that B has already
occurred”:
N AB
NB
7/21/2015

N AB / N
NB / N

P ( AB )
P(B)
Sharif University of Technology
27
Satisfying Probability Axioms
 We represent this measure by P(A|B) and define:
P( A | B) 
P ( AB )
,
P(B)
P ( B )  0.
 As we will show, the above definition is a valid one as it satisfies all
probability axioms discussed earlier.
7/21/2015
Sharif University of Technology
28
Satisfying Probability Axioms
7/21/2015
Sharif University of Technology
29
Properties of Conditional Probability
Example
In a dice tossing experiment,
-
A : outcome is even
-
B: outcome is 2.
The statement that B has occurred
makes the odds for A greater
7/21/2015
Sharif University of Technology
30
Law of Total Probability
 We can use the conditional probability to express the probability of a
complicated event in terms of “simpler” related events.
 Suppose that
 So,
7/21/2015
Sharif University of Technology
31
Conditional Probability and Independence
 A and B are said to be independent events, if
P ( AB )  P ( A )  P ( B ).
 This definition is a probabilistic statement, not a set theoretic notion
such as mutually exclusiveness.
 If A and B are independent,
P( A | B) 
P ( AB )
P(B)

P ( A) P ( B )
 P ( A ).
P(B)
 Thus knowing that the event B has occurred does not shed any
more light into the event A.
7/21/2015
Sharif University of Technology
32
Independence - Example
Example
From a box containing 6 white and 4 black balls, we remove two balls at
random without replacement.
What is the probability that the first one is white and the second one is black?
P (W 1  B 2 )  ?
W 1  B 2  W 1 B 2  B 2W 1 .
P (W 1 B 2 )  P ( B 2W 1 )  P ( B 2 | W 1 ) P (W 1 ).
P (W 1 ) 
6
6 4
P ( B 2 | W1 ) 
7/21/2015

6

10
4
5 4

3
5
4
,
P (W 1 B 2 ) 
3
5

4
9

12
45
,
9
Sharif University of Technology
33
Example - continued
 Are W1 and B2 independent?
Removing the first ball has two possible outcomes:
These outcomes form a partition because:
So,
P ( B 2 )  P ( B 2 | W 1 ) P (W 1 )  P ( B 2 | B 1 ) P ( B 1 )

4

3
54 5

3

4
6  3 10

4 3 1 2
42
2
   
 ,
9 5 3 5
15
5
Thus the two events are not independent.
P ( B 2 ) P (W 1 ) 
7/21/2015
2 3
4
  P ( B 2W 1 ) 
5 5
15
Sharif University of Technology
34
General Definition of Independence
 Independence between 2 or more events:
 Events A1,A2, ..., An are mutually independent if, for all possible
subcollections of k ≤ n events:
Example
In experiment of rolling a die,
A = {2, 4, 6}
B = {1, 2, 3, 4}
C = {1, 2, 4}.
Are events A and B independent?
What about A and C?
7/21/2015
Sharif University of Technology
Source: http://ocw.mit.edu
35
Bayes’ Theorem
We have:
P( A | B) 
P ( AB )
,
P(B)
Thus,
P ( AB )  P ( A | B ) P ( B ).
Also,
P ( B | A) 
P ( BA )
P ( A)

P ( AB )
,
P ( A)
P ( AB )  P ( B | A ) P ( A ).
P ( A | B ) P ( B )  P ( B | A ) P ( A ).
7/21/2015
Sharif University of Technology
36
Bayesian Updating: Application Of Bayes’ Theorem
 Suppose that A and B are dependent events and A has apriori
probability of P(A ) .
 How does Knowing that B has occurred affect the probability of A?
 The new probability can be computed based on Bayes’ Theorm.
 Bayes’ Theorm shows how to incorporate the knowledege about B’s
occuring to calculate the new probability of A.
7/21/2015
Sharif University of Technology
37
Bayesian Updating - Example
Example
 Suppose there is a new music device in the market that plays a new
digital format called MP∞. Since it’s new, it’s not 100% reliable.
 You know that
- 20% of the new devices don’t work at all,
- 30% last only for 1 year,
- and the rest last for 5 years.
 If you buy one and it works fine, what is the probability that it will last for 5
years?
Source: http://ocw.mit.edu
7/21/2015
Sharif University of Technology
38
Generalization of Bayes’ Theorem
A more general version of Bayes’ theorem involves partition of Ω :
P ( Ai | B ) 
P ( B | Ai ) P ( Ai )
P(B)

P ( B | Ai ) P ( Ai )
n

,
P ( B | Ai ) P ( Ai )
i 1
In which,
Ai , i  1  n ,
Represents a collection of mutually exclusive events with assiciated apriori
probabilities:
P ( Ai ), i  1  n .
With the new information “B has occurred”, the information about Ai can be
updated by the n conditional probabilities:
7/21/2015
Sharif University of Technology
39
Bayes’ Theorem - Example
Example
1. Two boxes, B1 and B2 contain 100 and 200 light bulbs
respectively. The first box has 15 defective bulbs and the second 5.
Suppose a box is selected at random and one bulb is picked out.
a) What is the probability that it is defective?
7/21/2015
Sharif University of Technology
40
Example - Continued
Suppose we test the bulb and it is found to be defective. What is the
probability that it came from box 1?
P ( B1 | D )  ?
P ( B1 | D ) 
P ( D | B1 ) P ( B1 )

P(D)
0 . 15  1 / 2
 0 . 8571 .
0 . 0875
 Note that initially,
P ( B1 )  0 . 5;
 But because of greater ratio of defective bulbs in B1 ,this probability
is increased after the bulb determined to be defective..
7/21/2015
Sharif University of Technology
41