mean hitting time

Let (Xn)n0 be a Markov chainMathworldPlanetmath with transition probabilities pij where i,j are states in an indexing set I. Let HA be the hitting timePlanetmathPlanetmath of (Xn)n0 for a subset AI. That is, HA is the random variableMathworldPlanetmath of the time it takes for the to first reach a in A.

Define the mean hitting time of A given the starts in state i to be

Proposition 1.

The mean hitting times are the minimalPlanetmathPlanetmath non negative solution to:


Remark. In this case, a solution is minimal if for any non negative solution {yi|iI} we have yikiA for all iI.


If iA, then HA=inf{n0XnA}0, which means kiA=0 (the is certain to be in a state in A at step n=0).

If iA we condition on the first step:

kiA =E(HAX0=i)
=jIpijE(HA|X1=j)(by the Markov property)

So the kiA satisfy the given equations.

Now suppose that {yi|yI} is any non-negative solution to the equations. Then for iA we have kiA=yi=0. If iA, then

yi =1+jIpijyj

where qn=P(X1A,X1A,,XnA|X0=i) is the probability that the chain X does not enter A in the first n steps after the initial state i.

yi is non negative by assumptionPlanetmathPlanetmath, therefore so is the final term, and so


Since n is arbitrary, by taking the limit n, we have that


So yikiA for all iI and therefore {kiA|iI} is the minimal solution. ∎

Title mean hitting time
Canonical name MeanHittingTime
Date of creation 2013-03-22 14:20:12
Last modified on 2013-03-22 14:20:12
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 24
Author CWoo (3771)
Entry type Theorem
Classification msc 60J10
Related topic HittingTime
Defines mean hitting time