東京大学 情報理工学系研究科 創造情報学専攻 2026年2月実施 筆記試験 第2問

标签：

• Tokyo-University
• Birth-Death-Process
• M-M-1-Queue
• Littles-Law
• Average-Waiting-Time

Author

itsuitsuki

Description

Memorized version (English)

Consider a server that can only handle one request at a time.

• Requests arrive continuously at an arrival rate of $\lambda$.
• The service rate for processing a request is $\mu$.
• We define the probabilities for a very small time interval $\Delta t$ as follows:
  • The probability of a new arrival is $\lambda \Delta t$.
  • The probability of completing the current task (service completion) is $\mu \Delta t$.
  • The probability of more than one event occurring (e.g., two arrivals, or one arrival and one departure) in this interval is negligible ($o(\Delta t)$).

Let $P_n(t)$ be the probability that there are $n$ requests in the system (waiting + being served) at time $t$. The boundary condition for an empty system is given by:

$$P_0(t+\Delta t) = P_0(t)(1 - \lambda \Delta t) + P_1(t) \mu \Delta t$$

Answer the following questions.

(1) For $n \ge 1$, derive the expression for $P_n(t+\Delta t)$ in terms of $P_{n-1}(t)$, $P_n(t)$, and $P_{n+1}(t)$.

(2) Assuming the system reaches a Steady State (where $P_n(t)$ does not change with time as $t \to \infty$), find the recurrence relation for $P_n$.

(3) Let the utilization rate be $\rho = \lambda / \mu$. Using the normalization condition $\sum_{n=0}^{\infty} P_n = 1$, find the explicit expression for $P_n$.

(4) Find the expected number of requests in the system, denoted as $L$. You can use the fact that $\sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}$ for $0 < x < 1$.

(5) Using Little's Law ($L = \lambda W$, where $W$ is the average time a request spends in the system), find the expression for $W$.

(6) Analyze what happens to $W$ as $\rho$ approaches 1.

Suppose the total cost is given by $Cost = C_s + L \times C_d$, where $C_s$ is the fixed cost of the server and $C_d$ is the delay cost per request per unit of time.

(7) Given: $\mu=10$, $\lambda=8$, $C_s=10$, $C_d=5$. Calculate the total cost.

(8) An enhancement is proposed: $\mu$ can be increased to 12, but the fixed cost $C_s$ will increase to 15. Calculate the new total cost and determine if this change is economically rational.

题目描述

本页原文标为“英文回忆版”。考虑一次只能处理一个请求的服务器：请求以到达率 (\lambda) 连续到来，服务率为 (\mu)。在很小时间 (\Delta t) 内，新到达概率为 (\lambda\Delta t)，当前服务完成概率为 (\mu\Delta t)，两个以上事件（如两次到达，或到达与离开同时发生）的概率可忽略，记为 (o(\Delta t))。令 (P_n(t)) 为时刻 (t) 系统中（等待加服务中）共有 (n) 个请求的概率。空系统边界式为 [ P_0(t+\Delta t)=P_0(t)(1-\lambda\Delta t)+P_1(t)\mu\Delta t. ]

1. 对 (n\ge1)，用 (P_{n-1}(t),P_n(t),P_{n+1}(t)) 写出 (P_n(t+\Delta t))。
2. 假设 (t\to\infty) 达到稳态，即 (P_n(t)) 不再随时间变化，求 (P_n) 的递推关系。
3. 定义利用率 (\rho=\lambda/\mu)。利用归一化 (\sum_{n=0}^\infty P_n=1)，求 (P_n) 的显式表达式。
4. 求系统内请求数期望 (L)。可使用 [ \sum_{n=0}^\infty nx^n=\frac{x}{(1-x)^2},\qquad0<x<1. ]
5. 用 Little 定律 (L=\lambda W) 求请求在系统中平均逗留时间 (W)。
6. 分析 (\rho\to1) 时 (W) 的变化。

总成本定义为 [ Cost=C_s+LC_d, ] 其中 (C_s) 是服务器固定成本，(C_d) 是每个请求、每单位时间的延迟成本。

7. 给定 (\mu=10,\lambda=8,C_s=10,C_d=5)，计算总成本。
8. 若把 (\mu) 提升到 12，但固定成本 (C_s) 增至 15，计算新总成本并判断该升级在经济上是否合理。

考点

• M/M/1 生灭过程：从小时间区间事件概率建立前向平衡方程与稳态递推。
• 稳态队长分布：在 (\rho<1) 下用归一化得到几何分布并计算平均系统人数。
• Little 定律与平均等待时间：由 (L=\lambda W) 推导平均逗留时间，解释利用率逼近 1 时发散。
• 容量成本权衡：比较提高服务率前后的固定成本和拥塞延迟成本。

Kai (by Gemini 3 Pro)

1. Derivation of $P_n(t+\Delta t)$

To have $n$ requests at time $t+\Delta t$ (where $n \ge 1$), one of three mutually exclusive events must have occurred during the interval $\Delta t$:

