1

CTMCs are normally defined with no self loops. That is, when in state $i$, you transition to state $j$ at a rate $Q_{ij}$. You never transition from $i$ to $i$, so we're free to choose $Q_{ii}$ such that the rows of $Q$ sum to zero, so that probability is conserved (as answered here).

But what if we did allow self loops? I'm designing a simulation where each state $j$ provides a score $S_j \geq 0$, where higher scores make it more likely to transition to that state. But I'd also like high scores to make you more likely to stay in that state. So generally I want to start with $Q'_{ij}=S_j$, but then normalize $Q'_{ij}$ to $Q_{ij}$, with rows summing to zero, without discarding $S_i=Q'_{ii}$.

Intuitively, given a CTMC with self loops on state $i$ (taken at rate $S_i$), I want to find an equivalent one without self loops. It seems that a node with a self loop could be replaced by one without, just with lower outgoing rates. But how exactly to do this?

Since I'm simulating this in discrete time steps anyway, I'm able to simply renormalize the probability distribution before I sample it:

$$P_i(t+{\Delta}t) = \frac{P_i(t)+S_i{\Delta}t}{1+{\Delta}t\sum_{j}S_j}$$

But I'm not having any luck writing that same distribution in terms a $Q$ matrix based on $S$ such that

$$ P_j(t+{\Delta}t) = P_j(t)+Q_{ij}{\Delta}t $$ $$ Q_{ij} \propto S_j, \text{ for all } j \neq i $$ $$ \sum_{j}Q_{ij} = 0 $$

tomfelker
  • 21
  • 3
  • I think you misunderstood something. The number $Q_{i i}$ is indeed (related to) the rate of self-transitions. For small $\Delta t$, the probability of remaining in state $i$ is $1 + Q_{i i} \Delta t$. Notice that we must have $Q_{i i} \le 0$ for this to make sense. – Zhen Lin May 13 '21 at 22:29
  • Yes, normalizing it so that $Q_{ii}$ less than zero (and the row sum is zero) is exactly what I'm trying to achieve. The question is basically how to do that while not completely ignoring $S_i$. – tomfelker May 14 '21 at 20:52
  • I would suggest making $1 + Q_{i i} \Delta t$ proportional to $S_i \Delta t$ while making $Q_{i j}$ proportional to $S_j$. I don't understand how you obtain your discretised probability distribution so I won't comment on that. – Zhen Lin May 14 '21 at 22:51

1 Answers1

1

Given a CTMC with self loops, finding the equivalent one without self loops turns out to be really easy - it's just the same CTMC with the self loops removed, and no other changes. In a discrete-time Markov chain, transitioning back to the current state "uses up" a time step, so it's in competition with all the other transitions. But with continuous time, transitioning back to the current state in any given instant has no effect on any subsequent instant (as the current state is the only connection between instants), and there are uncountably many instants, so there's no way a finite self-transition rate can compete with the other transitions.

This is explained in more detail here in theorem 3.3 (page 14).

To get the desired effect, where a high score for the current state makes it more likely to stay in that state, I'm thinking about hanging "safe" states off of each state. If the state's score is high, it'll have a high rate to transition into the associated safe state, whose only outgoing transition will be back to the state it came from at a constant rate, roughly the equivalent of the timestep in a DTMC. Thus, states with a high score would tend to spend a higher fraction of their time in the safe state, insulated from other transitions. If the self-scores and return rate are increased by the same factor, it won't change the equilibrium, but will shorten the dwell times, so in the limit of that factor going to infinity, the effect would be the same as decreasing all the outgoing transition rates by a factor related to the safe state equilibrium.

tomfelker
  • 21
  • 3