Take the 2-minute tour ×
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.

$\newcommand{\length}{\textrm{length}}$I have queues of packets of different sizes. The probability of choosing queue $i$ where I pop the first packet is

$$p(i) = \frac{\length(i)}{ \sum_j \length(j)}$$

The probability that I don't choose queue $i$ is $1-p(i)$. It should thus follow a Bernoulli distribution. I calculate these probabilities at the beginning and stick to them until the end.

My goal is have for each queue an approximation of a Poisson Process. Is this possible?

Example:

I have queues $a$,$b$,$c$ each with with packets 1, 2, 3, etc. Say that I get the following output:

$$a_1, b_1, b_2, c_1, a_2, b_3, a_3, c_2, b_4, a_4, b_5,\dots$$

I want to approximate the arrival times for elements from queue $a$ by some exponential random variable with a certain intensity. Same thing for queues $b$ and $c$. Is this possible?

share|improve this question
    
I assume that there are a finite number of packets in each queue? –  Chris Taylor Apr 12 '12 at 12:15
    
yes, queues are finite. –  Ricky Robinson Apr 12 '12 at 12:37
    
It's not as simple as you make out, because the probability of choosing queue $i$ changes every time a new element is popped. In general the rates after every popped element will be a complicated function of the initial sizes of the queues and the elements that have been popped so far. There may be a rough approximation though. I'll try to look at it later. –  Chris Taylor Apr 12 '12 at 13:14
    
Thank you. I forgot to emphasize that the probabilities of choosing each queue are fixed. I calculate them at the beginning based on the initial size of each queue and stick to them until the end. Does this make things any easier? –  Ricky Robinson Apr 12 '12 at 13:23
    
Ah, okay. That makes it easier (what happens when you pick a queue with nothing in it though?) –  Chris Taylor Apr 12 '12 at 13:36

1 Answer 1

up vote 1 down vote accepted

First consider the case when none of the queues is empty. You have probability $p_i$ of picking from queue $i$. The sequence of 0s and 1s that indicates whether an element came from queue $i$ or not is therefore a Bernoulli process with probability $p_i$.

The waiting time $W_i$ between arrival of packets from queue $i$ therefore follows a Geometric distribution with parameter $p_i$, i.e.

$$P(W_i=w) = (1-p_i)^{w-1}p_i$$

which is the exponential-like process you are after (a geometric distribution is the discrete version of the exponential distribution - if there are $n$ packets per second and you let $n\rightarrow \infty$ and $p\rightarrow 0$ in such a way that $\lambda=np$ remains constant, then you get an exponential distribution with parameter $\lambda$).

If you want to consider the case of finite queues, then I think that the simplest thing to do is to reset the model whenever one of the queues becomes empty. If queue $j$ empties, then one option is to shift all the probabilities by

$$p_j \rightarrow 0, \qquad p_i \rightarrow \frac{p_i}{1-p_j} \textrm{ for }i\neq j$$

and carry on as before (you now have zero probability of selecting from queue $j$, which is equivalent to ignoring that queue if it is selected with the previous probabilities). Another option is to re-evaluate the probabilities according to the current length of each queue.

share|improve this answer

Your Answer

 
discard

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.