First Passage Times

The symmetric random walk of SPction 5 . 1 starts at 0 at t ime zero. Fix an integer m, and let. Tm denote the first time the random walk reaches level m;

i.e. ,

Tm = mi_n{n; JIJ, = m}. (5.2 . 1 ) I f _the random walk never reaches the level m , we define T711 t o b e _in_fini_ty.

The random variable Tm is a stopping time, called t he first passage time of the random walk to level m. \\'e shall determine its distribution. We shall _see that Tm is finite with probability ₁ ( i .e .. with probability 1 . the random walk eventually reaches t lw level m ), but IErm ^{= Xi.} Once we have determined t he distribution of Tm for a s:vmmetric random walk, we shall see how to modif�·

t he formulas to obtain information about the distribution of Tm wlwn the walk is ru;ymmetric.

Our study of the distribution of r ^m for a symmetric random walk uses the martingale _{5.2

.

2) below, which is discussed in Exercise 2.4{ii) at the end of Chapter 2.

Lemma 5.2 . 1 . Let 1\!11 be a symmetric random walk. Fix a number ^a and define the prores8

(

²

)

^"

S = e"11I, "

e" + e -"

Then S, . 11 = 0. 1 , 2, ... i.� a martingale.

PROOF: In the notation of ( 5. 1 . 1 ) and ₍5.1.2), we have

(5.2.2)

We take out what is _known (Theorem 2.3.2(ii)) and use independence (The­

orem 2.3.2{iv)) to write

5.2 First Passage Times 121

EnSn+l

₌ Sn

(

²

) JEe<>"Xn+l

e" +

e-"

-S

