Mathematics for Computer Science

Chapter 18 Random Variables776

location

-4 -3 -2 -1 0 1 2 3 4

initially 1

after 1 step 1=2 0 1=2

after 2 steps?????

after 3 steps???????

after 4 steps?????????

(b)

1. What is the final location of at-step path that moves right exactlyitimes?


2. How many different paths are there that end at that location?


3. What is the probability that the sailor ends at this location?

(c)LetLbe the random variable giving the sailor’s location aftertsteps, and let
BWWD.LCt/=2. Use the answer to part (b) to show thatBhas an unbiased binomial
density function.

(d)Again letLbe the random variable giving the sailor’s location aftertsteps,
wheretis even. Show that

PrŒjLj<

p

t

2

ç <

1

2

:

So there is a better than even chance that the sailor ends up at least

p
t=2steps from
where he started.

Hint:Work in terms ofB. Then you can use an estimate that bounds the binomial
distribution. Alternatively, observe that the origin is the most likely final location
and then use the asymptotic estimate

PrŒLD0çDPrŒBDt=2ç

r

2

t

:

Problems for Section 18.4

Practice Problems

Problem 18.9.
Bruce Lee, on a movie that didn’t go public, is practicing by breaking 5 boards with
his fists. He is able to break a board with probability 0.8—he is practicing with his
left fist, that’s why it’s not 1—and he breaks each board independently.