1. No change: There were $n$ requests at time $t$, and no new arrivals or departures occurred. Probability: $P_n(t) \cdot (1 - \lambda \Delta t - \mu \Delta t)$
2. One Arrival: There were $n-1$ requests at time $t$, and one new request arrived. Probability: $P_{n-1}(t) \cdot (\lambda \Delta t)$
3. One Departure: There were $n+1$ requests at time $t$, and one request was served. Probability: $P_{n+1}(t) \cdot (\mu \Delta t)$

Combining these gives:

$$P_n(t+\Delta t) = P_n(t)(1 - \lambda \Delta t - \mu \Delta t) + P_{n-1}(t)\lambda \Delta t + P_{n+1}(t)\mu \Delta t$$

2. Recurrence Relation

Rearrange the equation from Q1 and divide by $\Delta t$:

$$\frac{P_n(t+\Delta t) - P_n(t)}{\Delta t} = -(\lambda + \mu)P_n(t) + \lambda P_{n-1}(t) + \mu P_{n+1}(t)$$

Take the limit as $\Delta t \to 0$. The left side becomes the derivative $\frac{dP_n(t)}{dt}$. In the Steady State, probabilities are constant, so $\frac{dP_n(t)}{dt} = 0$. Let $P_n(t) = P_n$.

$$0 = -(\lambda + \mu)P_n + \lambda P_{n-1} + \mu P_{n+1}$$

$$(\lambda + \mu)P_n = \lambda P_{n-1} + \mu P_{n+1}$$

This represents the global balance equations. It implies that the rate of entering state $n$ equals the rate of leaving state $n$. It simplifies to the local balance equation (Rate Up = Rate Down):

$$\lambda P_n = \mu P_{n+1}$$

$$P_{n+1} = \frac{\lambda}{\mu} P_n = \rho P_n$$

3. Explicit Expression for $P_n$

From the recurrence relation $P_{n+1} = \rho P_n$, we can see this is a geometric sequence:

$$P_n = \rho^n P_0$$

Using the normalization condition that the sum of all probabilities is 1:

$$\sum_{n=0}^{\infty} P_n = \sum_{n=0}^{\infty} \rho^n P_0 = P_0 \sum_{n=0}^{\infty} \rho^n = 1$$

Using the geometric series sum formula (assuming $\rho < 1$ for stability):

$$P_0 \cdot \frac{1}{1-\rho} = 1 \implies P_0 = 1 - \rho$$

Substituting back:

$$P_n = (1 - \rho)\rho^n$$

4. Average Number of Requests ($L$)

$$L = E[n] = \sum_{n=0}^{\infty} n P_n = \sum_{n=0}^{\infty} n (1-\rho)\rho^n$$

$$L = (1-\rho) \sum_{n=0}^{\infty} n \rho^n$$

Using the given hint $\sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}$ with $x = \rho$:

$$L = (1-\rho) \cdot \frac{\rho}{(1-\rho)^2}$$

$$L = \frac{\rho}{1 - \rho}$$

5. Average Waiting Time ($W$)

Using Little's Law: $L = \lambda W$.

$$W = \frac{L}{\lambda} = \frac{1}{\lambda} \cdot \frac{\rho}{1-\rho}$$

Since $\rho = \lambda / \mu$:

$$W = \frac{1}{\lambda} \cdot \frac{\lambda/\mu}{1 - \lambda/\mu} = \frac{1}{\lambda} \cdot \frac{\lambda}{\mu - \lambda}$$

$$W = \frac{1}{\mu - \lambda}$$

6. Behavior when $\rho \to 1$

As $\rho \to 1$ (which means $\lambda \to \mu$):

$$W = \frac{1}{\mu(1-\rho)}$$

The denominator approaches 0. Therefore, $W \to \infty$. This implies that as the arrival rate approaches the service capacity, the average time a request spends in the system grows asymptotically to infinity (the system becomes unstable).

7. Cost Calculation (Current State)

Parameters:

• $\mu = 10$
• $\lambda = 8$
• $C_s = 10$
• $C_d = 5$

Calculate $\rho$ and $L$:

$$\rho = \frac{8}{10} = 0.8$$

$$L = \frac{0.8}{1 - 0.8} = \frac{0.8}{0.2} = 4$$

Calculate Total Cost:

$$Cost_{current} = C_s + L \times C_d = 10 + 4 \times 5 = 10 + 20 = 30$$

The current total cost is 30.

8. Enhancement Evaluation

New Parameters:

• $\mu' = 12$
• $\lambda = 8$ (unchanged)
• $C_s' = 15$
• $C_d = 5$ (unchanged)

Calculate new $\rho'$ and $L'$:

$$\rho' = \frac{8}{12} = \frac{2}{3}$$

$$L' = \frac{2/3}{1 - 2/3} = \frac{2/3}{1/3} = 2$$

Calculate New Total Cost:

$$Cost_{new} = C_s' + L' \times C_d = 15 + 2 \times 5 = 15 + 10 = 25$$

Comparison:

• Original Cost: 30
• New Cost: 25

Conclusion: Since $25 < 30$, the total cost is reduced.

Therefore, the enhancement is economically rational.