Transcript + p(E | F)

461191 Discrete Math
Lecture 6: Discrete Probability
San Ratanasanya
CS, KMUTNB
Today’s topics





Basic of Counting Review
Administrivia
Probability
Baye’s Theorem
Expected Value and Variance
2
Basic Counting Tools

Basic rules of counting




Inclusion and Exclusion Principle



Sum rule: either task 1 or task 2 have to be done
Product rule: both task 1 and task 2 have to be done
Task 1 and Task 2 are independent
Exclude one that count more than once or irrelevant count
Include one that miss
Pigeonhole Principle

If there are k nest for at least k+1 pigeons, then there must
be at least one nest that has more than one pigeons
3
Example

How many strings of five ASCII character
contain the ‘@’ character at least once? (ASCII
has 128 characters)
1285 - 1275
4
Example

A computer company receives 350 applications from
computer graduates for a job planning a line of new
Web servers. Suppose that 220 of these people majored
in CS, 147 majored in business, and 51 majored both in
CS and business. How many of these applications
majored in CS nor in business?
|A  B| = 220 + 147 - 51 = 316
 U - |A  B| = 350 – 316 = 34
5
Example g pigeonhole



A drawer contains a dozen brown socks and a dozen black socks,
all un matched. A man takes socks out at random in the dark.
How many socks must he take out to be sure that he has at least
two socks of the same color?
3
How many socks must he take out to be sure that he has at least
two black socks?
14
6
Binomial Coefficient

THEOREM 1: The Binomial Theorem


THEOREM 2: PASCAL’S IDENTITY


Let x,y,n be positive integer
Let n and k be positive integer with n > k then
THEOREM 3: Let n be positive integer, then
7
Example

How many terms are therein the expansion of
(x + y)15?
215

What is the difference between the coefficient
of the term x8y3 and x5y6?
|C(11, 8) – C(11, 5)| = |165 – 462| = 297
8
Permutations and Combinations

Permutations



Ordered arrangement of a set of distinct objects.
An ordered arrangement of r elements of a set is rpermutation
P(n, r) = n!
(n - r)!
Combinations

An unordered selection of r elements from the set
is r-combination C(n, r) = P(n, r) = n!
r!
r!(n – r)!
9
Example

A group contain n men and n women. How
many ways are there to arrange these people in
a row if the men and women alternate?
2(n!)2

In how many ways can a set of five letters be
selected from the English alphabet?
C(26, 5) = 65780
10
Generalized Permutations and
Combinations



Permutations and Combinations
with repetition
Permutations with
Indistinguishable Objects
Distributing Objects into Boxes (4 cases)
 Distinguishable objects and distinguishable boxes
 Distinguishable objects and indistinguishable boxes
 Indistinguishable objects and distinguishable boxes
 Indistinguishable objects and indistinguishable boxes
11
Example General PC

How many string of six letter are there?

How many ways are there to select three
unordered elements from a set with five
elements when repetition is allowed?
266
C(5+3-1, 3) = C(7, 3) = 35
12
Generating Permutations and
Combinations


Counting permutations or combinations
can solve many problems
Counting is sometimes not enough. We
need to generate either one of them to find
the solution.
13
Example Generate PC

What is the next permutation in lexicographic order
after 362541?



Count number of permutations = n! -1 = 6! – 1 = 719
Lexicogrphic: aj < aj+1. Therefore, the next number is 364125
(Kakuro) Let S = {1, 2, …, 9}. What are the subset that
has 3 elements of S and their sum is 15?


Count number of combinations = 9! / 3!6! = 84
Generate subset: {1, 5, 9}, {1, 6, 8}, {2, 4, 9}, {2, 5, 8} ,{2, 6, 7},
{3, 4, 8}, {3, 5, 7}, {4, 5, 6}
14
Administrivia


Midterm Exam is in next 2 weeks. Please be
prepared!
All assignments MUST be submitted before
Midterm.
15
Discrete Probability and
Probability Theory
Finite Probability

Laplace’s definitions:



