2
$\begingroup$

I have a question regarding markov chains in continuous time.

I have a birth/death process(for every step we go 1 up & or 1 down), queue with 4 states. Customers arrive with the intensity of lambda per hour and can be seen as poisson distributed. The time to serve each customer can be seen as exponentially distributed and independent.

We start at time = 0 and state = 0. We are going to do 100 steps.

State 0 => There is no customers. (Arrival rate = 2, Departure rate = 0)

State 1 => There is one customer being served. (Arrival rate = 2, Departure rate = 10)

State 2 => There is one customer being served + 1 in queue. (Arrival rate = 2, Departure rate = 10)

State 3 => There is one customer being served + 2 in queue. (Arrival rate = 0, Departure rate = 10)

Givens: Arrival rate = 2. Depature rate = 10.

Is there a formula to calculate the total time spent in each state?

$\endgroup$
8
  • 2
    $\begingroup$ What do you mean exactly when you say "with 4 states"? Can there be only three people queued up at a time, so that the states are $0,1,2,3$? Anyway, in the long run the total time spent in each state is proportional to the total time that you have been running the chain multiplied by the probability of that state under the invariant distribution. You can compute the invariant distribution by looking for the normalized solution to $pL=0$ where $p$ is a row vector and $L$ is the generator matrix. $\endgroup$
    – Ian
    Aug 2, 2016 at 20:06
  • $\begingroup$ Ah, ill clarify what i mean with the states. State 0 => There is no customers. State 1 => There is one customer being served. State 2 => There is one customer being served + 1 in queue. State 3 => There is one customer being served + 2 in queue. $\endgroup$ Aug 2, 2016 at 20:25
  • 2
    $\begingroup$ You did not say what happens to customers arriving while there are one customer being served and two already in the queue. Once this will be made clear, simply follow @Ian's indications. $\endgroup$
    – Did
    Aug 2, 2016 at 20:38
  • $\begingroup$ The arrival time will be 2 in every state, except for in state 3(when 2 are in queue). What i find hard to see is to find the "probability of that state". Can any1 show me how that is done? With the given information. $\endgroup$ Aug 2, 2016 at 20:41
  • 1
    $\begingroup$ @Math1000 Thus: the point in my comment? Cool. $\endgroup$
    – Did
    Aug 3, 2016 at 6:51

1 Answer 1

1
$\begingroup$

Under the assumption that arriving customers are turned away when there are three customers in the system, this is a $M/M/1/3$ queue, that is, a single-server queueing system with arrival process Poisson, i.i.d. exponentially distributed service times, and a finite buffer size of $3$. Let $X(t)$ be the number of customers in the system at time $t$. Then $X=\{X(t):t\in\mathbb R_+\}$ is a continuous-time Markov chain with state space $S = \{0,1,2,3\}$ and transition rates $$ q_{ij} = \begin{cases} 2,& j=i+1\\ 10,& j=i-1\\ 0,& \text{otherwise}. \end{cases} $$ Let $P(t)$ be the matrix with entries $$[P(t)_{ij}] = \mathbb P(X(t) = j\mid X(0) = i).$$ Then $P$ satisfies the forward Kolmogorov equation $$P'(t) = P(t)Q(t), $$ with solution given by the matrix exponential $$P(t) = e^{tQ}.$$ (This may be verified by the Chapman-Kolmogorov equation $P(s+t) = P(s)P(t)$.) Since each row of $P(t)$ sums to $1$ (as it is a stochastic matrix), it follows that each row of $Q$ sums to $0$. The nondiagonal entries of $Q$ are precisely the transition rates $q_{ij}$, so the diagonal entries satisfy $$q_{ii} = -\sum_{j\in S\setminus\{i\}}q_{ij}. $$ Hence, $$ Q = \begin{pmatrix} -2 & 2 & 0 & 0\\ 10 & -12 & 2 & 0\\ 0 & 10 & -12 & 2\\ 0 & 0 & 10 & -10. \end{pmatrix} $$ If $\pi$ is a probability distribution on $S$, let $\{X_\pi(t):t\in\mathbb R_+\}$ denote the process $X$ conditioned on $X(0)\sim\pi$. If $X_\pi(t)$ is a stationary process, that is, $\{X_\pi(s+t):t\in\mathbb R_+\}\stackrel d=\{X_\pi(t):t\in\mathbb R_+\}$ for all $s\geqslant 0$, then $\pi$ is a stationary distribution. From the balance equations $$\sum_{j\in S\setminus\{ i\}} \pi_{i}q_{ij} = \sum_{j\in S\setminus\{ i\}} \pi_{j}q_{ji},$$ it can be verified that $\pi$ is a stationary distribution iff $\pi Q=0$. In this example, $\pi Q=0$ is the system of linear equations \begin{align} -2\pi_0 + 10\pi_1 &= 0\\ 2\pi_0 -12\pi_1 + 10\pi_2 &= 0\\ 2\pi_1 -12\pi_2 + 10\pi_3 &= 0\\ 2\pi_2 -10\pi_3 &= 0 \end{align}. These equations, along with $\sum_{i\in S}\pi_i = 1$ (since $\pi$ is a probability distribution), yield $$\pi = \begin{pmatrix}\dfrac{125}{156}& \dfrac{25}{156}& \dfrac{5}{156}& \dfrac1{156} \end{pmatrix}. $$ The fraction of time spent in each state satisfies $$\lim_{T\to\infty}\frac1T \int_0^T \mathsf 1_{\{X(t)=i\}}\,\mathsf dt = \pi(i).$$

This serves as a good approximation for the fraction of time spent in a state for large $t$, but computing the exact value of $\int_0^T \mathsf 1_{\{X(t)=i\}}\,\mathsf dt$ for a given $T$ is non-trivial and (especially for larger problems) is generally done by simulation.

$\endgroup$
3
  • $\begingroup$ I think you transcribed $\pi Q = 0$ into separate equations incorrectly, and I think your solution isn't right as well: when I solve it I get roughly $\pi=\begin{pmatrix} 0.8 & 0.16 & 0.032 & 0.008 \end{pmatrix}$. $\endgroup$
    – Ian
    Aug 3, 2016 at 1:08
  • $\begingroup$ @Ian The equations are correct; the solution not, due to a typo. I recall now the solution should be $$\pi_i = \frac{\rho^{c-i}}{\sum_{j=1}^c \rho^j},$$ where $\rho=\frac\lambda\mu$. $\endgroup$
    – Math1000
    Aug 3, 2016 at 1:22
  • 1
    $\begingroup$ Oh, yes, the equations are correct, I forgot to read down columns rather than across rows. $\endgroup$
    – Ian
    Aug 3, 2016 at 1:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .