Discrete Mathematics

(Math191)

By: Department of Mathematics

College of Natural and Social Sciences
Addis Ababa Science and Technology
University

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 1
AASTU
 Chapter 2
Elementary Probability
Theory

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 2
AASTU
• Probability theory originates in seventeenth
century when the French mathematician Blaise
Pascal determined the odds of winning some
popular bets based on the outcome, when a pair
of dice is repeatedly rolled.

• In eighteenth century French mathematician

Laplace who also studied gambling defined the
probability of an event as the number of
successful outcomes divided by number of
possible outcomes.
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 3
AASTU
• Random experiment is an experiment in which
the outcome cannot be determined or predicted
exactly in advance.
• Event: A collection of one or more outcomes in
a statistical experiment. We usually denote
events with capital letters 𝐴, 𝐵, 𝐶 …
• Simple Event: An event that consists of exactly
one outcome in a statistical experiment.
• Sample Space: The set of all simple events

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 4
AASTU
EXAMPLE : A coin is tossed twice
S= {(H,H),(H,T),(T,H),(T,T)}
E= {(H,H),(T,H)} the event that the second toss was a
head

EXAMPLE : Rolling a die

S ={ }
S={1,2,3,4,5,6}
E={1,3,5} the event that an odd number is rolled.
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 5
AASTU
• Union 𝐴 ∪ 𝐵: an outcome is in A ∪ 𝐵 if it is
either in A or in B.
• Intersection A ∩ B: an outcome is in A ∩ 𝐵 if it
is in both A and B.
• Mutually exclusive: A and B are mutually
exclusive if A ∩ 𝐵 = ∅. 𝑆
𝐴 𝐵
Example: Roll die
𝐴: Outcome is below 3
𝐵: Outcome is above 4 Mutually exclusive events
• Complement 𝐴𝑐 : outcome that is not in 𝐴.
2021/5/10
Chapter 2: Discrete Mathematics (Math191)
6
AASTU
 Venn Diagrams
Venn Diagrams allow us to combine events, e.g. “𝐴
happened and 𝐵 happened”.
𝑆 𝑆
𝐴 𝐵 𝐴 𝐵

The event “𝐴 and 𝐵” The event “𝐴 or 𝐵”

Known as the intersection of 𝐴 and 𝐵. Known as the union of 𝐴 and 𝐵.

𝑆 𝑆
𝐴 𝐵 𝐴 𝐵

The event “not 𝐴” These can be combined,

Events that does not belong
2021/5/10
Chapter 2:to
Discrete e.g. “𝐴 and not 𝐵”.
𝐴. Mathematics (Math191) 7
AASTU
• A ∪ B = B ∪ A and A ∩ B = B ∩ A
• A∪ B∪C = A∪B ∪C
• A ∩ (B ∩ C) = (A ∩ B) ∩ C
• A∩ B∪C = A∩B ∪ A∩C
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• (𝐴𝑐 )𝑐 = A
• A ∩ S = A; A ∪ S = S; A ∩ ∅ = ∅ ; and A ∪ A = A
• (A ∪ B)c = 𝐴𝑐 ∩ 𝐵𝑐 and (A ∩ B)c = 𝐴𝑐 ∪ 𝐵𝑐
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 8
AASTU
Suppose that the sample space
S = {a1, a2, a3, … an}
has a finite number, n, of outcomes. Suppose that
each of the outcomes is equally likely. Then for
any event E, the probability P(E) is defined as
𝑛(𝐸) 𝑁𝑜. 𝑜𝑓 𝑜𝑢𝑡𝑐𝑜𝑚𝑒𝑠 𝑖𝑛 𝐸
𝑃 𝐸 = =
𝑛(𝑆) 𝑇𝑜𝑡𝑎𝑙 𝑁𝑜. 𝑜𝑓 𝑜𝑢𝑡𝑐𝑜𝑚𝑒𝑠
The probability of event 𝐸 with sample space 𝑆 is a
number assigned to 𝐸 that satisfies the following
1. 0 ≤ 𝑝(𝐸) ≤ 1
2. 𝑝 𝑆 = 1
3. For any sequence of events 𝐸1 , 𝐸2 … , which are
mutually exclusive 𝑝 ∞ 𝐸
𝑛=1 𝑛 = ∞
𝑛=1 𝑝(𝐸𝑛 ).

Theorem: If A is an event in a discrete sample space

