Simulate M/M/1 and verify the utilisation wall

CodingIntermediate⏱ 1 hourAI Systemssimulationqueueinglittle's lawutilisation

Theory: Queueing and the Utilisation Wall →

Problem

Implement the closed forms for M/M/1 and a discrete-event simulation of the same queue, then check they agree.

theoretical_mm1(lam, mu) returning $\rho$ , $\E[W]$ , $\E[W_q]$ and $\E[N]$ .
simulate_mm1(lam, mu, n_requests, seed) returning the same four quantities measured from a first-come-first-served simulation.

Measure $\E[N]$ from the simulation independently — as the time-average occupancy — rather than computing it as $\lambda\E[W]$ . Little's law should then fall out of the measurements as a check, instead of being assumed.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here8 tests · Python runs in your browser

import numpy as np

def theoretical_mm1(lam, mu):
    """Closed-form M/M/1 quantities for arrival rate lam and service rate mu.

Return a dict with keys:
      'rho'        utilisation lam/mu
      'mean_wait'  E[W], time in system
      'mean_queue' E[W_q], time waiting before service starts
      'mean_number' E[N], number in system
    Assume lam < mu.
    """
    raise NotImplementedError

def simulate_mm1(lam, mu, n_requests=20000, seed=0):
    """Simulate a first-come-first-served M/M/1 queue.

Draw n_requests exponential inter-arrival times with rate lam and
    exponential service times with rate mu from a generator seeded with
    `seed`. Serve in arrival order on a single server. Return a dict with the
    same four keys, measured from the simulation:

'rho'         fraction of the simulated horizon the server was busy
      'mean_wait'   mean of (departure - arrival)
      'mean_queue'  mean of (service start - arrival)
      'mean_number' time-average number in system, computed as an integral
                    over the horizon rather than by sampling
      'horizon'     the length of the simulated interval, i.e. the last
                    departure time
      'n'           the number of requests simulated

Little's law should come out of the simulation rather than being assumed:
    compute 'mean_number' from the occupancy of the system, not as lam times
    'mean_wait'. Done properly, L * horizon equals n * mean_wait exactly —
    that is the area identity, and the tests check it to machine precision.
    """
    raise NotImplementedError

⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser

8 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Apply Little's law to a serving target	LLM Ops	Proof	Intermediate	30 min
Balls into bins, with one choice and with two run	AI Systems	Coding	Intermediate	1 hour
Cache hit rates under Zipf popularity run	AI Systems	Coding	Intermediate	1 hour
Derive the M/M/1 queue from detailed balance	AI Systems	Proof	Intermediate	1 hour

Problem

Write it

Hints

Solution

Related problems