Discrete Structures

CSC 208
Department of Mathematics and
Computer Sciences

Akinsola, JET Ph.D.

Discrete Probability

Module VIII Week 9

 Outline
Discrete Probability
Complimentary Events
Discrete Probability Examples
Conditional Probability
Independence
Bernoulli Trials

Second Semester 2019 CSC 208 - Discrete Structures 3

 Discrete Probability
Everything you have learned about counting
constitutes the basis for computing the probability
of events to happen.
In the following, we will use the notion
experiment for a procedure that yields one of a
given set of possible outcomes.
This set of possible outcomes is called the sample
space of the experiment.
An event is a subset of the sample space.
Second Semester 2019 CSC 208 - Discrete Structures 4
 Discrete Probability
If all outcomes in the sample space are equally
likely, the following definition of probability
applies:
The probability of an event E, which is a subset of
a finite sample space S of equally likely outcomes,
is given by p(E) = |E|/|S|.
Probability values range from 0 (for an event that
will never happen) to 1 (for an event that will
always happen whenever the experiment is carried
out).
Second Semester 2019 CSC 208 - Discrete Structures 5
 Discrete Probability
Example I:
An urn contains 4 blue balls and 5 red balls. What
is the probability that a ball chosen at random from
the urn is blue?
Solution:
There are 9 possible outcomes, and the event “blue
ball is chosen” comprises four of these outcomes.
Therefore, the probability of this event is 4/9 or
approximately 44.44%.
Second Semester 2019 CSC 208 - Discrete Structures 6
 Discrete Probability
Example II:
What is the probability of winning the lottery 6/49,
that is, picking the correct set of six numbers out of
49?
Solution:
There are C(49, 6) possible outcomes. Only one of
these outcomes will actually make us win the
lottery.
p(E) = 1/C(49, 6) = 1/13,983,816
Second Semester 2019 CSC 208 - Discrete Structures 7
 Complimentary Events
Let E be an event in a sample space S. The
probability of an event –E, the complimentary
event of E, is given by
p(-E) = 1 – p(E).
This can easily be shown:
p(-E) = (|S| - |E|)/|S| = 1 - |E|/|S| = 1 – p(E).
This rule is useful if it is easier to determine the
probability of the complimentary event than the
probability of the event itself.
Second Semester 2019 CSC 208 - Discrete Structures 8
 Complimentary Events
Example I: A sequence of 10 bits is randomly
generated. What is the probability that at least one of
these bits is zero?
Solution: There are 210 = 1024 possible outcomes of
generating such a sequence. The event –E, “none of
the bits is zero”, includes only one of these outcomes,
namely the sequence 1111111111.
Therefore, p(-E) = 1/1024.
Now p(E) can easily be computed as
p(E) = 1 – p(-E) = 1 – 1/1024 = 1023/1024.
Second Semester 2019 CSC 208 - Discrete Structures 9
 Complimentary Events
Example II: What is the probability that at least two out
of 36 people have the same birthday?
Solution: The sample space S encompasses all
possibilities for the birthdays of the 36 people,
so |S| = 36536.
Let us consider the event –E (“no two people out of 36
have the same birthday”). –E includes P(365, 36) outcomes
(365 possibilities for the first person’s birthday, 364 for the
second, and so on).
Then p(-E) = P(365, 36)/36536 = 0.168,
so p(E) = 0.832 or 83.2%
Second Semester 2019 CSC 208 - Discrete Structures 10
 Discrete Probability
Let E1 and E2 be events in the sample space S.
Then we have:

p(E1  E2) = p(E1) + p(E2) - p(E1  E2)

Does this remind you of something?

Of course, the principle of inclusion-

exclusion.

Second Semester 2019 CSC 208 - Discrete Structures 11

 Discrete Probability
Example: What is the probability of a positive
integer selected at random from the set of positive
integers not exceeding 100 to be divisible by 2 or
5?
Solution:
E2: “integer is divisible by 2”
E5: “integer is divisible by 5”
E2 = {2, 4, 6, …, 100}
|E2| = 50
p(E2) = 0.5
Second Semester 2019 CSC 208 - Discrete Structures 12
 Discrete Probability
E5 = {5, 10, 15, …, 100}
|E5| = 20
p(E5) = 0.2

E2  E5 = {10, 20, 30, …, 100}

|E2  E5| = 10
p(E2  E5) = 0.1

p(E2  E5) = p(E2) + p(E5) – p(E2  E5 )

p(E2  E5) = 0.5 + 0.2 – 0.1 = 0.6
Second Semester 2019 CSC 208 - Discrete Structures 13
 Discrete Probability
What happens if the outcomes of an experiment are not
equally likely?
In that case, we assign a probability p(s) to each outcome
sS, where S is the sample space.
Two conditions have to be met:
(1): 0  p(s)  1 for each sS, and
(2): sS p(s) = 1
This means, as we already know, that (1) each probability
must be a value between 0 and 1, and (2) the probabilities
must add up to 1, because one of the outcomes is
guaranteed to occur.
Second Semester 2019 CSC 208 - Discrete Structures 14
 Discrete Probability
How can we obtain these probabilities p(s) ?

The probability p(s) assigned to an outcome s equals the

limit of the number of times s occurs divided by the number
of times the experiment is performed.

Once we know the probabilities p(s), we can compute the

probability of an event E as follows:

p(E) = sE p(s)

