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.

| cite | improve this answer | |
  • $\begingroup$ Thank you so much. Could you point me to some paper which deals with the calculation of expected hitting time? $\endgroup$ – Bravo Feb 5 '13 at 15:31

This circle of questions is known as first passage percolation. There's an extensive literature on the subject.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Bravo Feb 4 '13 at 17:07
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Feb 4 '13 at 19:28
  • $\begingroup$ 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. $\endgroup$ – Ori Gurel-Gurevich Feb 4 '13 at 19:45
  • $\begingroup$ Oops... didn't see the $\mu_i$'s... $\endgroup$ – Anthony Quas Feb 4 '13 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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