Theorem 2 — for and for
ProvedJSQHalfinWhitt.Tightness.theorem_2Consider the join-the-shortest-queue system with identical exponential servers, Poisson arrivals of rate and the Halfin–Whitt scaling , . Let have a stationary distribution of the chain, being the number of servers with at least customers, and set and for .
For each there exists a constant such that for all (with ) and every stationary distribution of the chain,
The theorem says that, uniformly in the number of servers, the stationary number of idle servers and of servers with at least two customers are on average, and the stationary number of servers with at least customers is on average. It gives tightness of the diffusion-scaled stationary distributions , one of the two ingredients for the convergence of stationary distributions to the diffusion limit (Proposition 1).
Formalization Note The printed display of Theorem 2 omits the expectation ( and ); read as almost-sure bounds these are false, since with positive stationary probability. The intended statement, proved in the paper, bounds expectations: (1.3) on p. 2 states and , p. 7 computes , p. 10 bounds , and App. A.4 (p. 22) opens with "Our goal is to prove (2.3), or that ". That version is stated. The model needs , i.e. ; for there is no model. The constant is chosen after and before , and . The stationary distribution is a probability on with global balance , which for this bounded-rate chain characterizes stationarity; expectations are sums against of bounded functions (), so they always converge. Lean indices are 0-based: q.1 0 is , q.1 1 is , and q.1 i with is , so (2.3) is the Lean range .
import Mathlib import Definitions.Def_JSQHalfinWhitt_Tightness_Stationary import Definitions.Def_JSQHalfinWhitt_Tightness_Model
namespace JSQHalfinWhitt.Tightness
/-- Theorem 2 (Braverman, p. 5), with the expectation that the printed display omits: for each
`β > 0` there is a constant `C(β)` such that for every `n ≥ 1` with `β < √n` (so that
`λ = 1 − β/√n > 0`) and every stationary distribution `π` of the `n`-server JSQ chain with
`λ = 1 − β/√n`, `E|√n X_i| ≤ C(β)` for `i = 1, 2` (2.2) and `E|n X_i| ≤ C(β)` for `i ≥ 3` (2.3),
where `X_1 = (Q_1 − n)/n` and `X_i = Q_i/n` for `i ≥ 2`. Lean indices are 0-based: `q.1 0` is
`Q_1`, `q.1 1` is `Q_2`, and `q.1 i` with `i ≥ 2` is `Q_{i+1}`. -/
theorem theorem_2 (β : ℝ) (hβ : 0 < β) :
∃ C : ℝ, ∀ n : ℕ, 1 ≤ n → β < Real.sqrt n →
∀ π : State n → ℝ, IsStationaryDist (genQ n (lamHW β n)) π →
(expect π (fun q => |Real.sqrt n * (((q.1 0 : ℝ) - n) / n)|) ≤ C ∧
expect π (fun q => |Real.sqrt n * ((q.1 1 : ℝ) / n)|) ≤ C) ∧
∀ i : ℕ, 2 ≤ i → expect π (fun q => |(n : ℝ) * ((q.1 i : ℝ) / n)|) ≤ C := by sorry
end JSQHalfinWhitt.Tightness
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.