# First hit time in a graph setting

I considered the problem of a form of CTMC evolving in a graph:

Consider a graph of $G(V,E)$ with $|V|=N$ nodes. Each node has a 1-0 CTMC associated with it:

• There is a vertex dependent rate $\mu_i$ such that node $i$ moves from 1 to 0 at a Poisson rate $\mu_i$.
• There is an edge-dependent Poisson rate $\lambda_{ij}$ along the edge $e(i,j)\in E$ which takes $j$ from 0 to 1 whenever node $i$ is in state 1.
• As long as node $j$ is in state 1, its neighbours in state 0 could each move to state 1 at a Poisson rate of $\lambda_{jk}$ where $k$ is one of the neighbours of $j$. A node in state 0 cannot influence the states of its neighbouring nodes.
• If node $j$ is in state 0, and nodes $i$ and $k$ are its neighbours in state 1, the probabilities of $i$ changing $j$'s state and of $k$ changing $j$'s state are mutually exclusive.

In such a setting, if $X(0)$ represents the set of nodes in state 1 at time 0 and $T_j$ the random variable of the first time when $j$ moves into state 1, how do we determine $E(T_j|X(0)=\{i\})$?

Could someone provide me with relevant literature pertaining to such problems?

This model (at least when all the $\lambda_{ij}$ are the same and all the $\mu_i$ are the same) is called the Contact Process.
• Thanks Anthony. I did look into percolation problems which had a similar structure with the $\lambda$s on the edges, but the concept of nodes going from 1 to 0 at $\mu$s seemed to be absent in that formulation. Could you please lead me to a more specific setting? – Bravo Feb 4 '13 at 17:07
• Your setting just is exactly a reformulation of first passage percolation (not just percolation). If the graph has a regular structure (like $\mathbb Z^d$), lots of asymptotic information is known about the expected hitting time. If you just want a number for a less regular graph, I've no idea about how to actually compute the hitting time, other than brute force. You might also look up the Richardson model. – Anthony Quas Feb 4 '13 at 19:28
• First passage percolation is when $\mu_i=0$, i.e. when there's no 1 to 0 transition. The process described in the question is called the contact process. – Ori Gurel-Gurevich Feb 4 '13 at 19:45
• Oops... didn't see the $\mu_i$'s... – Anthony Quas Feb 4 '13 at 20:03