Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The equilibrium distribution of an M/M/1 queue

Proved
KellyStochasticNetworks.mm1_equilibrium

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainqueueing-theorystochastic-networks

An M/M/1 queue has a Poisson arrival stream of rate λ\lambdaλ, a single server, and independent exponential service times of parameter μ\muμ. Writing X(t)X(t)X(t) for the number of customers present, including the one in service, XXX is a Markov process on {0,1,2,… }\{0, 1, 2, \dots\}{0,1,2,…} with transition rates

q(j,j+1)=λ(j≥0),q(j,j−1)=μ(j≥1).q(j, j+1) = \lambda \quad (j \ge 0), \qquad q(j, j-1) = \mu \quad (j \ge 1).q(j,j+1)=λ(j≥0),q(j,j−1)=μ(j≥1).

Suppose 0<λ<μ0 < \lambda < \mu0<λ<μ and write ρ=λ/μ\rho = \lambda/\muρ=λ/μ for the traffic intensity. Then the geometric distribution

π(j)=(1−ρ)ρ j,j=0,1,2,…,\pi(j) = (1-\rho)\rho^{\,j}, \qquad j = 0, 1, 2, \dots,π(j)=(1−ρ)ρj,j=0,1,2,…,

satisfies the detailed balance equations for these rates, and its terms sum to 111. It is therefore the equilibrium distribution of the queue, and the queue is reversible.

The two conclusions are stated together because either alone is weaker than the claim: detailed balance is satisfied by every positive multiple of π\piπ, while summing to 111 says nothing about the dynamics.

Formalization Note The hypothesis λ<μ\lambda < \muλ<μ is exactly what makes the geometric series converge, and it is the stability condition for the queue. Convergence and the value of the sum are asserted together.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Balance
import Definitions.Def_KellyStochasticNetworks_Migration
Formal statement
namespace KellyStochasticNetworks

theorem mm1_equilibrium (lam mu : ℝ) (hlam : 0 < lam) (hmu : lam < mu) :
    DetailedBalance (fun j : ℕ => (1 - lam / mu) * (lam / mu) ^ j) (mm1Rates lam mu)
      ∧ HasSum (fun j : ℕ => (1 - lam / mu) * (lam / mu) ^ j) 1 := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 22 (PDF p. 30), section 2.1: 'If the arrival rate lambda is less than the service rate mu, the distribution pi(j) = (1 - rho) rho^j, j = 0, 1, ..., satisfies the detailed balance equations (1.4) and is thus the equilibrium distribution, where rho = lambda/mu is the traffic intensity.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me