# NTUEE Queueing Theory 2022 FALL PRACTICE MIDTERM

## 1

Suppose you are given Poisson processes from source-1, source-2 and source-3, with arrival rate $\lambda_1$, $\lambda_2$ and $\lambda_3$ respectively. And there is no arrival at the starting time $t=0$.

1. Please show that the inter-arrival time afer the aggregation of these Poisson processes is exponential with mean equal to $\frac{1}{\lambda_1 + \lambda_2 + \lambda_3}$. (5%)

:::spoiler Answer
Let $T_1$ denote the inter-arrival time for the Poisson process from source 1, $T_2$ for that from source 2, $T_3$ for that from source 3, and $T$ for the aggregated Poisson process of the three.

Obviously, $T = min(T_1, T_2, T_3)$, and we are interested in the probability distribution of $T$ and $E(T)$.

$$\begin{aligned}
P(T > t)
&= P(min(T_1, T_2, T_3) \gt T) \\
&= P(T_1 \gt t \cap T_2 \gt t \cap T_3 \gt t) \\
&= P(T_1 \gt t) \cdot P(T_2 \gt t) \cdot P(T_3 \gt t) \\
&= e^{-\lambda_1 t} \cdot e^{-\lambda_2 t} \cdot e^{-\lambda_3 t}\\
&= e^{-(\lambda_1+\lambda_2 + \lambda_3) t}
\end{aligned}$$

So $T$ is a exponential random variable with parameter $\lambda_1 + \lambda_2 + \lambda_3$, thus $$E[T] = \frac{1}{\lambda_1 + \lambda_2 + \lambda_3}$$
:::

2. If there is no arrival in interval $(0, a)$, please derive the probability that there is exactly one arrival from any source during $(a,b)$, where $a < b$. (3%)

:::spoiler Answer

By the memoryless property, the desired probability $P$ there is exactly one arrival from any source during $(a,b)$ is the same as that of time interval $(0, b-a)$, and we know that the probability of $k$ arrivals for a Poisson process with arrival rate $\lambda$ during time period of $[t, t+\tau]$ is
$$\frac{e^{-\lambda \tau}(\lambda \tau)^k}{k!}$$

So $P$ has the following form:

$$\begin{aligned}
P &= \frac{e^{-(\lambda_1 + \lambda_2 + \lambda_3)(b-a)}((\lambda_1 + \lambda_2 + \lambda_3)(b-a))}{1!} \newline &= (\lambda_1 + \lambda_2 + \lambda_3)(b-a) \cdot e^{-(\lambda_1 + \lambda_2 + \lambda_3)(b-a)}
\end{aligned}$$

3. If you randomly select a time epoch $t_0$ in the future to observe these 3 arrival processes, what is the expected length of the interval between the previous arival(from any source) $t_0$ and the first arrival(from any source) after $t_0$? And what is the probability that both of these 2 arrivals are both form source-1?(6%)

:::spoiler Answer
By memoryless property, the expected length is
$$2 \cdot \frac{1}{\lambda_1 + \lambda_2 + \lambda_3} = \frac{2}{\lambda_1 + \lambda_2 + \lambda_3}$$

