Exercises

$\lambda t = 12 \times 1/6 = 2$. $\mathbb{P}(N = 0) = e^{-2} \approx 0.1353$.

$\lambda t = 12 \times 1/4 = 3$. $\mathbb{P}(N \geq 2) = 1 - e^{-3} - 3e^{-3} = 1 - 4e^{-3} \approx 1 - 0.1991 = 0.8009$.

$\lambda = 1/\mathbb{E}[T] = 1/0.5 = 2$ arrivals/second.

$\mathbb{P}(T > 1) = e^{-\lambda \cdot 1} = e^{-2} \approx 0.1353$.

$\mathbb{P}(\text{process 1 first}) = \lambda_1/(\lambda_1+\lambda_2) = 5/8 = 0.625$.

$M_{S_n}(s) = [M_{T_1}(s)]^n = \left(\frac{\lambda}{\lambda-s}\right)^n$, $s < \lambda$. This is the MGF of a Gamma$(n, \lambda)$ distribution.

The Gamma$(n, \lambda)$ PDF is $f(t) = \lambda^n t^{n-1}e^{-\lambda t}/(n-1)!$ for $t > 0$. Its MGF is $\int_0^\infty e^{st}\lambda^n t^{n-1}e^{-\lambda t}/(n-1)!\,dt = (\lambda/(\lambda-s))^n$. Since MGFs uniquely determine distributions, $S_n \sim \text{Gamma}(n,\lambda)$. $\blacksquare$

The joint density of the first $n$ arrival times is $f_{S_1,\ldots,S_n}(s_1,\ldots,s_n) = \lambda^n e^{-\lambda s_n}$ on $0 < s_1 < \cdots < s_n$. The conditional density given $N(t) = n$ restricts to $s_n \leq t$ and divides by $\mathbb{P}(N(t)=n) = (\lambda t)^n e^{-\lambda t}/n!$: $$f(s_1,\ldots,s_n \mid N(t)=n) = \frac{\lambda^n e^{-\lambda t}}{(\lambda t)^n e^{-\lambda t}/n!} = \frac{n!}{t^n}$$ on $0 < s_1 < \cdots < s_n < t$. This is exactly the joint density of the order statistics of $n$ i.i.d. Uniform$(0,t)$ random variables. $\blacksquare$

$\mathbb{E}[N(24)] = \int_0^{24}(3+2\sin(\pi u/12))\,du = 72 + 2[-\frac{12}{\pi}\cos(\pi u/12)]_0^{24}$ $= 72 + 2 \cdot (-12/\pi)[\cos(2\pi) - \cos(0)] = 72 + 2(-12/\pi)(1-1) = 72$.

$\mathbb{E}[N(6)] = \int_0^{6}(3+2\sin(\pi u/12))\,du = 18 + 2[-\frac{12}{\pi}\cos(\pi u/12)]_0^{6}$ $= 18 - \frac{24}{\pi}[\cos(\pi/2) - \cos(0)] = 18 - \frac{24}{\pi}(0-1) = 18 + 24/\pi \approx 25.64$.

$\mathbf{G} = \begin{pmatrix} -3 & 2 & 1 \\ 3 & -3 & 0 \\ 4 & 1 & -5 \end{pmatrix}.$$

$-3\pi_0 + 3\pi_1 + 4\pi_2 = 0$ ... (i) $2\pi_0 - 3\pi_1 + \pi_2 = 0$ ... (ii) $\pi_0 + \pi_1 + \pi_2 = 1$ ... (iii)

From (ii): $\pi_2 = 3\pi_1 - 2\pi_0$. Substituting into (i): $-3\pi_0 + 3\pi_1 + 4(3\pi_1 - 2\pi_0) = 0$ $\Rightarrow -11\pi_0 + 15\pi_1 = 0 \Rightarrow \pi_0 = 15\pi_1/11$. Then $\pi_2 = 3\pi_1 - 30\pi_1/11 = 3\pi_1/11$. From (iii): $\pi_1(15/11 + 1 + 3/11) = 1 \Rightarrow \pi_1 \cdot 29/11 = 1$. $\pi_1 = 11/29$, $\pi_0 = 15/29$, $\pi_2 = 3/29$.

