2Classification of chains and states

IB Markov Chains

2.3 Hitting probabilities

Recurrence and transience tells us if we are going to return to the original

state with (almost) certainty. Often, we would like to know something more

qualitative. What is the actual probability of returning to the state

i

? If we

return, what is the expected duration of returning?

We can formulate this in a more general setting. Let

S

be our state space,

and let

A ⊆ S

. We want to know how likely and how long it takes for us to

reach

A

. For example, if we are in a casino, we want to win, say, a million, and

don’t want to go bankrupt. So we would like to know the probability of reaching

A = {1 million} and A = {0}.

Definition (Hitting time). The hitting time of

A ⊆ S

is the random variable

H

A

=

min{n ≥

0 :

X

n

∈ A}

. In particular, if we start in

A

, then

H

A

= 0. We

also have

h

A

i

= P

i

(H

A

< ∞) = P

i

(ever reach A).

To determine hitting times, we mostly rely on the following result:

Theorem. The vector (h

A

i

: i ∈ S) satisfies

h

A

i

=

(

1 i ∈ A

P

j∈S

p

i,j

h

A

j

i ∈ A

,

and is minimal in that for any non-negative solution (

x

i

:

i ∈ S

) to these

equations, we have h

A

i

≤ x

i

for all i.

It is easy to show that

h

A

i

satisfies the formula given, but it takes some more

work to show that

h

A

i

is the minimal. Recall, however, that we have proved a

similar result for random walks in IA probability, and the proof is more-or-less

the same.

Proof. By definition, h

A

i

= 1 if i ∈ A. Otherwise, we have

h

A

i

= P

i

(H

A

< ∞) =

X

j∈S

P

i

(H

A

< ∞ | X

1

= j)p

i,j

=

X

j∈S

h

A

j

p

i,j

.

So h

A

i

is indeed a solution to the equations.

To show that

h

A

i

is the minimal solution, suppose

x

= (

x

i

:

i ∈ S

) is a

non-negative solution, i.e.

x

i

=

(

1 i ∈ A

P

j∈S

p

i,j

x

j

A i ∈ A

,

If i ∈ A, we have h

A

i

= x

i

= 1. Otherwise, we can write

x

i

=

X

j

p

i,j

x

j

=

X

j∈A

p

i,j

x

j

+

X

j∈A

p

i,j

x

j

=

X

j∈A

p

i,j

+

X

j∈A

p

i,j

x

j

≥

X

j∈A

p

i,j

= P

i

(H

A

= 1).

By iterating this process, we can write

x

i

=

X

j∈A

p

i,j

+

X

j∈A

p

i,j

X

k

p

i,k

x

k

!

=

X

j∈A

p

i,j

+

X

j∈A

p

i,j

X

k∈A

p

i,k

x

k

+

X

k∈A

p

i,k

x

k

≥ P

i

(H

A

= 1) +

X

j∈A,k∈A

p

i,j

p

j,k

= P

i

(H

A

= 1) + P

i

(H

A

= 2)

= P

i

(H

A

≤ 2).

By induction, we obtain

x

i

≥ P

i

(H

A

≤ n)

for all n. Taking the limit as n → ∞, we get

x

i

≥ P

i

(H

A

≤ ∞) = h

A

i

.

So h

A

i

is minimal.

The next question we want to ask is how long it will take for us to hit

A

.

We want to find

E

i

(

H

A

) =

k

A

i

. Note that we have to be careful — if there is a

chance that we never hit

A

, then

H

A

could be infinite, and

E

i

(

H

A

) =

∞

. This

occurs if

h

A

i

<

1. So often we are only interested in the case where

h

A

i

= 1 (note

that h

A

i

= 1 does not imply that k

A

i

< ∞. It is merely a necessary condition).

We get a similar result characterizing the expected hitting time.

Theorem. (k

A

i

: i ∈ S) is the minimal non-negative solution to

k

A

i

=

(

0 i ∈ A

1 +

P

j

p

i,j

k

A

j

i ∈ A.

Note that we have this “1+” since when we move from

i

to

j

, one step has

already passed.

The proof is almost the same as the proof we had above.

Proof. The proof that (k

A

i

) satisfies the equations is the same as before.

Now let (y

i

: i ∈ S) be a non-negative solution. We show that y

i

≥ k

A

i

.

If i ∈ A, we get y

i

= k

A

i

= 0. Otherwise, suppose i ∈ A. Then we have

y

i

= 1 +

X

j

p

i,j

y

j

= 1 +

X

j∈A

p

i,j

y

j

+

X

j∈A

p

i,j

y

j

= 1 +

X

j∈A

p

i,j

y

j

= 1 +

X

j∈A

p

i,j

1 +

X

k∈A

p

j,k

y

k

≥ 1 +

X

j∈A

p

i,j

= P

i

(H

A

≥ 1) + P

i

(H

A

≥ 2).

By induction, we know that

y

i

≥ P

i

(H

A

≥ 1) + ··· + P

i

(H

A

≥ n)

for all n. Let n → ∞. Then we get

y

i

≥

X

m≥1

P

i

(H

A

≥ m) =

X

m≥1

mP

i

(H

A

= m) = k

A

i

.

Example (Gambler’s ruin). This time, we will consider a random walk on

N

.

In each step, we either move to the right with probability

p

, or to the left with

probability

q

= 1

− p

. What is the probability of ever hitting 0 from a given

initial point? In other words, we want to find h

i

= h

{0}

i

.

We know h

i

is the minimal solution to

h

i

=

(

1 i = 0

qh

i−1

+ ph

i+1

i = 0.

What are the solutions to these equations? We can view this as a difference

equation

ph

i+1

− h

i

+ qh

i−1

= 0, i ≥ 1.

with the boundary condition that

h

0

= 1. We all know how to solve difference

equations, so let’s just jump to the solution.

If p = q, i.e. p =

1

2

, then the solution has the form

h

i

= A + B

q

p

i

for

i ≥

0. If

p < q

, then for large

i

,

q

p

i

is very large and blows up. However,

since

h

i

is a probability, it can never blow up. So we must have

B

= 0. So

h

i

is

constant. Since h

0

= 1, we have h

i

= 1 for all i. So we always get to 0.

If p > q, since h

0

= 1, we have A + B = 1. So

h

i

=

q

p

i

+ A

1 −

q

p

i

!

.

This is in fact a solution for all A. So we want to find the smallest solution.

As

i → ∞

, we get

h

i

→ A

. Since

h

i

≥

0, we know that

A ≥

0. Subject to this

constraint, the minimum is attained when

A

= 0 (since (

q/p

)

i

and (1

−

(

q/p

)

i

)

are both positive). So we have

h

i

=

q

p

i

.

There is another way to solve this. We can give ourselves a ceiling, i.e. we also

stop when we hit

k >

0, i.e.

h

k

= 1. We now have two boundary conditions

and can find a unique solution. Then we take the limit as

k → ∞

. This is the

approach taken in IA Probability.

Here if p = q, then by the same arguments, we get h

i

= 1 for all i.

Example (Birth-death chain). Let (

p

i

:

i ≥

1) be an arbitrary sequence such

that

p

i

∈

(0

,

1). We let

q

i

= 1

− p

i

. We let

N

be our state space and define the

transition probabilities to be

p

i,i+1

= p

i

, p

i,i−1

= q

i

.

This is a more general case of the random walk — in the random walk we have

a constant p

i

sequence.

This is a general model for population growth, where the change in population

depends on what the current population is. Here each “step” does not correspond

to some unit time, since births and deaths occur rather randomly. Instead, we

just make a “step” whenever some birth or death occurs, regardless of what time

they occur.

Here, if we have no people left, then it is impossible for us to reproduce and

get more population. So we have

p

0,0

= 1.

We say 0 is absorbing in that {0} is closed. We let h

i

= h

{0}

i

. We know that

h

0

= 1, p

i

h

i+1

− h

i

+ q

i

h

i−1

= 0, i ≥ 1.

This is no longer a difference equation, since the coefficients depends on the

index i. To solve this, we need magic. We rewrite this as

p

i

h

i+1

− h

i

+ q

i

h

i−1

= p

i

h

i+1

− (p

i

+ q

i

)h

i

+ q

i

h

i−1

= p

i

(h

i+1

− h

i

) − q

i

(h

i

− h

i−1

).

We let

u

i

=

h

i−1

− h

i

(picking

h

i

− h

i−1

might seem more natural, but this

definition makes u

i

positive). Then our equation becomes

u

i+1

=

q

i

p

i

u

i

.

We can iterate this to become

u

i+1

=

q

i

p

i

q

i−1

p

i−1

···

q

1

p

1

u

1

.

We let

γ

i

=

q

1

q

2

···q

i

p

1

p

2

···p

i

.

Then we get

u

i+1

=

γ

i

u

1

. For convenience, we let

γ

0

= 1. Now we want to

retrieve our

h

i

. We can do this by summing the equation

u

i

=

h

i−1

− h

i

. So we

get

h

0

− h

i

= u

1

+ u

2

+ ··· + u

i

.

Using the fact that h

0

= 1, we get

h

i

= 1 − u

1

(γ

0

+ γ

1

+ ··· + γ

i−1

).

Here we have a parameter

u

1

, and we need to find out what this is. Our theorem

tells us the value of u

1

minimizes h

i

. This all depends on the value of

S =

∞

X

i=0

γ

i

.

By the law of excluded middle,

S

either diverges or converges. If

S

=

∞

, then

we must have

u

1

= 0. Otherwise,

h

i

blows up for large

i

, but we know that

0

≤ h

i

≤

1. If

S

is finite, then

u

1

can be non-zero. We know that the

γ

i

are

all positive. So to minimize

h

i

, we need to maximize

u

1

. We cannot make

u

1

arbitrarily large, since this will make

h

i

negative. To find the maximum possible

value of

u

1

, we take the limit as

i → ∞

. Then we know that the maximum value

of u

1

satisfies

0 = 1 − u

1

S.

In other words, u

1

= 1/S. So we have

h

i

=

P

∞

k=i

γ

k

P

∞

k=0

γ

k

.