0
$\begingroup$

Cars arrive at a toll booth according to a Poisson process at the rate of two cars per minute. The time taken by the attendant to collect the toll is exponentially distributed with mean $20$ seconds.

(a) Find the long-term mean number of cars in line at the toll booth.

(b) Find the long-term probability that there are more than three cars at the toll booth.

If the arrival is $2$ cars per minute, then the inter-arrival times between each successive car is $\text{exp}(1/2)$ distributed. So cars arrive with rate $\text{exp}(1/2)$ and they leave the booth with rate $\text{exp}(1/3)$.

Let the statespace be $S=\{0,1,2,...,n\}$ denote the number of cars at the booth at different times. Starting at state $0$, the first car to arrive is the car with time equal to

$$\text{min}\left(\text{exp}(1/2),...n \ \text{terms}...,\text{exp}(1/2)\right)=\text{exp}\left(\sum_{k=1}^n\frac{1}{2}\right)=\text{exp}\left(\frac{n}{2}\right).$$

The rate for the second car can be found summing $n-1$ terms in similar fashion. That is $\text{exp}\left(\frac{n-1}{2}\right)$ and so on for the third etc. At the same time, the cars leave the queue as the attendant is finished, an average each $20$ seconds. So the transition rate diagram is

$$0\xrightarrow{\frac{n}{2}}1\xrightarrow{\frac{n-1}{2}}2\xrightarrow{\frac{n-2}{2}}3...n-2\xrightarrow{1}n-1\xrightarrow{\frac{1}{2}}n.$$

(OBS: there are also arrows going to the left from each state with rate $1/3$, did not know how to latex that.)

This is where it gets tedious. I need to find the generator matrix $Q$ and then find the limiting distribution $\vec{\pi}$ using $\vec{\pi}\ Q=0$. Once I have it, I can simply multiply each entry in the limiting distribution vector with each state and sum all the factors obtained. How do I get there?

EDIT as per EDZ's suggestion using Little's rule. I'd be happy if someone could verify the below!


The problem is an M/M/1 process, which is a birth and death process with constant birth and death rates, that is $\lambda_i=\lambda$ and $\mu_i=\mu.$ Thus, the stationary distribution is given by

$$\pi_k=\pi_0\prod_{i=1}^k\frac{\lambda}{\mu}=\pi_0\left(\frac{\lambda}{\mu}\right)^k$$

and

$$\pi_0=\left(\sum_{k=0}^{\infty}\prod_{i=1}^{k}\frac{\lambda}{\mu}\right)^{-1}=1-\frac{\lambda}{\mu},$$

so

$$\pi_k=\left(1-\frac{\lambda}{\mu}\right)\left(\frac{\lambda}{\mu}\right)^k,$$

which is a geometric distribution with parameter $1-\lambda/\mu.$ In our case, $\lambda=2$ and $\mu=3$ since each minute, $3$ cars are given service and $2$ new cars arrive. So our distribution is of the number of cars $N$ in the queue is

$$N\sim\text{Geometric}\left(\frac{1}{3}\right).$$

For (a), the long term mean number of cars in line is the mean of the geometric distribution, which is

$$E[N]=\frac{1-1/3}{1/3}=2.$$

For (b), since we have the distribution, we can compute the desired probability as follows:

$$P(N>3)=1-P(N=0)-P(N=1)-P(N=2)=1-\frac{1}{3}-\frac{2}{9}-\frac{4}{27}\approx0.2963$$

$\endgroup$
  • $\begingroup$ have you looked at this as a queue where you can use Little's rules as well as other established formulas? en.wikipedia.org/wiki/M/M/1_queue $\endgroup$ – EDZ Jan 10 at 23:38
  • $\begingroup$ No I have not because I don't really know how to know when to use Little's rule or not. Some very similar assignments involving queue-theory uses it and some don't. However, I'm gonna try this now and edit in my attempt in the question above. Thanks! $\endgroup$ – Parseval Jan 11 at 0:33
  • $\begingroup$ @EDZ - I've added my attempt as per your suggestion. Can you please check if there are any mistakes? My book only has answers to odd numbered questions and this is an even numbered unfortunately. $\endgroup$ – Parseval Jan 11 at 1:20

Your Answer

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

Browse other questions tagged or ask your own question.