# NTUEE Queueing Theory 2022 FALL HW1

## 1

Suppose you are given Poisson processes from source-1 and source-2, with arrival rate $\lambda_1$ and $\lambda_2$ 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}$. (10%)

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

Obviously, $T = min(T_1, T_2)$, and we are interested in the probability distribution of $T$ and $E(T)$, and we know that the arrival from source-1 and the arrival from source-2 are independent of each other.
$$\begin{split}
P(T > t)
&= P(min(T_1, T_2) \gt t) \\
&= P(T_1 \gt t \cap T_2 \gt t) \\
&= P(T_1 \gt t) \cdot P(T_2 \gt t) \\
&= e^{-\lambda_1 t} \cdot e^{-\lambda_2 t}\\
&= e^{-(\lambda_1+\lambda_2) t}
\end{split}$$

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

2. Please derive the probability that the first arrival is from source-1 and the second arrival is from source-2, if the observation starts from $t = 0$. (5%)

:::spoiler Answer
There are two ways to solve this question:

First, let $T_1$ denote the time for the first arrival from source-1, and $T_2$ for that of source-2, since arrivals from source-1 & source-2 are independent of each other, their joint probability density function is

$$f_{T_1, T_2}(t_1, t_2) = \lambda_1 e^{-\lambda_1 t_1} \cdot \lambda_2 e^{-\lambda_2 t_2}$$

So, the probability that the first arrival is from source-1 is

$$\begin{aligned} Pr(T_1 \lt T_2)
&= \int_0^{\infty}\int_{t_1}^{\infty} \lambda_1 e^{-\lambda_1 t_1} \cdot \lambda_2 e^{-\lambda_2 t_2} dt_2dt_1 \newline
&= \int_0^{\infty}\lambda_1 e^{-\lambda_1 t_1} (-e^{-\lambda_2 t_2})\bigg\rvert_{t_1}^{\infty} dt_1 \newline
&= \int_0^{\infty}\lambda_1 e^{-\lambda_1 t_1} (e^{-\lambda_2 t_1}) dt_1 \newline
&= \lambda_1 \int_0^{\infty} e^{-(\lambda_1 + \lambda_2) t_1} dt_1 \newline
&= \frac{\lambda_1}{\lambda_1 + \lambda_2}
\end{aligned}$$

Similarly, the probability that the second arrival is from source-2 is

$$Pr(T_2 \lt T_1) = \frac{\lambda_2}{\lambda_1 + \lambda_2}$$

So the desired probability that the first arrival is from source-1 and the second arrival is from source-2 is
$$\frac{\lambda_1}{\lambda_1 + \lambda_2} \cdot \frac{\lambda_2}{\lambda_1 + \lambda_2} = \frac{\lambda_1\lambda_2}{(\lambda_1 + \lambda_2)^2}$$

The second solution to this problem based on the fact that 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]$.

Thus, the desired probability can be expressed as:

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

One can verify this by summing up all possible conditional probabilities((source of frist arrival, source of second arrival) can be (1, 1), (1, 2), (2, 1), (2, 2))：

$$\frac{\lambda_1^2}{(\lambda_1+\lambda_2)^2} + \frac{\lambda_1 \lambda_2}{(\lambda_1+\lambda_2)^2} + \frac{\lambda_2 \lambda_1}{(\lambda_1+\lambda_2)^2} + \frac{\lambda_2^2}{(\lambda_1+\lambda_2)^2} = 1$$
:::

3. Please derive the probability that there is no arrival from these two sources during time interval $(a,b)$, where $a < b$. (5%)

:::spoiler Answer
By the memoryless property, the desired probability $P$ there is no arrival from these two sources during time interval $(a,b)$ is the same as that of time interval $(0, b-a)$, and same as 2., 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)(b-a)}((\lambda_1 + \lambda_2)(b-a))^0}{0!} \newline &= e^{-(\lambda_1 + \lambda_2)(b-a)}\end{aligned}$$

4. If you randomly select time epoch $t_0$ in the future to observe these 2 arrival processes, what is the expected length of the interval between the nearest arival(from any source) before $t_0$ and the first arrival(from any source) after $t_0$? (10%)

:::spoiler Answer
The short answer is by memoryless property, the expected length is $2 \cdot \frac{1}{\lambda_1 + \lambda_2} = \frac{2}{\lambda_1 + \lambda_2}$.

But a explanation of why $\frac{2}{\lambda_1 + \lambda_2} \neq \frac{1}{\lambda_1 + \lambda_2}$ will be needed **if specified is the Midterm quiz**. The 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}$.
:::

## 2

Consider an $M/M/1/2$ 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). (5%)

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

