\documentclass{article}
\usepackage{amssymb}
\usepackage{amsmath}
 
\newcommand{\Comment}[1]{}
\newcommand{\ruleOne}[2]{\arraycolsep=14pt\renewcommand{\arraystretch}{1.75}%
\begin{array}[c]{c}#1\\
    \hline\multicolumn{1}{c}{#2}
\end{array}}


\newcommand{\statespace}[1]{\mathcal{#1}}
\newcommand{\myset}[1]{\{ #1\}}

\begin{document}
\begin{center}
{\bf COURSE 336 \\ 

PERFORMANCE ANALYSIS\\
P.G. HARRISON \\
Solutions  5 \\
March 2006 \\
}
\end{center}

\begin{enumerate}
\item In an M/M/1 queue, assume that customers arrive as a  Poisson  process with
parameter one per  
  $12$ minutes, and that the service time is exponential at rate 
  one service per $8$ minutes.  Calculate the following quantities:
\begin{enumerate} 
\item $L$ the average  number of customers  in the system;
\item $W$ the average amount of time that a customer spends  in the system;
\item $W_{Q}$  the average amount of time a customer spends in the queue, waiting to
start service.
\end{enumerate} 
 If  there are no customers waiting to be served on arrival, what  is the value of the
queueing time random variable? \\ 

{\bf Solution}

Since $\lambda = \frac{1}{12}$ and $ \mu = \frac{1}{8}$    minute$^{-1}$, then
\begin{enumerate}
\item $L = \frac{\lambda}{\mu -\lambda}$, then
 $L = \ruleOne{\frac{1}{12}}{ \frac{1}{24}}= 2 $;
  thus the average number of customers in the queue is $2$.
\item  $ W = \frac{1}{\mu - \lambda}$, so $W = 24$; thus
 the average time spent in the system  is $24$ minutes.
\item $W_{Q} = W - \frac{1}{\mu}$, so  $W_{Q} = 16$; thus the average time spent in
the queue waiting to start service is $16$ minutes.
\end{enumerate}
Intuitively, if the  queue is empty, the only time waiting is the 
service time. Formally, observing  that  $W = W_{Q}+ \frac{1}{\mu}$  
 and  $W_{Q}= 0$, we derive   $ W= \frac{1}{\mu}=8$ minutes. \\ \\
 
 
 \item  Consider an M/M/1 queue where the jobs' willingness to join the queue is influenced by the queue size.  More precisely, a job which finds $i$ other jobs in the system joins the queue with probability  $1/(i+1)$    and departs immediately otherwise ($i=0,1,\ldots$).  Draw the state diagram for this system with arrival rate $\lambda$ and mean service time $1/\mu$.  Write down and solve the balance equations for the equilibrium probabilities $\pi_i$ and show that a steady-state distribution always exists.  Find the utilisation of the server, the throughput , the average number of jobs in the system and the average reponse time for a job that decides to join.  Note that the form of equilibrium probabilities is the same as that of the M/M/$\infty$ queue.  \\ 

{\bf Solution}
Diagram is the same as for the M/M/1 queue drawn in lectures, with rates from states $i+1$ to $i$ all having rate $\mu$ and the rate from $i$ to $i+1$ having rate $\lambda \times \frac{1}{i+1}$ since a fraction $\frac{i}{i+1}$ of arrivals do not join the queue at all ($i \geq 0$).

Balance equation for contour round states $1,2,\ldots,i$ is therefore:
$$p_i \lambda / (i+1) = p_{i+1} \mu$$
so that $$p_{i} = \rho^i/i! p_0$$ where $\rho = \lambda/\mu$.
Normalising, $p_0 = e^{-\rho}$, so steady state always exists.

Utilisation = $1-p_0 = 1-e^{-\rho}$.

Throughput = $(1-e^{-\rho})\mu$ since service rate is constant.

Mean queue length $L = \sum_{i=1}^\infty ip_i = p_0\sum_{i=1}^\infty
i\rho^i/i! \\=  p_0\rho\sum_{i=1}^\infty \rho^{i-1}/(i-1)! = \rho$

By Little's result, mean response time $W = L/(1-e^{-\rho})\mu = \rho/(1-e^{-\rho})\mu =
\lambda/(1-e^{-\rho})\mu^2$
 \\ \\
 
 
 \item Consider an M/M/$\infty$ queue with discouraged arrivals but with the following birth-and-death coefficients: 
$$ \lambda(i) = \frac{\lambda}{(i+1)^b}~~~\mbox{and }~~~\mu(i)=i^c\mu $$
where $c$ is the ``pressure-coefficient'' -- a constant that indicates the degree to which the service rate of the system is affected by the system state -- and $b$ is the ``discouraging coefficien''.  Obtain the  equilibrium probabilities $\pi_i$ for this birth-and-death process.  What is the equilibrium distribution when $b+c = 1$? \\

{\bf Solution}
As in the previous  question,
$$p_i \lambda / (i+1)^b = p_{i+1} \mu (i+1)^c$$
i.e. $$p_{i+1} = p_i \rho / (i+1)^{b+c}$$
Thus $$p_{i} = \rho^i/(i!)^{b+c} p_0$$
$$p_0 = \left[ \sum_{k=0}^\infty \rho^k/(k!)^{b+c} \right]^{-1}$$
Same as previous question / IS queue when $b+c =1 $.
 \\ \\



\item  Let $D$ be a random interval between  two 
consecutive departures from an  M/M/$1$ queue 
at equilibrium. If, just  after the first departure,
 the queue was not empty, then  $D$ coincides 
 with the service time of the next job. 
  If the queue was empty, then $D$ consists 
   of the period up to the next arrival, 
   as well as the service time of the next job. Assuming
    that the probability of a non-empty system 
    just after departure is the same as the utilisation, 
    show that $D$ is exponentially distributed with parameter $\lambda$. \\ 

{\bf Solution}

Recall that
$\rho = \frac{\lambda}{\mu}$ is  the utilisation of the server.
Write $X$ and $Y$ for the random variables corresponding to the interarrival
time and the service time respectively.
Let $D$ have probability distribution function $F$.  Then:
\begin{eqnarray*}
F(t) &=& P(D \leq t) \;=\; \rho P(Y \leq t) + (1-\rho)P(X+Y \leq t) \\
&=& \rho(1-e^{-\mu t}) + (1-\rho) \int_0^t P(X \leq t-u) \mu e^{-\mu u} du \\
&&(\mbox{since $X,Y$ are independent}) \\
&=&  \rho(1-e^{-\mu t}) + (1-\rho) \int_0^t  \mu e^{-\mu u} - 
\mu e^{-\lambda t}e^{-(\mu-\lambda) u} du \\
&=&  \rho(1-e^{-\mu t}) + (1-\rho) \left[1 - e^{-\mu t} - 
e^{-\lambda t} (\mu / (\mu-\lambda)) (1-e^{-(\mu-\lambda) t})\right] \\
&=& 1-e^{-\mu t} - e^{-\lambda t} (1-e^{-(\mu-\lambda) t}) \\
&=&  1-e^{-\lambda t}
\end{eqnarray*}
as required. \\\\

%%{\it Some notes on the convolution}
%%In the previous solution we have used the  convolution $F_{X + Y}$, which is the distribution
%%function  of the sum of two independent random variables $X_1$ and  $X_2$, with 
%%distribution function  $F_{X_1}$ and $F_{X_2}$ respectively.
%%Let the probability density function  (pdf)  of $F_{X_1}$ be $f(x)$ and $g(x)$


\item Let $X_1$  and $X_2$ be two independent exponential
 random variables with parameters $\lambda_1$ and $\lambda_2$. Prove that the random variable $Z= \min(X_1,X_2)$
is an exponential random variable with  parameter $\lambda_1 + \lambda_2$. \\ 

{\bf Solution}
%%Since $X_1$  and $X_2$ are two independent random variables with rate $\lambda_1$ and $\lambda_2$, we have:
%%\[\begin{array}{rcl}
%%P ( X_1 \leq t)& =& 1- e^{-\lambda_1 t}\\
%%P ( X_2 \leq t)& =& 1- e^{-\lambda_2 t}\\
%%\end{array} \]
For the random variable $Z$ we are interested in the time
  until either $X_1$ or $X_2$ occurs, 
   so:
\[\begin{array}{rcl}
P(Z \leq t) & = & 1 -P(Z > t) \\
&=& 1 -P( \min(X_1,X_2) > t) \\
& =& 1 - P( X_1 > t, X_2 > t) \\
&=&  1 - P(X_1 > t)P(X_2 > t)  \,\,\,\, \mbox{ by independence} \\
& = & 1 - (e^{- \lambda_1 t})(e^{- \lambda_2 t})\\
& =&  1- e^{ - (\lambda_1 + \lambda_2) t}\\
\end{array} \]


\end{enumerate}

\end{document}

