# time between transitions in continous time discrete state Markov process

Problem Statement:

I want to compute the time between transitions in a birth-death model. As a simple example, consider that individuals are born with rate $$\lambda$$ and they die at rate $$\sigma n$$. The master equation for the number $$n$$ of individuals is $$\frac{d}{dt}P_n(t) = \lambda P_{n-1}(t) + \sigma (n+1) P_{n+1}(t) - (\lambda + \sigma n)P_n(t).$$

In steady state, the solution is a Poisson distribution: $$P_n = \frac{(\lambda/\sigma)^n}{n!}e^{-\lambda/\sigma}.$$

My target is the time between successive births, deaths, or transitions of any kind. How can I compute this?

Attempt:

First I'll try to get the distribution of waiting times between successive births. Consider that a birth has just occurred at $$t=0$$. Then defining $$F_n(t)$$ as the probability that there are $$n$$ individuals and no birth has occurred since $$t=0$$, one can write the master equation

$$F_n(t+\delta t) =\sigma (n+1)\delta t F_{n+1}(t) + [1-(\lambda + \sigma n)\delta t]F_n(t)$$ The first term represents death occurring in $$\delta t$$. The second term represents nothing occurring in $$\delta t$$. As $$\delta t \rightarrow 0$$, $$\frac{d}{dt}F_n(t) = \sigma(n+1)F_{n+1}(t)-(\lambda + \sigma n)F_n(t)$$

This should be the master equation for the probability distribution I'm looking for. Introducing a generating function $$H(z,t) = \sum_{n=0}^\infty z^n F_n(t)$$ leads to the differential equation $$\frac{\partial H}{\partial t} + \sigma (z-1)\frac{\partial H}{\partial z} = -\lambda H.$$ Using the method of characteristics implies the solution $$H(z,t) = [1-e^{\sigma t}(1-z)]e^{-\frac{\lambda}{\sigma}e^{\sigma t}(1-z)-\lambda t}.$$ Crucially, the initial condition is $$H(z,0)=\sum_{n=0}^{\infty} z^n F_n(0) = \kappa \lambda \sum z^n P_{n-1} = \kappa \lambda z e^{\lambda(z-1)\sigma}.$$ $$\kappa$$ is a normalization factor. This point I don't fully understand. The initial condition is intended to indicate a birth transition just occurred at $$t=0$$.

Incorporating the normalization $$H(1,0)=1$$ sets $$\kappa = 1/\lambda,$$ so $$H(z,0) = z e^{-\lambda(z-1)/\sigma}.$$

The probability that no birth occurs from any state in time $$t$$ is then the sum over all possible states $$n$$: $$\sum_{n=0}^\infty F_n$$. The pdf is $$f_T(t) = -\frac{d}{dt} \sum_{n=0}^\infty F_n$$. Summing every difference equation for $$F_n$$ gives this quantity as

$$f_T(t) = \lambda \sum_{n=0}^\infty F_n(t).$$

Using the generating function $$H(z,t)$$, this can be written as $$f_T(t) = \lambda \sum_{n} z^n F_n(t) |_{z=1} = \lambda H(1,t) = \lambda e^{-\lambda t}.$$

So there's the distribution of time between births. It's the same as the distribution of time for one birth, given there were initially no individuals at $$t=0$$.

• It sounds like if you are in state $n\in \{1, 2, 3, ...\}$ you have an upgoing arrow of rate $\lambda$ and downgoing arrow of rate $\sigma n$. So the time to remain in that state is exponentially distributed with rate $\lambda + \sigma n$. The expected time in that state is $1/(\lambda + \sigma n)$. – Michael Dec 30 '18 at 1:16
• This is just the definition of that type of Continuous Time Markov Chain (CTMC). We go from one state to the next according to arrows labeled with transition rates. It is not clear what you want to derive. – Michael Dec 30 '18 at 1:18
• Are you asking about the time to get to state $n+1$, given we are in state $n$? Clearly the time to go from 0 to 1 is exponential with rate $\lambda$ but the time to go from 1 to 2 is not obvious (since we might transition back to state 0 first). It is certainly not exponential with rate $\lambda$. – Michael Dec 30 '18 at 1:43
• Let $E[T_i]$ be the average time to get to state 2 give we start in state $i$. Then $$E[T_2]=0, E[T_0] = 1/\lambda + E[T_1], E[T_1] = 1/(\lambda + \sigma) + \frac{\sigma}{\lambda+\sigma}E[T_0]$$ You can solve for $E[T_0]$ to find $E[T_0] \neq 1/\lambda$. – Michael Dec 30 '18 at 1:52
• I understand and agree with your derivation of F_n(t) (except for a minor typo where a term should be multiplied by dt). However I don’t know how it relates to the question of interest. I also think I disagree with your P_n(t) equation, depending on your def of P_n(t) it may need three terms on right hand side. – Michael Dec 30 '18 at 2:18