Eigenvalues: $\mu_1 = 0$, $\mu_2 = -(\alpha+\beta)$. Right eigenvectors: $\mathbf{v}_1 = (1, 1)^T$, $\mathbf{v}_2 = (\alpha, -\beta)^T$. $\mathbf{S} = \begin{pmatrix} 1 & \alpha \\ 1 & -\beta \end{pmatrix}$, $\mathbf{S}^{-1} = \frac{1}{\alpha+\beta}\begin{pmatrix} \beta & \alpha \\ 1 & -1 \end{pmatrix}$.

$\mathbf{P}(t) = \mathbf{S}\begin{pmatrix}1&0\\0&e^{-(\alpha+\beta)t}\end{pmatrix}\mathbf{S}^{-1}$ $= \frac{1}{\alpha+\beta}\begin{pmatrix}\beta+\alpha e^{-(\alpha+\beta)t} & \alpha-\alpha e^{-(\alpha+\beta)t}\\\beta-\beta e^{-(\alpha+\beta)t} & \alpha+\beta e^{-(\alpha+\beta)t}\end{pmatrix}$.

At $t=0$: $\mathbf{P}(0) = \mathbf{I}$. $\checkmark$ As $t \to \infty$: each row $\to (\beta/(\alpha+\beta), \alpha/(\alpha+\beta)) = \boldsymbol{\pi}$. $\checkmark$

$\rho = 6/10 = 0.6$. $\pi_n = 0.4 \times 0.6^n$.

$\mathbb{P}(N \geq 5) = \sum_{n=5}^{\infty}\pi_n = \rho^5 = 0.6^5 = 0.07776$.

$W = 1/(\mu - \lambda) = 1/4 = 0.25$ time units.

The sojourn time $W$ is Exp$(\mu-\lambda) =$ Exp$(4)$. $\mathbb{P}(W > t) = e^{-4t}$. Set $e^{-4t} = 0.05$: $t = -\ln(0.05)/4 = 2.996/4 \approx 0.749$ time units.

$L = \rho/(1-\rho) = 9$. The mean number being served is $\rho = 0.9$. $L_q = L - \rho = 9 - 0.9 = 8.1$.

$\pi_0 = 1 - \rho = 0.1$, so the server is idle 10% of the time.

$\rho = 1.25$. $\pi_n = \frac{(1-1.25)(1.25)^n}{1-(1.25)^{11}} = \frac{-0.25 \times 1.25^n}{1-11.642} = \frac{0.25 \times 1.25^n}{10.642}$.

$P_{\text{block}} = \pi_{10} = \frac{0.25 \times 1.25^{10}}{10.642} = \frac{0.25 \times 9.3132}{10.642} = \frac{2.3283}{10.642} \approx 0.2188$.

About 21.9% of arriving customers are lost. Despite $\rho > 1$, the finite buffer ensures stability — but at the cost of significant loss.

Let arrivals occur at times $A_1, A_2, \ldots$ of a Poisson process independent of $\{X(t)\}$. Define the fraction of arrivals in state $j$: $\hat{\pi}_j = \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n \mathbf{1}(X(A_k)=j)$.

Since the Poisson process has independent increments and is independent of $\{X(t)\}$, the arrival times $A_k$ are "random observers" of the chain. Formally, $\mathbb{P}(X(A_k)=j \mid A_k = t) = \mathbb{P}(X(t)=j)$ by independence. In steady state, $\mathbb{P}(X(t)=j) = \pi_j$.

By the strong law applied to the i.i.d. (by the Poisson property) indicators $\mathbf{1}(X(A_k)=j)$: $\hat{\pi}_j = \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n\mathbf{1}(X(A_k)=j) = \pi_j$ a.s.

The essential point is that Poisson arrivals are "memoryless observers" — they do not synchronize with the chain's state transitions. Non-Poisson arrivals can be correlated with the state and may see a biased view. $\blacksquare$

$\pi_n = \pi_0\prod_{k=0}^{n-1}\frac{\lambda}{(k+1)\mu} = \pi_0\frac{(\lambda/\mu)^n}{n!} = \pi_0\frac{A^n}{n!}$.

