Recover Little's law from an event log

CodingIntermediate⏱ 1 hourAI Systemslittle's lawevent logoccupancymeasurement

Theory: Little's Law and the Capacity of a Serving System →

Problem

Given arrival and departure timestamps for a set of requests, reconstruct the three quantities in Little's law and verify the identity numerically.

number_in_system(arrivals, departures, times) — occupancy at each queried instant, with an item present on $[a_i, d_i)$ .
time_average_number(arrivals, departures) — the exact time-average occupancy over $[0,T]$ with $T$ the last departure, computed from the area identity rather than by sampling.
littles_law_check(arrivals, departures) — returning $L$ , $\lambda$ , $W$ and the residual $L - \lambda W$ .

The residual should be zero to machine precision, not merely small.

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

Write it

Solve it here7 tests · Python runs in your browser

import numpy as np

def number_in_system(arrivals, departures, times):
    """Occupancy at each instant in `times`.

`arrivals[i]` and `departures[i]` are the entry and exit times of item i,
    with departures[i] >= arrivals[i]. Item i counts as present at time t when
    arrivals[i] <= t < departures[i]. Return an integer array the same length
    as `times`.
    """
    raise NotImplementedError

def time_average_number(arrivals, departures):
    """The exact time-average occupancy over [0, T], T = max(departures).

Compute it from the area identity rather than by sampling: the integral of
    the occupancy equals the total time items spent in the system.
    """
    raise NotImplementedError

def littles_law_check(arrivals, departures):
    """Return a dict with 'L', 'lam', 'W' and 'residual'.

L is the time-average occupancy, lam the arrival rate over [0, T], W the
    mean time in system, and residual = L - lam*W, which the law says is zero.
    """
    raise NotImplementedError

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

7 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
Apply Little's law to a serving target	LLM Ops	Proof	Intermediate	30 min
Prove Little's law on a finite horizon	AI Systems	Proof	Intermediate	1 hour
Simulate M/M/1 and verify the utilisation wall run	AI Systems	Coding	Intermediate	1 hour

Problem

Write it

Hints

Solution

Related problems