0

I am reading the queueing theory volume 1 by Kleinrock. In the chapter on Continuous Time Markov Chain(CTMC), the author defines the infinitesimal generator, $Q(t)$ as having the following elements:

\begin{align} q_{ii}(t) &= \lim_{\Delta t \to 0 } \frac{p_{ii}(t, t+ \Delta t) - 1}{\Delta t} \\ q_{ij}(t) &= \lim_{\Delta t \to 0 } \frac{p_{ij}(t, t+ \Delta t)}{\Delta t} & i &\neq j \end{align}

where $p_{ij}(t, t+ \Delta t)$ is the probability of moving to state j from i in a small interval $\Delta t$.

The author says that - "if the system at time $t$ is in the state $E_i$ then the probability that a transition occurs ( to any state other than $E_i$) during the interval $(t + \Delta t)$ is given by $- q_{ii} \Delta t + o(\Delta t) $. Thus we may say that $-q_{ii}$ is the rate at which the process departs from the state $E_i$ when it in the state."

I am unable to understand how the author arrives at the above interpretation from the limit definition. Can someone please provide clarification or point me to resources where there is an elaborate explanation?

Lee David Chung Lin
  • 7,043
gaganso
  • 217

2 Answers2

1

$P_{ij}(t,t+\Delta t)$ is the probability that the system is on the state $i$ at time $t$ and in the state $j$ at time $t+\Delta t$.
In discrete time MC, it is good enough because the system moves only once at each time step. (including moves to the same state)

However, in continuous time MC, the $P_{ij}(t,t+\Delta t)$ includes that the system moves from $i$ to $k$ and moves to $j$. Between $t$ and $t+\Delta t$ it can go any state as long as it comes back to the state $j$.
And also it doesn't show how long it will stay the current state. we need another variable to show the staying time which should be exponential random.

Therefore, I believe, the rate comes in.
If you compare the limit with the definition of the derivative, you will get the idea.
I don't know why the author uses $p_{ii}-1$ instead of $1-p_{ii}$, though it is just a matter of sign.
$1-p_{ii}$ can be interpreted as the probability to leave the state $i$.
And as $\Delta t$ goes to $0$, the limit becomes the rate (the slope of the probability curve, or the speed of probability change at time $t$) of leaving the current state $i$.

By limiting $\Delta t$ to $0$ we don't need to care about moving out and coming back.

Not sure I made all the statements mathematically correct. This is how I understand the rate (instead of Probability) in CTMC.

S. Phil Kim
  • 645
  • Thank you, Professor – gaganso Apr 13 '19 at 23:47
  • 1
    The sign of the diagonal entries of $q$ is negative for a reason; it is the derivative of $p_i$ when $p_i(t)=1$, so it must decrease as probability flows from $i$ to its neighbors $j$. Eventually it will tend to increase again as probability flows back to it, of course. – Ian Apr 14 '19 at 02:39
  • @Ian, I am sorry I didn't get your comment completely. When you say $p_i(t)$, does it mean the probability of being in state $i$ at time $t$? – gaganso Apr 14 '19 at 15:25
  • @gaganso Yes. This is because $q_{ij}$ is just $\left. \frac{d}{dt} P(X_t=j \mid X_s=j) \right |{t=s}$. So the fact that $q{ii}<0$ is not just convention. – Ian Apr 14 '19 at 16:18
  • @Ian, Got it. Thank you! – gaganso Apr 14 '19 at 16:23
  • (There is an obvious typo in my previous comment...) – Ian Apr 14 '19 at 19:21
1

For discrete state space $S$, note that: $$\sum_{j \in S : j \neq i} q_{ij}$$ is the instantaneous rate that the process departs state $i$, given it is in state $i$. So for small $\delta>0$ we have $$P[X(t+\delta) = i|X(t)=i] \approx 1-\sum_{j \in S : j \neq i}q_{ij} \delta$$ So $$\frac{P[X(t+\delta)=i|X(t)=i] - 1}{\delta} \approx -\sum_{j \in S : j \neq i}q_{ij}$$ and this approximation becomes exact as $\delta\rightarrow 0$.

Michael
  • 23,905
  • 1
    Note that for small $\delta>0$, we can safely assume there is either no transition in a time interval of size $\delta$, or exactly 1 transition. The probability of 2 or more transitions is negligible. – Michael Apr 13 '19 at 23:09
  • 1
    Note that you can view $q_{ii}$ as being defined as $q_{ii} := -\sum_{j \in S : j \neq i} q_{ij}$. – Michael Apr 13 '19 at 23:11
  • Thank you, Professor. – gaganso Apr 13 '19 at 23:43