Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a reversible markov chain $X_t$ defined on a square lattice, with transition probabilities defined between adjacent vertices. Take a square subset of the lattice and call it $V$. Let $dV$ be the set of vertices attached by incoming edges into $V$, ie the hair around the square. Let $\tau$ be the first time that X hits a vertex in $dV$. Suppose I start $X$ at a point $x$ in $dV$ and condition it to enter $V$ on the next step. What can one say about the joint probability that $\tau=n$ and $X_\tau=y$? In particular, are there good references for this somewhere? I believe the proper term for this is "first return time" yet a google search gives ambiguous results. Thanks!!

share|cite|improve this question
up vote 1 down vote accepted

To start at $x$ in $dV$ and to condition to enter $V$ on the next step is equivalent to assuming that one starts from the unique vertex in $V$ which is a neighbor of $x$. Hence from now on I will assume that the Markov chain starts from a vertex in $V$. Of course, the case which interests you is when this vertex has a neighbor in $dV$ but I will not need this hypothesis. Likewise the structure of the graph has no relevance so I consider a general Markov chain, with transition probability kernel $p(\cdot,\cdot)$.

For every $n\ge1$, $x$ in $V$ and $y$ in $dV$, call $h_n(x,y)$ the probability that $X_\tau=y$ and $\tau=n$ when the Markov chain starts from $x$. Then, $h_1(x,y)=p(x,y)$ and the Markov property of the Markov chain at time $1$ yields that, for every $n\ge1$, $$ h_{n+1}(x,y)=\sum_{z\in V}p(x,z)h_n(z,y). $$ One can also encode the whole sequence $(h_n(x,y))_n$ through a single function $H_{x,y}$, as $$ H_{x,y}(s)=\sum_{n\ge1}h_n(x,y)s^n. $$ Then, the recursions given above are equivalent to the relations $$ H_{x,y}(s)=sp(x,y)+s\sum_{z\in V}p(x,z)H_{z,y}(s). $$ Finally, for every $n\ge1$, $$ h_n(x,y)=\sum_cp(c), $$ where the sum over $c$ enumerates the paths $c$ of length $n$ which start from $x$ and stay in $V$ until their endpoint $y$, and $p(c)$ is the product of the transition probabilities from one vertex of $c$ to the next one.

As already said somewhere else, one these matters one could do worse than read the beautiful small book Random Walks and Electric Networks by Peter G. Doyle and J. Laurie Snell, which explains this and a lot of related stuff in a very accessible way.

share|cite|improve this answer
I am a bit confused by your recurrence relation. It does not take into account hitting the boundary stops the process. I would think that your z sum must run over vertices not in dV. Moreover the transition probability for vertices bordering the boundary should be renormalized because you are conditioning to not hit a vertex on the boundary other than y. I'm presuming your p is therefor defined only on V? – SKS May 1 '11 at 19:13
@Sam: Thanks for the imput, I think the modified version holds water. – Did May 1 '11 at 20:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.