I think this question belongs to queue-theory but it doesn't really mention anything about queue-theory:

Suppose we have a queue of jobs serviced by one server. There is a total of $n$ jobs in the system. At time $t$, each remaining job independently decides to join the queue to be serviced with probability $p = d/n$, where $d < 1$ is a constant. Each job has a processing time of $1$ and at each time the server services one job, if the queue is nonempty. Show that with high probability, no job waits more than $\Omega(\ln n)$ time to be serviced once it joins the queue.

I really have no idea how to attack this one, I do not wish for an exact answer but rather someone to point me in the right direction, I know this has something to be with the number $e$ powered to something which reminds me to some probability distribution functions but I'm not sure how to proceed here. Thanks in advance!

  • 1
    $\begingroup$ Does the server always service the job that has been in the queue the longest? How does the server pick which job to service if two jobs join the queue at the same time? $\endgroup$ – Joe Feb 7 '18 at 20:42
  • $\begingroup$ @Joe: I suspect it's still most often $O(\log n)$ if we assume that any jobs entering the queue at the same time are served simultaneously, completing service at the end of their collective service times. $\endgroup$ – Brian Tung Feb 7 '18 at 21:32
  • $\begingroup$ @BrianTung Yeah I don't think it should matter either -- I just want to make sure I'm thinking in the same framework as the OP. $\endgroup$ – Joe Feb 7 '18 at 21:46
  • 1
    $\begingroup$ @Joe quite frankly the problem states just the information I gave you, nevertheless this question appears in a 'Random Graphs' section of exercises. It doesn't mention anything about the states of the jobs. $\endgroup$ – David Merinos Feb 8 '18 at 0:34
  • 1
    $\begingroup$ So I suppose we can assume anything. $\endgroup$ – David Merinos Feb 8 '18 at 0:53

"I do not wish for an exact answer but rather someone to point me in the right direction, I know this has something to be with the number e powered to something which reminds ...".

Conditionally fixing the distribution of the waiting time - P.35: http://www.win.tue.nl/~iadan/queueing.pdf

See from this equation, reading backwards, for less of a hint and more of an answer:

$$P(W\gt t| W \gt 0) = \frac {P(W \gt t)} {P(W \gt 0)} = e^{-u (1-p)t} $$

$W$ is with probability $(1−ρ)$ equal to zero, and with probability $ρ$ equal to an exponential random variable with parameter $µ(1 − ρ)$. So the conditional waiting time $W|W > 0$ is exponentially distributed with parameter $µ(1−ρ)$.

The exponential distribution (also known as negative exponential distribution) inhibits infinite divisibility and is the probability distribution that describes the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being a memoryless.

M/M/1 Queuing: Example Spoiler. Variable t is the chosen time interval, µ is the average service rate of a single service, part of the Poisson parameter that is used to define the Poisson distribution, the Poisson point is interpreted as a point process on a real line.

Kendall's notation (or sometimes Kendall notation) is the standard system used to describe and classify a queueing node.


Additional reading: Wikipedia queuing, ruin, maximum entropy probability distribution, even Pollaczek–Khinchine formula for claims with expotential distribution - derivation.

Other documents showing the usage of $ e^{-u (1-p)t} $

Waiting Systems - Page 9: https://www.netlab.tkk.fi/opetus/s383143/kalvot/E_mm1jono.pdf

ETSN10 Formula Sheet - Page 2: http://www.eit.lth.se/fileadmin/eit/courses/etsn10/formula_sheet.pdf

Introduction to Queueing theory - Computer Communication Networks - Page 14: http://web.iitd.ac.in/~jbseo/ell785_16/Queueing_theory_2016.pdf

ST333 Applied Stochastic Processes: Outline ... - University of Warwick - Page: 66: http://web.warwick.ac.uk/statsdept/teaching/notes/st333.pdf

  • $\begingroup$ Thanks for your answer kind sir, however I do not know what $u$ and $t$ are, mind explaining? $\endgroup$ – David Merinos Feb 11 '18 at 18:31
  • $\begingroup$ I've updated the answer. Also visit stats.stackexchange.com . $\endgroup$ – Rob Feb 12 '18 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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