Take the 2-minute tour ×

following is my problem:

Pulses arrive at a processor according to a Poisson process of rate λ. Suppose each arriving pulse that is processed by the processor locks the processor for a fixed time T, so that pulses arriving during the locked period are not processed, and pulses arriving after the locked period are possible to be processed subject to the same locking rule by the following processed pulses.

Let $X (t)$ be the number of all pulses having been (being) processed up to time $t$. Then try to compute:

  1. $P (X (t) ≥ n+1)$ for $t ≥ nT$. Can we also compute the distribution of $X(t)$?
  2. the distribution of the inter-arrival time between every two processed pulses.
  3. the probability that the processor is free at an arbitrarily given time $t > 0$.

The farthest I can imagine is that $X$ seems to be a renewal process (although not sure how to show that), and I don't know how to go further.

Also any reference that might be helpful?

Thanks in advance!


As Stijn commented, this a M/D/1 queue, which I have not learned yet and can't find answers to my questions in the file he linked. Can someone give more clues?

share|improve this question
Isn't this a M/D/1 queue? There is ample literature on the properties of this queue. See, for instance, win.tue.nl/~iadan/queueing.pdf –  Stijn Apr 24 '11 at 21:36
If you've never heard about queues then it might not be smart to put much effort into it. However, chapters 2 to 4 might be of interest to you. –  Stijn Apr 25 '11 at 13:33
@Stijn: Thanks! I was wondering which concept(s) addresses the probability that the processor is free at an arbitrarily given time in the pdf file? Is it "3.2 occupation rate", "4.6 Busy period" or ...? –  steveO Apr 25 '11 at 13:40
you should be looking for $L_q$, the number of users waiting in a queue. There are derivations of $P(L_q = n)$ but I'm not sure whether they only look at stationary distributions or not... –  Stijn Apr 25 '11 at 14:59
@Stijn: Thanks! I am confused. How is Lq, the number of users waiting in a queue, related to the probability that the processor is free at an arbitrarily given time? –  steveO Apr 25 '11 at 15:58

1 Answer 1

Let $u_n(t) = P(X(t) \ge n)$, where the process starts at $t=0$. Condition on the time $Y$ of the first arriving pulse, which will be processed. Since there is a delay of time $T$ before another pulse can be processed, $P(X(t) \ge n | Y = y) = P(X(t - y - T) \ge n-1)$ (and 0 if $t - y - T \le (n-1) T$). Thus $u_n(t) = \int_0^{t-nT} \lambda \exp(-\lambda y) u_{n-1}(t-y-T)\, dy$. I get $u_n(t) = 1 - q_n(t-nT) \exp(-\lambda (t-nT))$ where $q_n(s) = \sum_{j=0}^{n-1} (\lambda s)^j/j!$.

share|improve this answer
Thank you so much! How did you solve the integral recurrence equation of $u_n$ with respect to $n$? Also, I was wondering if you have idea about the remaining questions? –  steveO Apr 22 '11 at 23:00

Your Answer