(

²

) (

-e + -e ^{1 ()" 1 -<T}

)

- " e" + e-" 2 2

=

Sn.

This shows that the process S

n

^, n ⁼ 0, 1, 2, . . . is a martingale. ₀ Because a martingale stopped at a stopping time is still a martingale (Theorem 4.3.2), the process

SniiT'"

is a martingale and hence has constant expectation, i.e.,

1 = So = IES

_ni\Tm

₌ E e"111n/\Tm

[ ⁽

²

^{) n/\Tm} l

^{for all} n > 0.

e<>"

⁺ e-<>" - (5.2.3)

We would like to let _n __, oo in (5.2.3). In order to do that, we must

( ) ni\Tm

determine the limit as _n __, oo of e"111"1\T"'

e"+2e_"

. We treat the two factors separately.

We observe first that cosh(a) ₌

e"+2e-"

attains its minimum at (J = 0, where it takes the value 1. Hence, cosh((!) > ₁ for all (J > 0, so

0 < e" + e-" 2 < 1 ^{for all (J > 0.}

We now fix (J > 0 and conclude from (5.2.4) that

(

²

) ^n/\Tm { ^{( 2 ) Tm}

^"f

lim ₌

e"+e-"

• 1 Tm < oo,

n-oo

e" + e-<>" _{0, if} Tm ₌ 00.

(5.2.4)

(5.2.5)

We may write the right-hand side of (5.2.5) as H{rm<oo}

(e _{.. )} e-" ) ^{Tm ,}

^which

captures both cases.

To study the other factor,

e"M""'m ,

we assume that m > 0 and note that

Mn/\Tm

^{$ m} because we stop this martingale when it reaches the level m.

Hence, regardless of whether T m is finite or infinite, we have

We also have

lim e<>"Mn/\T•n ⁼ e

"

M

T ^m

^{= e"m} if Tm < 00.

n.-oo

Taking the product of (5.2.5) and (5.2.7), we see that

( e"

+ ² e-"

) ^ni\Tm

^{= e"m}

(

e" ₊ ² e-"

) ^Tm

^{if Tm} < 00.

(5.2.6)

(5.2.7)

(5.2.8)

5.2 First Passage Times 123 In order to determine the distribution of the first passage time Tm, we examine its moment-generating function 'PTm (u) = Eeu

T ,.

^{. For all x ;::: 0,}

ez = 1 ₊ x +

�x2

+ · · ·

;:::

x. Hence, for positive u, we have e

u

Tm ;::: UT"m and so 'PTm (u) = EeuTm ;::: uErm. We shall see in Corollary 5.2.4 below that Erm = oo, which implies that 'PTm (u) = oo for u > 0. For u = 0, we have 'PTm (u) = 1. Therefore, the moment-generating function 'PTm (u) is interesting only for u < 0. For u < 0, we set a = eu _so that 0 < a < 1 and 'PTm(u) = JEaTm.

Theorem 5.2.3.

Let m be a nonzero integer. The first 11assage time 'Tm for the symmetric random walk satisfies

1 - �

( )

^lml

Ea""' =

a for all a _E (0, ^{1). (5.2.13)}

PROOF: For the symmetric random walk, Tm and r -m have the same distri­

bution, so it is enough to prove the theorem for the case that m is a positive integer. We take m to be a positive integer. Because lP'{rm < oo} = 1 , we may simplify (5.2.11) to

E e"m

[ (

²

)

^Tm

]

- 1 e" + e-" - · This equation holds for all strictly positive cr.

{5.2.14)

To obtain (5.2.13) from (5.2.14), we let a E (0, 1) be given and solve for a > 0, which satisfies

This is equivalent to

Q = 2

--­

e" + e-"

ae_{" + ae-" -}2 = 0, which is in turn equivalent to

(5.2.15)

This last equation is a quadratic equation in the unknown

e-",

and the solu­

tions are

_ 2 ± J 4 -

4a2 1 ±

^{JI -a2}

e " -^{- 2a} -^-

---

^a ·

We need to find a. strictly positive CT satisfying this equation, and thus we need

e-"

to be strictly less than one. That suggests we should take the solution for e-" corresponding to the negative sign in the formula above; i.e.,

_ 1 -Jl - a2

e

^{u =} .

a (5.2.16)

We verify that (5.2.16) leads to a value of cr that is strictly positive. Because

we have chosen a to satisfy 0 < a < 1, we have

' _I

124 5 Random Walk

0 < ( 1 - o)2 < 1 - o < 1 - o2 . Taking positive square roots, we obtain

1 - o < �.

Therefore, _{1 -}vT=Q2 ^{< o ,} and dividing through by o, we see that the right­

hand side of _{(5.2. 16)} is strictly less than _{1 .} This implies that a in _{(5.2. 16)} is strictly positive.

With a and o related by (5.2. 16). we have that o and a are also related by _(5.2.15) and hence may rewrite _{(5.2. 14)} as

( ) m

Because

l-�

^{is not.} random, we may take it outside the expectation and divide through by it. Equation _(5.2.13) for positive m follows immediately.

0

Corollary 5.2.4. Under the conditions of Theorem 5. 2. 3, we have

IErm = ^00. (5.2. 17)

P ROOF:� We first show that IEr1 = oo . To do this, we differentiate both sides of _{(5.2. 13)} with respect to o :

= -JEorl D 00

8 1 - Jf=Q2

00: 0

- ! ( 1 - o2 ) - ! ( -2o:)o: - ( 1 - ( 1 - o2 ) ! ) o:2

o 2 ( 1 - o2) - ! - 1 ₊ ( 1 - o2 ) 1 o2

o2 - � + 1 - o2

a2�

1 - � o:2J1 - o2 .

This equation is valid for all o E (^0, 1 ) . We may not substitute o = 1 into this equation, but we may take the limit of both sides as o i 1 , and this gives ns IEr1 = oo.

3 There are two steps in the proof of Corollary 5.2.4 that require the interchange of limit and expectation. The first of these, differentiation of 1Eor1 with respect. to a ,

can be justified by an argument like that in Exercise 8 in Volume II, Chapter 1 . The second, where we let a I 1 . i s an application of the Monotone Convergence Theorem 1.4.5 of Volume JT, ChRpt.er ^{1 .}

...

L

5 . 2 First Passage Times 125 For m �

1,

we have Tm � TJ and hence IETm � IET1

=

^{oo .} For strictly negative integers m, the symmetry of the random walk now implies IETm = oo .

0

From the formula

(5.2. 13),

it is possible to compute explicitly the distribu­

tion of the random variable

T1 .

We have the special case of formula

(5.2.13):

1 - v'1 - a2

1Ear1 = a

^{for all}

a

E

(0, 1). ^(5.2.18)

Because the random walk can reach level

1

only on an odd-numbered step, the left-hand side of

(5.2. 18)

may be rewritten as

00

1Ear1 = E a21-11P'{T1 = 2j - 1 }

j=l

(5.2.19)

We work out a power series expansion for the right-hand side of

(5.2. 18).

Define

f(x) = 1 -

vT=X ^{so that}

'( 1

¹

f x) = '2 ( 1 - x) - > ,

"( 1

³

f x) = 4 (1 - x)- > , j111(x) = � (1 - x)- � ,

and, in general, the jtl1-order derivative of

f

^is

( ') 1

. 3 . . . (2j - 3)

�

f 1 (x)

= 21 (1 - x) -

^{2 ,}

j = l , 2, 3, . . . .

Evaluating at

0,

we obtain

f(O) = 0, j'(O) = �· j"(O) = �· j"'(O)

⁼⁼

�

and, in general,

1u> (o) = 1 . 3 . . . (2j - 3) 2J

1

. 3 . . . (2j - 3) 2 .

⁴

. . . (2j - 2)

2J 2J-1 (j - I)!

= (�)2j-J ^{(2j - 2)!}

2 (j - 1)! ' j = 1, 2, 3, . . . . (5.2.20)

(We use here the definition

0! = 1.)

The Taylor series expansion of

f(x)

^is

00 1 . . 00

( ¹ ) ^2j-l (2 . - 2)'

f(x) = 1 -

v'l='X

= L

_{J-0 . _} ⁷

1! jC1> (o)x1 = ""

_{J= l}

L 2

^-

J!(J - 1)! . 1. · x1 .

126 5 Random Walk

Therefore,

1 -�

=

f(a2)

= � (�)2i-I

^{(2j -2)! .}

Q Ct

f:r

² j!(j - 1)! (5.2.21)

We have t.hus worked out the power series (5.2.19) and (5.2.21) for the two sides of (5.2.18). Equating them, we obtain

� 2j-t 1P'{r =

2 . - 1 } ⁼

� (�)2j-I

^{(2j - 2)!}

� ^{Ct I} J � 2 '!( . - I ) !

j=l j=l

^{J J}

for all a E (0, 1).

The only way these two power series can be equal for all a E (0, 1) is for their coefficients to be equal term-by-term (i.e., the term multiplying

a2i-l

must be the same in both series). This gives us the formula

. (2j -2)!

( 1) ^2j-l

IP'{rt

⁼ 2J - 1} ⁼

j!(j _ 1)!

· 2 ,

j = 1,2, . . . . We verify (5.2.22) for the first few values of j. For j = 1, we have

(5.2.22)

The only way r1 can be 1 is for the first coin toss to result in H. and t,he probability of this for a symmetric random walk is

4.

^{For j}

=

2, we have

2!

(

¹

)

³

(

¹

)

³

JP'{ TJ

= 3} = 2!1! .

2 = 2

The only way r1 can be 3 is for the first thref' coin tosses to result in T H H,

and the probability of this is

( � t

^{For j =} 3, we have 41

(

¹

)

⁵

(

¹

)

⁵

JP'{

_TJ = 5} = 3!�! .

2 =

2 .

2

There are two ways T1 can be 5; the first five tosses could be either T HT H H

or TTH H H, and the probability of each of these outcomes is

(�t

From these examples, we see how to interpret the two factors appearing on the right-hand side of (5.2.22). The term

j��-=.W,

counts the number of paths with 2j -1 steps that first reach level 1 on the (2j -1 )st step ^so that

T1 = 2j -1 . The term

( �) 2j-I

is the probability of each of these paths.

Suppose now that the random walk is not symmetric, but has probability p for H and probability q = 1 - p for T. The number of paths that first reach level 1 on the (2j - l)st step is unaffected. However, since each of these paths must have j up steps and j - 1 down steps, the probability of such a path is now

piqi-t.

This observation leads to the following theorem.

문서에서 Springer New York Berlin Heidelberg Hong Kong London Milan Paris Tokyo (페이지 135-142)