]>
In a queuing model, customers arrive at a station for service. As always, the terms are generic; here are some typical examples:
Queuing models can be quite complex, depending on such factors as the probability distribution that governs the arrival of customers, the probability distribution that governs the service of customers, the number of servers, and the behavior of the customers when all servers are busy. Indeed, queuing theory has its own lexicon to indicate some of these factors. In this section, we will study one of the simplest, discrete time queuing models. However, as we will see, this discrete time chain is embedded in a much more realistic continuous time queuing process knows as the M/G/1 queue. In a general sense, the main interest in any queuing model is the number of customers in the system as a function of time, and in particular, whether the servers can adequately handle the flow of customers.
Our main assumptions are as follows:
Thus, let denote the number of customers in the system at time , and let denote the number of new customers who arrive at time . Then is a sequence of independent random variables, with common probability density function on , and
Show that is a Markov chain with state space and transition probability matrix given by
Explicitly find the one-step transition matrix for each of the following customer distributions:
Consider the queuing chain with customer probability density function given by , where is a parameter. Thus, at each time period, either no new customers arrive or 2 new customers arrive. Find the probability density function of starting with 1 customer.
From now on we will assume that and . Show that the chain is irreducible.
Our goal in this section is to compute the probability that the chain reaches 0, as a function of the initial state (so that the server is able to serve all of the customers). As we will see, there are some curious and unexpected parallels between this problem and the problem of computing the extinction probability in the branching chain. As a corollary, we will also be able to classify the queuing chain as transient or recurrent. Our basic parameter of interest is , the probability that the queue eventually empties, starting with a single customer, where as usual, is the hitting probability matrix.
Prove the following facts:
Condition on the first state to establish the following equation:
Note that this is exactly the same equation that we considered for the branching chain, namely , where is the probability generating function of the distribution that governs the number of new customers that arrive during each period.
Based on our analysis of the branching chain and the graphs above, show that is the smallest solution in and prove the following results:
Find the probability generating function of each of the following new customer probability density functions. Find the probability that the queue is eventually empty, starting with 1 customer.
Our next goal is to find conditions for the queuing chain to be positive recurrent. Let denote the mean of the probability density function ; that is, the expected number of new customers who arrive during a time period.
Let denote the probability generating function of , starting in state 1, where as usual, is the first positive time that the chain is in state 0. Show that
Show that for .
Show that
As usual, let , the mean return time to state 0. Let in the previous exercise to conclude that
For each of the new customer distributions in Exercise 8, compute the mean . Find conditions on the parameter for the queuing chain to be positive recurrent, null recurrent, and transient.