## You are here

Homemean hitting time

## Primary tabs

# 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 chain to first reach a state in $A$.

Define the *mean hitting time* of $A$ given the chain 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&i\in A\\ 1+\displaystyle{\sum_{{j\in I}}p_{{ij}}k_{j}^{A}}&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 chain 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}$ |

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. ∎

## Mathematics Subject Classification

60J10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Summation Sign

How do I get the j \in I to appear under the summation sign rather than to the right? I can't seem to get it to move.

Cheers

## Re: Summation Sign

$$ \sum_{j \in I} $$ will do the trick.

But I'm not sure if \[ \sum_{j \in I} \] will work.

What is the difference, if someone knows?

## Re: Summation Sign

the difference is that \[ \] is better and $$ is evil (due to spacing handling).

Go br.endernet.org/~drini/TeX and get Sins of LaTeX2e to see what I'm talking about. I think there's a copy somewhere on CTAN too

Now to grandparent post: if you want the j\in I to show up below while the summation sign being inside a paragraph (instead of isolated centered equation) then please don't

(it will mess up interline space (might not be noticeable in HTML mode but it does in others) and make things look really ugly).

If you don't believe me, go for any calculus book and see how often to they use j\in I BELOW the summation and INSIDE a paragraph

f

G -----> H G

p \ /_ ----- ~ f(G)

\ / f ker f

G/ker f

## Re: Summation Sign

I'm trying to use it inside the array environment, to let me define a function in 2 cases, one of which includes a summation. I've made the entry public editable, so if someone can get it to work that would be great.

## Re: Summation Sign

I can fix it, but... which entry?

f

G -----> H G

p \ /_ ----- ~ f(G)

\ / f ker f

G/ker f

## PM.ORG Improvement WAS: Summation Sign

Oh it's mean hitting time

when one follows a post on htemain page

and such post comes from some encyclopedia article

there's no way to know which article it came from

since nor [up] link nor [top] will open the entry

f

G -----> H G

p \ /_ ----- ~ f(G)

\ / f ker f

G/ker f

## Re: PM.ORG Improvement WAS: Summation Sign

Thanks for doing that. The cases environment looks useful.

To get to the parent article from the main page, can't you just click the little planet by the post on the main page? Or when you're reading the message click the red up arrow? Both seem to work for me.

## Re: PM.ORG Improvement WAS: Summation Sign

ah ok, the little red arrow works when reading posts. It's just not so intuitive as the links BELOW the actual post

f

G -----> H G

p \ /_ ----- ~ f(G)

\ / f ker f

G/ker f

## Help with Formatting

Hi,

I'm trying to get a part of the proof to display right, but I just can't get it all aligned. I've commented it out, but would be grateful if someone could fix it for me and explain why it didn't work. (Its in mean hitting time if you're reading from the front page).

I've got a similar thing to do later in the proof, but I'll do that once I can see what I need to do differently.

Cheers

## Re: Help with Formatting

> Hi,

> I'm trying to get a part of the proof to display right, but

> I just can't get it all aligned. I've commented it out, but

> would be grateful if someone could fix it for me and explain

> why it didn't work. (Its in mean hitting time if you're

> reading from the front page).

What I can do is tell you what you seem to be doing wrong.

You must not put $...$'s inside an `align' environment, its

contents are already in math mode. Also, put a \quad between

any math and following text. And put \usepackage{amsthm} in

your preamble so you can use the `proof' environment

instead of \subsection{proof}. When you're not sure how to

make something look right, try checking the PM Content and Style

guide, it's liked to right above the editing box of the entry.

Finally, check your grammar. You have some slip ups with

subject-verb agreement in number.

Hope this helps.

## Re: Help with Formatting

Cheers. I had tried it without $'s too, but I've now found my problem. I had accidentally typed \Sum instead of \sum. I've made the entry non world readable while i finish the proof.