# mean hitting time

Let $(X_{n})_{n\geq 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\geq 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:

 $k_{i}^{A}=\begin{cases}0&\qquad i\in A\\ 1+\displaystyle{\sum_{j\in I}p_{ij}k_{j}^{A}}&\qquad i\notin A\end{cases}$

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

###### Proof.

If $i\in A$, then $H^{A}=\inf\{n\geq 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:

 $\displaystyle k_{i}^{A}$ $\displaystyle=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)\quad\textrm{(by the Markov % property)}$ $\displaystyle=\sum_{j\in I}p_{ij}(1+k_{j}^{A})$ $\displaystyle=1+\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

 $\displaystyle y_{i}$ $\displaystyle=1+\sum_{j\in I}p_{ij}y_{j}$ $\displaystyle=1+\sum_{j\notin A}p_{ij}(1+\sum_{k\notin A}p_{jk}y_{k})$ $\displaystyle=1+\sum_{j\notin A}p_{ij}+\sum_{j\notin A}\sum_{k\notin A}p_{ij}p% _{jk}y_{k}$ $\displaystyle=1+q_{1}+q_{2}+\cdots+q_{n}+\sum\cdots\sum p_{ij}\cdots p_{uv}y_{% v},$

where $q_{n}=P(X_{1}\notin A,X_{1}\notin A,\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}\geq 1+q_{1}+q_{2}+\cdots+q_{n}.$

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

 $y_{i}\geq\lim_{n\to\infty}(1+q_{1}+q_{2}+\cdots+q_{n})\geq k_{i}^{A}.$

So $y_{i}\geq k_{i}^{A}$ for all $i\in I$ and therefore $\{k_{i}^{A}|i\in I\}$ is the minimal solution. ∎

Title mean hitting time MeanHittingTime 2013-03-22 14:20:12 2013-03-22 14:20:12 CWoo (3771) CWoo (3771) 24 CWoo (3771) Theorem msc 60J10 HittingTime mean hitting time