Mathematics for Computer Science

Chapter 18 Deviation from the Mean660

Class Problems

Problem 18.22.
You have a biased coin with nonzero probabilityp < 1of coming up heads. You
toss until a head comes up, and then, as in Section 18.8, you keep tossing until you
get a long run of tails, but this time let “long run” mean a run of tails that is at least
k 10 when your initial run was lengthk. Prove that the expected number of times
you toss a head and start over is still infinite.

Problem 18.23.
LetT 0 ;T 1 ;:::be a sequence of mutually independent random variables with the
same distribution. Let

RWWDminfk > 0jTk> T 0 g:
(a)Suppose the range of theT 0 is the setft 0 < t 1 < t 2 <


g. Explain why the
following Theorem implies that ExŒRçD1.
Theorem 18.8.1.Ifp 0 Cp 1 Cp 2 C


D 1 and allpi 0 , then the sum

WWD

X

k 2 N

pk

pkC 1 CpkC 2 C

:

diverges.

(b)Let

SkWWDpkCpkC 1 C:::;

and

akWWD

Sk

SkC 1

1:

Prove that
D

X

k 2 N

ak: (18.31)

(c)Prove that

Y

kn

.akC1/D

1

SnC 1

:

(d)Conclude from part (c) that

Y

k 2 N

.akC1/D1: (18.32)

(e)Conclude thateD1and henceD1.