S, then P(S) equals the sum of the probabilities of
the individual outcomes comprising A.
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 10
AASTU
Example 1: Roll a fair die, we have 6 equally likely
outcome *1,2,3,4,5,6+
𝑝(*1+) = 1/6, 𝑝(*2+) = 1/6, … 𝑝(*6+) = 1/6.
Example 2: E: The outcome is even. 𝑝(𝐸) =?
𝑝(𝐸) = 𝑝(2,4,6) = 𝑝(2) + 𝑝(4) + 𝑝(6) = 1/2
Example 3: Choosing a point from the interval
(𝑎, 𝑏) at random, that is each point is equally likely to
be chosen the probability measure is given by
𝑑−𝑐
𝑝 𝑐, 𝑑 = , for all interval (𝑐, 𝑑) ⊂ (𝑎, 𝑏)
𝑏−𝑎

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 11
AASTU
Properties
1) 𝑝 𝐸 + 𝑃 𝐸 𝑐 = 1
2) Any event E and F (may not mutually exclusive)
p E ∪ 𝐹 = p E + p F − p(𝐸 ∩ 𝐹)
• Proof. E and 𝐸 𝑐 ∩ 𝐹 are disjoint
𝐸 ∪ 𝐸𝑐 ∩ 𝐹 = 𝐸 ∪ 𝐹
𝑃 𝐸 ∪ 𝐸𝑐 ∩ 𝐹 = 𝑃 𝐸 ∪ 𝐹
𝑃 𝐸 + 𝑃 𝐸𝑐 ∩ 𝐹 = 𝑃 𝐸 ∪ 𝐹
𝑃 𝐸 + 𝑃 𝐸𝑐 ∩ 𝐹 + 𝑃 𝐸 ∩ 𝐹 − 𝑃 𝐸 ∩ 𝐹 = 𝑃 𝐸 ∪ 𝐹
𝑃 𝐸 + 𝑃 𝐸𝑐 ∩ 𝐹 ∪ 𝑃 𝐸 ∩ 𝐹 − 𝑃 𝐸 ∩ 𝐹 = 𝑃 𝐸 ∪ 𝐹
But 𝐸 𝑐 ∩ 𝐹 ∪ 𝑃 𝐸 ∩ 𝐹 = 𝐹
Therefore p E ∪ 𝐹 = p E + p F − p(𝐸 ∩ 𝐹).
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 12
AASTU
• Suppose that we have a random experiment
with sample space 𝑆 and probability function 𝑃
and 𝐴 and 𝐵 are events. Then we have the
following results:
I. 𝑃(∅ ) = 0
II. 𝑃(𝐴𝑐 ) = 1 − 𝑃(𝐴)
III. 𝑃(𝐵 ∩ 𝐴𝑐 ) = 𝑃(𝐵) − 𝑃(𝐴 ∩ 𝐵)
IV. If 𝐴 subset of 𝐵 then 𝑃(𝐴) ≤ 𝑃(𝐵).

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 13
AASTU
• 𝑆𝑢𝑝𝑝𝑜𝑠𝑒 𝑡ℎ𝑎𝑡 𝑤𝑒 𝑡𝑜𝑠𝑠 𝑡𝑤𝑜 𝑐𝑜𝑖𝑛𝑠, 𝑎𝑛𝑑 𝑎𝑠𝑠𝑢𝑚𝑒 𝑡ℎ𝑒𝑦
𝑎𝑟𝑒 𝑒𝑞𝑢𝑎𝑙𝑙𝑦 𝑙𝑖𝑘𝑒𝑙𝑦.
𝐿𝑒𝑡 𝐴 = 𝐻, 𝐻 , 𝐻, 𝑇 𝑎𝑛𝑑 𝐵 = 𝐻, 𝐻 , 𝑇 , 𝐻
𝑡ℎ𝑒𝑛 𝑓𝑖𝑛𝑑 𝑡ℎ𝑒 𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑖𝑒𝑠 𝑜𝑓 𝐴, 𝐵, 𝐴𝑐 , 𝐵𝑐 , 𝑎𝑛𝑑 𝑆 𝑐 .