Second Semester 2019 CSC 208 - Discrete Structures 15

 Discrete Probability
Example I: A die is biased so that the number 3 appears
twice as often as each other number.
What are the probabilities of all possible outcomes?
Solution: There are 6 possible outcomes s1, …, s6.
p(s1) = p(s2) = p(s4) = p(s5) = p(s6)
p(s3) = 2p(s1)
Since the probabilities must add up to 1, we have:
5p(s1) + 2p(s1) = 1
7p(s1) = 1
p(s1) = p(s2) = p(s4) = p(s5) = p(s6) = 1/7, p(s3) = 2/7

Second Semester 2019 CSC 208 - Discrete Structures 16

 Discrete Probability
Example II: For the biased die from Example I, what is
the probability that an odd number appears when we roll
the die?
Solution:
Eodd = {s1, s3, s5}
Remember the formula p(E) = sE p(s).
p(Eodd) = sE p(s) = p(s1) + p(s3) + p(s5)
odd

p(Eodd) = 1/7 + 2/7 + 1/7 = 4/7 = 57.14%

Second Semester 2019 CSC 208 - Discrete Structures 17

 Conditional Probability
If we toss a coin three times, what is the
probability that an odd number of tails appears
(event E), if the first toss is a tail (event F) ?
If the first toss is a tail, the possible sequences are
TTT, TTH, THT, and THH.
In two out of these four cases, there is an odd
number of tails.
Therefore, the probability of E, under the
condition that F occurs, is 0.5.
We call this conditional probability.
Second Semester 2019 CSC 208 - Discrete Structures 18
 Conditional Probability
If we want to compute the conditional probability
of E given F, we use F as the sample space.
For any outcome of E to occur under the condition
that F also occurs, this outcome must also be in
E  F.

Definition: 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)
Second Semester 2019 CSC 208 - Discrete Structures 19
 Conditional Probability
Example: What is the probability of a random bit string
of length four contains at least two consecutive 0s, given
that its first bit is a 0 ?
Solution:
E: “bit string contains at least two consecutive 0s”
F: “first bit of the string is a 0”
We know the formula p(E | F) = p(E  F)/p(F).
E  F = {0000, 0001, 0010, 0011, 0100}
p(E  F) = 5/16
p(F) = 8/16 = 1/2
p(E | F) = (5/16)/(1/2) = 10/16 = 5/8 = 0.625
Second Semester 2019 CSC 208 - Discrete Structures 20
 Independence
Let us return to the example of tossing a coin three
times.
Does the probability of event E (odd number of
tails) depend on the occurrence of event F (first toss
is a tail) ?
In other words, is it the case that
p(E | F)  p(E) ?
We actually find that p(E | F) = 0.5 and p(E) = 0.5,
so we say that E and F are independent events.
Second Semester 2019 CSC 208 - Discrete Structures 21
 Independence
Because we have p(E | F) = p(E  F)/p(F),
p(E | F) = p(E) if and only if p(E  F) = p(E)p(F).

Definition: The events E and F are said to be

independent if and only if p(E  F) = p(E)p(F).

Obviously, this definition is symmetrical for E

and F. If we have p(E  F) = p(E)p(F), then it is also
true that p(F | E) = p(F).

Second Semester 2019 CSC 208 - Discrete Structures 22

 Independence
Example: Suppose E is the event that a randomly generated
bit string of length four begins with a 1, and F is the event that a
randomly generated bit string contains an even number of 0s.
Are E and F independent?

Solution: Obviously, p(E) = p(F) = 0.5.

E  F = {1111, 1001, 1010, 1100}

p(E  F) = 0.25
p(E  F) = p(E)p(F)

Conclusion: E And F are independent.

Second Semester 2019 CSC 208 - Discrete Structures 23
 Bernoulli Trials
Suppose an experiment with two possible
outcomes, such as tossing a coin.
Each performance of such an experiment is called
a Bernoulli trial.
We will call the two possible outcomes a success
or a failure, respectively.
If p is the probability of a success and q is the
probability of a failure, it is obvious that
p + q = 1.
Second Semester 2019 CSC 208 - Discrete Structures 24
 Bernoulli Trials
Often we are interested in the probability of
exactly k successes when an experiment consists of
n independent Bernoulli trials.

Example:
A coin is biased so that the probability of head is
2/3. What is the probability of exactly four heads to
come up when the coin is tossed seven times?

Second Semester 2019 CSC 208 - Discrete Structures 25

 Bernoulli Trials
Solution:
There are 27 = 128 possible outcomes.
The number of possibilities for four heads among
the seven trials is C(7, 4).
The seven trials are independent, so the probability
of each of these outcomes is
(2/3)4(1/3)3.
Consequently, the probability of exactly four heads
to appear is
C(7, 4)(2/3)4(1/3)3 = 560/2187 = 25.61%
Second Semester 2019 CSC 208 - Discrete Structures 26
 Bernoulli Trials
Theorem: The probability of k successes in n
independent Bernoulli trials, with probability of
success p and probability of failure q = 1 – p, is
C(n, k)pkqn-k .

We denote by b(k; n, p) the probability of k

successes in n independent Bernoulli trials with
probability of success p and probability of failure q
= 1 – p.
Considered as function of k, we call b the
binomial distribution.
Second Semester 2019 CSC 208 - Discrete Structures 27
Second Semester 2019 CSC 208 - Discrete Structures 28