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

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 .
• The service rate for processing a request is .
• We define the probabilities for a very small time interval as follows:
  • The probability of a new arrival is .
  • The probability of completing the current task (service completion) is .
  • The probability of more than one event occurring (e.g., two arrivals, or one arrival and one departure) in this interval is negligible ().

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

Answer the following questions.

(1) For , derive the expression for in terms of , , and .

(2) Assuming the system reaches a Steady State (where does not change with time as ), find the recurrence relation for .

(3) Let the utilization rate be . Using the normalization condition , find the explicit expression for .

(4) Find the expected number of requests in the system, denoted as . You can use the fact that for .

(5) Using Little's Law (, where is the average time a request spends in the system), find the expression for .

(6) Analyze what happens to as approaches 1.

Suppose the total cost is given by , where is the fixed cost of the server and is the delay cost per request per unit of time.

(7) Given: , , , . Calculate the total cost.

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

Kai (by Gemini 3 Pro)

1. Derivation of

To have requests at time (where ), one of three mutually exclusive events must have occurred during the interval :

1. No change: There were requests at time , and no new arrivals or departures occurred. Probability:
2. One Arrival: There were requests at time , and one new request arrived. Probability:
3. One Departure: There were requests at time , and one request was served. Probability:

Combining these gives:

2. Recurrence Relation

Rearrange the equation from Q1 and divide by :

Take the limit as . The left side becomes the derivative . In the Steady State, probabilities are constant, so . Let .

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

3. Explicit Expression for

From the recurrence relation , we can see this is a geometric sequence:

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

Using the geometric series sum formula (assuming for stability):

Substituting back:

4. Average Number of Requests ()

Using the given hint with :

5. Average Waiting Time ()

Using Little's Law: .

Since :

6. Behavior when

As (which means ):

The denominator approaches 0. Therefore, . 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:

Calculate and :

Calculate Total Cost:

The current total cost is 30.

8. Enhancement Evaluation

New Parameters:

• (unchanged)
• (unchanged)

Calculate new and :

Calculate New Total Cost:

Comparison:

• Original Cost: 30
• New Cost: 25

Conclusion: Since , the total cost is reduced.

Therefore, the enhancement is economically rational.