Mathematics for Computer Science

Chapter 19 Deviation from the Mean836

(b)Prove that VarŒRçis infinite.

A joking way to phrase the point of this example is “the square root of infinity may
be finite.” Namely, letT WWDR^2 ; then part (b) implies that ExŒTç D 1while
ExŒ

p

Tç < 1 by (a).

Class Problems

Problem 19.34.
You have a biased coin with nonzero probabilityp < 1of tossing a Head. You
toss until a Head comes up. Then, similar to the example in Section 19.7, you
keep tossing until you get another Head preceded by a run of consecutive Tails
whose length is within 10 of your original run. That is, if you began by tossingk
tails followed by a Head, then you continue tossing until you get a run of at least
maxfk10;0gconsecutive Tails.

(a)LetHbe the number of Heads that you toss until you get the required run of
Tails. Prove that the expected value ofHis infinite.

(b)Letr < 1be a positive real number. Instead of waiting for a run of Tails of
lengthk 10 when your original run was lengthk, just wait for a run of length at
leastrk. Show that in this case, the expected number of Heads is finite.

Exam Problems

Problem 19.35.
You have a random process for generating a positive integer,K. The behavior
of your process each time you use it is (mutually) independent of all its other uses.
You use your process to generate an integer, and then use your procedure repeatedly
until you generate an integer as big as your first one. LetRbe the number of
additional integers you have to generate.

(a)State and briefly explain a simple closed formula for ExŒRjKDkçin terms
of PrŒKkç.

Suppose PrŒKDkçD‚.k^4 /.

(b)Show that PrŒKkçD‚.k^3 /.

(c)Show that ExŒRçis infinite.

Problem 19.36.