Experiment – a procedure that yields one of a given set
of possible outcomes.
Sample space – the set of possible outcomes from the
experiment.
Event – a subset of the sample space.
Definition 1:
If S is a finite sample space of equally likely outcomes,
and E is an event, that is , a subset of S, then
the probability of E is p(E) = |E|
|S|
17
The Probability of
Combinations of Events
Theorem 1:
Let E be an event in a sample space S. The probability of
the event E, the complementary event of E, is given by
p(E) = 1 – p(E)
Theorem 2:
Let E1 and E2 be events in sample space S. Then
p(E1  E2) = p(E1) + p(E2) – p(E1  E2)
18
Example

There are many lotteries now that award enormous prizes to
people who correctly choose a set of six numbers out of the first n
positive integers, where n is usually between 30 and 60. What is
the probability that a person picks the correct numbers out of 40?
1 / C(40, 6) = 1 / 3838380 = 0.00000026

What is the probability that a positive integer selected at random
from the set of positive integers not exceeding 100 is divisible by
either 2 or 5?
0.5 + 0.2 – 0.1 = 0.6
19
Probabilistic Reasoning

The Monty Hall Three-door Puzzle




You are asked to select one of the 3 doors to win the
price.
Once you select the door, the host, who knows what is
behind each door, he opens one of the other two doors
that he know is a losing door.
Then he ask you whether you would like to switch doors.
Should you change doors or keep your original selection?
You should change the door whenever you have chance!
The probability of wining will change from 1/3 to 2/3
20
Assigning Probabilities

Let S be the sample space of an experiment with a
finite or countable number of outcomes. We assign
a probaility p(s) to each outcome s such that these
2 conditions must be met

0  p(s)  1 for each s  S

 p( s )  1
sS

The function p() is called a probability distribution
21
Definition 1:
Suppose that S is a set with n elements. The uniform distribution
assigns the probability 1/n to each element of S.
Definition 2:
The probability of the event E is the sum of the probabilities of
the outcomes in E. That is, p( E )   p(s)
sE
(Note that when E is an infinite set,  p(s) is a convergent infinite series.)
sE
22
Example

Suppose that a die is biased so that 3 appears twice as
often as each number but that the other five outcomes
are equally likely. What is the probability that an odd
number appears when we roll this die?
Let E = {1, 3, 5}
p(1) = p(2) = p(4) = p(5) = p(6) = 1/7; p(3) = 2/7
Then p(E) = 4/7
23
Conditional Probability and
Independence
Definition 3:
Let E and F be events with p(F) > 0. The conditional probability of
E given F, denoted by p(E | F), is defined as
p(E | F) = p(E  F)
p(F)
Definition 4:
The events E and F are independent if and only if p(E  F) = p(E)∙p(F)
24
Example

What is the conditional probability that a family with two
kids has two boys, given they have at least one boy?
Let E = {BB}, F = {BB, GB, BG} then E  F = {BB}
p(E|F) = (1/4)/(3/4) = 1/3

Are the events E, that a family with three kids has of both
sexes, and F, that this family has at most one boy,
independent?
Yes. Because p(E  F) = p(E)p(F) = 3/8
25
Bernoulli Trials and the Binomial
Distribution
An experiment with only 2 outcomes either Success or Failure is
called Bernoulli Trials.
 Let p and q be a probability of success and failure, respectively.
Then, it follows that
p+q=1
 Bernoulli Trails are mutually independent.
Theorem 2:
The probability of exactly k successes in n independent Bernoulli trials,
with probability of success p and probability of failure q = 1 – p, is
b(k; n, p) = C(n, k)pkqn-k


If we consider it as a function of k, we call this function the
n
Binomial Distribution.
C (n, k ) p k q n  k  ( p  q) n  1

k 0
26
Random variable
Definition 5:
A random variable is a function fro the sample space of an experiment
to the set of real numbers. That is, a random variable assigns
a real number to each possible outcome.
Definition 6:
The distribution of random variable X on a sample space S
is the set of pairs (r, p(X = r)) for all r  X(S), where p(X = r) is
the probability that X takes the value r. A distribution is usually
described by specifying p(X = r) fro each r  X(S).
27
Example

