Lecture on 8th Nov 2002

Puneet Bhargava Akshiv Singhla

 

Queuing and Simulation (continued)

 

The inter arrival times A₁, A₂, A₃ … are assumed to be independent of each other.

Although we may argue that each next A tells something about the distribution. Each new A would be helping in better defining the model i.e. the probability distribution of A. But once the model has been defined i.e. the probability distribution is fixed, these A are independent of each other (within the model).

Therefore we will assume that the inter arrival times are independent of each other (once the model is fixed).

In the previous lecture, we had said,

Waiting time for the (n+1)^th customer,

W_n+1 = [W_n + B_n –A_n+1]⁺ = Max (0, W_n + B_n –A_n+1)

This is valid only under the assumption of FCFS (first come first serve)

 

The function N(t) is defined as the total no of arrivals till time t (includes people already served and those in the queue) defined for t ≥ 0. It is non-negative, integer and increasing function of t. A graph of increasing function, N(t) with time is shown below.

 

Note that if (N(t):t ≥ 0) is known and then so are (A₁, A₂, A₃ …) and vice versa. This can be easily seen through the graph.

We now discuss a popular process for modeling arrivals to the queue i.e. Poisson Process.

 

Poisson process

The integer valued arrival process {N(t)} is said to be a Poisson process with rate λ, λ ≥ 0, if:

i)        N(0) = 0 i.e. there is no arrival in the interval of length beginning at t = 0, which is intuitively reasonable.

ii)      Process has independent increments

      No of events in any time interval are independent of the past i.e.

      {N(t+s) – N(t)} is independent of {N(u) u ≤ t} for all s and t.

Note:- In an internet traffic, this assumption is not valid since the data is coming in bursts. So if data is detected then there is high probability that there will be more data coming in the next unit of time. This holds true even for the idle periods of time.

iii)    No of events in any interval of length t is Poisson distributed with mean λt which means that

 for n = 0, 1, 2 …

for any s and t.

 

It therefore follows that,

E(N(t)) = λt

i.e. N(t) is a Poisson process with mean λt

 

The following definition is used to characterize negligible terms in an analysis so that these terms do not get undue attention.

Definition: A function f is o(h) when:

e.g. h² + h³, etc. So here we are interested only in the order of magnitude.

So by this definition the negligible terms can be easily left and only the significant terms are allowed in the analysis.

 

The Poisson process can be characterized in an alternate and equivalent form which is intuitively more appealing.

The counting process {N(t)} is said to be Poisson process with rate λ, λ ≥ 0, if:

i)       N(0) = 0

ii)     Process has stationary and independent increments

      N(t+s) – N(t) has a distribution dependent only on s

Here stationary depicts that the behavior of the process does not depend on time, but only on the length of the interval.

i.e. P(s,s+t) = P(0,t)

and independent means that the increments of the process do not depend on other increments. The increments of a process are independent of the past, no matter what happens in the past. So the probability distribution of an event remains same irrespective of the how many events have occurred before that interval. For e.g. persons coming to a barber shop. This event of arriving at the barber shop is independent of the previous event, but whether he chooses to remain there or not after seeing the line is a different issue.

iii)   P(N(h) = 1) = λh + o(h), i.e. probability of arrival in a small interval h is proportional to length the of interval h.

iv)    P(N(h) ≥ 2) = o(h), i.e. probability of having two or more events in the interval h is negligible. It follows that

P(N(h) = 0) = 1 - λh + o(h).

Violations to this in real life: people arriving in batches at places such as airports etc. So if we count the number of persons, many events are occurring in a small interval h i.e. the probability of more than two intervals in small interval h is not negligible. The assumption would still be valid if we considered no of batches. An event occurs if a batch enters and hence the same analysis can be done on it.

 

Relationship between N(t) and (A₁, A₂, A₃ ….)

A relationship between N(t) and (A₁, A₂, A₃ ….) is derived, to show that the inter-arrival times are IID’s.(independent identically distributed function)

Let A₁, A₂, … be a sequence of inter arrival times of a Poisson process. Note that

P(A₁ > t) <=> P(N(t) = 0)

If the first event occurs after time t then there can be no arrivals from time 0 to t.

N(t) is a Poisson process, therefore it is given by:

P(N(t) = 0) = e^-λt

The cumulative distribution function(CDF) of the number of arrivals is given by:

P(A₁ ≤ t) = 1 – P(A₁ > t)

                   = 1 – P(N(t) = 0)

       = 1 – e^{-λ t}

After differentiating the CDF, PDF is given by: λe^-λt for t ≥ 0

We still have not shown that A_i’s are IID (independent identically distributed)

P(A₂ > t | A₁ = s) =  P(no event in (s, s+t) | A₁ = s)

= P(no event in (s, s+t) (assuming independent increments)

= P(no event in (0, t)) (because of stationarity) = e^-λt

 

By alternate argument,

P(A₂ > t | A₁ = s) =  P(N(s+t) – N(s) = 0 | N(u) = 0, u<s, N(s) = 1 )

                           = P(N(s+t) – N(s) = 0 ) (by assumption of independent increments)

                           = P(N(t) = 0)  (by assumption of stationary increments)

                           = e^-λt

 

Similarly by the method of induction, it can be shown for all the A_i‘s that all of them follow the same distribution. Hence all A_i’s are IIDs.