Consider $L$ queues in a discrete time system. At each time $n=0,1,2,\ldots$, one task would arrive at one of the queues with equal probability $\frac{1}{L}$. Immediately after that, a task scheduler would uniformly randomly pick up a queue, and schedule one task in that queue (if there is any). Tasks in queues are first come first served. Assume that working time of each task is 0, i.e., the task is gone immediately when it's scheduled. My question is, what is the probability that the task scheduler picks up an empty queue over the time? Would someone point me to any references if this is a known problem? Thanks.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ What state does the system start in ? Also, I think maybe you can view the problem as looking at a continuous time queueing system at event times, arrivals at each queue independent poisson with the same parameter gives the right behaviour for the next arrival, and also with service times, in which case the queues are independent. $\endgroup$– user83457Aug 9, 2016 at 8:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Heuristically, this probability should behave as $O(\sqrt{L/n})$, I guess. Observe that each queue, when not empty, is a random walk with zero drift, that actually moves once every $O(L^{-1})$ instances of time. So, up to time $n$ it would jump roughly $n/L$ times, and therefore visit the origin about $\sqrt{n/L}$ times and so there will be around the same (in order) number of instances when the walk "attempts to jump to (-1)", that is, the empty queue is selected. Overall, there would be around $L\times\sqrt{n/L}=\sqrt{Ln}$ such moments up to time $n$, and so that probability should behave as indicated.
Of course, this does not take the interactions into account; but my intuition says that wouldn't change the order, only constants.
I'm pretty sure that one can analyse the case $L=2$ very accurately, but I'm not so sure about larger $L$'s.
-
$\begingroup$ Interactions should be very important. Note that whenever an empty queue is chosen the overall number of tasks in the system has increased by one. So for two queues, i.e. $L=2$, the length of the other queue goes to infinity if we just consider the times when an empty queue is chosen. In any situation the probability of never again choosing an empty queue is zero. Hence the overall number of tasks goes to $\infty$ almost surely. In the long run, the case of two queues should behave almost like a single random walk with zero drift. I guess the case $L>2$ is much the same. $\endgroup$ Aug 9, 2016 at 12:16