mean hitting time

Let ${(X_n)}_{n\ge 0}$ be a Markov chain with transition probabilities $p_{ij}$ where $i,j$ are states in an indexing set $I$. Let $H^A$ be the hitting time of ${(X_n)}_{n\ge 0}$ for a subset $A\subseteq I$. That is, $H^A$ is the random variable 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

$$k_i^A:=E(H^A|X_0=i).$$

Proposition 1.

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

Remark. In this case, a solution is minimal if for any non negative solution $\{y_i|i\in I\}$ we have $y_i\ge k_i^A$ for all $i\in I$.

Proof.

If $i\in A$, then $H^A=inf\{n\ge 0\mid X_n\in A\}\equiv 0$, which means $k_i^A=0$ (the is certain to be in a state in $A$ at step $n=0$).

If $i\notin A$ we condition on the first step:

$k_i^A$$=E(H^A\mid X_0=i)$

$={\displaystyle \sum _{j\in I}}P(X_1=j|X_0=i)E(H^A|X_0=i,X_1=j)$

$={\displaystyle \sum _{j\in I}}{p}_{ij}E(H^A|X_1=j)\mathit{\hspace{1em}}\text{(by the Markov property)}$

$={\displaystyle \sum _{j\in I}}{p}_{ij}(1+k_j^A)$

$=1+{\displaystyle \sum _{j\in I}}{p}_{ij}{k}_j^A$

So the $k_i^A$ satisfy the given equations.

Now suppose that $\{y_i|y\in I\}$ is any non-negative solution to the equations. Then for $i\in A$ we have $k_i^A=y_i=0$. If $i\notin A$, then

$y_i$$=1+{\displaystyle \sum _{j\in I}}{p}_{ij}{y}_j$

$=1+{\displaystyle \sum _{j\notin A}}{p}_{ij}(1+{\displaystyle \sum _{k\notin A}}{p}_{jk}{y}_k)$

$=1+{\displaystyle \sum _{j\notin A}}{p}_{ij}+{\displaystyle \sum _{j\notin A}}{\displaystyle \sum _{k\notin A}}{p}_{ij}{p}_{jk}{y}_k$

$=1+q_1+q_2+\mathrm{\cdots }+q_n+{\displaystyle \sum \mathrm{\cdots }\sum p_{ij}\mathrm{\cdots }{p}_{uv}{y}_v},$

where $q_n=P(X_1\notin A,X_1\notin A,\mathrm{\cdots },X_n\notin A|X_0=i)$ is the probability that the chain $X$ does not enter $A$ in the first $n$ steps after the initial state $i$.

$y_i$ is non negative by assumption, therefore so is the final term, and so

$$y_i\ge 1+q_1+q_2+\mathrm{\cdots }+q_n.$$

Since $n$ is arbitrary, by taking the limit $n\to \mathrm{\infty }$, we have that

$$y_i\ge \underset{n\to \mathrm{\infty }}{lim}(1+q_1+q_2+\mathrm{\cdots }+q_n)\ge k_i^A.$$

So $y_i\ge k_i^A$ for all $i\in I$ and therefore $\{k_i^A|i\in I\}$ is the minimal solution.∎