Detail explanation follows the same process in [note of Forward Recurrence Time & Backward Recurrence Time in Poisson Process](https://hackmd.io/5a0BMBLqTdaOrjxfoeqdEg#Forward-Recurrence-Time-amp-Backward-Recurrence-Time-in-Poisson-Process), we can show that the expected length is $\frac{2}{\lambda_1 + \lambda_2 + \lambda_3}$.

The probability that both of these 2 arrivals are both form source-1 is

$$\frac{\lambda_1^2}{(\lambda_1+\lambda_2 + \lambda_3)^2}$$

Detail explanation follows:

We know that the probability of $k$ arrivals for a Poisson process with arrival rate $\lambda$ during time period of $[t, t+\tau]$ being $\frac{e^{-\lambda \tau}(\lambda \tau)^k}{k!}$.

We use $Pr_n(k)$ to denote that there are $k$ arrivals from source $n$ in time period of $[0, T]$, and by memoryless property, whether we observe at time epoch $t_0$, or from another arbitrary time interval $[0, T]$, the results are the same.

Thus, with memoryless property, the desired probability can be expressed as:

$$\begin{aligned}
P &= \frac{Pr_1(2)}{Pr_{1||2||3}(2)} \newline
&= \frac{\frac{e^{-\lambda_1 T}(\lambda_1 T)^2}{2!} \cdot \frac{e^{-\lambda_2 T}(\lambda_2 T)^0}{0!} \cdot \frac{e^{-\lambda_3 T}(\lambda_3 T)^0}{0!} }{\frac{e^{-(\lambda_1+\lambda_2 + \lambda_3) T}((\lambda_1+\lambda_2 + \lambda_3) T)^2}{2!}} \newline
&= \frac{\lambda_1^2}{(\lambda_1+\lambda_2 + \lambda_3)^2}
\end{aligned}$$

## 2

Consider an $M/M/1/4$ queue with arrival rate $\lambda$ and service rate $\mu = \lambda$.

1. Please write down the generator matrix Q for its continuous time Markov Chain, which represents its system size(the number of customers in the system). (4%)

:::spoiler Answer
$$Q =
\begin{pmatrix}
-\lambda & \lambda & 0 & 0 & 0 \\
\mu & -(\lambda+\mu) & \lambda & 0 & 0 \\
0 & \mu & -(\lambda+\mu) & \lambda & 0 \\
0 & 0 & \mu & -(\lambda+\mu) & \lambda \\
0 & 0 & 0 & \mu & -\mu
\end{pmatrix}$$
:::

2. Please then solve its steady-state probability $p_n$ for $n=0,1,2,3,4$ using the generator matrix obtained in 1. (6%)

:::spoiler Answer
let $P = (p_0, p_1, p_2, p_3, p_4), e = (1,1,1,1,1)$
solve:

$$\begin{cases}
PQ = 0 \\
Qe = 1
\end{cases}
\Longrightarrow
\begin{cases}
p_1 = \frac{\lambda}{\mu} \cdot p_0 \\
p_2 = (\frac{\lambda}{\mu})^2 \cdot p_0 \\
p_3 = (\frac{\lambda}{\mu})^3 \cdot p_0 \\
p_4 = (\frac{\lambda}{\mu})^4 \cdot p_0 \\
p_0 = (1 + (\frac{\lambda}{\mu}) + (\frac{\lambda}{\mu})^2 + (\frac{\lambda}{\mu})^3 + (\frac{\lambda}{\mu})^4)^{-1}
\end{cases}$$

$$\Rightarrow p_0 = \frac{\mu^4}{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}$$
:::

3. Derive the imbedded Markov chain of this $M/M/1/4$ queue and obtain its steady state probability $\pi_n$ for $n=0,1,2,3,4$. (6%)

:::spoiler Answer
The transition matrix：
$$P = \begin{pmatrix}
0 & 1 & 0 & 0 & 0 \\
\frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu} & 0 & 0 \\
0 & \frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu} & 0 \\
0 & 0 & \frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu}\\
0 & 0 & 0 & 1 & 0
\end{pmatrix}$$

let $\pi = (\pi_0, \pi_1, \pi_2, \pi_3, \pi_4), e = (1,1,1, 1, 1)$
solve:

$$\begin{cases}
\pi P = \pi \\
\pi e = 1
\end{cases}
\Longrightarrow
\begin{cases}
\begin{multline}
\pi_0 = (1 + \frac{\mu + \lambda}{\mu} + \frac{\lambda}{\mu}\frac{\mu + \lambda}{\mu} + (\frac{\lambda}{\mu})^2 \frac{\mu + \lambda}{\mu} + (\frac{\lambda}{\mu})^3)^{-1}
\end{multline}\\
\pi_1 = \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_2 = \frac{\lambda}{\mu}\frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_3 = (\frac{\lambda}{\mu})^2 \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_4 = (\frac{\lambda}{\mu})^3 \cdot \pi_0 \\
\end{cases}$$
:::

4. Please determine the mean holding time for state 0,1,2,3 and 4.(4%)

:::spoiler Answer
let $m_i$ denote the mean holding time(mean state sojourn time) for state $i$.

$$\begin{cases} m_0 = \frac{1}{-q_{00}} = \frac{1}{\lambda} \newline
m_1 = \frac{1}{-q_{11}} = \frac{1}{\lambda + \mu} \newline
m_2 = \frac{1}{-q_{22}} = \frac{1}{\lambda + \mu} \newline
m_3 = \frac{1}{-q_{33}} = \frac{1}{\lambda + \mu} \newline
m_4 = \frac{1}{-q_{44}} = \frac{1}{\mu} \end{cases}$$
:::

5. Use the results of $\pi_n$ in 3. and the mean holding time in 4. to derive the formula for the steady-state probability $p_n$.(Hint: the results should be the same as in 2.)(6%)

:::spoiler Answer
We know that

$$p_i = \frac{m_i \pi_i}{\sum_{i=0}^4 m_j \pi_j}$$

First,

