Mathematics for Computer Science

Chapter 16 Events and Probability Spaces536

1=2

1=2

1=2

1=2

H

H

H

H

T

T

T

T

1=2

1=2

1=2

1=2

1=2

1=4

1=8

1= 16

1 st

player

1 st

2 nd player

player

2 nd

player

Figure 16.11 The tree diagram for the game where players take turns flipping a
fair coin. The first player to flip heads wins.

16.4.4 Infinite Probability Spaces

Infinite probability spaces are fairly common. For example, two players take turns
flipping a fair coin. Whoever flips heads first is declared the winner. What is the
probability that the first player wins? A tree diagram for this problem is shown in
Figure 16.11.
The event that the first player wins contains an infinite number of outcomes, but
we can still sum their probabilities:

PrŒfirst player winsçD

1

2

C

1

8

C

1

32

C

1

128

C

D

1

2

X^1

nD 0



1

4

n

D

1

2



1

1 1=4



D

2

3

:

Similarly, we can compute the probability that the second player wins:

PrŒsecond player winsçD

1

4

C

1

16

C

1

64

C

1

256

C


D

1

3

:

In this case, the sample space is the infinite set

SWWDfTnHjn 2 Ng;