Solution:
𝟐
• P(A)= = 𝟎. 𝟓
𝟒
𝟐
• P(B)= = 𝟎. 𝟓
𝟒
• P(𝑨𝒄 )=𝟏 − 𝑷(𝑨) = 𝟎. 𝟓
• P(𝑩𝒄 )=𝟏 − 𝑷(𝑩) = 𝟎. 𝟓
• 𝑃(𝑆 𝑐 ) = 1 − 𝑃 𝑆 = 1 − 1 = 0 = 𝑃(∅)

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 14
AASTU
• Definition: If 𝑃(𝐵) > 0, the conditional
probability of 𝐴 given 𝐵, denoted by 𝑃(𝐴|𝐵), is
p(A∩B)
P AB =
P(B)
Example :A box contains black chips and white chips. A
person selects two chips without replacement. If the
probability of selecting a black chip and a white chip is
15/56 , and the probability of selecting a black chip on
the first draw is 3/8, find the probability of selecting the
white chip on the second draw, given that the first chip
selected was a black chip.
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 15
AASTU
Solution
Let B= selecting a black chip and W= selecting a white
chip. Then
p(W∩B) 15/56 5
P 𝑊B = = =
P(B) 3/8 7

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 16
AASTU
• Theorem: Suppose events 𝐹1 , 𝐹2 , 𝐹3 , … , 𝐹𝑛 are mutually exclusive
and 𝑛𝑖=1 𝐹𝑖 = 𝑆. Given any event E

𝑃 𝐹𝑖 𝑃(𝐸|𝐹𝑖 )
𝑝 𝐹𝑖 𝐸 = 𝑛
𝑗=1 𝑃 𝐹𝑗 𝑃(𝐸|𝐹𝑗 )

Example: A bag X contains 2 white and 3 red balls and a bag Y

contains 4 white and 5 red balls. One ball is drawn at random
from one of the bags and is found to be red. Find the probability
that it was drawn from bag Y.
Solution 𝐸1 ∶ the event of choosing bag X
𝐸2 : the ball is drawn from bag Y
A: ball is red
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 17
AASTU
 𝑃 𝐸2 𝑃(𝐴|𝐸2 )
𝑝 𝐸2 𝐴 = 2
𝑗=1 𝑃 𝐸𝑗 𝑃(𝐴|𝐸𝑗 )

1 5
∗9
𝑝 𝐸2 𝐴 = 2
1 3 1 5
∗ + ∗
2 5 2 9

25
=
52

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 18
AASTU
Definition:-Two events A and B are said to be
independent if 𝑃(𝐴 ∩ 𝐵) = 𝑃(𝐴)𝑃(𝐵). If in
addition, 𝑃(𝐵) > 0, independence is equivalent to
the condition 𝑃(𝐴|𝐵) = 𝑃(𝐴).
Example: A coin is tossed and a dice is rolled
simultaneously. What is the probability of a tail and
a 6 coming at the output
Solution: Since 𝑝(𝑇) = 1/2 and 𝑝(6) = 1/6
probability of a tail coming in the toss and getting
a 6 in dice is 1 2 ∗ 1 6 = 1 12 .
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 19
AASTU
 2.5 Random variables and expectation
Example: A random variable is a variable whose value
depends on the outcome of a random event.
Probability distributions
𝒙 red green blue orange
𝑷(𝑿 = 𝒙) 0.3 0.4 0.1 0.2

! A random variable 𝑿 represents a single experiment/ trial. It

consists of outcomes with a probability for each.
i.e. 𝑋 is a random variable (capital
𝑃(𝑋 = 𝑥) letter), but 𝑥 is a particular
outcome

“The probability …the outcome of the …was the specific