Suppose that a coin is flipped three times. Let X(t) be
the random variable that equals the number of heads
that appear when t is the outcome. Find X(t).
X(HHH) = 3, X(HHT) = X(HTH) = X(THH) = 2,
X(TTH) = X(THT) = X(HTT) = 1, X(TTT) = 0
Because each of the eight possible outcomes
Has probability of 1/8, the distribution of X(t) is given by
P(X=3) = 1/8, P(X=2)=3/8, P(X=1) = 3/8, P(X=0) = 1/8
28
More Examples

Birthday Problem. What is the minimum number of people who
need to be in a room so that the probability that at least two of
them have the same birthday is greater than 1/2?
1- pn = 1- 365 364 363 … 367-n
366 366 366 366
n = 22

Example 14 - 16
29
Monte Carlo Algorithms

Deterministic Algorithms


Always proceed in the same way whenever given the same
input.
Probabilistic Algorithms


Make random choices at one or more step for its efficiency in
a huge number of possible case.
Mote Carlo Algorithms


The probability that the algorithm give the correct answer increases as
more test carried out.
Details in Section 6.2 page 411
30
The Probabilistic Method

is used as existence proof to proof
results about set S.
Theorem 3:
If the probability that an element of a set S does not have a
particular property is less than 1,
there exists an element in S with this property.

See Theorem 4 for example
31
Baye’s Theorem
Bayes’ Theorem

The probability that a particular event occurs on the basis of partial evidence,
i.e., it is like conditional probability
Theorem 1:
Suppose that E and F are events from a sample space S such that p(E)  0 and p(F)
 0. Then
P(F | E) =
p(E | F)p(F)
p(E | F)p(F) + p(E | F)p(F)
Theorem 2: Suppose that E is an event from a sample space S and that F1, F2, …,
n
Fn are mutually exclusive events such that i 0 Fi  S
Assume that p(E)  0 and p(Fi)  0 for i = 1, 2, .., n. Then
p( F j | E ) 
p( E | F j ) p( F j )

n
i 0
p( E | Fi ) p( Fi )
33
Example

We have 2 boxes. The first box contains two green balls and seven red balls;
the second box contains four green balls and three red balls. Bob selects a ball
by first choosing one of the two boxes at random. He then selects one of the
balls in this box at random. If Bob has selected a red ball, what is the
probability that he selected a ball from the first box?

Details in Section 6.3 on page 417
34
Example: Bayesian Spam Filter



Uses information about previously seen e-mail
messages whether an incoming e-mail message
is spam.
Look for occurrences of particular word in
messages.
See details in Section 6.3 on page 421
35
Expected Value and Variance
Expected Value (of Random
Variable)


is a weighted average of the values of a random variable.
provides central point for the distribution of values of the
random variable.
Definition 1: The expected value (or expectation) of
the random variable X(s) on the sample space S is equal to
E ( X )   p( s) X ( s)
sS
Theorem 1: If X is a random variable and p(X = r) is the probability
p ( s ), then
that X = r, so that p(X = r) =sS ,
X ( s )r
E( X ) 
 p( X  r )r
r X ( S )
37
Variance
Definition 4: Let X be a random variable on a sample space
S. The variance of X, denoted by V(X), is
V ( X )   ( X ( s)  E ( X )) 2 p( s)
sS
The standard deviation of X is defined to be  ( X )  V ( X )
Theorem 6: If X is a random variable on sample space S, then
V(X) = E(X2) – E(X)2
 p( s)
sS , X ( s )r
E ( X )   p( X  r )r
r X ( S )
38
Average-case Computational
Complexity

See Example 8-9 on page 431-432
39
Homework





Section 6.1
 8, 20, 35, 38, 41
Section 6.2
 18, 22, 36, 37, 39, 40
Section 6.3
 5, 10, 15, 18, 23
Section 6.4
 2, 7, 9, 10, 22, 23
Supplementary
 2, 3, 15, 16, 21, 22
40