Ideas of Chance in Computer Science 483are assumed to be fair, meaning that each card of a deck, face of a coin, or side of a die is
equally likely to occur.
Notation. Since we will be using the counting techniques of Chapter 7, now is a good
time to recall that C(m, n), denotes the binomial coefficient-that is, the number of ways
of choosing n elements from a set of m elements. See Section 7.9.1 for more details.
Example 6. A (fair) coin is tossed three times. What is the probability that at least two
heads turn up?
Solution. The experiment is to toss a coin three times. The event E of interest is that
either two or three heads turn up. To make this event easy to describe, we choose a sample
space 02 with outcomes co that are ordered triples (H representing heads and T representing
tails) describing what happens on each toss:
(01 = (H, H, H) (05 = (H, T, T)
0)2 = (H, H, T) (06 = (T, H, T)
(03 = (H, T, H) w 7 = (T, T, H)
0o4 = (T, H, H) (08 = (T, T, T)Hence, 2 = {o01,0&2.. U81 and E = {11, (0 2 , (03, (0 4 ).
Since the coin is fair, we choose a uniform probability density function for Q2. This
assigns a probability of p(o) = 1/I Q2 I = 1/8 to each outcome wi for 1 < i < 8. Hence,
by Definition 5 in Section 8.1.2, P(E) I E 1(1/8) = 4/8 = 1/2. U
Example 7. A coin is tossed 10 times. What is the probability that eight or more heads
turn up?
Solution. Choosing £2 = {(fl, f2_. , flo) : fi E {H, T}} gives a sample space with
outcomes that can describe every possible result of flipping the coin 10 times. Since the
coin is fair, the outcomes can be assumed to be equally likely. Since I Q2I = 210, set-
ting p(w) = 2-10 for each o E Q2 defines a uniform probability density function on £2.
Rather than enumerate all the elements of Q2, we use counting techniques from com-
binatorics to compute the size of the set E that describes the situation "eight or more
heads." This set E is the disjoint union of three other events-namely, getting exactly
8 heads, exactly 9 heads, and exactly 10 heads. These events are given by sets of size
C(10, 8) = 45, C(1O, 9) = 10, and C(10, 10) = 1, respectively. Consequently, P(E) =
(2-10)(45 + 10 + 1) = 56. 2-10. NExample 8. A die is rolled five times. What is the probability of obtaining exactly one 2?
Solution. We choose the sample space with outcomes that are all the length of five se-
quences of die values. Each single roll results in one of six numbers, so there are 65 possible
outcomes in £2. Putting a uniform probability density function on £2 gives p(a) = 6-5 for
each sequence (0. We can count the number of length-five sequences with exactly one 2
using the Multiplication Principle. First, choose a location for the 2. This can be done in
C(5, 1) ways. For the other four locations, we can fill each in five ways using all the values
that can occur on the top face after the roll of a die, except for 2. Therefore, the total num-
ber of such sequences is C(5, 1) • 54. It follows that the probability of obtaining exactly
one 2 is C(5, 1)(54)(6-5). U