that… random variable 𝑋… outcome 𝑥”
A shorthand for 𝑃 𝑋 = 𝑥 is ! 𝑝 𝑥 (note the lowercase 𝑝).
It‟s like saying “the probability that the outcome of my coin throw was heads
” (𝑃(𝑋 = ℎ𝑒𝑎𝑑𝑠)) vs “the probability of heads” (𝑝(ℎ𝑒𝑎𝑑𝑠)). In the latter the coin throw
was implicit, so we can skip the „𝑋 = ′.
Probability Distributions vs Probability Functions
There are two ways to write the mapping from outcomes to
probabilities:
The “{“ means we have a „piecewise function‟. This just simply
As a function: means we choose the function from a list depending on the
input.
0.1𝑥, 𝑥 = 1,2,3,4 e.g. if 𝑥 =3, then the
𝑝 𝑥 = probability is 0.1 × 3 = 0.3
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Advantages of functional form:
Can have a rule/expression based on the
As a table: outcome. it would be impossible to list the
probability for every outcome. More compact.
𝒙 1 2 3 4
𝒑(𝒙) 0.1 0.2 0.3 0.4

Advantages of table form:

Probability for each outcome more explicit.
Example
The random variable 𝑋 represents the number of
heads when three coins are tossed.
Underlying Distribution as a Table
Sample Space
Num heads 𝒙 0 1 2 3
{ HHH, 𝑷(𝑿 = 𝒙) 1 3 3 1
HHT, 8 8 8 8

HTT,
Distribution as a Function
HTH,
THH,
THT,
TTH,
TTT }
• Many real problems (experiments) have two possible
outcomes, for instance, a person may be HIV-Positive
or HIV-Negative, a seed may germinate or not, the sex
of a new born bay may be a girl or a boy, etc.

• Technically, the two outcomes are called Success and

Failure.

• Experiments or trials whose outcomes can be classified

as either a “success” or as a “failure” are called
Bernoulli trails.
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 23
AASTU
! You can model a random variable 𝑋 with a
binomial distribution 𝐵(𝑛, 𝑝) if
• there are a fixed number of trials, 𝑛,
• there are two possible outcomes: „success‟ and
„failure‟,
• there is a fixed probability of success, 𝑝
• the trials are independent of each other
If 𝑋~𝐵(𝑛, 𝑝) then:
𝑛 𝑟
𝑃 𝑋=𝑟 = 𝑝 1 − 𝑝 𝑛−𝑟
𝑟
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 24
AASTU
Theorem: The probability of exactly 𝑟 successes in
𝑛 independent Bernoulli trials, with probability of
success 𝑝 and probability of failure 𝑞 = 1 − 𝑝, is

𝑃 𝑋 = 𝑟 = 𝐶 𝑛, 𝑟 𝑝𝑟 𝑞𝑛−𝑟

Exercise: A fair coin is flipped 4 times. Let X be

the number of heads appearing out of the four
trials. Calculate the following probabilities that 2
heads will appear
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 25
AASTU
Example: The probability that a randomly chosen
member of a reading group is left-handed is 0.15.
A random sample of 20 members of the group is taken.
a. Suggest a suitable model for the random variable X, the
number of members in the sample who are left-handed.
Justify your choice.
b. Use your model to calculate the probability that:
i. exactly 7 of the members in the sample are left-handed
ii. fewer than two of the members in the sample are left-
handed.

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 26
AASTU
a. The random variable can take two values, left-handed
or right-handed.
There are a fixed number of trials, 20, and a fixed probability of
success: 0.15.
Assuming each member in the sample is
independent, a suitable model is X ∼ B(20, 0.15).
b. i P(X = 7) = ( 270 ) × (0.15)7(0.85)13
= 0.016 01…
= 0.0160 (3 s.f.)
ii P(X < 2) = P(X = 0) + P(X = 1)
= 0.038 75… + 0.136 79…
= 0.176 (3 s.f.)
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 27
AASTU
Definition: Let 𝑋 be a discrete random variable
with possible values 𝑥1 , 𝑥2 , . . . and probability
mass function (pmf) p(x). The expected value
and variance of 𝑋 are calculated by
𝐸 𝑋 =𝜇= 𝑥𝑖 𝑝(𝑥𝑖 )
𝑖
𝑉𝑎𝑟 𝑋 = 𝜎 2 = 𝐸 𝑋 2 − 𝐸 𝑋 2

= 𝑥 2 𝑝 𝑥 − 𝜇2

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 28
AASTU
• Example: Flip a coin 3 times. Let 𝑋 be the number of
heads. Find 𝐸(𝑋).
Solution:
1
𝐸(𝑋) = (𝑋(𝐻𝐻𝐻)
+ 𝑋 𝐻𝐻𝑇 + 𝑋 𝐻𝑇𝐻 +
8
𝑋 𝑇𝐻𝐻 + 𝑋 𝑇𝑇𝐻 + 𝑋 𝑇𝐻𝑇 +
𝑋 𝐻𝑇𝑇 + 𝑋(𝑇𝑇𝑇 ) )
1
= (3 + 2 + 2 + 2 + 1 + 1 + 1 + 0)
8
12
=
8
3
=
2
Chapter 2: Discrete Mathematics (Math191)
2021/5/10 29
AASTU
Theorem: let X and Y are random variable on
the sample space S and 𝑎 and 𝑏 are real number,
then
i. 𝐸(𝑋 + 𝑌) = 𝐸(𝑋) + 𝐸(𝑌)
ii. 𝐸(𝑎𝑋 + 𝑏) = 𝑎𝐸(𝑋) + 𝑏

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 30
AASTU
 End of Chapter 2
Thank you!

Chapter 2: Discrete Mathematics (Math191)

2021/5/10 31
AASTU