Mathematics for Computer Science

Chapter 16 Events and Probability Spaces690

whereTnstands for a lengthnstring ofT’s. The probability function is

PrŒTnHçWWD

1

2 nC^1

:

To verify that this is a probability space, we just have to check that all the prob-

abilities are nonnegative and that they sum to 1. The given probabilities are all

nonnegative, and applying the formula for the sum of a geometric series, we find

that X

n 2 N

PrŒTnHçD

X

n 2 N

1

2 nC^1

D1:

Notice that this model does not have an outcome corresponding to the possi-

bility that both players keep flipping tails forever. (In the diagram, flipping for-

ever corresponds to following the infinite path in the tree without ever reaching

a leaf/outcome.) If leaving this possibility out of the model bothers you, you’re

welcome to fix it by adding another outcome,!forever, to indicate that that’s what

happened. Of course since the probabililities of the other outcomes already sum to

1, you have to define the probability of!foreverto be 0. Now outcomes with prob-

ability zero will have no impact on our calculations, so there’s no harm in adding

it in if it makes you happier. On the other hand, in countable probability spaces

it isn’t necessary to have outcomes with probability zero, and we will generally

ignore them.

16.6 References

[16], [23], [27], [30], [34], [35] [39], [38], [47]

Problems for Section 16.2

Practice Problems

Problem 16.1.

LetBbe the number of heads that come up on2nindependent tosses of a fair coin.

(a)PrŒB D nçis asymptotically equal to one of the expressions given below.

Explain which one.

1. p2n^1


2. p^2 n