$$\begin{aligned}
\sum_{i=0}^4 m_j \pi_j &= (\frac{1}{\lambda} + \frac{1}{\mu} + \frac{\lambda}{\mu^2} + \frac{\lambda^2}{\mu^3} + \frac{\lambda^3}{\mu^4}) \cdot \pi_0 \newline
&= \frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4} \cdot \pi_0
\end{aligned}$$

So,

$$\begin{aligned} p_0 &= \frac{m_0 \pi_0}{\sum_{i=0}^4 m_j \pi_j} \newline
&= \frac{\frac{1}{\lambda}}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4}} \newline
&= \frac{\mu^4}{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4} \newline
&= p_0
\end{aligned}$$

and,

$$\begin{aligned} p_1 &= \frac{m_1 \pi_1}{\sum_{i=0}^4 m_j \pi_j} \newline
&= \frac{\frac{1}{\lambda + \mu} \cdot \pi_1}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4} \cdot \pi_0} \newline
&= \frac{\frac{1}{\lambda + \mu} \cdot \frac{\mu + \lambda}{\mu} \cdot \pi_0}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4} \cdot \pi_0} \newline
&= \frac{\frac{1}{\mu}}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4}} \newline
&= \frac{\lambda}{\mu} \cdot p_0 \newline
&= p_1
\end{aligned}$$

and follow the same reasoning, we can verify $p_2, p_3, p_4$ are the same as in 2. （同學請自行化簡，考試時不可省略此過程）
:::

## 3

Consider an M/D/1 queue with $p_0 = 0.2$, service rate $\mu = 1$ customer/min (per server).

1. What is the expected length of its busy cycle and its busy period?(Derivation required, and reuse some M/M/1 formula) (6%)

:::spoiler Answer
Since
$$L - L_q = 1 - p_0 = \rho = \frac{\lambda}{\mu}$$

so
$$\begin{aligned} &\frac{\lambda}{\mu} = 1 - 0.2 = 0.8 \newline &\Rightarrow \lambda = 0.8 \end{aligned}$$

Define $E[N_{bp}]$ as the average customer served in a busy period, $E[T_{bp}]$ as the expected length of the busy people, $E[T_{idle}]$ as the expected length of the idle period.

Since the arrival process is Poisson

$$E[T_{idle}] = \frac{1}{\lambda}$$

and by PASTA property

$$\begin{aligned} &\frac{1}{E[N_{bp}]} = p_0 = 0.2 \newline
&\Rightarrow E[N_{bp}] = 5 \end{aligned}$$

So
$$E[T_{bp}] = \frac{1}{\mu} \cdot E[N_{bp}] = 5$$

Hence, the expected length of the busy cycle is

$$E[T_{idle}] + E[T_{bc}] = \frac{5}{4} + 5 = \frac{25}{4}$$
:::

2. What is the average number of customers served in each busy cycle?(4%)

:::spoiler Answer
Since customers don't get served during idle period, so the answer is the same as $E[N_{bp}]$, which is $5$.
:::

## 4

Consider a finite source queue with 2 servers, 3 sources and 1 spare. Assuming exponential service time and arrival rate $\lambda$ for each active source. Mean service time $\frac{1}{\mu}$.

1. Please draw its state transition diagram and write down all global balance equations.(7%)

:::spoiler Answer
Given $M = 3, Y = 1, c = 2$, from [Finite-Source Queues](/ZQIknMLdTLqgehDNQ0gixg), we know that:

$$\lambda_n = \begin{cases} 3\lambda ,\ (0 \le n \lt 1) \\ (3-n+1)\lambda , \ (1 \le n \lt 4) \\ 0, \ (n \ge 4)\end{cases}$$

$$\mu_n = \begin{cases} n\mu ,\ (0 \le n \lt 2) \\ 2\mu,\ (n \ge 2)\end{cases}$$

From above, the state diagram is:


Thus, its global balance equations is:

$$\begin{cases}
p_0 3\lambda = p_1 \mu \newline
p_1(3 \lambda + \mu) = p_0 3\lambda + p_2 2 \lambda \newline
p_2(2 \lambda + 2\mu) = p_1 3\lambda + p_3 2\mu \newline
p_3(\lambda + 2\mu) = p_2 2\lambda + p_4 2\mu \newline
p_4 2\mu = p_3 \lambda
\end{cases}$$
:::

2. Please solve steady state probability $p_n$ form 1.(6%)

:::spoiler Answer
解聯立方程式可得 $p_0, p_1, p_2, p_3, p_4$。（同學考試時不可以直接這樣寫！）
:::

3. Please derive $q_n$, the probability that an arriving customer see population n in the system.(5%)

:::spoiler Answer
From Textbook page 90:

