1
$\begingroup$

I'm trying to model an irreversible, discrete Markov process. I have a set of states $S$ arranged in a tree-like structure (it is only possible to move from parent vertex to child vertex). I compute the transition rates of parent-to-child arcs (the transition rates are assumed to parametrize exponential random variables characterizing the time to transition), and I aggregate the transition rates in an upper-triangular, weighted Laplacian matrix $L$.

From what I understand, the weighted Laplacian $L$ is the transition rate matrix (infinitesimal generator) describing the rate a continuous Markov chain will transition between states. Based on this question, to simulate from the transition rate matrix, it seems that I need the transition probability matrix (a stochastic matrix).

How might I simulate trajectories from the transition rate matrix given in $L$? Since my process is irreversible, must I take into account the exponential distribution of transition times, or is there an alternative way to "convert" $L$ to a transition probability matrix?

$\endgroup$
2
$\begingroup$

The simplest way is this (it does not require the structure of a tree). Assume: \begin{align} S &= \mbox{State space}\\ (q_{ij}) &= \mbox{transition rates} \\ v_i &= \sum_{j \in S: j \neq i} q_{ij} \end{align}

  • When you enter a new state $i$, independently generate an exponentially distributed random variable $T_i$ with parameter $v_i$. The time $T_i$ is the time you stay in state $i$.

  • After time $T_i$, independently transition to a new state $j \in S$ according to transition probabilities: $$ P_{ij} = \left\{\begin{array}{ll} \frac{q_{ij}}{v_i} \quad & \mbox{ if $j \neq i$}\\ 0 & \mbox{ if $i=j$}\end{array}\right. $$ Notice that these probabilities indeed sum to 1: $\sum_{j\in S}P_{ij} = 1$.

$\endgroup$
  • $\begingroup$ essentially Gillespie? $\endgroup$ – jjjjjj May 20 at 21:02
  • $\begingroup$ I do not know what "essentially Gillespie" means. $\endgroup$ – Michael May 20 at 21:05
  • $\begingroup$ Sorry, basically this is the Gillespie algorithm? $\endgroup$ – jjjjjj May 20 at 21:05
  • $\begingroup$ I have not heard that term before. Yet, if you already know some algorithm, what was the point of your question? $\endgroup$ – Michael May 20 at 21:06
  • $\begingroup$ A related method of "uniformization" allows for self-transitions with rates $q_{ii}\geq 0$ and treats $v_i=v$ for all $i \in S$ (constant) where $q_{ii}$ is simply chosen to impose this constant condition. The advantage of such uniformization is that if you skip the generation of the exponential variables $T_i$ and just stay in each state for one unit of time, then the steady state in this "embedded discrete time chain" is the same as the true steady state. $\endgroup$ – Michael May 20 at 21:06

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.