## 1 Answer

You are describing an M/M/$$\infty$$ queue with arrival rate $$\lambda$$ and server rate $$\sigma$$.

The arrival process is Poisson with rate $$\lambda$$, so inter-arrival times are iid exponential with rate $$\lambda$$.

The system is reversible, so if we start out in the steady state distribution $$P[N(0)=k] =\frac{(\lambda/\sigma)^k}{k!}e^{-\lambda/\sigma}$$ for all nonnegative integers $$k$$ then the departure process is Poisson with rate $$\lambda$$, so inter-departure times are iid exponential with rate $$\lambda$$.

Edit: For any stable queue we must have the long term arrival rate equals the long term departure rate:

$$\lim_{t\rightarrow\infty}\frac{arrive[0,t]}{t}=\lim_{t\rightarrow\infty}\frac{depart[0,t]}{t}$$

where $$arrive[0,t]$$ is the total number of arrivals during the interval $$[0,t]$$, and $$depart[0,t]$$ is the total number of departures during that time. Since the long term arrival rate is $$\lambda$$, the long term departure rate is also $$\lambda$$. Indeed, if not, then the queue would either be creating new jobs, or eating existing jobs.

The fact that inter-departure times are (in steady state) iid exponential is not obvious and comes from the detail equation reversible properties (which hold for every birth-death chain that is stable). It is not true if we do not start in steady state. Assuming initial steady state, your calculations could verify the marginal inter-departure time is exponential. However (assuming initial steady state) it further holds that each inter-departure time is independent of all prior ones.

The inter-event time is more complicated. In fact, even if we start in steady state, the first event is more likely to be an arrival, rather than a departure:

$$\sum_{k=0}^{\infty} \left(\frac{\lambda}{\lambda + k\sigma}\right) \frac{(\lambda/\sigma)^k}{k!}e^{-\lambda/\sigma} > 1/2$$ The inter-event times are not identically distributed. An arrival sees the system in steady state (and then adds 1 to that) while a departure leaves the system in steady state. So the expected time to the next event, given we just had an arrival, is less than the expected time to the next event, given we just had a departure.

The fact that Poisson Arrivals See Time Averages is often called PASTA.

• Thanks @Michael, I just replicated my earlier analysis for time between death events and found the interdeparture times, like the interarrival times, were exponential with rate $\lambda$. This is confusing to me. Can you comment on the reversible attribute? I expected interdeparture times exponential with rate related to $\sigma$. Why is it controlled by $\lambda$? – kevinkayaks Dec 30 '18 at 5:24
• And what would be expected for the distribution of intervals between any two transitions? – kevinkayaks Dec 30 '18 at 5:26
• I added some to my answer. – Michael Dec 30 '18 at 13:37
• Thanks @Michael -- wish I could upvote twice. The reversible statement makes sense now. Your statement about inter-event times is very helpful. Previously, I derived a distribution and found it had inconsistent attributes. You made me see the problem is that I assumed independence. I think I should read more of a queueing theory perspective on birth-death processes. Do you have a favorite book? – kevinkayaks Dec 31 '18 at 23:46
• Thanks. I had not thought about "inter-event" times before in this context, and I had an initial misconception before I thought about it more. A free book download is Bertsekas and Gallager, chapter 3 has queueing: web.mit.edu/dimitrib/www/datanets.html – Michael Jan 1 at 14:58