$\sum_{n=0}^{\infty}\pi_n = \pi_0\sum_{n=0}^{\infty}\frac{A^n}{n!} = \pi_0 e^A = 1$. So $\pi_0 = e^{-A}$ and $\pi_n = e^{-A}A^n/n!$, which is Poisson$(A)$. $\blacksquare$

Let $D_c = \sum_{k=0}^c A^k/k!$. Then $B(A,c) = (A^c/c!)/D_c$. Note $D_c = D_{c-1} + A^c/c!$.

$1/B(A,c) = D_c/(A^c/c!) = D_{c-1}/(A^c/c!) + 1$. Also $D_{c-1}/(A^c/c!) = (c/A) \cdot D_{c-1}/(A^{c-1}/(c-1)!) = (c/A)/B(A,c-1)$. So $1/B(A,c) = c/(A\cdot B(A,c-1)) + 1 = (c + A\cdot B(A,c-1))/(A\cdot B(A,c-1))$. Inverting: $B(A,c) = A\cdot B(A,c-1)/(c + A\cdot B(A,c-1))$. $\blacksquare$

$B(15, 0) = 1$. $B(15, 1) = 15 \cdot 1/(1 + 15) = 15/16 = 0.9375$. $B(15, 2) = 15 \cdot 0.9375/(2 + 15 \cdot 0.9375) = 14.0625/16.0625 = 0.8755$. Continuing iteratively (each step is a single multiply and divide): $B(15, 5) \approx 0.6504$, $B(15, 10) \approx 0.2845$, $B(15, 15) \approx 0.0682$, $B(15, 18) \approx 0.0243$, $B(15, 20) \approx 0.0107$.

With 20 channels, about 1.07% of calls are blocked. This is below the standard 2% Grade of Service target. If the offered load increases to 16 Erlangs, $B(16, 20) \approx 0.0178$ — still within the target.

$\rho = 10/12 = 5/6$. The Erlang-C formula gives (by numerical computation): $C(10, 12) \approx 0.3472$.

$W_q = \frac{C(A,c)}{c\mu - \lambda}$. With $\mu = 1$ (WLOG, measuring time in service times): $W_q = 0.3472/(12-10) = 0.3472/2 = 0.1736$ service times.

$\mathbb{P}(W_q > 2/\mu) = C(A,c) \cdot e^{-(c\mu-\lambda) \cdot 2/\mu} = 0.3472 \cdot e^{-2 \cdot 2} = 0.3472 \cdot e^{-4} \approx 0.00635$.

The key insight is that in a loss system, the state is just the number of busy servers $n \in \{0, \ldots, c\}$. The transition rates between states depend only on the arrival rate $\lambda$ and the overall departure rate from state $n$, which is $n\mu$ regardless of the service time distribution (as long as the mean is $1/\mu$).

More formally, the M/G/c/c queue can be analyzed using the theory of symmetric queues (Kelly, 1979). A queue is symmetric if the service discipline treats all customers identically, and in a loss system this is automatic (no queueing). For symmetric queues, the stationary distribution depends on the service time distribution only through its mean. Therefore: $$\pi_n = \frac{A^n/n!}{\sum_{k=0}^c A^k/k!}, \quad A = \lambda/\mu,$$ regardless of the service time distribution.

This is why Erlang-B is used so widely: the formula is robust to misspecification of the service time distribution. $\blacksquare$

Consider the queue length $Q_n$ at the $n$-th departure. This is an embedded DTMC. Using the relation between arrivals during a service time and the queue evolution, one derives (via generating functions): $L_q = \frac{\lambda^2\mathbb{E}[S^2]}{2(1-\rho)}$.

$\mathbb{E}[S^2] = \text{Var}(S) + (\mathbb{E}[S])^2 = \mathbb{E}[S]^2(C_s^2 + 1)$. $L_q = \frac{\lambda^2\mathbb{E}[S]^2(1+C_s^2)}{2(1-\rho)} = \frac{\rho^2(1+C_s^2)}{2(1-\rho)}$. $L = L_q + \rho = \rho + \frac{\rho^2(1+C_s^2)}{2(1-\rho)}$.