So
$$q_n =
\begin{cases}
\frac{3p_n}{3 - \sum_{i=1}^4 (i-1)p_n}, (n = 0) \\
\frac{(4-n)p_n}{3 - \sum_{i=1}^4 (i-1)p_n}, (0 \lt n \le 3)
\end{cases}$$
:::

4. If an arriving customer observes 3 customers in the system, what is the expected waiting time before service for this customer? (4%)

:::spoiler Answer

One has to wait at least 2 customers being served and depart before himself get served(enter server), and the mean service time for system size equals $3$ & $2$ are both $\frac{1}{2\mu}$, so

$$E(W_q | 3\ customer) = 2 \cdot \frac{1}{2\mu} = \frac{1}{\mu}$$

:::

5. What is the average utilization fo the servers in the system? (You may express the answer in $p_n$) (4%)

:::spoiler Answer
$$\frac{1}{2} \cdot p_1 + 1 \cdot p_2 +1 \cdot p_3 + 1\cdot p_4$$
:::

6. What is the average no. of customers departing from the queue per unit time? (You may express the answer in $p_n$) (4%)

:::spoiler Answer

The goal is to derive the departure rate.

Since we know that the Effective arrival rate = Departure rate, and from Textbook page 89:


So the average no. of customers departing from the queue per unit time is $\lambda_{eff}$.
:::

## 5

Compare and M/M/1 queue and an M/M/3 queue with the same $\rho(\rho \lt 1$) and the same arrival rate $\lambda$.

1. Which queue has higher server utilization?(4%)

:::spoiler Answer

We know that server utilization for M/M/c queue is

$$\frac{\lambda}{c\mu} = \rho$$

so server utilization is the same for both queue.
:::

2. Which queue has larger $p_0$?(5%)

:::spoiler Answer
Since two queue has the same $\rho$ and $\lambda$, which means

$$\frac{\lambda}{\mu_{M/M/1}} = \frac{\lambda}{3 \mu_{M/M/3}} \Rightarrow \mu_{M/M/1} = 3\mu_{M/M/3}$$

So,
$$r = \frac{\lambda}{\mu_{M/M/1}}\ ,\ r' = \frac{\lambda }{\mu_{M/M/3}} = 3r$$

Consider M/M/1 queue:

$$p_0 = (1 + r + r^2 + r^3 + \cdots)^{-1}$$

Consider M/M/3 queue:

$$\begin{aligned}
p_0
&= (1 + r' + \frac{1}{2!}(r')^2 + \frac{1}{3!}(r')^3 + \frac{1}{3!3}(r')^4 + \cdots)^{-1} \\
&= (1 + (3r) + \frac{9}{2!}r^2 + \frac{27}{3!}r^3 + \frac{81}{3!3}r^4 + \cdots)^{-1}
\end{aligned}$$

compare the coefficient of the two equation, since each coefficient of M/M/3 is larger or equal to that of M/M/1, so the inverse of it is smaller than that of M/M/1, hence we can say that $p_0$ for M/M/1 is larger.
:::

3. Which queue has larger mean busy cycle?(5%)

:::spoiler Answer
From [Busy-Period Analysis: Take M/M/1 as an Example](/1CiLXdwCS_uqCVx-WQqXmw), we know that the mean of the length of busy cycle is

$$E[T_{bc}] = E[T_{idle}] + E[T_{bp}]$$

since arrival rate $\lambda$ is the same for both M/M/1 and M/M/3, so their $E[T_{idle}] = \frac{1}{\lambda}$ are the same.

We also know that, given mean service rate as $\mu$

$$E(T_{bp}) = \frac{1}{\mu} \cdot E(N_{bp})$$

and given server utilization $\rho$

$$p_0 = 1 - \rho = \frac{1}{E(N_{bp})}$$

From 2., we know that $p_0$ for M/M/1 is larger, so $E(N_{bp})$ for M/M/1 is smaller. And from 2. we also know that the mean service rate for M/M/1 is larger than that of M/M/3, so the mean service time for M/M/1 is smaller, therefore, $E(T_{bp})$ is smaller for M/M/1.

And since $E[T_{idle}]$ are the same for both queue, $E[T_{bc}]$ is smaller for M/M/1, in other words, M/M/3 has larger busy cycle.
:::

## 6

1. Please draw the state transition diagram and write all global balance equations for an $M/E_4/1/1$ queue, assume arrival rate is $\lambda$ and mean service time is $\frac{1}{\mu}$ (6%)

2. Solve $P_0$ from the global balance equations in 1.(5%)

3. What is the effective arrival rate and the mean system size for this $M/E_4/1/1$ queue?(4%)