2. Please then solve its steady-state probability $p_n$ for $n=0,1,2$ using the generator matrix obtained in 1 and the equation $PQ = 0$, and $Pe=1$.(10%)

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

$$\begin{cases}
PQ = 0 \\
Pe = 1
\end{cases}
\Longrightarrow
\begin{cases}
p_1 = \frac{\lambda}{\mu} \cdot p_0 \\
p_2 = (\frac{\lambda}{\mu})^2 \cdot p_0 \\
p_0 = (1 + \frac{\lambda}{\mu} + (\frac{\lambda}{\mu})^2)^{-1}
\end{cases}$$
:::

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

:::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}{\mu} \end{cases}$$
:::

## 3

Suppose there is an $M/M/1/2$ queue with blocking probability $P_b$, and $\lambda = 2, \mu = 3$.

1. Please calculate the average system size $L$ using $p_n$, and then derive average waiting time $W$ using Little's formula. (5%)

:::spoiler Answer
from 2. we know $p_n$ has the following form:

$$\begin{cases}
p_1 = \frac{\lambda}{\mu} \cdot p_0 = \frac{6}{19}\\
p_2 = (\frac{\lambda}{\mu})^2 \cdot p_0 = \frac{4}{19}\\
p_0 = (1 + \frac{\lambda}{\mu} + (\frac{\lambda}{\mu})^2)^{-1} = \frac{9}{19}
\end{cases}$$

$L$ can be calculated as:

$$\begin{aligned} L &= E[N] = \sum_{i=0}^2 np_n \newline
&= 0p_0 + 1p_1 + 2p_2 \newline
&= \frac{6}{19} + 2\frac{4}{19} \newline
&= \frac{14}{19}
\end{aligned}$$

The effective arrival rate is:

$$\lambda_{eff} = \lambda(1 - p_2) = \frac{30}{19}$$

Using Little's formula:

$$\begin{aligned} W = \frac{L}{\lambda_{eff}} = \frac{7}{15}
\end{aligned}$$
:::

2. Please show that $P_b = p_2$. (5%)

:::spoiler Answer
Since the queue's capcity is $2$, so queue blocks customer from entering when the queue size is $2$, thus $P_b = p_2$.
:::

3. Please show that the effective arrival rate (the rate that customers are admitted in this queue) is given by $\lambda_{eff} = \lambda(1 - P_b)$. (5%)

:::spoiler Answer
Since $(1 - P_b)$ is the probability that customers will not be blocked by queue, which is to say, customers can enter the queue with probability $(1 - P_b)$, thus, the effective arrival rate $\lambda_{eff}$ is $\lambda(1 - P_b)$.
:::

4. Please calculate this queue's utilization, and the probability that it is idle. (5%)

:::spoiler Answer
The queue is idle when there is no customer in the queue, so the probability that this queue is idle is:

$$p_0 = \frac{9}{19}$$

Since the queue is either idle or being in use, so the queue's utilization is
$$U = 1 - p_0 = \frac{10}{19}$$

The queue's utilization can also be calculated as:

$$U = \frac{\lambda_{eff}}{\mu} = \frac{10}{19}$$
:::

5. Please verify your results in 1., 2., 4. and using JMT simulator, and attach your simulation results (i.e. the obtained figures). (20%, 5% for each result in 1., 2., 4.)

:::spoiler Answer
Model Structure:


$L$ corresponds to **Number of Customers**, $$L = \frac{14}{19} \approx 0.736842$$


$W$ corresponds to **Response Time**, $$W = \frac{7}{15} \approx 0.466$$


$U$ corresponds to **Utilization**, $$U = 1 - p_0 = \frac{10}{19} = \approx 0.5263157$$


$\lambda P_b$ corresponds to **Drop Rate**, $$\lambda P_b = \lambda p_2 = 2\frac{4}{19} = \approx 0.42105$$
:::

## 4

Now Consider the same $M/M/1/2$ queue in 3.

1. If we set $\lambda = 4, \mu = 3$, why we can still obtain its steady state prob.distribution even though $\lambda > \mu$ ? (5%)

:::spoiler Answer
from 3., we know that the queue's utilization is
$$U = \frac{\lambda_{eff}}{\mu} = \frac{10}{19} < 1$$
Since utilization is less than $1$, the queue can stay stable, thus has state prob.distribution.
:::

2. If we set $\lambda$ to be very large, what is the mean inter-departure time for this queue? (5%)

:::spoiler Answer
There are always customers in the queue being served when $lambda$ is very large, which is to say, the server is always busy, so the inter-departure time is equal to the mean service time $\frac{1}{\mu} = \frac{1}{3}$.
:::