For $S \sim \text{Exp}(\mu)$: $C_s = 1$. $L = \rho + \frac{\rho^2 \cdot 2}{2(1-\rho)} = \rho + \frac{\rho^2}{1-\rho} = \frac{\rho(1-\rho)+\rho^2}{1-\rho} = \frac{\rho}{1-\rho}$. $\checkmark$

Rate out: $(\lambda + \mu_1 + \mu_2)\pi(n_1,n_2)$. Rate in: $\lambda\pi(n_1-1,n_2) + \mu_1\pi(n_1+1,n_2-1) + \mu_2\pi(n_1,n_2+1)$.

Using $\pi(n_1,n_2) = (1-\rho_1)\rho_1^{n_1}(1-\rho_2)\rho_2^{n_2}$:

• $\lambda\pi(n_1-1,n_2) = \lambda \cdot \pi(n_1,n_2)/\rho_1 = \mu_1\pi(n_1,n_2)$ since $\rho_1 = \lambda/\mu_1$. Wait — $\lambda/\rho_1 = \mu_1$, so $\lambda\pi(n_1-1,n_2) = \lambda\pi(n_1,n_2)/\rho_1 = \mu_1\pi(n_1,n_2)$.
• $\mu_1\pi(n_1+1,n_2-1) = \mu_1\rho_1\pi(n_1,n_2-1)/1 = \mu_1\rho_1\pi(n_1,n_2)/\rho_2 = \lambda\pi(n_1,n_2)/\rho_2 = \lambda\mu_2\pi(n_1,n_2)/\lambda = \mu_2\cdot\rho_1\cdot\pi(n_1,n_2)/\rho_2$. Let us be more careful. $\mu_1\pi(n_1+1,n_2-1) = \mu_1(1-\rho_1)\rho_1^{n_1+1}(1-\rho_2)\rho_2^{n_2-1} = \mu_1\rho_1/\rho_2 \cdot \pi(n_1,n_2) = \lambda/\rho_2\cdot\pi(n_1,n_2) = \lambda\mu_2/\lambda\cdot\pi(n_1,n_2)$. Hmm, $\lambda/\rho_2 = \lambda\mu_2/\lambda = \mu_2$. So $\mu_1\pi(n_1+1,n_2-1) = \mu_2\cdot\rho_1\cdot\pi(n_1,n_2)/\rho_2$...

Let us redo cleanly. $\mu_1\pi(n_1+1,n_2-1) = \mu_1\cdot\rho_1\cdot(1/\rho_2)\cdot\pi(n_1,n_2)$. $\mu_1\rho_1 = \lambda$ and $1/\rho_2 = \mu_2/\lambda$, so the product is $\mu_2\pi(n_1,n_2)$.

• $\mu_2\pi(n_1,n_2+1) = \mu_2\rho_2\pi(n_1,n_2) = \lambda\pi(n_1,n_2)$.

Total rate in: $(\mu_1 + \mu_2 + \lambda)\pi(n_1,n_2)$ = rate out. $\checkmark$ $\blacksquare$

Using the recursion $B(A, k) = AB(A,k-1)/(k + AB(A,k-1))$ with $A = 20$: Iterating from $B(20,0) = 1$: $B(20, 25) \approx 0.0354$, $B(20, 27) \approx 0.0167$, $B(20, 28) \approx 0.0112$, $B(20, 29) \approx 0.0074$.

So $c = 29$ channels are needed for $B \leq 1\%$.

The Erlang-B blocking probability for large $A$ can be approximated by noting that the Poisson$(A)$ distribution is approximately normal: $B(A, c) \approx Q\left(\frac{c - A}{\sqrt{A}}\right)$ (after proper continuity correction and accounting for the truncation).

Setting $B = B_{\text{target}}$: $Q((c-A)/\sqrt{A}) = B_{\text{target}}$, so $c \approx A + \sqrt{A}\,Q^{-1}(B_{\text{target}})$.

For $A = 20$, $B = 0.01$: $Q^{-1}(0.01) \approx 2.326$. $c \approx 20 + \sqrt{20}\times 2.326 = 20 + 10.4 \approx 30.4$, so $c = 31$. The approximation slightly overestimates (exact: $c = 29$), but gives the right scaling: $c = A + O(\sqrt{A})$. $\blacksquare$