Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Within a queue with capacity = K death rate is μ and birth rate λ.

A packet is discarded when the queue is full with probability Pk=P(K elements in the queue)

Moreover there's a probability $p1 > 0$ that a packet is discarded at arrival.

What are the transition probabilities ?

My guess is that with

  • $Λ = \frac{λ(1 - p1)}{λ(1 - p1)+μ}$
  • $Μ = \frac{μ}{λ(1 - p1)+μ}$

the transition table is

State              n             n-1              n+1

  n = 0           1-Λ             0                Λ

  n >= 1         1-M-Λ            M                Λ

  n = K           1-M             M                0    

is this correct ?

Do i have to consider the conditioned probability $P(\frac{λ}{λ+μ} | 1-p1)$ instead (if not, why) ?

share|cite|improve this question
Two questions. What happened to $S_0$? If $p_1=0$ shouldn't you get the normal birth death process? – deinst Feb 23 '12 at 2:47
I've updated the transition table. If p1 = 0 it's a plain birth death process indeed. Assume p1 > 0. – gpilotino Feb 23 '12 at 8:16
What is $\mu p_1$ if $p_1$ is 0? – deinst Feb 23 '12 at 13:50
good point. i've updated the table according. you can put hints in answer instead of comments if you want some upvote. – gpilotino Feb 24 '12 at 9:22
This can't be right; suppose $\lambda = 10$ and $p_1 = 1/2$. Then your table would say that the probability of a transition from state 0 to $n+1$ is 5. Probabilities bigger than 1 (or less than 0) don't make sense. Are you really asking about transition probabilities or transition rates? – Nate Eldredge Feb 25 '12 at 14:05
up vote 2 down vote accepted

If I understand your problem hypotheses correctly, it is a modification of an M/M/1/K queueing system. What do I mean with this? It is a specific continuous-time Markov process on the state space $\{0,1,\dots,K\}$, whose transition rates are specified by a certain generator matrix $Q$. Being in state $n$ means that there are $n$ packets in the systems and the oldest of them is currently being served/processed.

Why the name M/M/1/K? The first M stands for memoryless arrival times for the packets (thus described by a Poisson process), the second M stands for memoryless service times (i.e. exponentially distributed), the number 1 means that there is only one server handling the packets and the number K is the maximum size of the queue (above which the new arriving packets are simply rejected).

The modification comes from the fact that you have a certain probability $p_1$ of rejecting a new packet, but it is well know that the probabilistic thinning (with probability $p$) of a Poisson process with rate $\lambda$ is again a Poisson process with rate $\lambda p$. Therefore, in our case, the arrival process is Poisson with rate $(1-p_1)\lambda$.

With these assumptions, the transition rates of this process are

  • $q_{0,1}=(1-p_1)\lambda$,

  • $q_{n,n+1}=(1-p_1) \lambda$ and $q_{n,n-1}=\mu$ for $1 \leq n \leq K-1$,

  • $q_{K,K-1}=\mu$.

Usually the diagonal elements of the generator matrix $Q$ are set such that every row sums to zero.

One can then uniformize the process, in order to get a discrete-time Markov chain: this can be done simply by defining its probability transition matrix as $P= Q / q^*+I$, where $q^*:=\max_i |q_{i,i}|$. Otherwise one can simply compute from the generator Q the probabilities of going back or forth, given that a jump has occurred, i.e. the matrix $\hat{P}$, obtained by dividing each row of $Q$ by the opposite of its diagonal element.

The only differences that I see between this model and yours is that you do not assume the whole system to be Markovian (or was this implicit?) and the fact that apparently in your model packets are not always rejected when the queue is full (i.e. $K$), but they are accepted with probability $1-p_K$ (but where do you put them, if the capacity is only $K$?).

share|cite|improve this answer
I get the whole part about poisson process (system is markovian indeed) and transition rates (probability Pk is used just to evalutate the mean birth rate = λ(1-Pk) disregarding p1) . I'm a little bit lost about the probability transition matrix calculation. Can you please make an example ie. from n to n+1 ? – gpilotino Feb 26 '12 at 20:13
From the matrix $Q$ you can compute two different things: 1) the transition matrix of the uniformized process $P=Q/q^*+I$ or 2) the matrix $\hat{P}$ of the transition probabilities. They are describing the same process in two different ways: the matrix $P$ tells you the transition probabilities every time an exponential clock with rate $q^*$ rings, while the matrix $\hat{P}$ tells you the transition probabilities, given that a jumps has occured. – alezok Feb 26 '12 at 21:11
For $1 \leq n \leq K-1$, one has that $\hat{p}_{n,n+1}=p_{n,n+1}=\frac{(1-p_1)\lambda}{(1-p_1)\lambda + \mu}$ and $\hat{p}_{n,n-1}=p_{n,n-1}=\frac{\mu}{(1-p_1)\lambda + \mu}$, since $q^*=(1-p_1)\lambda + \mu$. On the other hand one has that $p_{0,1}\neq \hat{p}_{0,1}$ and $p_{K,K-1}\neq \hat{p}_{K,K-1}$ – alezok Feb 26 '12 at 21:15
thank you, clearer now. that said, my table above is correct then ? :) – gpilotino Feb 26 '12 at 23:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.