Soluciones al libro de steele de calculo estocastico

Appendix I: Problem Hints and Solutions

Chapter 1 Solution for Problem 1.1. Let Ti,j denote the expected time to go from level i to level j, and note by formula (1.16) that T25,20 = 15 and T21,20 = 3. By first-step analysis we also have T20,19 = 1 9 ·1+ · {1 + T21,20 + T20,19 } 10 10 check!

so substituting T21,20 = 3 and solving gives T20,19 = 37. Similarly, we have T19,18 = 1 2 · 1 + · {1 +T20,19 + T19,18 }, 3 3

so substituting T20,19 = 37 and solving gives T19,18 = 77. Finally, one finds T25,18 = T25,20 + T20,19 + T19,18 = 15 + 37 + 77 = 129. Solution for Problem 1.2. We get (1.26) just by substitution, and we also have Nn =
k:2k≤n

I(S2k = 0) and

E(Nn ) =
k:2k≤n

P (S2k = 0),

so (1.26) and integral comparison give us √ P (S2k = 0) ∼ 1/ πk ∼
k:2k≤n 1≤k≤n/2

2n/πas n → ∞.

Solution for Problem 1.3. First set N∞ = lim Nn and then note that P (N∞ ≥ k) = rk since the event {N∞ ≥ k} entails k successes of independent events each of which has success probability r. Now, if it were truely the case that 0 ≤ r < 1, then we would have

340

Problem Hints and Solutions
∞ ∞

E(Nn ) ≤ E(N∞ ) =
k=1

P (N∞ ≥ k) =
k=1

rk =

r < ∞, 1−r

but byExercise 1.2 we know E(Nn ) ∼

2n/π, so we must have r = 1.

Solution for Problem 1.4. First-step analysis gives us P (τ0 = 2k) = 1 1 P (τ0 = 2k | X1 = 1) + P (τ0 = 2k | X1 = −1), 2 2

but by symmetry and the identity (1.24) we have P (τ0 = 2k | X1 = 1) = P (τ0 = 2k | X1 = −1) = 1 2k −2k 2 2k − 1 k

from which (1.28) follows. The asymptotic formula (1.29) follows directly from Stirling’sformula, and the relation E(τ0 ) = ∞ is also straightforward. With α just a little more work, one can use (1.29) to check that E(τ0 ) < ∞ for all 1 1 α α < 2 and that E(τ0 ) = ∞ for all α ≥ 2 . Solution for Problem 1.5. To prove the first identity of (1.31), note that for k ≥ 1 the event {Lk > 0} cannot occur unless the first step of the random walk is to +1. If the first step is to +1, then {Lk > 0}occurs if and only if the walk hits k before it hits 0. By (1.2) this occurs with probability 1/k. When we put these two independent requirements together, we see that P (Lk > 0) = (1/2)(1/k). To prove the second identity of (1.31), we consider a time at which the walk hits level k, and we make two observations. If on its next step the walk goes up, then it is guaranteed to hit level k at least onemore time before it hits level 0. On the other hand, if the walk goes down on the next step after hitting level k, then by (1.2) the walk will hit level k a least one more time with probability (k − 1)/k. These observations combine to give us (1.31). Finally, to prove (1.30), we note that P (Nk > j) = P (Nk > 0)P (Nk > 1 | Nk > 0) · · · P (Nk > j | Nk > j − 1) = 1 2k 1 1k−1 + 2 2 k
j

=

1 2k2k − 1 2k

j

.

If we now sum over 0 ≤ j < ∞ we get E(Nk ) on the left, while on the right we see that geometric summation gives us exactly 1. Incidentally, this problem has an elegant generalization to biased random walk where p < q. If we repeat our argument but use the ruin probability formula (1.13) in place of the formula (1.2) for unbiased ruin probabilities, we discover that E(Lk )= (p/q)k . For p = q this recaptures the formula (1.30), and, in a way, it explains why E(Lk ) does not depend on k for unbiased walk. Solution for Problem 1.6. Let N(1,1)(α+β,α−β) denote the total number of random walk paths from (1, 1) to (α + β, α − β) and let

Problem Hints and Solutions
DoTouch N(1,1)(α+β,α−β)

341

and

DoNotTouch N(1,1)(α+β,α−β)

denote the corresponding numberof paths that respectively do and do not touch the axis. By the reflection principle and path counting we find
DoNotTouch DoTouch N(1,1)(α+β,α−β) = N(1,1)(α+β,α−β) − N(1,1)(α+β,α−β)

= N(1,1)(α+β,α−β) − N(1,−1)(α+β,α−β) = α+β−1 α+β−1 − α−1 α = α−β α+β , α+β α

so the probability that A leads throughout the counting process is
DoNotTouch DoNotTouch N(1,1)(α+β,α−β) /N(0,0)(α+β,α−β) =...