Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds Hao Liang∗
Cheng Tang∗
Yunzong Xu∗
arXiv:2606.18218v1 [math.PR] 16 Jun 2026
University of Illinois Urbana–Champaign {hliang17,chengt6,xyz}@illinois.edu
Abstract We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, time-varying, and adapted to the past; the standing load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.
1
Introduction
Stochastic networks [9, 26, 4] model systems in which many queues compete for shared service resources: cloud clusters allocate compute capacity to jobs, AI inference platforms allocate accelerator capacity to requests, packet switches match input ports to output ports, and wireless systems allocate time-frequency resources to users. Classical performance measures—throughput, stability, steady-state backlog, and time-average cost—describe what a network can sustain in the long run. Yet many modern systems operate over finite planning windows, under bursty and highly uncertain demand, with scarce shared capacity and tight service-level requirements. In this regime, even a brief congestion episode can constitute an operational failure: a GPU queue spike can cause missed training or inference deadlines; a burst of inference requests can violate latency guarantees; and a congested port or wireless bottleneck can trigger packet drops, delay spikes, or costly intervention, even when long-run averages remain benign. This motivates a foundational finite-horizon question about extremes: over the next T slots, how large can the backlog become? We study this question in the discrete-time generalized switch of Stolyar [23], a canonical stochastic-network model that represents service constraints through a general capacity geometry. ∗
Authors are listed alphabetically.
1
We retain this geometric framework but embed it in more flexible dynamics. Arrivals may be dependent, time-varying, and adapted to the past: the next-slot arrival law may depend arbitrarily on the observed history, as in feedback-driven traffic where demand or routing reacts to recent congestion. Service may also be random after the scheduling decision, so the realized service in a slot may fluctuate around the chosen feasible rate. Starting from Q0 = 0, we seek explicit guarantees for PeakT := max ∥Qt ∥2 , 0≤t≤T
the largest backlog observed up to time T . The load condition requires only that the one-step conditional mean arrival vector remain uniformly ε inside the capacity region—the set of arrival rates that the service resources can sustain on average. The problem is therefore genuinely nonstationary and nonasymptotic: a steady state need not exist, the arrival law may change with the history, and the guarantee must control queue peaks for every finite T . Finite-time control of queue peaks has important precursors in the stochastic-network literature. Shah, Tsitsiklis, and Zhong [18, 20] proved maximal-excursion inequalities for Bernoulli switched networks and bandwidth-sharing networks under time-homogeneous arrivals. These analyses, however, are restricted to fixed stochastic input laws and specialized capacity geometries, rather than the adapted-arrival setting with general capacity geometry considered here. The closest starting point for the present paper is Liu, Tan, and Xu [12], which placed the peak question on a minimax, online-learning footing. Their framework accommodates √ general capacity geometry, time-varying arrivals, and post-decision random service, and yields a T upper bound on PeakT .1 That rate is sharp at the boundary of the capacity region: when ε = 0 and there is no interior slack to exploit, √ it is the correct robust law. But when the system operates strictly inside capacity, a persistent T description can be overly pessimistic, since it still permits the backlog to grow polynomially with the horizon despite sustained slack. Classical queueing, scheduling, and stochastic-network theory point toward a much sharper picture, but they address a different question. The MaxWeight policy of Tassiulas and Ephremides [24] showed that interior slack ε > 0 is sufficient for stability, and subsequent heavy-traffic and diffusion theory for generalized switches and processing networks identified how bottleneck geometry governs steady-state performance [23, 13, 14, 15, 26]. These results form the standard asymptotic picture: positive recurrence, steady-state or time-average bounds, and diffusion limits, typically derived under time-homogeneous or Markovian input models. They do not, however, answer the finite-time question that motivates this paper: under adapted, nonstationary arrivals, how large can the backlog grow before time T , with high probability? This gap is not cosmetic. A bounded steady-state mean controls an average, not the largest excursion along a finite sample path. The operational horizon may be shorter than the time needed to approach steady state, and in a time-varying environment there may be no relevant steady state at all. The peak question therefore does not merely call for a new interpretation of classical theory; it requires a genuinely new finite-time theory. Such a theory should retain the generality and strengths of the recent finite-time viewpoint of Liu, Tan, and Xu [12]—distribution-free over adapted arrivals, explicit in the horizon, and stated directly for the running maximum—while sharply capturing the slack- and geometry-sensitive behavior that classical queueing theory identifies as central.
1.1
Our contributions
We develop a finite-time theory of queue peak laws under interior slack. Our upper bounds are 1
The √ statements in [12] impose independence across time. Theorem 2.2 in Section 2 records the direct extension of their T guarantee to the adapted-arrival setting considered here.
2
achieved using the MaxWeight policy [24],2 while our lower bounds hold for every scheduling policy. Together, they identify the structure of optimal finite-time peak behavior, summarized below. A new two-phase √ characterization. The first message is a two-phase law enabled by interior slack. The robust T law of [12] remains the right slack-free characterization, but under interior slack it becomes only a burn-in upper envelope: once the queue length exceeds a threshold, the queue peak grows only logarithmically. For MaxWeight, our characterization implies3 √ D D2 , D := Amax + Smax . (1) E[PeakT ] ≲ min D T , log(T + 1) + ε εα(Π) Here Amax and Smax bound the one-slot realized arrival and service norms, ε is the interior slack, and α(Π) is the global service margin—the smallest projected service capacity over nonnegative unit directions—associated with the capacity region Π. The term D2 /(εα(Π)) is the threshold. Above it, running the process longer costs only (D/ε) log T . See Figure 1 for an illustration. The upper bound is complemented by √ policy-independent lower bounds. A one-dimensional reflected walk shows that both the initial T regime and the later log T regime are unavoidable. A separate deterministic construction shows that no theorem at this level of generality can eliminate geometric dependence, such as α(Π), from the threshold. Thus, the structure of (1) is essentially sharp: any general finite-time peak law must include a burn-in envelope, a logarithmic envelope, and a geometric threshold. Conversely, (1) should be √ interpreted as a universal upper envelope, not as a claim that every instance undergoes an exact T -to-log T transition. Geometry-free logarithms via self-normalization. A notable feature of (1) is that the logarithmic coefficient D/ε is geometry-free: it is universal over capacity geometries and, in particular, independent of α(Π). This is not a generic consequence of classical stability. A direct Lyapunov drift argument would typically carry global geometry into the logarithmic term. MaxWeight avoids this loss through self-normalization. In the current queue direction ut = Qt /∥Qt ∥2 , it attains the projected service capacity H(ut ): the stabilizing drift is of order εH(ut ), while the projected fluctuation scale is controlled by DH(ut ). Since the same factor H(ut ) controls both drift and fluctuation, a directional exponential-supermartingale calculation cancels it, yielding the universal coefficient D/ε. Geometry governs the threshold at which self-normalization becomes effective, not the logarithmic growth after that threshold. A classical queueing reader may expect logarithmic growth of running maximum from an exponential steady-state tail [18, 20]. The point here is that this intuition extends to a finite-time, distribution-free, geometry-agnostic form. The coefficient D/ε holds without asymptotics, heavy traffic, stationarity, or even the existence of a steady state, and it holds uniformly over all capacity geometries. Thus the logarithmic law is not merely a steady-state consequence; it is a new finite-time principle. Improved geometric thresholds via state-space collapse. In (1), self-normalization has already removed geometry from the logarithmic coefficient; the remaining geometric cost appears only through the entrance threshold D2 /(εα(Π)). This raises a natural question: is the global 2
More broadly, the main upper bound extends to any scheduling policy satisfying the directional certificate in Remark 2.2. This includes the LyapOpt policy [12]. 3 [12] shows that MaxWeight’s dependence on Smax is fundamental when ε = 0, whereas its LyapOpt policy avoids √ this dependence in the T law. Our paper focuses on optimizing the dependence on T , ε, and α(Π). Whether another policy can improve the Amax and Smax -dependence over MaxWeight is an interesting future direction.
3
margin α(Π) the right complexity measure for a given network? For fully uniform guarantees it is, but it can be overly conservative: it protects against all nonnegative directions, including directions that the queue process may never visit. State-space collapse (SSC) [17] is the classical phenomenon whereby a high-dimensional queueing process remains close to a lower-dimensional bottleneck set. In this sense, SSC is an adaptive form of dimension reduction induced by network geometry. Under a quantitative finite-time complete resource pooling (CRP) condition [23, 5], we show that this collapse can be converted directly into a sharper peak law: the global worst-direction margin α(Π) in the entrance threshold is replaced by the local geometry of the active bottleneck face, together with the finite-time collapse error needed to keep the queue near that face. Thus, SSC provides a principled way to replace global worst-case geometry by the geometry actually seen by the queue, without relying on asymptotics or i.i.d./Markovian input laws. This finite-time, nonstationary extension of SSC is a methodological contribution of independent interest. Application to input-queued switches and beyond. We instantiate the framework on input-queued switches (IQS), a canonical model for wireless scheduling and internet routing. In a generalized IQS model allowing adversarial, dependent, and fractional arrivals, we prove matching upper and lower bounds for the logarithmic coefficient of the total-backlog peak. The bounds become sharper under the quantitative CRP geometry, and also under independent Bernoulli arrivals. Simulations for IQS and for more general parallel-server networks closely track the theory, illustrating the two-phase envelope, the gains from local geometry, and the variance-sensitive improvements.
T burn-in envelope
peak scale
√
ε−1 log T + threshold
horizon T Figure 1: An illustration √ of the two-phase upper envelope given by (1). The red dashed curve represents the slack-free T burn-in envelope from Theorem 2.2. The blue dotted curve represents the slack-sensitive logarithmic envelope from Corollary 2.1, shifted by the queue-length threshold D2 /(εα(Π)). The black curve illustrates a possible realized √ or typical growth pattern of the queue peak as the horizon T increases; we do not claim an exact T -to-log T transition for every instance.
1.2
Relation to prior work
This paper sits at the intersection of two complementary viewpoints. Classical stochastic-network theory captures the roles of slack, bottlenecks, and capacity geometry, but mainly through asymptotic, stationary, or steady-state guarantees: the MaxWeight and heavy-traffic literatures study stability, time averages, steady-state backlog, tails, and diffusion limits, typically under fixed or Markovian input laws [24, 23, 13, 14, 15, 26, 4]. Recent finite-time peak theory asks the right sample-path question, but existing results either rely on fixed input laws and specialized geometries [18, 20], 4
√ or apply in much greater generality while giving a robust T envelope rather than a slack- and geometry-sensitive logarithmic law [12]. We show that the two perspectives can be combined: under adapted arrivals, interior slack and bottleneck geometry yield finite-time peak bounds that cross √ over from a T burn-in to log T growth after a geometric entrance threshold. For this reason, the classical literature enters our results mainly through geometry. The global margin α(Π) is the finite-time analogue of a worst bottleneck direction in a generalized switch. In the input-queued-switch results, we use more refined bottleneck geometry from the steady-state and heavy-traffic literature on complete resource pooling, saturation structure, and state-space collapse [5, 22, 21, 13, 14, 27]. The use is different: those works identify where the queue concentrates in steady state or heavy traffic; here the same geometry sharpens finite-time bounds for the running maximum under non-stationarity. The logarithmic scale also has a familiar queueing interpretation. Exponential steady-state tails suggest that the maximum over a long stationary window should grow on the order of log T . Our theorem has the same extreme-value scale, but it does not come from stationarity: the logarithm is produced directly by self-normalized drift analysis along a finite path. Remark 2.1 makes this comparison precise. A distinct finite-time perspective was recently developed by [16] for the Erlang-C, or M/M/n, queue. They establish quantitative convergence to steady state in χ2 -distance and use these mixing estimates to obtain finite-time bounds on time-average queue lengths and fixed-time tails across many-server heavy-traffic regimes. Their results address when steady-state approximations become valid for a reversible birth-death queue. Our question is complementary: rather than estimating convergence to equilibrium, we directly bound the running maximum of a finite-horizon sample path. Moreover, in our adapted-arrival model, a stationary distribution need not exist, and our results apply to more general controlled stochastic networks.4 Worst-case approaches such as adversarial queueing and network calculus [1, 11] provide another form of finite-time robustness. They deliberately avoid slack conditions, and therefore give robust envelopes rather than the slack-sensitive logarithmic law proved here. Finally, the paper also points to a useful bridge between online learning [2, 7] and queueing [25]. Online learning supplies the finite-time standard: guarantees should hold along a single path, with minimal probabilistic structure, and with rates governed by the complexity of the instance or instance family. Queueing supplies a different set of ideas: persistent state, negative drift, bottleneck geometry, and collapse. The generalized switch is a natural meeting point. Actions create future state, as in reinforcement learning and control, but the feasible actions retain enough geometric structure to permit sharp pathwise guarantees. From this viewpoint, [12] gives the minimax theory of queue peaks. The present paper gives√ the sharper instance-dependent theory: under interior slack and the right geometry, the worst-case T scale gives way to log T .
1.3
Organization and notation
Section 2 states the main upper and lower bounds and gives the two-phase envelope for finite-time queue peaks. The resulting characterization isolates three fundamental features: square-root burnin, geometry-free logarithmic growth, and a geometry-dependent entrance threshold. Section 3 explains why the logarithmic coefficient is geometry-free through self-normalization, and identifies queue-Bernstein conditions as a natural unbounded-arrival class for which this mechanism survives. Section 4 shows how state-space collapse can sharpen the geometric threshold: a two-queue example illustrates how favorable local geometry removes the global margin, and the CRP theorem converts 4 Technically, our direct peak analysis also avoids the large cold-start prefactor that arises when χ2 -mixing bounds are used to convert fixed-time tail estimates into running-maximum bounds.
5
finite-horizon collapse into a local peak law. Section 5 specializes the framework to generalized input-queued switches, proving sharp logarithmic peak bounds in the robust model, CRP refinements, and a variance-sensitive Bernoulli bound. Section 6 reports simulations of the predicted two-phase envelope, the gap between global and local geometry, and the effects of bottleneck structure and arrival variance. Section 7 closes with the main open directions. We use the following global conventions. Vector inequalities are coordinatewise, x+ denotes coordinatewise projection onto Rd+ , ⟨·, ·⟩ is the Euclidean inner product, and ∥·∥p is the ℓp norm. Throughout, c and C denote positive universal numerical constants that may change from line to line. We write f ≲ g, f ≳ g, and f ≍ g to mean f ≤ Cg, f ≥ cg, and cg ≤ f ≤ Cg, respectively. Model-specific notation is introduced in Section 2.
2
Model and main results
We work with a discrete-time generalized switch [23] starting from Q0 = 0. At each slot, the scheduler chooses from a finite set S ⊂ Rd+ of feasible mean-service vectors. Building on the general formulation of [12], we allow arrivals to be time-varying, and further allow them to be dependent and adapted to the past; realized service is observed only after the scheduling decision. This pathwise formulation departs from the classical generalized-switch setting, which typically assumes i.i.d. arrivals and pre-decision service randomness [23, 8]. In this sense, the model is also a stateful online learning problem; see Section 1.2. Dynamics.
The queue vector Qt ∈ Rd+ evolves by Qt+1 = (Qt + At+1 − St )+ ,
(2)
where (·)+ denotes coordinatewise projection onto Rd+ . At time t, the queue Qt is Ft -measurable, the scheduler chooses an Ft -measurable service-rate vector st ∈ S, and then the arrival vector At+1 ∈ Rd+ and realized service vector St ∈ Rd+ are revealed. The realized service has conditional mean E[St | Ft ] = st a.s. (3) Thus S is the menu of feasible mean services, while St is the service actually available after the decision. We write λt := E[At+1 | Ft ] for the one-step conditional mean arrival vector. Policy.
Throughout the main upper bounds the scheduler uses the MaxWeight policy [24]: st ∈ arg max⟨Qt , s⟩. s∈S
The scheduler need not know λt . Extensions beyond MaxWeight are discussed in Remark 2.2. Capacity geometry. The capacity region is the downward closure of the convexified service set, Π := x ∈ Rd+ : there exists r ∈ conv(S) such that 0 ≤ x ≤ r coordinatewise . (4) This is the usual stability region: by classical stochastic-network theory [3, 4], arrival-rate vectors in the interior of Π are stabilizable, while rates outside Π cannot be supported. We use this convention throughout. 6
For nonnegative directions, define the support function q ∈ Rd+ .
HΠ (q) := max⟨q, s⟩ = max⟨q, x⟩, s∈S
x∈Π
When u is a unit queue direction, HΠ (u) is the projected service capacity in direction u. Since the region is fixed within the model, we write H(q) = HΠ (q). MaxWeight gives the identity ⟨Qt , st ⟩ = H(Qt ), which is the directional fact used throughout the proofs. The global Euclidean service margin is α(Π) := α2 (Π) := inf{HΠ (w) : w ∈ Rd+ , ∥w∥2 = 1}. Thus α(Π) is the worst-served nonnegative Euclidean unit direction. We will show that it plays a fundamental role in connecting geometry with queue peaks. Whenever α(Π) appears, we work on the served subspace and assume α(Π) > 0. Interior slack and bounded primitives. The next assumption is the finite-horizon analogue of operating strictly inside capacity. It constrains only the conditional arrival mean; the realized arrivals may be dependent, time-varying, and adapted to the past. Assumption 2.1 (Uniform conditional interior slack). There exists ε ∈ (0, 1) such that λt ∈ (1 − ε)Π
a.s. for every t ≥ 0.
(5)
Equivalently, for every q ∈ Rd+ , ⟨q, λt ⟩ ≤ (1 − ε)H(q)
a.s.
The main upper bounds are derived based on the following boundedness assumptions on arrivals and service; we extend our results to the unbounded case in Section 3.2. Assumption 2.2 (Bounded post-decision primitives). There are finite constants Amax and Smax such that, for every t, ∥At+1 ∥2 ≤ Amax , ∥St ∥2 ≤ Smax a.s. and sups∈S ∥s∥2 ≤ Smax . Moreover, conditional on Ft , the arrival randomness At+1 and the post-decision service randomness St are independent.
2.1
The self-normalized peak law
The first main bound is the logarithmic law. Theorem 2.1 (Self-normalized logarithmic peak law). Consider MaxWeight scheduling under Assumptions 2.1 and 2.2. Let D := Amax + Smax . For every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, D T +1 D2 PeakT ≲ log + . ε δ εα(Π) Consequently, E[PeakT ] ≲
D D2 log(T + 1) + . ε εα(Π)
If service is deterministic, the logarithmic coefficient D/ε can be replaced by Amax /ε. 7
In Theorem 2.1, geometry enters only through the entrance level D2 /(εα(Π)). Once the process is above that level, the coefficient of log T , D/ε, is independent of α(Π). The main mechanism behind Theorem 2.1 will be explained in detail in Section 3. We make two remarks below. Remark 2.1 (An exponential steady-state tail analogue without steady state). Exponential steadystate tails for positive recurrent queues [18, 20] imply that the maximum over T approximately steady-state observations should scale as log T . Theorem 2.1 gives a finite-time counterpart to this heuristic: it requires neither stationarity, positive recurrence, nor a fixed arrival law, and it applies under general network geometry. Thus, the logarithmic term in our bound should not be viewed as a finite-horizon shadow of an equilibrium tail estimate. It is produced directly by the self-normalization argument in Section 3, which identifies a foundational finite-time mechanism for logarithmic peak growth. Remark 2.2 (Extension beyond MaxWeight). We extend the proof to any Ft -measurable policy satisfying a directional certificate given in Appendix C.4. As an example, Appendix C.4 verifies this certificate for the LyapOpt policy [12], so the same logarithmic law applies to LyapOpt.
2.2
The finite-time two-phase envelope
The logarithmic law is a finite-time theorem on its own, but its entrance threshold matters. When T is small relative to a polynomial√scale in 1/ε, or when ε is small, or when the global service margin α(Π) is small, the minimax T envelope of Liu, Tan, and Xu [12] can be smaller than the logarithmic bound because the threshold term D2 /(εα(Π)) dominates. It is therefore natural to √ combine the robust T bound with our logarithmic bound, taking the better of the two, to obtain a sharper cross-regime characterization of finite-time queue peaks. √ Theorem 2.2 (A slack-free T envelope for the peak). Consider MaxWeight scheduling under Assumption 2.2. Assume only the boundary-load condition λt ∈ Π a.s. for every t; no strict interior slack is used. Let D := Amax + Smax . Then for every T ≥ 1 and every r > 0, P(PeakT ≥ r) ≤
D2 T . r2
√ In particular, E[PeakT ] ≤ 2D T . Appendix C.7 proves the estimate by telescoping the one-step quadratic drift and applying Doob’s maximal inequality. This is the bounded-primitive version of the finite-time viewpoint of √ Liu, Tan, and Xu [12]: before one uses slack, T growth is the natural robust envelope. Combining Theorem 2.2 with Theorem 2.1 yields the two-phase upper envelope. Corollary 2.1 (Two-phase upper envelope). Consider MaxWeight scheduling under Assumptions 2.1 and 2.2. Assume α(Π) > 0, and let D := Amax + Smax . Then √ D D2 E[PeakT ] ≲ min D T , log(T + 1) + . ε εα(Π) With xth := D2 /(εα(Π)) denoting the geometric threshold, the transition between the two phases occurs near T ≍ x2th /D2 , which in normalized bounded models is T ≍ (εα(Π))−2 . We emphasize that this corollary is an upper envelope, not a claim that every instance has a sharp deterministic transition time. See Figure 1 for an illustration, and see Section 6 for empirical queue peak scaling simulations. 8
2.3
Why the two phases and the threshold are necessary
The upper envelope has two independent obstructions. The first is probabilistic: even a onedimensional queue has an initial diffusive regime and, after enough time, a logarithmic maximum. The second is geometric: even at constant slack, a scheduler may need to serve many weak directions before the backlog can be kept below the global threshold scale. Theorem 2.3 (One-dimensional lower bound at arbitrary arrival scale). There exist universal constants c, C > 0 such that the following holds. For every A ≥ 1, ε ∈ (0, 1/8], and T ≥ CA, there is a one-dimensional queue in the present model, with deterministic unit service St = st = 1, arrivals taking values in {0, A + 1}, such that h i √ A ε2 AT , . E max ∥Qt ∥1 ≥ c min log 1 + T 0≤t≤T ε A Since Amax = A + 1, the logarithmic term may be written with Amax in place of A, up to universal constants. In particular, for horizons above Amax /ε2 , the deterministic-service coefficient (Amax /ε) log T is unavoidable. The logarithmic coefficient matches the deterministic-service upper bound in Theorem 2.1. A complementary (Smax /ε) log T lower bound can be obtained by a randomservice construction, which we omit here. Proof idea. The mechanism is clearest in the regenerative analysis of Appendix C.5. A typical excursion lasts O(1/ε) steps, while its maximum has an exponential tail with decay rate Θ(ε/A). Maximizing over the excursions seen by time T gives the logarithmic term, and the same construction has a diffusive initial regime, giving the square-root term. Theorem 2.4 (Geometric threshold lower bound under constant slack). There exists a universal constant c > 0 such that, for every d ≥ 2, ε ∈ [1/4, 1/2], there is a switched network with deterministic arrivals and services, satisfying Assumptions 2.1 and 2.2, with Amax ≤ 1, Smax = 1, √ and α(Π) = 1/ d, such that the following holds. For any scheduling policy, max ∥Qt ∥2 ≥
0≤t≤T0
c , εα(Π)
where the horizon T0 := ⌊d/2⌋ is polynomial in 1/α(Π). Proof idea. The proof in Appendix C.6 uses the simplex schedule set. In each slot a policy can serve at most one coordinate. By time T0 = ⌊d/2⌋, at least d − T0 coordinates √ have never been served, and these untouched coordinates alone carry Euclidean backlog of order d = 1/α(Π). Since ε is bounded away from zero, this is the same scale as 1/(εα(Π)). Therefore, the structure of Corollary 2.1 is essentially sharp: any general finite-time peak law must include a burn-in envelope, a logarithmic envelope, and a geometric threshold. Section 3 explains why the logarithmic coefficient is already geometry-free, and Section 4 shows how state-space collapse can replace the global service margin by local bottleneck geometry.
3
Self-normalization and geometry-free logarithms
We now explain the mechanism behind Theorem 2.1. The full proof is given in Appendix C.2.
9
3.1
Key proof idea: self-normalization
Scalar peak principle. The logarithm in Theorem 2.1 comes from a one-dimensional excursion bound. Appendix B develops the scalar martingale concentration machinery; the following simplified form captures the intuition. Let (Xt )t≥0 be a nonnegative adapted process. Suppose that, above a level x0 , its conditional drift is at most E[Xt+1 − Xt | Ft ] ≤ −∆, its upward jumps are bounded by L, and its centered increments have conditional Bernstein variance proxy σ 2 . Then, with probability at least 1 − δ, T +1 σ2 log max Xt ≲ x0 + L + . 0≤t≤T ∆ δ Thus the logarithmic coefficient is governed by a one-step fluctuation-to-drift ratio σ 2 /∆. The queue peak problem is not only to prove negative drift, but to identify the coordinate in which the fluctuation scale and the drift scale should be compared. The queue direction is the right coordinate. A direct quadratic-Lyapunov argument gives the right stability mechanism but loses the sharp coefficient when inserted into the scalar peak principle. It controls fluctuations by the worst one-step scale D2 and controls drift by the worst directional margin εα(Π). This yields the ratio D2 /(εα(Π)), so the logarithmic coefficient inherits the weakest global service direction even if the queue rarely points there. Appendix C.1 gives this calculation. The self-normalized proof keeps the current queue direction in the estimate. Let Xt := ∥Qt ∥2 ,
ut := Qt /Xt
when Xt > 0.
In one slot the realized net input is At+1 − St . The Euclidean norm is almost linear at a large queue: Xt+1 − Xt ≤ ⟨ut , At+1 − St ⟩ +
∥At+1 − St ∥22 . 2Xt
(6)
The first term is the net input projected onto the queue direction. By Assumption 2.1 and the MaxWeight choice of St , E[⟨ut , At+1 − St ⟩ | Ft ] ≤ (1 − ε)H(ut ) − H(ut ) = −εH(ut ). The second term in (6) is the curvature cost of replacing a vector recursion by a norm recursion: transverse motion can bend the norm, and this cost is quadratic in the one-slot movement but inverse in the current queue size. Since ∥At+1 ∥2 ≤ Amax ,
∥St ∥2 ≤ Smax ,
D = Amax + Smax ,
the curvature term is at most D2 /(2Xt ). Hence, once Xt ≳
D2 , εα(Π)
the curvature cost is dominated by the projected drift. Beyond this threshold, the peak is governed by the scalar process obtained by projecting the net input onto the current queue direction ut . 10
The decisive point is that the same support value H(ut ) controls both sides of this scalar comparison. The drift scale is εH(ut ). The fluctuation scale is also proportional to H(ut ): for θ ≲ 1/D, h i log E exp θ ⟨ut , At+1 − St ⟩ − E[⟨ut , At+1 − St ⟩ | Ft ] Ft ≲ θ2 D H(ut ). (7) Thus the projected fluctuation is self-normalized : the same factor H(ut ) that measures how much service MaxWeight can extract in direction ut also measures how much randomness remains in that direction. A poorly served direction therefore has weak drift, but it also has proportionally weak projected fluctuation. The scalar ratio is not obtained by combining the largest possible fluctuation with the smallest possible drift. Rather, along the realized path, projected fluctuation scale at time t D H(ut ) D ≍ = . directional drift scale at time t εH(ut ) ε Geometry still matters, but only through the entrance level needed to reach this aligned regime. After that, the logarithmic coefficient is the local fluctuation-to-drift ratio, uniformly over the directions exposed by the queue process ut . If service is deterministic after the scheduling decision, the service-noise contribution in (7) disappears, and the coefficient improves from D/ε to Amax /ε.
3.2
Beyond bounded primitives: queue-Bernstein conditions
Boundedness (Assumption 2.2) is only one route to (7). The real structural requirement is mass sensitivity: a direction that carries little mean traffic should also carry little stochastic variation. Motivated by this requirement, we identify a new, general distribution class of random vectors that enable self-normalization, leading to an unbounded, variance-sensitive extension of Theorem 2.1. Definition 3.1 (Queue-Bernstein condition). Let Z ∈ Rd+ be nonnegative and let G be a sigma-field. Write m := E[Z | G]. We say that Z is queue-Bernstein with parameters (ν, b) conditional on G if, for every w ∈ [0, 1]d and every |θ| < 1/b, log E[exp(θ⟨w, Z − m⟩)|G] ≤
θ2 ν⟨w, m⟩ 2(1 − b|θ|)
a.s.
(8)
Here 1/0 = ∞. A deterministic primitive has parameters (0, 0). Queue-Bernstein can be understood as a strengthened version of the sub-exponential condition. The point of (8) is that every nonnegative projection has a Bernstein MGF whose variance proxy is proportional to its own mean. We provide many natural examples satisfying the queue-Bernstein condition below. Example 3.1 (Standard queue-Bernstein examples). The following primitives are queue-Bernstein conditionally on any past with respect to which their means are fixed. Appendix D.1 gives the calculations. (i) Bernoulli and binomial coordinates. Independent unit Bernoulli coordinates, and sums of independent unit Bernoulli variables, satisfy (8) with (ν, b) = (1, 1). (ii) Poisson coordinates. Independent Poisson coordinates with arbitrary predictable means satisfy (8) with (ν, b) = (1, 1). 11
(iii) Bounded total mass. If ∥Z∥1 ≤ L a.s., then Z is queue-Bernstein with (ν, b) = (L, L). P (iv) Bounded-batch compound Poisson input. If Z = N k=1 Bk , where N is Poisson and ∥Bk ∥1 ≤ L a.s., then Z is queue-Bernstein with (ν, b) = (L, L). (v) Gamma and exponential coordinates. Independent Gamma coordinates with scales bounded by β, including exponential coordinates, satisfy (8) with (ν, b) = (β, β). The following theorem extends Theorem 2.1 to general queue-Bernstein arrival and service classes. Theorem 3.1 (Peak law under queue-Bernstein conditions). Consider MaxWeight scheduling under Assumption 2.1. Conditional on Ft , assume At+1 and St are independent, At+1 is queue-Bernstein with parameters (νA , bA ) and mean λt , and St is queue-Bernstein with parameters (νS , bS ) and mean st , uniformly over t. Let xQB be the geometric threshold formula defined in (42) (deferred to Appendix D.2). Then, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, T +1 νA + νS log . PeakT ≲ xQB + bA + bS + ε δ Moreover, if ∥At+1 − St ∥2 ≤ D a.s., then xQB ≲ 1 + D +
D2 εα(Π)
.
Consequently, if the queue-Bernstein constants also satisfy bA + bS + νA + νS ≲ D, the guarantee recovers the bounded self-normalized law, up to universal constants. The bound is variance-sensitive. Even in a bounded model, the Euclidean bound may see only a worst-case jump of size D, while (8) sees the projected conditional mean. When many small independent coordinates replace one large batch, νA can stay order one although D grows with dimension. This is the improvement exploited for Bernoulli IQS in Section 5 and illustrated in the experiments. One-dimensional special case: recovering Kingman’s scale. To further illustrate the power of Theorem 3.1, we consider the one-dimensional queue as a special case, where the queue-Bernstein parameter ν can be put in familiar queueing language. Write the scalar workload recursion as + Qt+1 = Qt + At+1 − St , where At+1 is work added and St is the service opportunity in the slot. This is the G/G/1 Lindley recursion, written with the service-index convention of this paper.5 In one dimension there is no Euclidean curvature term, so the geometric entrance threshold disappears. Appendix D.4 proves the following consequence of the queue-Bernstein condition: if λt := E[At+1 | Ft ], st := E[St | Ft ], and λt ≤ (1 − ε)st , then, up to terms independent of 1/ε, PeakT ≲
νA + νS T +1 log ε δ
5
Kingman’s approximation is usually stated for the steady-state waiting time in the G/G/1 Lindley recursion. We write the same recursion as a scalar workload queue to keep notation aligned with the rest of the paper; the mathematics is the same.
12
with probability at least 1 − δ. For i.i.d. primitives, ν is the variance-to-mean scale. Thus, with τ := E[S], ρ := 1 − ε ∈ [0.5, 1), and squared coefficients of variation c2s , c2a , the dominant logarithmic coefficient has the same order as νA + νS ρ c2s + c2a ≍ τ ε 1−ρ 2 where ≍ means equality up to universal numerical constants. This is the Kingman scale [10]. Its role here is different: it is not an asymptotic approximation to the steady-state mean, which is strictly smaller, but the nonasymptotic logarithmic coefficient governing the finite-horizon peak.
4
Geometric thresholds and state-space collapse
Section 3 showed that the logarithmic term need not carry the global geometry of the capacity region. What remains is the entrance threshold. The global theorem, Theorem 2.1, waits until the queue is large enough to certify drift uniformly over all directions; this costs the global margin α(Π). That cost is unavoidable without further structure, as Theorem 2.4 shows. In many networks, however, the queue does not explore all directions. It accumulates near the bottleneck set selected by the active capacity constraints. Then the final peak bound should pay for entering a neighborhood of that local set, not for the worst margin of the whole Π. State-space collapse (SSC) is the geometric statement that makes this refinement precise. It says that, over the relevant time horizon, the queue does not explore the whole state space; instead, it remains close to a lower-dimensional bottleneck set determined by the active face of the capacity region. This principle is classical in heavy-traffic theory; see Reiman [17] and Williams [26] for background, and Stolyar [23] and Eryilmaz and Srikant [5] for MaxWeight-type collapse arguments. Here we extend the machinery to a finite-time, nonstationary form. On a high-probability collapse event, the queue stays within a controlled neighborhood of the local bottleneck set throughout the horizon. We then analyze the queue peak accumulated inside the neighborhood, where the global margin can be replaced by the local bottleneck geometry.
4.1
Two queues: collapse removes the global margin
The following two-queue example is the smallest setting in which the global and local geometries separate. The parameter a makes the capacity triangle thin, so the global margin satisfies α(Π) ≍ a. A geometry-free theorem that must protect against every direction therefore predicts an entrance cost of order 1/a. The peak bound proved in this subsection does not. Example 4.1 (A two-queue geometry). Fix a ∈ (0, 1] and let S = {(1, 0), (0, a)} ⊂ R2+ . Throughout this example service is deterministic. With our capacity-region convention, a Π = {r ∈ R2+ : r1 + r2 /a ≤ 1}, H(q) = max{q1 , aq2 }, α(Π) = √ ≍ a. 1 + a2 Write Ai,t+1 for the ith component of At+1 . Assume A1,t+1 ∈ {0, 1},
0 ≤ A2,t+1 ≤ 1
a.s. for every t.
Assume also that the conditional means satisfy 1 E[A1,t+1 | Ft ] + E[A2,t+1 | Ft ] ≤ 1 − ε a 13
a.s. for every t.
(9)
Figure 2 illustrates the geometry. The green triangle is the capacity region Π. Its upper green segment lies on r1 + r2 /a = 1; this is the exposed/active face associated with the load constraint in (9). Its normal is v := (a, 1). Define Yt := ⟨v, Qt ⟩ = aQ1,t + Q2,t . Thus Yt is the queue length projected onto the bottleneck normal. A bound on Yt alone is not enough to tightly control PeakT : from Yt ≤ M we can only get Q1,t ≤ M/a, which still pays 1/a. The collapse strip in Figure 2 is the mechanism that removes this global-margin loss: state-space collapse confines Qt to the strip, so the analysis no longer has to protect directions that the process never reaches. q2 collapse strip
v
q1 − aq2 = 1 + a2
a q1
1
Figure 2: The local geometry behind the two-queue bound. The green triangle is the capacity region, and the green segment is the bottleneck face associated with the load constraint. The red normal v = (a, 1) defines the projected queue length Y = ⟨v, q⟩. Without the strip, Y ≤ M permits q1 as large as M/a; inside the strip q1 ≤ aq2 + O(1), the same projection controls q1 + q2 at constant cost. Lemma 4.1 (Two-queue finite-time collapse and local drift). In the deterministic-service two-queue instance of Example 4.1, the following two facts hold for every sample path. 1. Collapse strip. The orthogonal overshoot is uniformly bounded: 0 ≤ (Q1,t − aQ2,t )+ ≤ 1 + a2
for every t ≥ 0.
2. No-waste projection drift. If Yt ≥ 2, then the chosen service is fully used in the bottleneck direction and Yt+1 = Yt + aA1,t+1 + A2,t+1 − a. Consequently, E[Yt+1 − Yt | Ft ] ≤ −aε
on {Yt ≥ 2}.
The lemma separates the two ingredients. The no-waste identity gives negative drift for the scalar projection once Yt is above a constant. The collapse strip gives the geometric conversion. Indeed, on the strip, Q1,t + Q2,t ≤ (1 + a)Yt + O(1), whereas without the strip the same projected bound would lose a factor 1/a. This is why the final peak bound below has no global-margin term.
14
Proposition 4.1 (A local threshold in the two-queue example). For the deterministic-service two-queue instance in Example 4.1, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ PeakT ≲ 1 +
1 T +1 log . ε δ
In particular, the bound is uniform in the anisotropy parameter a, even though α(Π) ≍ a. Proof sketch. The scalar recursion for Yt has drift of order aε above a constant level. Its upward fluctuations have variance proxy O(a) because the projection sees aA1,t+1 + A2,t+1 . The factors of a cancel in the Bernstein peak estimate, giving max Yt ≲ 1 + t≤T
1 T +1 log ε δ
with high probability. The collapse strip then converts this projected bound to the stated totalbacklog bound. Appendix E.1 gives the details.
4.2
Single-bottleneck collapse and complete resource pooling
We now pass from the two-queue example to a generalized switch. The global theorem pays the margin α(Π) because, without further structure, a large queue can point in any nonnegative direction. State-space collapse changes the geometry. If the dynamics keep the queue close to its active bottleneck set, then the peak is governed by the local bottleneck geometry, together with the finite-horizon cost of keeping the queue near that set. Complete resource pooling (CRP) is the cleanest setting in which this reduction becomes onedimensional. It is the canonical single-bottleneck condition in the heavy-traffic theory of state-space collapse [17, 23, 5, 26]. Under CRP, the saturated capacity face has a normal cone generated by a single ray. The queue may fluctuate, but its large component is pulled toward this bottleneck ray. Thus the high-dimensional peak problem separates into two tasks: prove that the queue remains in a tube around the ray, and, within that tube, control the one-dimensional bottleneck excursion while paying the tube radius to translate this control back to the full queue peak. We answer these questions in that order. First, CRP gives finite-horizon SSC: with high probability, the queue remains in a controlled tube around the bottleneck ray. Second, on this SSC event, MaxWeight reduces the remaining peak analysis to a one-dimensional motion along the bottleneck ray. The tube radius is then paid when translating this one-dimensional bound back into a bound on PeakT . The reusable conversion from a single-bottleneck collapse bound to a queue-peak bound is proved in Appendix E.3; the main text states the resulting CRP peak law directly. Under Assumption 2.1, define λt rt◦ := ∈ Π. (10) 1−ε as the nominal load point. An exposed face is active for the load process if it contains the nominal points rt◦ . CRP says that the same active facet is selected at every time and that the nominal points stay a positive distance from its relative boundary. The normal to this facet is the bottleneck direction. Assumption 4.1 (Nonstationary complete resource pooling (CRP)). There is a vector v ∈ Rd+ with ∥v∥2 = 1 and µ := H(v) > 0 such that H⋆ := {r ∈ Rd : ⟨v, r⟩ = µ}, 15
F ⋆ := Π ∩ H⋆
is the unique exposed bottleneck facet.6 The nominal points in (10) satisfy rt◦ ∈ F ⋆ a.s. for every t ≥ 0. Moreover, there is a deterministic constant δface > 0 such that, almost surely, for every integer t ≥ 0, B2 (rt◦ , δface ) ∩ H⋆ ⊆ F ⋆ . (11) That is, the distance from rt◦ to the relative boundary of F ⋆ is uniformly bounded below by δface . The slack ε and the face margin δface have different geometric meanings. The slack measures distance below the bottleneck face, in the normal direction v. The face margin measures room to move within the active face. That transverse room is what lets MaxWeight compare its chosen schedule with nearby points of F ⋆ and push the perpendicular component back toward the ray. Figure 3 illustrates the assumption. In a stationary system, rt◦ ≡ r◦ and CRP is a positive relative-inradius condition around one nominal load point. Here rt◦ may move with time and may depend on the past, but it must remain on the same face. The bottleneck direction is fixed even though the input law is not. q3 Π δ face
rt◦
F⋆
q2
S q1 Figure 3: Nonstationary CRP geometry. The nominal point rt◦ may move with time and with the past, but it remains uniformly inside the same exposed face F ⋆ . The normal to this face is the bottleneck direction v. The dashed inner polygon marks the relative-boundary margin δface . For the CRP normal v, define Yt := ⟨v, Qt ⟩,
∥
Qt := Yt v,
∥
Q⊥ t := Qt − Qt . ∥
We call Yt the bottleneck projection. Since v, Qt ≥ 0 and ∥v∥2 = 1, Qt is the orthogonal projection of Qt onto the ray spanned by v, while Q⊥ t is the transverse residual. The first result is the promised tube estimate. It is a finite-time, nonstationary analogue of the perpendicular-drift argument behind complete-resource-pooling SSC [23, 5]. If Q⊥ t is large, the ◦ ⊥ face-margin condition (11) lets us move a fixed fraction of δface from rt in the direction Q⊥ t / Qt 2 while staying on the same active face. MaxWeight must score at least as well as this feasible comparison point, and the resulting transverse gain gives negative drift for Q⊥ t . 6 Here “facet” is used in the relative sense: F ⋆ is full-dimensional inside its supporting hyperplane, equivalently aff(F ⋆ ) = H⋆ , and has nonempty relative interior in H⋆ .
16
Theorem 4.1 (Finite-time state-space collapse under CRP). Consider MaxWeight scheduling under Assumptions 2.1, 2.2, and 4.1. Let D := Amax + Smax . Suppose ε ≤ δface /(2Smax ). Let v be the CRP normal and set Q⊥ t := Qt − ⟨v, Qt ⟩v. For every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, D2 e(T + 1) max Q⊥ ≲ log . t 0≤t≤T δface δ 2 Equivalently, the network satisfies finite-horizon ray collapse with radius R⊥ (T, δ) := C
D2 e(T + 1) log δface δ
(12)
for a universal constant C. The restriction ε ≤ δface /(2Smax ) is automatic in heavy traffic for a fixed CRP geometry. It appears only because the statement is nonasymptotic: the transverse comparison point must remain inside the face after the load is scaled by 1 − ε. Appendix E.2 gives the proof. On the collapse event, the network is essentially one-dimensional: Qt = Yt v + Q⊥ t ,
Q⊥ t
2
≤ R⊥ (T, δ).
It remains to identify the entrance level above which the scalar projection has clean negative drift. Two local obstructions must be cleared. First, the transverse error can tilt a MaxWeight comparison between a v-optimal schedule and a nearly optimal one; the schedule gap ∆gap determines how large Yt must be before this tilt is irrelevant. Second, even a v-optimal schedule contributes its full bottleneck service only when the queues in the positive coordinates of v are not empty; this is the no-waste threshold governed by vmin . Under CRP, the scalar arrival rate in the bottleneck direction is exactly ⟨v, λt ⟩ = (1 − ε)µ
a.s. for every t,
because λt = (1 − ε)rt◦ and rt◦ ∈ F ⋆ . Thus, once the two local obstructions are absent, the projection Yt has drift −εµ and can be controlled by the same one-dimensional self-normalized peak argument used earlier. Theorem 4.2 (Local peak law under CRP). Consider MaxWeight scheduling under Assumptions 2.1, 2.2, and 4.1. Let D := Amax + Smax and suppose ε ≤ δface /(2Smax ). Let v be the CRP normal, set µ := H(v) > 0, and let R⊥ be the CRP collapse radius in (12). Define ∆gap := min{µ − ⟨v, s⟩ : s ∈ S, ⟨v, s⟩ < µ}, with the convention ∆gap = ∞ if every schedule is v-optimal, and interpret a/∞ := 0 for finite a. Let vmin := min{vi : vi > 0}. For T ≥ 1 and δ ∈ (0, 1), write Rδ := R⊥ (T, δ/2) and set
xloc (T, δ) := max
4Smax Rδ Smax + Rδ , ∆gap vmin
17
.
Then, with probability at least 1 − δ, both bounds hold: PeakT ≲
D T +1 log + xloc (T, δ) + Rδ , ε δ
and
√ ∥v∥1 D T +1 log + ∥v∥1 xloc (T, δ) + d Rδ . 0≤t≤T ε δ If service is deterministic, St = st a.s., then D can be replaced by Amax in the displayed logarithmic coefficients. The collapse radius remains the one supplied by (12). max ∥Qt ∥1 ≲
Proof sketch. Apply Theorem 4.1 with error probability δ/2 and stop the process when it leaves the resulting tube. Inside the tube, the first term in xloc makes the bottleneck component dominate the transverse error in the MaxWeight comparison, so every selected schedule is v-optimal. The second term ensures that service in the positive coordinates of v is actually used. Therefore the stopped projection has drift −εµ above xloc and upward jumps bounded by D. Appendix B gives ⊥ the scalar peak bound; the identities Qt = Yt v + Q⊥ t and Qt 2 ≤ Rδ convert it back to Euclidean peak and total backlog. Appendix E.3 proves this conversion in reusable form, and Appendix E.4 applies it here. Theorem 4.2 is the local counterpart of the global peak theorem. The global argument waits until the queue is large enough to certify drift uniformly over the whole nonnegative orthant; the price is the global margin α(Π). CRP first rules out most of those directions. The entrance threshold is then governed by local quantities: the schedule gap ∆gap , the face margin through R⊥ , and −1 the no-waste scale vmin . None of these carries the global 1/α(Π) cost. After localization, the only remaining growth is scalar, with logarithmic coefficient D/ε, or Amax /ε under deterministic service. The theorem still contains the finite-horizon cost of proving localization. The generic SSC estimate above gives a logarithmic radius R⊥ (T, δ), and that logarithm appears in the final bound. Thus the result should be read as a principled replacement of global geometry by local bottleneck geometry, rather than an identification of the optimal local geometric threshold independent of T . The two-queue bound in Proposition 4.1 illustrates what is possible when a sharper, model-specific collapse estimate yields a tube radius that is independent of the horizon.
5
Applications to input-queued switches
We now apply the finite-time framework to input-queued switches. This is the canonical matching network behind packet switches, crossbar routers, and related data-center and internet-routing architectures. The model is simple enough for the geometry to be explicit and rich enough to contain one of the central queue-size scaling problems in stochastic networks.
5.1
Summary of results for the three IQS models
An n × n input-queued switch has d = n2 queues indexed by input-output pairs (i, j). A schedule s ∈ SIQS is a full permutation matrix. Thus every schedule serves exactly one queue from each row and one queue from each column, and service is deterministic: St = st . With the downward-closed convention (4), the capacity region is the substochastic bipartite matching polytope, X X ΠIQS = x ∈ Rn×n : xij ≤ 1 ∀i, xij ≤ 1 ∀j . + j
i
18
Setting
Logarithmic coefficient
Geometric threshold
Generalized IQS (Theorem 5.1) Generalized IQS under CRP (Corollary 5.1) Bernoulli IQS (Theorem 5.4)
n3/2 /ε n/ε + n2 /δface n/ε
n5/2 /ε n/ε + n2 /δface + n3/2 n5/2 /ε
Table 1: Upper bounds of max0≤t≤T ∥Qt ∥1 for three IQS regimes. The CRP row reports the bound obtained by combining the local theorem with the generic finite-time SSC radius: n/ε is the bottleneck-projection coefficient, while n2 /δface comes from the collapse radius. For nonnegative queue weights, maximizing over full permutation matrices has the same support function as maximizing over this downward-closed polytope, since any partial matching can be completed to a full permutation without decreasing a nonnegative weight. We identify matrices with their vectorizations and use the Frobenius norm as the Euclidean norm. We consider three IQS settings. We call the first setting the generalized IQS model (to be defined shortly in the next subsection): arrivals may be adapted, dependent, deterministic, and fractional, subject to a pathwise Frobenius envelope and conditional row/column slack. The second is the same generalized model under CRP, where a single row or column is the active bottleneck. Collapse then exposes a smaller logarithmic coefficient for the bottleneck projection, while the total-backlog bound also contains the finite-time collapse-radius contribution. The third is a Bernoulli IQS model with predictable, possibly time-varying arrival probabilities. This contains the classical time-homogeneous Bernoulli IQS as a special case, but is nonstationary in nature. It is not a pathwise submodel of the generalized IQS, but its entrywise independence structure gives stronger variance-sensitive concentration. The upper bound results of three IQS models are summarized in Table 1. The results are shown for the total backlog peak max0≤t≤T ∥Qt ∥1 rather than PeakT due to convention in IQS literature. We note that the classical independent Bernoulli IQS model is usually studied in steady state, where the optimal queue-size scaling problem remains open [19, 22, 21, 27]. Our bounds address finite-time peaks, whose geometric thresholds can be larger than the steady-state scales, and we do not intend to improve existing steady-state bounds. The contributions here are different: we identify the tight coefficient multiplying log T under robust nonstationary input models and show how geometry and variance change that coefficient. Before explaining the detailed guarantees of each IQS model, we state some elementary properties shared by the three IQS models. The proof is deferred to Appendix F.1. Proposition 5.1 (Euclidean geometry of IQS models). For the n × n input-queued switch, Smax =
5.2
√
n,
1 α(Π) = √ , n
∥Q∥1 ≤ n ∥Q∥2
for all Q ∈ Rn×n + .
Generalized IQS: achieving the tight logarithmic coefficient
The generalized IQS model is defined by the following assumption. Assumption 5.1 (Generalized IQS arrival envelope). The arrival matrix At+1 ∈ Rn×n is Ft+1 + measurable and satisfies √ ∥At+1 ∥2 = ∥At+1 ∥F ≤ n a.s. for every t.
19
Its conditional mean λt := E[At+1 | Ft ] satisfies n X j=1
λij (t) ≤ 1 − ε,
n X
λij (t) ≤ 1 − ε
a.s. for all i, j, t.
(13)
i=1
The Frobenius envelope is normalized to the natural service scale: every permutation schedule √ has Frobenius norm n. The row and column inequalities in (13) are exactly the condition λt ∈ (1 − ε)ΠIQS . Thus Assumption 5.1 preserves the usual IQS capacity region and slack condition while discarding the classical independence structure: arrivals may be correlated across queues and time, and may even be chosen adaptively, subject only to the aggregate slack condition and the pathwise Frobenius envelope.7 Our global theorem, stated below, immediately gives a finite-time total-backlog peak bound. The important term is the logarithmic coefficient; the threshold has higher dependence on n, which is why this estimate is not a steady-state-mean improvement. Theorem 5.1 (Generalized IQS upper bound). Consider the n × n input-queued switch with full-permutation deterministic service St = st and MaxWeight scheduling. Suppose the arrivals satisfy Assumption 5.1 for some ε ∈ (0, 1). Then, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, we have n3/2 T + 1 n5/2 max ∥Qt ∥1 ≲ log + . 0≤t≤T ε δ ε This is a corollary of Theorem 2.1 (deterministic service part) plus Proposition 5.1; Appendix F.1 records the calculation. We establish a matching lower bound (in terms of the logarithmic coefficient) by constructing a hard instance satisfying the all-ports-loaded slack form, meaning that every row and every column of the mean arrival matrix has sum 1 − ε. Theorem 5.2 (Generalized IQS lower bound). There exist universal constants c, C > 0 such that, for every n ≥ 4, ε ∈ (0, 1/16], there is a generalized n × n IQS arrival instance satisfying the all-ports-loaded slack form with the following property. Under any nonanticipative full-permutation √ deterministic-service scheduling rule, in particular under MaxWeight, for every T ≥ C n/ε2 , h i ε2 n3/2 log 1 + √ T . E max ∥Qt ∥1 ≥ c 0≤t≤T ε n
(14)
The upper and lower bounds match in the coefficient of the log T term. This is the finite-time message of the generalized IQS: under adapted, dependent, fractional arrivals, the n3/2 ε−1 log T contribution to the total-backlog peak is fundamental. The lower bound does not rule out better n scaling in the classical independent Bernoulli model, because the generalized IQS construction uses dependent and fractional arrivals that are excluded there. √ The classical independent Bernoulli IQS is not literally a submodel of Assumption 5.1 with the pathwise n envelope, since one slot may contain more than n arrivals. Nevertheless, generalized IQS captures a natural deterministic-envelope analogue of the classical model. Let Nt = ∥At+1 ∥2F . In the independent Bernoulli model, E[Nt | Ft ] ≤ n. Bernstein’s inequality and a union bound give, with L = log(T /δ), √ 2 P max Nt > n + 2nL + L ≤ δ. 0≤t<T 3 7
When n ≳ L, this recovers the generalized-IQS envelope in Assumption 5.1, up to universal constants. For smaller n, any pathwise envelope of this form must depend on the horizon. The queue-Bernstein theorem (Theorem 3.1) later treats independent Bernoulli IQS directly, without this localization, and yields Theorem 5.4.
20
5.3
Generalized IQS under CRP: local refinement via state-space collapse
The global generalized IQS bound treats the switch as an n2 -dimensional object. In a CRP regime with a single tight row or column, the switch is approximately described by the corresponding bottleneck projection plus a transverse collapse error. The bottleneck vector is the normalized √ indicator of the tight row or column, and hence ∥v∥1 = n. Feeding this local direction into the deterministic-service form of Theorem 4.2 sharpens the projected-coordinate logarithmic coefficient from n3/2 /ε to n/ε. If the CRP-based SSC estimate of Theorem 4.1 is used to supply the collapse radius, the total-backlog upper bound also includes the collapse logarithmic coefficient of order n2 /δface . See Corollary 5.1 for the formal guarantee. Corollary 5.1 (Generalized IQS under CRP: upper bound). Consider the generalized n × n IQS with full-permutation deterministic service, MaxWeight scheduling, and nonstationary bounded arrivals satisfying Assumption 5.1. Write rt◦ := λt /(1 − ε). Suppose Assumption 4.1 holds and its bottleneck face is one row or one column. Assume ε ≤ δface /(2Smax ) and let R⊥,IQS (T, δ) :=
e(T + 1) C0 n log δface δ
for a universal constant C0 . Then, with probability at least 1 − δ, max ∥Qt ∥1 ≲
0≤t≤T
n T +1 log + n3/2 + n R⊥,IQS (T, δ/2). ε δ
Appendix F.2 records the calculation. The corollary is not a replacement for the global theorem; it is the payoff when collapse information is available. It separates the bottleneck-projection coefficient, n/ε, from the additional finite-time price of proving collapse. With the generic SSC radius displayed above, this additional logarithmic coefficient is of order n2 /δface . We also establish a lower bound, stated below. Theorem 5.3 (Generalized IQS under CRP: lower bound). There exist universal constants c′ , C ′ > 0 such that, for every n ≥ 4, ε ∈ (0, 1/16], there is a generalized n × n IQS arrival instance satisfying Assumption 4.1 with the following property. Under any nonanticipative full-permutation deterministic-service scheduling rule, in particular under MaxWeight, started from Q0 = 0, for every T ≥ C ′ n/ε2 , h i ε2 n E max ∥Qt ∥1 ≥ c′ log 1 + T . (15) 0≤t≤T ε n Thus the SSC refinement has the right bottleneck-projection logarithmic coefficient in the generalized model. With the generic finite-time SSC estimate inserted, the total-backlog coefficient is the sum of this projected-coordinate coefficient and the collapse coefficient shown in Table 1.
5.4
Bernoulli IQS: variance-sensitive improvement
√ The global generalized-IQS theorem pays for the crude Frobenius scale Amax = n in Assumption 5.1. Independent Bernoulli input has more structure, even when its rates are nonstationary. Throughout this subsection, “Bernoulli IQS” means that, conditional on the past, the entries of At+1 are independent Bernoulli variables with predictable means λij (t) satisfying the row and column slack inequalities (13). The classical time-homogeneous Bernoulli IQS corresponds to the special case in which these means are constant in t. In every nonnegative queue direction, the projected arrival ⟨ut , At+1 ⟩ is queue-Bernstein with a dimension-free variance-to-mean constant. Applying the variance-sensitive queue-Bernstein theorem 21
of Section 3.2, we find that the logarithmic coefficient for PeakT is 1/ε, corresponding to n/ε for √ max0≤t≤T ∥Qt ∥1 , rather than n/ε, corresponding to n3/2 /ε for max0≤t≤T ∥Qt ∥1 . Theorem 5.4 (Bernoulli IQS upper bound). Consider the n × n input-queued switch with fullpermutation deterministic service and MaxWeight scheduling. Let ε ∈ (0, 1). For every t, assume that, conditional on Ft , the entries of At+1 are independent Bernoulli random variables with predictable conditional means λij (t) ∈ [0, 1]: P Aij (t + 1) = 1 | Ft = λij (t), 1 ≤ i, j ≤ n, and assume that the predictable mean matrix λt satisfies the row and column slack inequalities (13). Then, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, max ∥Qt ∥2 ≲
0≤t≤T
1 T + 1 n3/2 log + . ε δ ε
Consequently, with the same probability, max ∥Qt ∥1 ≲
0≤t≤T
T + 1 n5/2 n log + . ε δ ε
From Table 1, we can see that compared to generalized IQS, the independent Bernoulli structure sharpens the logarithmic term.
6
Experiments
The preceding results establish √ three quantitative, testable finite-time mechanisms: a two-phase peak envelope transitioning from T to log T , sharper geometric thresholds under state-space collapse, and variance-sensitive peak scaling under the queue-Bernstein condition. The experiments below confirm each of them. In all experiments we simulate MaxWeight scheduling, start from Q0 = 0, and record the running peak max0≤s≤t ∥Qs ∥, using total backlog or Euclidean norm according to the theorem being illustrated. The main control parameters were the horizon T , slack ε, network size, and bottleneck geometry. Curves report empirical means over independent replications; shaded bands are ± one standard error. Experiment 1 averages over 500 runs, while Experiments 2 and 3 average over 200 independent runs. All experiments were run on standard CPU resources. No GPU or accelerator was used. The reported experiments require at most a few CPU-hours in total. Appendix A contains the full experimental details, additional diagnostics, and instructions for accessing the GitHub replication package. Experiment 1: the two-phase law. The first experiment tests the two regimes in Corollary 2.1: √ T burn-in followed by log T growth after a geometric entrance threshold. A direct consequence is that the transition becomes visible at shorter horizons when the slack ε is larger. We examine two networks: the first network is an n × n input-queued switch with n = 20, independent Bernoulli arrivals Aij (t + 1) ∼ Bernoulli((1 − ε)/n) and deterministic full-permutation service, under MaxWeight scheduling. We plot the Frobenius-norm peak; the second is a discretetime parallel-server system with L = K = 40 customer classes and servers, connected by a ring compatibility graph: each class ℓ can be served by servers ℓ and (ℓ+1) mod L. Arrivals per class are Bernoulli Aℓ (t + 1) ∼ Bernoulli((1 − ε)µK/L), and each server has geometric service times with 22
parameter µ = 0.05. Idle servers are assigned to compatible waiting classes by MaxWeight. We plot the Euclidean-norm peak. In both networks, we sweep ε ∈ {0.005, 0.01, 0.02, 0.05}. The top curves plot the empirical mean running peak E [PeakT ], and the bottom curves plot the d x local log-log slope β(T ) := d log T log E [PeakT ]. A pure T growth has β(T ) = x, while a logarithmic growth has β(T ) ≍ 1/√log T . In both the IQS and parallel-server examples, larger slack makes β(T ) drop away from the T reference line much earlier, illustrating the transition from the burn-in envelope to the logarithmic-growth regime. model=iqs, R=500, n=20 = 0.005 = 0.01 = 0.02 = 0.05
140 120 100 max Q 0 s t s 2
]
150 100
[
max Q 0 s t s 2
]
200
[
model=parallel_server, R=500
= 0.005 = 0.01 = 0.02 = 0.05
80 60 40
50
20 0
0 = 0.005 = 0.01 = 0.02
0.2 0.0
0
20000
40000
T
60000
80000
= 0.005 = 0.01 = 0.02
0.4 (T)
(T)
0.4
= 0.05 T logT
0.2 0.0
100000
(a) Input-queued switch, n = 20.
= 0.05 T logT
0
50000
100000
T
150000
200000
250000
(b) Parallel-server, 40 servers & 40 classes.
Figure 4: Two-phase behavior of the mean running peak. Top: mean peak with ±SE bands. Bottom: local log-log slope β(T ).
Experiment 2: local versus global geometry. This experiment uses the two-queue system of Section 4 with service set S = {(1, 0), (0, a)} and global margin α(Π) ≍ a, under MaxWeight scheduling. Figure 5 varies the anisotropy parameter a ∈ {0.5, 0.25, 0.1} and compares three curves: the simulated peak, the global prediction from Theorem 2.1 (which pays the worst-direction margin α(Π)), and the local prediction from Proposition 4.1 (which exploits collapse). The simulations track the local prediction closely, and the gap with the global prediction grows as a decreases. This is the finite-time signature of state-space collapse: the process pays for the geometry it actually visits, not for the worst direction of the capacity region. Experiment 3: CRP and variance. The third experiment separates two effects that are invisible from Theorem 2.1 alone: bottleneck geometry and arrival variability. Both comparisons use a generalized n × n IQS with n = 20, ε = 0.01. Service is deterministic and schedules are chosen by MaxWeight. CRP versus non-CRP geometry (Figure 6(a)). We compare two instances whose arrivals equal a fixed matrix M with probability 1 − ε and zero otherwise, ( 0, with probability ε, At+1 := M, with probability 1 − ε, so the mean load is λ = (1 − ε)M in both cases. The non-CRP instance loads the first row and the
23
Simulation
Global prediction
a = 0.5
Local prediction
a = 0.25
a = 0.1
70
[
0 t T
max Qt 2
]
60 50
Constant gap O(1/a)
40 30
Constant gap O(1/a)
Constant gap O(1/a)
20 10 0 0.0
0.2
0.4
T
0.6
0.8
1.0 1e5
0.0
0.2
0.4
T
0.6
0.8
1.0 1e5
0.0
0.2
0.4
T
0.6
0.8
1.0 1e5
Figure 5: Two-queue example. Global prediction uses Theorem 2.1; local prediction uses Proposition 4.1. first column at level 1/n, with all other entries at 1/n2 : ( 1/n, i = 1 or j = 1, MijnonCRP := 1/n2 , i ̸= 1 and j ̸= 1. This creates two nearly active bottleneck constraints, since both the first row and the first column carry elevated traffic. In the CRP instance, the elevated traffic is concentrated on the first row and on the diagonal: ( 1/n, i = 1 or i = j, CRP Mij := 1/n2 , otherwise. Here the first row is the sole dominant bottleneck. For each instance we simulate the running total-backlog peak maxs≤t ∥Qs ∥1 over independent replications. Figure 6(a) shows that the CRP instance has a visibly smaller peak, consistent with the local refinement: collapse near a single bottleneck face reduces the projected-coordinate contribution from the global n3/2 /ε scale toward the local n/ε scale, while a finite-time proof must still account for the collapse radius itself. Independent versus synchronous arrivals (Figure 6(b)). We compare two arrival processes with the same entrywise means but different dependence across entries. In the independent model, Aij (t+1) ∼ Bernoulli((1 − ε)/n) independently across entries and slots. In the synchronous model, arrivals remain independent across slots but are dependent across entries: for every slot, with probability (1 − ε)/n every entry receives one arrival simultaneously, and otherwise every entry is zero. Thus the two models have the same entrywise mean load, but very different dependence and total-mass variance. The synchronous model produces larger peaks, illustrating that finite-time peaks are controlled not only by mean arrivals but also by the directional variance structure captured by the queue-Bernstein condition.
7
Discussion and open directions
This paper identifies the finite-time outer shape of queue peaks. Before the queue has had √ time to exploit the network’s global or local geometry, the natural envelope is the minimax T law. After the queue has paid the geometric entrance fee, additional growth is only logarithmic. The logarithmic coefficient is geometry-free, while the entrance scale is geometric. This separation,
24
= 0.01
Synchronous Independent
1500 1250 0 t T
max Qt 1
]
150
1000 750
[
100
[
0 t T
max Qt 1
]
200
= 0.01
1750
CRP Non-CRP
500
50
250 0
0 0.0
0.2
0.4
T
0.6
0.8
1.0 1e5
(a) CRP vs. non-CRP geometry.
0.0
0.2
0.4
T
0.6
0.8
1.0 1e5
(b) Independent vs. synchronous arrivals.
Figure 6: Geometry and variance effects in generalized IQS. together with its origin and possible refinements, is the main conceptual outcome of the paper and points to many future research directions. We discuss two open directions below. Beyond CRP-based state-space collapse. Theorem 2.4 shows that the global margin α(Π) is unavoidable for fully uniform, policy-independent peak laws. Section 4, however, shows that this margin can be far too pessimistic once the queue is known to remain near its active bottleneck set. Our local theorem captures the cleanest version of this picture: quantitative CRP, with a unique exposed bottleneck facet and one bottleneck direction, matching the classical single-bottleneck collapse geometry in heavy traffic [17, 23, 5, 26]. There is a limitation of the present theory. It does not yet cover non-CRP or nearly non-CRP networks, where several bottleneck constraints may be simultaneously active. In such systems, the right local object should be a cone, or even a stratified collection of bottleneck faces, rather than a single ray. A sharp extension would assign to each local geometry a collapse radius and a local service margin that can be inserted into Proposition E.1. This would translate the steady-state and heavy-traffic geometry known for switches with richer saturation structure [13, 14, 4] into nonasymptotic peak laws, and would clarify when the global threshold is genuinely structural and when it is only the cost of not knowing where the queue lives. Beyond uniform slack. A second limitation is the uniform slack condition in Assumption 2.1. Weakening this assumption is delicate. A time-averaged slack condition T
1X λt ∈ (1 − ε)Π T t=1
by itself is too weak: one can construct environments whose average interior margin over the horizon is of order ε, yet whose queue length still grows linearly in T , simply because the slack arrives too late to undo earlier backlog accumulation. Any useful replacement for uniform slack must therefore control not only how much slack exists on average, but also how it is distributed in time relative to the queue dynamics. Existing nonstationary queueing frameworks, such as Markov-modulated service or channelfading models [15], suggest one possible route. These models impose enough temporal structure to recover meaningful long-run guarantees without full stationarity. Developing a finite-time peak law under weaker, temporally structured slack conditions remains an appealing direction for future work. 25
References [1] Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P. Williamson. Adversarial queueing theory. Journal of the ACM, 48(1):13–38, 2001. [2] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. [3] J. G. Dai. Stability of fluid and stochastic processing networks. MaPhySto Miscellanea Publication 9, MaPhySto, Centre for Mathematical Physics and Stochastics, 1999. [4] J. G. Dai and J. Michael Harrison. Processing Networks: Fluid Models and Stability. Cambridge University Press, 2020. ISBN 9781108488891. [5] Atilla Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems, 72(3–4):311–359, 2012. [6] Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3):502–525, 1982. [7] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3–4):157–325, 2016. [8] Daniela Hurtado-Lange, Sushil M. Varma, and Siva Theja Maguluri. Logarithmic heavy traffic error bounds in generalized switch and load balancing systems. Journal of Applied Probability, 59(3):652–669, 2022. [9] Frank P. Kelly. Stochastic networks. Part III lecture notes, Lent Term, Statistical Laboratory, University of Cambridge, 2011. [10] J. F. C. Kingman. The single server queue in heavy traffic. Proceedings of the Cambridge Philosophical Society, 57(4):902–904, 1961. [11] Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer, 2001. [12] Yujie Liu, Vincent Y. F. Tan, and Yunbei Xu. Finite-time minimax bounds and an optimal lyapunov policy in queueing control, 2025. arXiv:2506.18278. [13] Siva Theja Maguluri and R. Srikant. Heavy traffic queue length behavior in a switch under the MaxWeight algorithm. Stochastic Systems, 6(1):211–250, 2016. [14] Siva Theja Maguluri, Sai Kiran Burle, and R. Srikant. Optimal heavy-traffic queue length scaling in an incompletely saturated switch. Queueing Systems, 88(3–4):279–309, 2018. [15] Michael J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool, 2010. [16] Hoang Huy Nguyen, Sushil Mahavir Varma, and Siva Theja Maguluri. Finite-time behavior of erlang-c model: Mixing time, mean queue length and tail bounds. ACM SIGMETRICS Performance Evaluation Review, 53(1):4–6, 2025.
26
[17] Martin I. Reiman. Some diffusion approximations with state space collapse. In François Baccelli and Guy Fayolle, editors, Modelling and Performance Evaluation Methodology, volume 60 of Lecture Notes in Control and Information Sciences, pages 207–240. Springer, Berlin, Heidelberg, 1984. [18] Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Qualitative properties of α-weighted scheduling policies. ACM SIGMETRICS Performance Evaluation Review, 38(1):239–250, 2010. [19] Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Optimal scaling of average queue sizes in an input-queued switch: an open problem. Queueing Systems, 68(3–4):375–384, 2011. [20] Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. Qualitative properties of α-fair policies in bandwidth-sharing networks. Annals of Applied Probability, 24(1):76–113, 2014. [21] Devavrat Shah, Neil Walton, and Yuan Zhong. Optimal queue-size scaling in switched networks. Annals of Applied Probability, 24(6):2207–2245, 2014. [22] Devavrat Shah, John N. Tsitsiklis, and Yuan Zhong. On queue-size scaling for input-queued switches. Stochastic Systems, 6(1):1–25, 2016. [23] Alexander L. Stolyar. MaxWeight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Annals of Applied Probability, 14(1):1–53, 2004. [24] Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936–1948, 1992. [25] Neil Walton and Kuang Xu. Learning and information in stochastic networks and queues. In Tutorials in operations research: Emerging optimization methods and modeling techniques with applications, pages 161–198. INFORMS, 2021. [26] Ruth J. Williams. Stochastic processing networks. Annual Review of Statistics and Its Application, 3:323–345, 2016. [27] Jiaming Xu and Yuan Zhong. Improved queue-size scaling for input-queued switches via graph factorization. Advances in Applied Probability, 52(3):798–824, 2020.
27
Appendix Contents A Experimental details A.1 Experiment 1: two-phase behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Experiment 2: local versus global geometry . . . . . . . . . . . . . . . . . . . . . . . A.3 Experiment 3: CRP and variance in IQS . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Code and data availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29 29 30 31 31
B The scalar drift-to-peak principle B.1 Exponential drift above a threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 From negative drift and Bernstein fluctuations to exponential drift . . . . . . . . . . B.3 Why self-normalization matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31 32 33 34
C Proofs for the model section C.1 A warm-up via global geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 The self-normalized theorem for MaxWeight . . . . . . . . . . . . . . . . . . . . . . . C.3 Comparison with the classical steady-state bound . . . . . . . . . . . . . . . . . . . . C.4 Directional certificate and LyapOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.5 One-dimensional lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.6 Geometry-threshold lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.7 A slack-free square-root envelope . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35 35 36 39 40 42 46 47
D Proofs for self-normalization and extensions D.1 Queue-Bernstein calculus and examples . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Queue-Bernstein geometric threshold formula . . . . . . . . . . . . . . . . . . . . . . D.3 Proof of the unbounded queue-Bernstein theorem . . . . . . . . . . . . . . . . . . . . D.4 One-dimensional queue-Bernstein peaks and Kingman’s scale . . . . . . . . . . . . .
48 48 50 51 53
E Proofs for the geometry section E.1 The two-queue collapse example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Finite-time state-space collapse under CRP . . . . . . . . . . . . . . . . . . . . . . . E.3 Collapse-to-peak conversion near a ray . . . . . . . . . . . . . . . . . . . . . . . . . . E.4 Local peak law under CRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54 54 56 57 60
F Proofs for the IQS section F.1 Generalized IQS upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 Generalized IQS upper bound under CRP . . . . . . . . . . . . . . . . . . . . . . . . F.3 Generalized IQS lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.4 Bernoulli IQS upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60 60 60 62 63
28
A
Experimental details
This appendix gives the simulation details for the experiments in Section 6.
A.1
Experiment 1: two-phase behavior
This experiment visualizes the two regimes in Corollary 2.1. The qualitative prediction is that smaller slack delays the transition, while larger slack moves the logarithmic regime into smaller, practically visible horizons. Local log-log slope.
For the two-phase experiment we also plot the local log-log slope β(T ) :=
d log PeakT , d log T
estimated from the downsampled log-log curve by finite differences. This is a diagnostic for the local log T 1 growth exponent. If PeakT ≍ T x , then β(T ) = x. If PeakT ≍ log T , then β(T ) = d log d log T = log T . √ Thus β(T ) ≈ 1/2 signals T -type growth, while a small positive value at large T indicates logarithmic-scale growth. The slope estimate is more sensitive to downsampling than the raw peak curve, because it is derivative-like. We therefore choose the downsampling resolution 104 grid points to stabilize the displayed finite-difference estimate; nearby choices give the similar qualitative conclusions. Input-queued switch. The IQS experiment uses an n × n input-queued switch with n = 20. Arrivals are independent Bernoulli across entries and time slots: 1−ε Aij (t + 1) ∼ Bernoulli . n The scheduling rule is MaxWeight. We sweep ε ∈ {0.005, 0.01, 0.02, 0.05}. The plotted metric is max0≤t≤T ∥Q(t)∥2 . The horizon is T = 105 . Parallel-server model. We consider a discrete-time parallel-server queueing system with L customer classes and K servers. Compatibility between classes and servers is described by a bipartite graph G = (L, K, E), L = {0, 1, . . . , L − 1} and K = {0, 1, . . . , K − 1}, where (ℓ, k) ∈ E means that server k is able to serve class ℓ. Figure 7 illustrates the compatibility graph used in our experiments. In the two-phase parallel-server setup we use a sparse ring (“ring zigzag”) connectivity with L = K = 40: each class ℓ is compatible with two servers, namely k = ℓ and k = (ℓ + 1) mod L. Equivalently, E = {(ℓ, ℓ), (ℓ, (ℓ + 1) mod L) : ℓ = 0, 1, . . . , L − 1}, so |E| = 2L and both sides have degree 2. For example, class 0 connects to servers {0, 1}, while class 39 connects to servers {39, 0}. Let Qℓ (t) denote the number of waiting class-ℓ customers at the beginning of slot t, and write Q(t) = (Q0 (t), . . . , QL−1 (t)). Arrivals are independent Bernoulli across classes and time slots: (1 − ε)µK Aℓ (t + 1) ∼ Bernoulli . L 29
A0 (t + 1)
Q0 (t)
Server 0
Q1 (t)
Server 1
Q2 (t)
Server 2
A1 (t + 1)
A2 (t + 1)
. . . A39 (t + 1)
. . .
Q39 (t)
Server 39
Figure 7: Illustrative compatibility graph for the parallel-server model with L = K = 40. The left column represents customer classes and the right column represents servers. Each server has i.i.d. service probability psvc = 0.05 (geometric service times with parameter µ). A busy server remains unavailable until its current service is completed; upon completion, it becomes available for a new assignment. At each slot, after service completions are revealed, the scheduling policy assigns idle servers to waiting compatible customers. Let xℓk (t) ∈ {0, 1} indicate is assigned to class P whether idle server k P ℓ in slot t. Feasibility ensures xℓk (t) = 0 if (ℓ, k) ∈ / E, ℓ:(ℓ,k)∈E xℓk (t) ≤ 1, and k:(ℓ,k)∈E xℓk (t) ≤ Qℓ (t), so that no class is assigned more servers than its current queue length. In our experiments we use MaxWeight. The waiting queues then evolve as X Qℓ (t + 1) = Qℓ (t) − xℓk (t) + Aℓ (t + 1), ℓ ∈ [L]. k:(ℓ,k)∈E
Thus Q(t) tracks waiting customers only; customers that have been assigned to servers leave the waiting queue and occupy their servers for a random service duration. We sweep ε ∈ {0.005, 0.01, 0.02, 0.05}. The plotted metric is max0≤t≤T ∥Q(t)∥2 . The horizon is T = 2.5 × 105 .
A.2
Experiment 2: local versus global geometry
This experiment uses the two-queue system from Section 4 with service set S = {(1, 0), (0, a)}. The support function is H(q) = max{q1 , aq2 }, and the global Euclidean margin satisfies α(Π) ≍ a. We vary the anisotropy parameter a and compare the simulated expected peak with two predictions: 30
• the global prediction from Theorem 2.1, which pays the worst-direction margin α(Π); • the local prediction from Proposition 4.1, exploiting state-space collapse. The simulations track the local prediction much more closely than the global one, illustrating that state-space collapse can improve the entrance threshold by replacing worst-case geometry with the geometry actually visited by the process.
A.3
Experiment 3: CRP and variance in IQS
This experiment compares two effects that are invisible from the scalar slack alone: bottleneck geometry and arrival variability. Both comparisons use a generalized n × n IQS with n = 20 and ε = 0.01. The horizon is T = 105 and the plotted metric is the total-backlog peak max0≤t≤T ∥Qt ∥1 . CRP versus non-CRP geometry. The third experiment first isolates the effect of bottleneck geometry in a generalized IQS. We fix a switch size n, a fractional arrival matrix M , a slack parameter ε, we let the arrival process At satisfy: ( 0, with probability ε, At := M, with probability 1 − ε. Hence the mean matrix is λ = (1 − ε)M. Thus M is the displayed normalized load matrix, and the factor 1 − ε enforces the same row/column slack in both instances. Service is deterministic and schedules are chosen by MaxWeight. We compare two choices of M . The two load matrices M nonCRP and M CRP are defined in Section 6, which makes the dominant bottleneck effectively single-face: the first row is the main active constraint, while the diagonal entries distribute the remaining traffic without creating the same row/column intersection bottleneck as in the non-CRP construction. In both the actual arrival mean is (1 − ε)M , so the comparison keeps the global load scale fixed and changes only the active-face geometry. Independent versus synchronous arrivals. Both have mean load (1 − ε)/n per entry.
A.4
The two arrival processes are defined in Section 6.
Code and data availability
The replication package is provided at https://github.com/learning-decision/finite-time-queue-peaklaws. The experiments use synthetic data generated by the code; no proprietary data is required.
B
The scalar drift-to-peak principle
The queueing arguments in this paper use a scalar drift-to-peak principle to produce logarithmic finite-horizon bounds. This scalar estimate is a finite-horizon peak version of the classical drift-tohitting principle developed by Hajek [6]. Hajek proved exponential bounds for first-hitting and occupation times of real-valued processes with uniform negative drift above a level and exponentially controlled increments, with queueing applications including GI/G/1 workloads. Since max Xt ≥ x = {τx ≤ T }, τx := inf{t : Xt ≥ x}, 0≤t≤T
31
the scalar peak principle developed below should be understood as a tailored finite-horizon formulation of this hitting-time mechanism. The novelty in this paper is not the scalar drift-to-hitting argument itself, but how this scalar formulation is coupled to high-dimensional stochastic networks. In the global bound, the key step is to project along the current queue direction, where the drift and fluctuation scales normalize each other; see Section 3. In the local geometric analysis, the same scalar principle is applied after localization near a bottleneck face, with the projection direction given by the corresponding face normal; see Section 4.
B.1
Exponential drift above a threshold
Let (Xt )t≥0 be a nonnegative process adapted to (Ft ) and write ∆Xt := Xt+1 − Xt . Definition B.1 (Exponential drift above a threshold). Fix θ > 0. We say that Xt satisfies exponential drift above a threshold with parameters (θ, x0 , γ) if for every t ≥ 0, E eθ∆Xt | Ft ≤ e−γ a.s. on {Xt ≥ x0 }. (16) Definition B.2 (One-sided upward MGF envelope). Fix θ > 0. We say that Xt admits a one-sided upward MGF envelope at level θ if there exists M+ (θ) < ∞ such that + sup E eθ(∆Xt ) | Ft ≤ M+ (θ) a.s. (17) t≥0
Theorem B.1 (Exponential drift-to-peak). Assume that Xt satisfies (16) and (17) for some θ > 0, x0 ≥ 0, γ > 0, and M+ (θ) < ∞, and assume also that E[eθX0 ] < ∞. Then for every T ≥ 0 and every u ≥ 0, P If X0 ≤ x0 a.s., then
max Xt ≥ x0 + u
0≤t≤T
≤ e−θ(x0 +u) E[eθX0 ] + T M+ (θ)e−θu .
(18)
P max Xt ≥ x0 + u ≤ (T + 1)M+ (θ)e−θu . 0≤t≤T
In particular, if X0 ≤ x0 a.s., then with probability at least 1 − δ, max Xt ≤ x0 +
0≤t≤T
1 1 T +1 log M+ (θ) + log . θ θ δ
Proof. The path is naturally decomposed into excursions above the threshold x0 . For the initial excursion, define τ0 := inf{t ≥ 0 : Xt < x0 or Xt ≥ x0 + u} ∧ (T + 1). On {t < τ0 } we have Xt ≥ x0 , so (16) implies E[eθXt+1 | Ft ] ≤ eθXt . Hence (eθXt∧τ0 )t≥0 is a nonnegative supermartingale. Optional stopping gives eθ(x0 +u) P(Xτ0 ≥ x0 + u) ≤ E[eθXτ0 ] ≤ E[eθX0 ], that is, P(Xτ0 ≥ x0 + u) ≤ e−θ(x0 +u) E[eθX0 ]. 32
(19)
Now fix s ∈ {0, . . . , T − 1} and consider an excursion that starts between times s and s + 1. Let n o Es := Xs < x0 , Xs+1 ≥ x0 , ∃ t ∈ {s + 1, . . . , T } : Xt ≥ x0 + u before the next return below x0 . On Es , define τs := inf{t ≥ s + 1 : Xt < x0 or Xt ≥ x0 + u} ∧ (T + 1). Conditionally on Fs+1 , the same supermartingale argument on the interval [s + 1, τs ] yields P(Es | Fs+1 ) ≤ 1{Xs <x0 , Xs+1 ≥x0 } e−θ(x0 +u) eθXs+1 . Taking conditional expectation with respect to Fs , and using Xs+1 ≤ x0 + (∆Xs )+ on {Xs < x0 , Xs+1 ≥ x0 }, we obtain +
P(Es | Fs ) ≤ 1{Xs <x0 } e−θu E[eθ(∆Xs ) | Fs ] ≤ M+ (θ)e−θu . Therefore P(Es ) ≤ M+ (θ)e−θu
for every s = 0, . . . , T − 1.
(20)
If max0≤t≤T Xt ≥ x0 + u, then either the initial excursion hits x0 + u, or there exists s ∈ {0, . . . , T − 1} such that Es occurs. Combining (19) and (20) with a union bound proves (18). If X0 ≤ x0 a.s., then the first term in (18) is at most e−θu , and Jensen’s inequality gives M+ (θ) ≥ 1, so P max Xt ≥ x0 + u ≤ (T + 1)M+ (θ)e−θu . 0≤t≤T
The high-probability bound is the inversion of this inequality.
B.2
From negative drift and Bernstein fluctuations to exponential drift
The previous theorem becomes useful once the exponential drift is verified from a more primitive drift condition and a one-step fluctuation bound. Definition B.3 (Negative drift above a threshold). We say that Xt satisfies negative drift above a threshold with parameters (x0 , ∆) if for every t ≥ 0, E[∆Xt | Ft ] ≤ −∆
a.s. on {Xt ≥ x0 }.
(21)
Definition B.4 (Conditional Bernstein increments). We say that Xt satisfies conditional Bernstein increments with parameters (σ 2 , b) if for every t and every θ ∈ [0, 1/b), h i log E exp θ(∆Xt − E[∆Xt | Ft ]) Ft ≤
θ2 σ2 2(1 − θb)
a.s.
(22)
When b = 0 we interpret 1/b = ∞. Theorem B.2 (Bernstein drift-to-peak). Assume (21) and (22). Fix θ > 0 with θ < 1/b, interpreting 1/0 = ∞, and assume that the upward MGF envelope (17) holds at this θ. Define γ(θ) := θ∆ −
33
θ2 σ2 . 2(1 − θb)
If γ(θ) > 0, then Theorem B.1 applies with this choice of θ and γ(θ). In particular, if X0 ≤ x0 a.s., then P
≤ (T + 1)M+ (θ)e−θu .
max Xt ≥ x0 + u
0≤t≤T
If σ 2 + b > 0, choose θ∗ := min
∆ 1 , 2σ 2 2b
,
(23)
where ∆/(2σ 2 ) := ∞ when σ 2 = 0, and 1/(2b) := ∞ when b = 0. Then θ∗ < ∞ and γ(θ∗ ) ≥ θ∗ ∆/4. If X0 ≤ x0 a.s. and (17) holds at θ∗ , then max Xt ≤ x0 +
0≤t≤T
1 1 T +1 log M+ (θ∗ ) + log θ∗ θ∗ δ
with probability at least 1 − δ. Moreover 1/θ∗ ≍ max{σ 2 /∆, b}. If σ 2 = b = 0, then the Bernstein fluctuation term vanishes and γ(θ) = θ∆ for every θ > 0. In this deterministic-centered case the same tail bound holds for every θ at which (17) holds; no finite Bernstein scale restricts the tilt. Proof. Under (21) and (22), on {Xt ≥ x0 } we have h i log E[eθ∆Xt | Ft ] = θE[∆Xt | Ft ] + log E exp θ(∆Xt − E[∆Xt | Ft ]) Ft ≤ −θ∆ +
θ2 σ2 = −γ(θ). 2(1 − θb)
Thus (16) holds, and Theorem B.1 gives the asserted tail bound. Assume next that σ 2 + b > 0. The conventions in (23) make θ∗ finite and place it in (0, 1/b). Since θ∗ b ≤ 1/2 and θ∗ σ 2 ≤ ∆/2, θ∗2 σ 2 θ∗ ∆ ≤ θ∗2 σ 2 ≤ , 2(1 − θ∗ b) 2 so γ(θ∗ ) ≥ θ∗ ∆/2, and in particular γ(θ∗ ) ≥ θ∗ ∆/4. The displayed high-probability bound follows by taking u = θ∗−1 log((T + 1)M+ (θ∗ )/δ). The relation 1/θ∗ ≍ max{σ 2 /∆, b} is immediate from the definition of θ∗ . When σ 2 = b = 0, the curvature term in γ is identically zero, so γ(θ) = θ∆ for every admissible θ. The first part of the proof therefore applies at any θ > 0 for which the upward MGF envelope is available.
B.3
Why self-normalization matters
Theorem B.2 makes the main methodological point transparent. The logarithmic coefficient is governed by the ratio σ2 , ∆ where ∆ is the one-step drift above the threshold and σ 2 is the one-step fluctuation scale. In the queueing problems studied here these are not independent quantities. Above the threshold, both are proportional to the same directional workload. Schematically, ∆t ≳ εH(ut ),
σt2 ≲ DH(ut ), 34
hence
σt2 D ≲ . ∆t ε
This is the self-normalization phenomenon. The geometry of the schedule set still matters, but it enters through the threshold x0 , where one must guarantee that the deterministic contraction dominates lower-order quadratic terms.
C
Proofs for Section 2
This section verifies the scalar conditions of Appendix B for switched networks under MaxWeight.
C.1
Theorem C.1: a warm-up via global geometry
Let
1 ∥q∥22 . 2 The starting point is the standard quadratic drift inequality. Φ(q) :=
Lemma C.1 (Quadratic drift under conditional interior slack). Consider MaxWeight scheduling under Assumptions 2.1 and 2.2. Set D := Amax + Smax and B := D2 /2. Then E Φ(Qt+1 ) − Φ(Qt ) | Ft ≤ B − εH(Qt ) a.s. for every t. (24) Proof. From (2) and (x+ )2 ≤ x2 componentwise, ∥Qt+1 ∥22 ≤ ∥Qt + At+1 − St ∥22 = ∥Qt ∥22 + ∥At+1 − St ∥22 + 2⟨Qt , At+1 − St ⟩. Divide by 2 and take conditional expectation. Since ∥At+1 − St ∥2 ≤ D a.s., the quadratic term contributes at most B. By (3) and MaxWeight, E[⟨Qt , St ⟩ | Ft ] = ⟨Qt , st ⟩ = H(Qt ). Finally, (5) implies ⟨Qt , λt ⟩ ≤ (1 − ε)H(Qt ). Substituting these bounds proves (24). Lemma C.2 (Geometry comparison). For every q ∈ Rd+ , H(q) ≥ α(Π) ∥q∥2 . Proof. If q = 0 there is nothing to prove. Otherwise write w = q/ ∥q∥2 . By definition of α(Π), H(w) ≥ α(Π). Since H is positively homogeneous, H(q) = ∥q∥2 H(w) ≥ α(Π) ∥q∥2 . Theorem C.1 (Baseline peak law from global geometry). Consider MaxWeight scheduling under Assumptions 2.1 and 2.2. Let D := Amax + Smax and assume α(Π) > 0. Then for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, PeakT ≲
D2 T +1 D2 log + . εα(Π) δ εα(Π)
This appendix benchmark is the direction-blind quadratic-drift proof. It is useful for comparison because it places the global margin α(Π) in both the threshold and the logarithmic coefficient.
35
Proof of Theorem C.1. The proof turns the quadratic drift of Lemma C.1 into a linear drift for Xt := ∥Qt ∥2 . The concavity of the square root gives Xt+1 − Xt ≤
Φ(Qt+1 ) − Φ(Qt ) Xt
on {Xt > 0}.
Taking conditional expectation and using Lemmas C.1 and C.2 yields E[∆Xt | Ft ] ≤
B − εα(Π) Xt
on {Xt > 0}.
Hence if Xt ≥ x0 := 2B/(εα(Π)), then 1 E[∆Xt | Ft ] ≤ − εα(Π). 2 Also |∆Xt | ≤ D a.s. by the triangle inequality, so Hoeffding’s lemma gives (22) with σ 2 = D2 and b = 0, while (17) holds with M+ (θ) ≤ eθD . Theorem B.2 therefore yields max Xt ≲ x0 + D +
0≤t≤T
D2 T +1 log εα(Π) δ
with probability at least 1 − δ.
Since α(Π) ≤ Smax ≤ D, we have x0 = D2 /(εα(Π)) ≥ D, so the additive D is absorbed into the threshold. This proves the stated bound. The theorem is already informative: it is the nonasymptotic analogue of the classical mean bound Eπ ∥Q∥2 ≲ D2 /(εα(Π)). But it still attributes the logarithmic term to the worst global direction. The next subsection shows that this is not the right fluctuation scale.
C.2
Theorem 2.1: the self-normalized theorem for MaxWeight
The key estimate is a one-step bound for the queue norm itself. Lemma C.3 (Norm increment bound). For every q ∈ Rd \ {0}, every y ∈ Rd , and u = q/ ∥q∥2 , ∥q + y∥2 − ∥q∥2 ≤ ⟨u, y⟩ +
∥y∥22 . 2 ∥q∥2
(25)
Proof. Write q ∥q + y∥2 = ∥q∥22 + 2⟨q, y⟩ + ∥y∥22 = ∥q∥2 and apply
√
s
2⟨u, y⟩ ∥y∥22 1+ + , ∥q∥2 ∥q∥22
1 + z ≤ 1 + z/2 for z ≥ −1.
Lemma C.4 (MGF of a bounded nonnegative variable). Let Z be a nonnegative random variable with 0 ≤ Z ≤ A a.s., and write m := E[Z]. Then for every θ ∈ [0, 1/A), log E[eθZ ] ≤ θm +
θ2 Am . 2(1 − θA)
The same bound holds conditionally: if Z is Ft+1 -measurable and 0 ≤ Z ≤ A a.s., then log E[eθZ | Ft ] ≤ θE[Z | Ft ] + 36
θ2 A E[Z | Ft ] 2(1 − θA)
a.s.
Proof. For x ∈ [0, 1) we have ex ≤ 1 + x +
x2 . 2(1 − x)
Applying this with x = θZ and using Z 2 ≤ AZ gives eθZ ≤ 1 + θZ +
θ2 AZ . 2(1 − θA)
Taking expectations and using log(1 + y) ≤ y proves the unconditional bound; the conditional version is identical. Lemma C.5 (Directional net-input MGF). Assume Assumption 2.2. Fix t and an Ft -measurable vector u ∈ Rd+ with ∥u∥2 = 1. Let mt (u) := ⟨u, λt ⟩,
gt (u) := ⟨u, st ⟩.
For D := Amax + Smax and every θ ∈ [0, 1/D), θ2 D gt (u) log E exp θ ⟨u, At+1 ⟩ + ⟨u, st − St ⟩ Ft ≤ θmt (u) + 2(1 − θD)
(26)
whenever mt (u) ≤ gt (u). If service is deterministic, St = st a.s., then the sharper bound h i θ2 Amax gt (u) log E eθ⟨u,At+1 ⟩ Ft ≤ θmt (u) + 2(1 − θAmax )
(27)
holds for every θ ∈ [0, 1/Amax ). Proof. We first control the arrival term. Since u ∈ Rd+ and ∥u∥2 = 1, 0 ≤ ⟨u, At+1 ⟩ ≤ Amax a.s. Lemma C.4 gives h i θ2 Amax mt (u) log E eθ⟨u,At+1 ⟩ Ft ≤ θmt (u) + . 2(1 − θAmax ) For the service-shortfall term, set Y := ⟨u, St ⟩. Then 0 ≤ Y ≤ Smax and E[Y | Ft ] = gt (u). The elementary inequality e−x ≤ 1 − x + x2 /2 for x ≥ 0 yields E[e−θY | Ft ] ≤ 1 − θgt (u) +
θ2 Smax gt (u) . 2
Multiplying by eθgt (u) and using log(1 + z) ≤ z gives log E[eθ(gt (u)−Y ) | Ft ] ≤
θ2 Smax gt (u) . 2
Conditional independence of At+1 and St given Ft factorizes the two conditional MGFs. Since mt (u) ≤ gt (u) and θD < 1, Amax mt (u) (Amax + Smax )gt (u) + Smax gt (u) ≤ . 1 − θAmax 1 − θD Combining the displayed bounds proves (26). If St = st a.s., the service-shortfall term vanishes and the arrival estimate, together with mt (u) ≤ gt (u), gives (27). 37
Proof of Theorem 2.1. Set Xt := ∥Qt ∥2 and let ut := Qt /Xt on {Xt > 0}. By nonexpansiveness of projection onto Rd+ and Lemma C.3, ∆Xt ≤ ⟨ut , At+1 ⟩ + ⟨ut , st − St ⟩ − H(ut ) +
D2 2Xt
on {Xt > 0}.
(28)
Here D = Amax + Smax and we used ⟨ut , st ⟩ = H(ut ) under MaxWeight. Choose D2 x0 := . εα(Π) If Xt ≥ x0 , then Lemma C.2 gives D2 εα(Π) ε ≤ ≤ H(ut ), 2Xt 2 2 and hence
ε H(ut ) on {Xt ≥ x0 }. (29) ∆Xt ≤ ⟨ut , At+1 ⟩ + ⟨ut , st − St ⟩ − 1 − 2 For this direction, set mt := ⟨ut , λt ⟩ and gt := ⟨ut , st ⟩ = H(ut ). The slack condition gives mt ≤ (1 − ε)gt , so Lemma C.5 yields, for every θ ∈ [0, 1/D), ε θ2 Dgt log E[eθ∆Xt | Ft ] ≤ −θ 1 − gt + θmt + 2 2(1 − θD) 2 θ Dgt θε . ≤ − gt + 2 2(1 − θD) Take θ :=
ε . 4D
Then θD ≤ 1/4, and the last display is at most −
θε θεα(Π) gt ≤ − 3 3
on {Xt ≥ x0 }.
Thus the exponential-drift condition (16) holds. Moreover, a service realization can only decrease queues, so positive norm increments are caused by arrivals: (∆Xt )+ ≤ (Qt + At+1 )+ 2 − ∥Qt ∥2 ≤ ∥At+1 ∥2 ≤ Amax ≤ D. Therefore (17) holds with M+ (θ) ≤ eθD . Since Q0 = 0, Theorem B.1 gives max Xt ≲ x0 + D +
0≤t≤T
1 T +1 log θ δ
with probability at least 1 − δ. Finally, 1/θ = 4D/ε and x0 ≥ D because α(Π) ≤ H(u) ≤ Smax ≤ D for some unit u ∈ Rd+ . This proves the high-probability bound.
38
Expectation bound.
More precisely, we have just shown that
P(PeakT ≥ x0 + D + s) ≤ (T + 1)e−θs
for every s ≥ 0,
where x0 = D2 /(εα(Π)) and θ = ε/(4D). Therefore Z ∞ E[PeakT ] ≤ x0 + D + min{1, (T + 1)e−θs } ds 0
1 + log(T + 1) . ≤ x0 + D + θ Since x0 ≥ D and 1/θ ≍ D/ε, this yields E[PeakT ] ≲
D D2 log(T + 1) + , ε εα(Π)
as claimed in the expectation bound. Deterministic service refinement. When St = st a.s., the term ⟨ut , st − St ⟩ vanishes in (29). Applying the deterministic-service part of Lemma C.5 gives, on {Xt ≥ x0 }, log E[eθ∆Xt | Ft ] ≤ −
θε θ2 Amax H(ut ) H(ut ) + . 2 2(1 − θAmax )
With θ := ε/(4Amax ) when Amax > 0, the right-hand side is at most −cθεH(ut ) for a universal c > 0. Also (∆Xt )+ ≤ Amax . The same exponential-drift peak lemma therefore replaces 1/θ ≍ D/ε by Amax /ε, while the entrance threshold remains x0 = D2 /(εα(Π)). If Amax = 0, the queue is nonincreasing from Q0 = 0 and the claim is immediate. Integrating the resulting tail bound proves the expectation statement. This proves the entire theorem.
C.3
Comparison with the classical steady-state bound
The finite-time peak law should be compared with the classical steady-state mean bound derived from the same quadratic drift. Proposition C.1 (Classical steady-state mean comparison). Assume the time-homogeneous Markovchain version of Lemma C.1: the primitive conditional laws are fixed, MaxWeight is used, and the bounded drift inequality (24) holds with the same constants at every state. Suppose the chain has an invariant distribution π such that, for Q̄ ∼ π, E∥Q̄∥22 < ∞. For a continuous, nonnegative, positively homogeneous functional V : Rd+ → R+ with V (q) > 0 for all q ̸= 0, q ≥ 0, define αV (Π) := inf{HΠ (w) : w ∈ Rd+ , V (w) = 1}. If αV (Π) > 0, then E[V (Q̄)] ≤
D2 . 2εαV (Π)
In particular, taking V (q) = ∥q∥2 , for which αV (Π) = α(Π), gives E Q̄ 2 ≤ 39
D2 . 2εα(Π)
Proof. The finite second-moment assumption justifies taking expectations of the unbounded quadratic Lyapunov drift in steady state. Since Qt ∼ π implies Qt+1 ∼ π, E[Φ(Qt+1 ) − Φ(Qt )] = 0. Taking expectations in (24) gives E[H(Q̄)] ≤
D2 . 2ε
By definition of αV (Π), positive homogeneity gives H(q) ≥ αV (Π)V (q) for every q ∈ Rd+ . The result follows. The proposition controls a steady-state mean. Theorem 2.1 controls the entire peak process with high probability. The two bounds have the same base scale. The extra log T is the price of looking at extremes over a horizon instead of at a single steady-state sample. This is why we call the logarithmic term the finite-time shadow of exponential steady-state tails.
C.4
Directional certificate and LyapOpt
Here we provide the directional certificate in Remark 2.2: any scheduling policy satisfying this certificate will enjoy a self-normalized logarithmic queue peak law. We then verify this directional certificate for LyapOpt [12]. Proposition C.2 (A general directional certificate). Consider any Ft -measurable policy st ∈ S under Assumptions 2.1 and 2.2, with Q0 = 0. Let Xt := ∥Qt ∥2 and let ut := Qt /Xt on {Xt > 0}. Suppose that there exist constants xcert ≥ 0, ε⋆ ∈ (0, 1), cG ≥ 1, and α > 0, and an Ft -measurable random variable Gt , such that, on {Xt ≥ xcert }, Gt ≥ α,
Gt ≤ ⟨ut , st ⟩ ≤ cG Gt ,
⟨ut , λt ⟩ ≤ (1 − ε⋆ )Gt .
Set D := Amax + Smax . Then, for every T ≥ 1 and δ ∈ (0, 1), D2 cG D T +1 P PeakT ≲ xcert + + ≥ 1 − δ. log ε⋆ α ε⋆ δ Moreover, E[PeakT ] ≲ xcert +
D2 cG D + log(T + 1). ε⋆ α ε⋆
If service is deterministic after the decision, the two conclusions hold with cG D/ε⋆ replaced by cG Amax /ε⋆ . Proof. We repeat the MaxWeight proof with Gt replacing H(ut ). Set D2 x0 := max xcert , . ε⋆ α On {Xt ≥ x0 }, the norm increment bound gives ∆Xt ≤ ⟨ut , At+1 ⟩ + ⟨ut , st − St ⟩ − ⟨ut , st ⟩ +
D2 ε⋆ ≤ ⟨ut , At+1 ⟩ + ⟨ut , st − St ⟩ − 1 − Gt . 2Xt 2
40
Indeed, the last step uses ⟨ut , st ⟩ ≥ Gt and D2 /(2Xt ) ≤ ε⋆ α/2 ≤ ε⋆ Gt /2. Put mt := ⟨ut , λt ⟩ and gt := ⟨ut , st ⟩. The certificate gives mt ≤ (1 − ε⋆ )Gt ≤ gt , so Lemma C.5 yields, for θ ∈ [0, 1/D), ε⋆ θ2 Dgt θε⋆ θ2 DcG Gt log E[eθ∆Xt | Ft ] ≤ −θ 1 − Gt + θmt + ≤− Gt + . 2 2(1 − θD) 2 2(1 − θD) Choose θ := ε⋆ /(4cG D). Since cG ≥ 1 and ε⋆ < 1, we have θD ≤ 1/4, and the last display is at most −θε⋆ Gt /3 ≤ −θε⋆ α/3. Thus the exponential-drift condition of Definition B.1 holds above x0 . As in the proof of Theorem 2.1, service can only decrease the queue relative to adding arrivals alone, so (∆Xt )+ ≤ Amax ≤ D and Definition B.2 holds with M+ (θ) ≤ eθD . Since Q0 = 0, Theorem B.1 gives the stated high-probability bound, and integrating its tail gives the expectation bound. When St = st a.s., the service-noise term vanishes. The arrival-only bound in Lemma C.5 gives the same argument with D replaced by Amax in the logarithmic coefficient; if Amax = 0, then the queue is nonincreasing from Q0 = 0 and the claim is immediate. Definition C.1 (LyapOpt in the present model). The LyapOpt policy chooses any Ft -measurable minimizer 2 sLO ∈ arg min (Qt − s)+ 2 . (30) t s∈S
This is the one-step quadratic Lyapunov lookahead of [12], specialized to the fixed scheduling set and mean-service convention used here. Lemma C.6 (LyapOpt preserves directional service above the entrance scale). Let q ∈ Rd+ \ {0}, 2 set u := q/ ∥q∥2 , and let sLO ∈ arg mins∈S ∥(q − s)+ ∥2 . Then ⟨u, sLO ⟩ ≥ H(u) −
2 Smax . 2 ∥q∥2
Proof. For every s ∈ S and every coordinate i, 2 qi − si + ≥ qi2 − 2qi si . Hence
2
(q − s)+ 2 ≥ ∥q∥22 − 2⟨q, s⟩. Let s̄ ∈ arg maxs∈S ⟨u, s⟩, so ⟨u, s̄⟩ = H(u). By optimality of sLO and by ∥s̄∥2 ≤ Smax , 2
2
2 ∥q∥22 − 2⟨q, sLO ⟩ ≤ (q − sLO )+ 2 ≤ (q − s̄)+ 2 ≤ ∥q − s̄∥22 ≤ ∥q∥22 − 2 ∥q∥2 H(u) + Smax .
Dividing by 2 ∥q∥2 proves the claim. Proposition C.3 (Self-normalized peak law for LyapOpt). Assume Assumptions 2.1 and 2.2, the LyapOpt policy (30), and Q0 = 0. Let D := Amax + Smax and assume α(Π) > 0. Then, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, PeakT ≲
D T +1 D2 log + . ε δ εα(Π)
Consequently, E[PeakT ] ≲
D D2 log(T + 1) + . ε εα(Π)
If service is deterministic, the logarithmic coefficient D/ε can be replaced by Amax /ε. 41
Proof. Set Xt := ∥Qt ∥2 . Fix a time t with Xt > 0 and write ut = Qt /Xt . Lemma C.6 gives ⟨ut , sLO t ⟩ ≥ H(ut ) − On the event Xt ≥ xcert :=
2 Smax . 2Xt
2 Smax , εα(Π)
Lemma C.2 gives H(ut ) ≥ α(Π), and therefore ε ⟨ut , sLO ⟩ ≥ 1 − H(ut ). t 2 Set
ε Gt := 1 − H(ut ), 2
ε ε⋆ := , 2
ε α := 1 − α(Π), 2
cG :=
1 . 1 − ε/2
Since ε ∈ (0, 1), α ≥ α(Π)/2 and cG ≤ 2. The preceding display gives ⟨ut , sLO t ⟩ ≥ Gt , while the LO support bound gives ⟨ut , st ⟩ ≤ H(ut ) = cG Gt . The interior slack condition gives ε Gt = (1 − ε⋆ )Gt . ⟨ut , λt ⟩ ≤ (1 − ε)H(ut ) ≤ 1 − 2 Thus LyapOpt satisfies the certificate of Proposition C.2. Applying that proposition and using Smax ≤ D, ε⋆ = ε/2, α ≥ α(Π)/2, and cG ≤ 2 gives the high-probability bound. The expectation and deterministic-service statements follow from the corresponding conclusions of Proposition C.2.
C.5
Theorem 2.3: one-dimensional lower bound
Fix A ≥ 1 and let p :=
1−ε . A+1
Let (Xt )t≥1 be i.i.d. with Xt =
( A, −1,
with probability p,
(31)
with probability 1 − p.
Then EXt = pA − (1 − p) = −ε. Define Qt+1 = (Qt + Xt+1 )+ ,
Q0 = 0,
MT := max Qt . 0≤t≤T
Lemma C.7. Let σ0 := 0 and σr+1 := inf{t > σr : Qt = 0}. Set Lr := σr+1 − σr ,
Prcyc :=
max
σr ≤t≤σr+1
Qt .
Then (Lr , Prcyc )r≥0 are i.i.d. Moreover, for every integer M ≥ 1, if ΣM := then MT ≥ max Prcyc .
PM −1 r=0
Lr = σM ≤ T ,
0≤r<M
Proof. The process regenerates whenever it returns to zero, so the cycle pairs are i.i.d. If σM ≤ T , then the first M cycles are completed by time T , and their peaks are included in the horizon-T maximum. 42
Lemma C.8. There is a universal constant C such that EL0 ≤ 3/ε. Consequently, if M := ⌊εT /12⌋, then 3 P(ΣM ≤ T ) ≥ . (32) 4 Proof. If the first increment of a cycle is −1, the cycle length is one. If it is +A, compare the subsequent evolution with the unreflected walk Wm = A +
m X
Xr ,
τ := inf{m ≥ 0 : Wm ≤ 0}.
r=1
For N ≥ 1, the stopped time τ ∧ N is bounded, so optional stopping for the martingale Wm + εm gives EWτ ∧N + εE[τ ∧ N ] = A. Before time τ the walk is positive, and at time τ it can undershoot the origin by at most one, because the only downward jump is −1. Thus Wτ ∧N ≥ −1. Hence εE[τ ∧ N ] = A − EWτ ∧N ≤ A + 1. Monotone convergence gives Eτ ≤ (A + 1)/ε. Therefore A+1 1 3 EL0 ≤ 1 + p 1 + ≤2+ ≤ . ε ε ε Thus EΣM ≤ 3M/ε ≤ T /4, and Markov’s inequality gives (32). Lemma C.9. For k ≥ A, let βk := P(P0cyc ≥ k). There exists r > 1 solving prA + (1 − p)r−1 = 1,
(33)
βk ≥ p (rA − 1) r−(k+A) .
(34)
and for this r, Proof. First we justify the root. Put ϕ(θ) := peAθ + (1 − p)e−θ . Then ϕ(0) = 1, ϕ′ (0) = −ε < 0, ϕ is strictly convex, and ϕ(θ) → ∞ as θ → ∞. Hence there is a ∗ unique positive root θ∗ > 0 of ϕ(θ) = 1; set r = eθ > 1. This is exactly (33). Condition on the first increment being +A. Until the cycle returns to zero, the reflected and unreflected walks agree. Let the unreflected walk start from A, and let τ0 be its first time at or below zero and τk its first time at or above k. The process rWt is a martingale by (33). First note that τ0 ∧ τk < ∞ a.s. For N ≥ 1, optional stopping for the martingale Wt + εt at (τ0 ∧ τk ) ∧ N gives EW(τ0 ∧τk )∧N + εE[(τ0 ∧ τk ) ∧ N ] = A. The stopped walk is always at least −1: it is positive before τ0 , and the first crossing of the nonpositive half-line has overshoot at most one. Hence E[(τ0 ∧ τk ) ∧ N ] ≤ Letting N → ∞ shows that τ0 ∧ τk is finite a.s. 43
A+1 . ε
Now stop the martingale rWt at (τ0 ∧ τk ) ∧ N . The stopped values are bounded by rk+A : before stopping the walk lies below k, at τk it overshoots by at most A, and at τ0 it lies in [−1, 0]. Dominated convergence gives rA = EA rWτ0 ∧τk . On {τ0 < τk }, the terminal value is at most 1; on {τk < τ0 }, it is at most rk+A . Therefore rA ≤ 1 · PA (τ0 < τk ) + rk+A PA (τk < τ0 ), which gives PA (τk < τ0 ) ≥ (rA − 1)r−(k+A) . Multiplying by the probability p of the first upward jump proves the claim. Lemma C.10. Let θ∗ := log r, where r is defined by (33). For ε ≤ 1/8, 8ε ε ≤ θ∗ ≤ . 16A A Consequently, for all k ≥ A, βk ≥ c
ε ε exp −C (k + A) A A
(35)
for universal constants c, C > 0. Proof. Let ϕ(θ) := EeθX1 . Then ϕ(0) = 1, ϕ′ (0) = −ε, and θ∗ is the positive root of ϕ(θ) = 1. For θ0 := ε/(16A), using ex ≤ 1 + x + x2 for 0 ≤ x ≤ 1 and e−x ≤ 1 − x + x2 /2 gives ε2 ε2 ϕ(θ0 ) − 1 ≤ −εθ0 + θ02 pA2 + (1 − p)/2 ≤ − + < 0. 16A 128A Thus θ∗ ≥ θ0 . For θ1 := 8ε/A, using ex ≥ 1 + x + x2 /2 and e−x ≥ 1 − x gives 1 ϕ(θ1 ) − 1 ≥ −εθ1 + pA2 θ12 . 2 Since pA2 = (1 − ε)A2 /(A + 1) ≥ 7A/16, the right-hand side is positive; hence θ∗ ≤ θ1 . Also ∗ rA − 1 = eAθ − 1 ≥ Aθ∗ /2 ≥ ε/32. Combining this with p ≍ 1/A and (34) proves (35). Lemma C.11. There exist universal constants c, C > 0 such that, for T ≥ CA/ε2 , A ε2 T E[MT ] ≥ c log 1 + . ε A Proof. Let M := ⌊εT /12⌋. Choose k :=
ε2 T A log 1 + − A, 2C0 ε A
where C0 is the constant in (35). For C large enough, k ≥ A and −1/2 ε ε2 T βk ≥ c0 1+ . A A Also M ≥ εT /24, so M βk ≥ log 4 after increasing C. Hence 3 cyc P max Pr ≥ k ≥ 1 − (1 − βk )M ≥ . 0≤r<M 4 By (32) and the union bound, the event above intersects {ΣM ≤ T } with probability at least 1/2. Lemma C.7 then gives P(MT ≥ k) ≥ 1/2, and therefore EMT ≥ k/2. The definition of k gives the result. 44
Lemma C.12. There exist universal constants c, C, c′ > 0 such that, whenever A CA ≤ T ≤ c′ 2 , ε one has
√ E[MT ] ≥ c AT . P P Proof. Let WT := Tt=1 Xt and ZT := WT + εT = Tt=1 (Xt + ε). The reflected walk dominates the unreflected walk, so MT ≥ WT+ . The centered increment ξ := X1 + ε has variance σ 2 ≍ A and fourth moment E|ξ|4 ≤ CA3 . Hence EZT4 ≤ C(T A3 + T 2 A2 ) ≤ C ′ T 2 A2 √ for√T ≥ CA. Paley–Zygmund applied to ZT2 gives P(|ZT | ≥ c0 AT ) ≥ c1 , and therefore E|ZT | ≥ c2 AT . Since EZT = 0, EZT+ = 12 E|ZT |. Thus √ EWT+ = E(ZT − εT )+ ≥ EZT+ − εT ≥ c3 AT − εT. √ Choosing c′ > 0 small enough makes εT ≤ (c3 /2) AT , proving the claim. EZT2 = T σ 2 ≍ AT,
Lemma C.13 (A constant-scale lower bound). There exist universal constants c, C > 0 such that, whenever T ≥ CA, E[MT ] ≥ cA. Proof. If at least one of the first T increments is equal to A, then MT ≥ A. Since ε ≤ 1/8 and A ≥ 1, 1−ε 7 p= ≥ . A+1 16A Thus, for T ≥ CA with C large enough, 1 7T T ≥ , P(MT ≥ A) ≥ 1 − (1 − p) ≥ 1 − exp − 16A 2 and the claim follows. Proof of Theorem 2.3. Fix A ≥ 1 and use the construction above. The increment law (31) is realized by a queue with deterministic service St = st = 1 and arrivals equal to A + 1 with probability (1 − ε)/(A + 1) and 0 otherwise. Thus Amax = A + 1, Smax = 1, the upward net-input jump is A, and the mean net input is −ε. Let (cs , Cs , c′s ) be constants for Lemma C.12, let (cℓ , Cℓ ) be constants for Lemma C.11, and let (cb , Cb ) be constants for Lemma C.13. Increase the universal lower-horizon constant in the theorem so that T ≥ CA =⇒ T ≥ Cs A and T ≥ Cb A. It remains to prove E[MT ] ≥ c min
√
A ε2 T AT , log 1 + . ε A
(36)
If T ≤ c′s A/ε2 , Lemma C.12 applies and gives the first term in (36). If T ≥ Cℓ A/ε2 , Lemma C.11 gives the second term. It remains to consider the interval A A c′s 2 < T < Cℓ 2 . ε ε 45
First suppose c′s A/ε2 ≥ Cs A. Then Ts := c′s A/ε2 lies in the range of Lemma C.12; monotonicity of T 7→ MT gives p p A EMT ≥ EMTs ≥ cs ATs = cs c′s . ε On the same interval, the right-hand side of (36) is at most p A A Cℓ , log(1 + Cℓ ) , min ε ε so (36) follows after reducing c. It remains to handle the case c′s A/ε2 < Cs A. In this case ε is bounded below by the positive universal constant ( r ) 1 c′s η := min . , 8 Cs p Indeed, if the case can occur under ε ≤ 1/8, then ε > c′s /Cs ≥ η. Since T < Cℓ A/ε2 ≤ Cℓ A/η 2 , the right-hand side of (36) is at most a universal multiple of A. Lemma C.13, which applies because T ≥ Cb A, gives EMT ≥ cb A and proves (36) in the last case. This is exactly the displayed lower bound in Theorem 2.3 for all T ≥ CA.
C.6
Theorem 2.4: geometry-threshold lower bound
Proof of Theorem 2.4. The construction is the simplex server. Its essential feature is pathwise: after t slots, no sequence of schedules can have touched more than t coordinates. Fix d ≥ 2 and let S = {e1 , . . . , ed } ⊂ Rd+ . For this schedule set, the downward-closed capacity region is exactly ( ) d X d Π = x ∈ R+ : xi ≤ 1 . i=1
P P Indeed, if x ≤ r coordinatewise for some r ∈ conv(S), then i xi ≤ i ri = 1. Conversely, if P P x ∈ Rd+ and i xi ≤ 1, then the vector r defined by r1 = x1 + 1 − i xi and ri = xi for i ≥ 2 belongs to conv(S) and satisfies x ≤ r. There is no post-decision service noise: for any schedule sequence, St = st in every slot. Thus Smax = 1. Since the capacity support is evaluated only on nonnegative directions, H(q) = max⟨q, x⟩ = max qi , x∈Π
Therefore
α(Π) = inf
1≤i≤d
q ∈ Rd+ .
max wi : w ∈ Rd+ , ∥w∥2 = 1 1≤i≤d
1 =√ . d
The lower bound follows from 1 = ∥w∥22 ≤ d(maxi wi )2 ; equality is attained at w = d−1/2 1. For the prescribed ε ∈ [1/4, 1/2], take deterministic arrivals At+1 ≡ a1,
a :=
1−ε . d
√ Then λt = a1 and ∥At+1 ∥2 = (1−ε)/ d ≤ 1. Since d−1 1 ∈ conv(S) ⊂ Π, we have λt = (1−ε)d−1 1 ∈ (1 − ε)Π. Thus Assumption 2.1 holds with slack ε. Assumption 2.2 also holds with Amax ≤ 1 46
and Smax = 1: the arrival vector is deterministic, St = st is conditionally degenerate given Ft , the identity E[St | Ft ] = st is exact, and the conditional independence requirement is therefore automatic. It remains to prove the lower bound uniformly over scheduling rules. We prove the stronger deterministic claim in the theorem. Fix any sequence s0 , . . . , sT0 −1 ∈ S, where T0 := ⌊d/2⌋. The sequence need not be generated by a nonanticipative rule. For 0 ≤ t ≤ T0 , let Nt := {i ∈ {1, . . . , d} : sτ,i = 0 for every 0 ≤ τ < t} . This is the set of coordinates that have received no service during the first t slots. Each schedule sτ is a unit vector, so in one slot at most one new coordinate can leave this set. Hence |Nt | ≥ d − t,
0 ≤ t ≤ T0 .
(37)
For every i ∈ Nt , the coordinate i has had zero service in all slots 0, . . . , t − 1. The queue recursion (2) then gives the exact identity Qt,i = ta, i ∈ Nt . (38) To verify (38), start from Q0,i = 0. If i ∈ Nt , then for each 0 ≤ τ < t we have Sτ,i = sτ,i = 0, and therefore Qτ +1,i = (Qτ,i + a)+ = Qτ,i + a; induction over τ gives Qt,i = ta. Combining (37) and (38), for every 0 ≤ t ≤ T0 , ∥Qt ∥22 ≥
X
Q2t,i = |Nt |t2 a2 ≥ (d − t)t2
i∈Nt
1−ε d
2 .
Apply this at t = T0 . For d ≥ 2, T0 ≥ d/3 and d − T0 ≥ d/2. The first inequality is immediate when d = 2, and for d ≥ 3 follows from ⌊d/2⌋ ≥ (d − 1)/2 ≥ d/3. Thus 1 − ε√ 1 √ 1−ε p d ≥ √ d, T0 d − T0 ≥ √ d 3 2 6 2 √ where the last step uses ε ≤ 1/2. Since α(Π) = 1/ d and ε ≥ 1/4, ∥QT0 ∥2 ≥
1 √ 1 1 ε 1 √ d= √ ≥ √ . εα(Π) εα(Π) 6 2 6 2 24 2 Therefore max ∥Qt ∥2 ≥ ∥QT0 ∥2 ≥
0≤t≤T0
1 1 √ . 24 2 εα(Π)
√ This proves the deterministic sequence-level lower bound with c = 1/(24 2). A randomized nonanticipative policy produces, on each realization of its internal randomization, one admissible schedule sequence; the deterministic bound applies to that realization. Hence the lower bound holds almost surely and, √ by taking expectations, under every randomized nonanticipative policy. Finally, because α(Π) = 1/ d, the horizon T0 = ⌊d/2⌋ is Θ(1/α(Π)2 ) and is polynomial in 1/α(Π).
C.7
Theorem 2.2: a slack-free square-root envelope
Proof of Theorem 2.2. Set PeakT := max ∥Qs ∥2 . 0≤s≤T
47
From (2) and ∥At+1 − St ∥2 ≤ D a.s., ∥Qt+1 ∥22 ≤ ∥Qt ∥22 + D2 + 2⟨Qt , At+1 − St ⟩. Taking conditional expectations and using λt ∈ Π together with MaxWeight, E[⟨Qt , At+1 − St ⟩ | Ft ] = ⟨Qt , λt ⟩ − ⟨Qt , st ⟩ = ⟨Qt , λt ⟩ − H(Qt ) ≤ 0. Hence E[∥Qt+1 ∥22 | Ft ] ≤ ∥Qt ∥22 + D2 . Fix T ≥ 1 and define, for 0 ≤ t ≤ T , Yt := ∥Qt ∥22 + (T − t)D2 . Then (Yt )Tt=0 is a nonnegative supermartingale and Y0 = T D2 . Since Peak2T ≤ max0≤t≤T Yt , Doob’s maximal inequality gives E[Y0 ] D2 T 2 2 2 P(PeakT ≥ r) = P(PeakT ≥ r ) ≤ P max Yt ≥ r ≤ = ∀r > 0. 0≤t≤T r2 r2 Integrating the tail, Z ∞ P(PeakT ≥ r) dr
E[PeakT ] = 0
Z D √T ≤
√ D2 T dr = 2D T . √ 2 D T r
Z ∞ 1 dr +
0
This proves the theorem.
D
Proofs for Section 3
D.1
Queue-Bernstein calculus and examples
This subsection records the elementary calculations behind Example 3.1. The common inequality is ex − 1 − x ≤
x2 2(1 − |x|)
for |x| < 1.
(39)
We use it conditionally throughout. Lemma D.1 (Basic queue-Bernstein examples). The primitives listed in Example 3.1 satisfy Definition 3.1 with the stated parameters. Proof. Fix w ∈ [0, 1]d . Bernoulli and binomial coordinates. Let Zi be a sum of conditionally independent unit Bernoulli variables, and let mi = E[Zi | G]. Independence and (39) give, for |θ| < 1, h i X θ2 w2 m θ2 ⟨w, m⟩ i i log E eθ⟨w,Z−m⟩ | G ≤ ≤ . 2(1 − |θ|) 2(1 − |θ|) i
Thus (ν, b) = (1, 1). 48
Poisson coordinates. If Zi are conditionally independent Poisson variables with means mi , then h i X log E eθ⟨w,Z−m⟩ | G = mi eθwi − 1 − θwi . i
Using (39) and wi2 ≤ wi gives the same (1, 1) bound. Bounded total mass. If ∥Z∥1 ≤ L a.s., then 0 ≤ Y := ⟨w, Z⟩ ≤ L and mY := E[Y | G] = ⟨w, m⟩. For 0 ≤ θ < 1/L, Lemma C.4 gives log E[eθ(Y −mY ) | G] ≤
θ2 LmY . 2(1 − Lθ)
For the lower tail, let η ∈ [0, 1/L). Since e−x ≤ 1 − x + x2 /2 for x ≥ 0 and Y 2 ≤ LY , η 2 LmY E[e−ηY | G] ≤ 1 − ηmY + , 2 η 2 LmY log E[e−η(Y −mY ) | G] ≤ ηmY + log 1 − ηmY + 2 2 2 η LmY η LmY ≤ . ≤ 2 2(1 − Lη) Combining the two signs proves the asserted bound P for |θ| < 1/L. Hence (ν, b) = (L, L). Bounded-batch compound Poisson input. Let Z = N k=1 Bk , where N is conditionally Poisson and the batches are conditionally i.i.d. with ∥Bk ∥1 ≤ L. Put Y = ⟨w, B1 ⟩ ≤ L. The compound-Poisson MGF gives log E[eθ⟨w,Z−m⟩ | G] = η E eθY − 1 − θY | G , where η is the conditional Poisson intensity. Applying (39) with |θ| < 1/L and using Y 2 ≤ LY yields θ2 L ηE[Y | G] θ2 L ⟨w, m⟩ log E[eθ⟨w,Z−m⟩ | G] ≤ = . 2(1 − L|θ|) 2(1 − L|θ|) Gamma and exponential coordinates. Let Zi be conditionally independent Gamma variables with scales βi ≤ β, shapes ki , and means mi = βi ki . For |θ| < 1/β, log E[eθwi (Zi −mi ) | G] = ki −θβi wi − log(1 − θβi wi ) . The inequality −x − log(1 − x) ≤ x2 /[2(1 − |x|)] for |x| < 1, together with wi2 ≤ wi , gives log E[eθwi (Zi −mi ) | G] ≤
θ2 βi mi wi θ2 βmi wi ≤ . 2(1 − β|θ|) 2(1 − β|θ|)
Summing over i proves (ν, b) = (β, β). Exponential coordinates are the special case ki = 1. Lemma D.2 (Elementary closure properties). Conditionally independent queue-Bernstein conditions add: if Z (1) and Z (2) have parameters (ν1 , b1 ) and (ν2 , b2 ), then their sum is queue-Bernstein with parameters (ν1 + ν2 , max{b1 , b2 }), and also with (ν1 + ν2 , b1 + b2 ). Deterministic primitives have parameters (0, 0). Proof. The centered MGF of a conditionally independent sum factorizes. The denominator can be bounded using 1 − max{b1 , b2 }|θ| ≤ 1 − bi |θ|. The looser parameter b1 + b2 is sometimes more convenient and is the one used in the theorem statement. 49
D.2
Queue-Bernstein geometric threshold formula
Theorem 3.1 involves a key geometric threshold xQB , whose precise formula and related properties are provided in this appendix. When bA + bS + (νA + νS )/ε > 0, set θQB := c0
νA + νS bA + bS + ε
−1 ,
(40)
where c0 > 0 is a sufficiently small universal constant. For a candidate entrance level x ≥ 1, define 2 z , 2z , z ≥ 0. ρx (z) := min 2x The term z 2 /(2x) is the usual Euclidean norm-expansion error for a one-slot change of length z when ∥Qt ∥2 ≥ x. The term 2z is a Lipschitz fallback for rare large changes. For θ > 0, set Jt := ∥At+1 − St ∥2 and define h i Kup (θ) := sup ess sup E e8θJt | Ft , (41) t≥0
κθ (x) := sup ess sup log E[exp(2θρx (Jt ))|Ft ] , t≥0 θεα(Π) . xcurv (θ) := inf x ≥ 1 : κθ (x) ≤ 4 The numerical factor 8 is inessential. It gives a little extra exponential moment, which is useful for the uniform integrability step below. Finally define the queue-Bernstein entrance scale used in Theorem 3.1 by xQB := 1 + xcurv (θQB ) +
1 θQB
log Kup (θQB ),
bA + bS +
νA + νS > 0. ε
(42)
If bA + bS + (νA + νS )/ε = 0, all queue-Bernstein conditions are conditionally deterministic. In that degenerate case define D02 D0 := sup ess sup ∥At+1 − St ∥2 , xQB := 1 + C0 D0 + , εα(Π) t≥0 where C0 is a sufficiently large universal constant. This deterministic convention is finite under the theorem assumptions, since Π is compact and S is finite. If also ∥At+1 − St ∥2 ≤ D a.s., then D0 ≤ D, so this definition gives xQB ≤ C(1 + D + D2 /(εα(Π))). The logarithmic term is absent; Appendix D.3 proves the resulting deterministic pathwise bound. When the displayed queue-Bernstein scale is positive, xQB is finite under the assumptions of Theorem 3.1. Indeed, since S is finite and λt ∈ (1 − ε)Π, the conditional mean total arrival and service masses are uniformly bounded. The all-ones queue-Bernstein projection, applied with a sufficiently small universal constant c0 in (40), gives h i sup ess sup E e16θQB (∥At+1 ∥1 +∥St ∥1 ) | Ft < ∞. t
Because Jt ≤ ∥At+1 ∥1 + ∥St ∥1 , this implies Kup (θQB ) < ∞. It also gives uniform integrability for e4θQB Jt . To see the required uniform convergence, fix R > 0. On {Jt ≤ R}, ρx (Jt ) ≤ R2 /(2x). On 50
{Jt > R}, e2θQB ρx (Jt ) ≤ e4θQB Jt , and the displayed exponential moment bounds the tail uniformly by Ce−4θQB R . Letting first x → ∞ and then R → ∞ gives κθQB (x) ↓ 0. Hence xcurv (θQB ) < ∞. If ∥At+1 − St ∥2 ≤ D a.s., then ρx (∥At+1 − St ∥2 ) ≤ D2 /(2x), so xcurv (θQB ) ≲ D2 /(εα(Π)), while −1 θQB log Kup (θQB ) ≤ 8D. Thus D2 xQB ≤ C 1 + D + . εα(Π) In a nontrivial bounded system α(Π) ≤ Smax ≤ D, so the additive D is absorbed by the displayed threshold.
D.3
Proof of Theorem 3.1
We prove a slightly sharper tilted statement and then choose θ = θQB . Lemma D.3 (Tilted queue-Bernstein peak estimate). Under the assumptions of Theorem 3.1, assume bA + bS + (νA + νS )/ε > 0. Let θ > 0 satisfy νA + νS −1 θ ≤ c bA + bS + (43) ε for a sufficiently small universal constant c. Assume in addition that Kup (θ) < ∞ and xcurv (θ) < ∞. Then, for every T ≥ 1 and δ ∈ (0, 1), with probability at least 1 − δ, (T + 1)Kup (θ) 1 log . θ δ
PeakT ≲ xcurv (θ) +
(44)
Proof. Let Xt := ∥Qt ∥2 and, on {Xt > 0}, set ut := Qt /Xt . On {Xt = 0}, choose any nonnegative unit vector. Write Yt+1 := At+1 − St ,
Jt := ∥Yt+1 ∥2 ,
Zt+1 := ⟨ut , At+1 ⟩ + ⟨ut , st − St ⟩.
Since projection onto Rd+ is nonexpansive, Lemma C.3 and the triangle inequality imply Xt+1 − Xt ≤ Zt+1 − H(ut ) + ρXt (Jt )
on {Xt > 0}.
(45)
Let b∗ := bA ∨ bS . Choose c in (43) so that 1 2θb∗ ≤ , 2
θ(νA + νS ) ε ≤ . 1 − 2θb∗ 4
Conditional independence and the queue-Bernstein bounds, applied to At+1 with tilt 2θ and to St with tilt −2θ, give 1 θ2 (νA ⟨ut , λt ⟩ + νS ⟨ut , st ⟩) log E[e2θZt+1 | Ft ] ≤ θ⟨ut , λt ⟩ + . 2 1 − 2θb∗
(46)
By Assumption 2.1 and MaxWeight, ⟨ut , λt ⟩ ≤ (1 − ε)H(ut ),
⟨ut , st ⟩ = H(ut ).
Substituting into (46) yields 1 3ε 2θZt+1 log E[e | Ft ] ≤ θ 1 − H(ut ). 2 4 51
(47)
Let x0 := 2xcurv (θ) + 1. The map x 7→ ρx (z) is nonincreasing for every fixed z, hence x 7→ κθ (x) is nonincreasing. Therefore the feasible set in the definition of xcurv (θ) is upward closed. Since x0 > xcurv (θ) and xcurv (θ) < ∞, the definition of the infimum gives some feasible y < x0 , and upward closure then makes x0 feasible. Thus h i θεα(Π) 1 log E e2θρx0 (Jt ) | Ft ≤ . (48) 2 8 On {Xt ≥ x0 }, combining (45), conditional Cauchy–Schwarz, (47), and (48) gives 1 1 log E[e2θZt+1 | Ft ] + log E[e2θρx0 (Jt ) | Ft ] 2 2 3θε θεα(Π) 5θεα(Π) ≤− H(ut ) + ≤− , 4 8 8 where the last step uses H(ut ) ≥ α(Π). Thus Xt satisfies the exponential drift condition (16) above threshold x0 at tilt θ. Moreover, (Xt+1 −Xt )+ ≤ Jt , so the upward-increment envelope (17) holds with M+ (θ) ≤ Kup (θ). Since X0 = 0 ≤ x0 , Theorem B.1 gives log E[eθ(Xt+1 −Xt ) | Ft ] ≤ −θH(ut ) +
P(PeakT ≥ x0 + u) ≤ (T + 1)Kup (θ)e−θu . Taking u = θ−1 log((T + 1)Kup (θ)/δ) proves (44). Proof of Theorem 3.1. If bA + bS + (νA + νS )/ε > 0, the finiteness argument in Appendix D.2 gives Kup (θQB ) < ∞ and xcurv (θQB ) < ∞. Thus Lemma D.3 applies with θ = θQB . By definition of xQB , xcurv (θQB ) +
1 θQB
log Kup (θQB ) ≤ xQB ,
1 θQB
≲ bA + bS +
νA + νS . ε
This gives the displayed bound in Theorem 3.1. The bounded-jump reduction follows from the last paragraph of Appendix D.2. It remains to handle the degenerate case bA + bS + (νA + νS )/ε = 0. The queue-Bernstein inequalities then have zero right-hand side. For each coordinate vector ei , Jensen’s inequality gives h i 1 ≤ E eθ(At+1,i −λt,i ) | Ft ≤ 1, θ > 0, and the equality case for the strictly convex exponential implies At+1,i = λt,i a.s. Applying the same argument to St gives St = st a.s. Thus the primitives are conditionally deterministic. Let Xt := ∥Qt ∥2 and let Yt+1 := At+1 − St . If D0 = 0, then Yt+1 = 0 a.s. for every t, and the path stays at the origin. Assume therefore that D0 > 0, and put a :=
D02 . εα(Π)
If Xt > 0, set ut = Qt /Xt . Lemma C.3, Assumption 2.1, and MaxWeight give Xt+1 − Xt ≤ ⟨ut , Yt+1 ⟩ +
D2 ∥Yt+1 ∥22 ≤ −εH(ut ) + 0 . 2Xt 2Xt
Consequently, whenever Xt ≥ a, the last display is at most −εα(Π)/2, so Xt+1 ≤ Xt . If Xt < a, nonexpansiveness of projection gives Xt+1 ≤ Xt + D0 < a + D0 . Since X0 = 0, induction yields the pathwise bound PeakT ≤ a + D0 ≤ xQB after increasing C0 , if necessary. This proves the theorem in the deterministic degenerate case, with no logarithmic term. 52
D.4
One-dimensional queue-Bernstein peaks and Kingman’s scale
The one-dimensional recursion admits a sharper argument than Theorem 3.1: there is no Euclidean curvature term, and the reflected workload is the running maximum of net-input partial sums. Theorem D.1 (One-dimensional queue-Bernstein peak). Let Qt+1 = (Qt + At+1 − St )+ ,
Q0 = 0,
where, conditional on Ft , At+1 and St are independent nonnegative random variables. Let λt = E[At+1 | Ft ] and st = E[St | Ft ], and assume λt ≤ (1 − ε)st a.s. for every t. Suppose At+1 and St satisfy the one-dimensional queue-Bernstein condition with parameters (νA , bA ) and (νS , bS ), uniformly over t. Then there is a universal constant C such that, for every T ≥ 1 and δ ∈ (0, 1), T +1 νA + νS log ≥ 1 − δ. P max Qt ≤ C bA + bS + 0≤t≤T ε δ Proof. Let
νA + νS . ε If K = 0, then bA = bS = νA = νS = 0. The queue-Bernstein inequalities have zero right-hand side. Jensen’s inequality, applied to eθ(At+1 −λt ) and eθ(St −st ) for θ > 0, forces At+1 = λt and St = st a.s. conditionally on Ft . Since λt ≤ (1 − ε)st ≤ st , the net input is nonpositive in every slot. Starting from Q0 = 0, the queue remains identically zero, and the stated bound holds with its zero right-hand side. We may therefore assume K > 0. Write Yt+1 := At+1 − St . The Lindley representation gives the pathwise identity !+ t−1 X Qt = max Yr+1 . K := bA + bS +
0≤k≤t
r=k
Fix θ > 0 satisfying νA + νS −1 θ ≤ c bA + bS + ε with c > 0 sufficiently small. The queue-Bernstein bounds and conditional independence give
θ2 νA λt θ2 νS st + 2(1 − bA θ) 2(1 − bS θ) 2 θ (νA + νS )st ≤ −θεst + ≤ 0. 2(1 − (bA + bS )θ)
log E[eθYt+1 | Ft ] ≤ θ(λt − st ) +
Here we used λt ≤ st and the choice of c in the last step. Hence, for each deterministic starting time k, the process ! m−1 X exp θ Yr+1 , m ≥ k, r=k
is a nonnegative supermartingale. Doob’s maximal inequality yields ! m−1 X P max Yr+1 ≥ u ≤ e−θu . k≤m≤T
r=k
A union bound over k = 0, 1, . . . , T , together with the Lindley representation, gives P max Qt ≥ u ≤ (T + 1)e−θu . 0≤t≤T
Taking u = θ−1 log((T + 1)/δ) proves the result. 53
For i.i.d. primitives with means EA = ρτ , ES = τ , and ρ = 1 − ε, a variance-to-mean queue-Bernstein scale has the same order as νA + νS ≍
Var(A) Var(S) + = ρc2a τ + c2s τ. EA ES
Thus the dominant logarithmic coefficient in Theorem D.1 is of order νA + νS τ (ρc2a + c2s ) ≍ , ε 1−ρ which matches Kingman’s scale up to universal constants when ρ = Ω(1). The theorem is a finite-horizon high-probability peak statement, whereas Kingman’s formula is a constant-level approximation for a steady-state mean.
E
Proofs for Section 4
E.1
Proposition 4.1: the two-queue collapse example
Proof of Lemma 4.1. The service is deterministic in Example 4.1, so the realized service in each slot equals the selected vector. Write Gt := Q1 (t) − aQ2 (t). 2 We first prove the collapse estimate G+ t ≤ 1 + a by induction. It holds at t = 0. Suppose it holds at time t. If MaxWeight serves queue 1, then Gt ≥ 0. The service vector is (1, 0), so
Q1 (t + 1) = (Q1 (t) + A1 (t + 1) − 1)+ ,
Q2 (t + 1) = Q2 (t) + A2 (t + 1).
There are two cases. If Q1 (t) + A1 (t + 1) ≥ 1, then one full unit of service is used in the first coordinate, and Gt+1 = Gt − 1 + A1 (t + 1) − aA2 (t + 1) ≤ Gt ≤ 1 + a2 , where the last inequality uses Gt = G+ t and the induction hypothesis. If instead Q1 (t)+A1 (t+1) < 1, then Q1 (t) = A1 (t + 1) = 0. Since queue 1 was selected, Gt ≥ 0, hence Q2 (t) = 0, and therefore Gt+1 = −aA2 (t + 1) ≤ 0. 2 Thus service of queue 1 preserves the induction invariant G+ t+1 ≤ 1 + a . If MaxWeight serves queue 2, then Gt ≤ 0. The service vector is (0, a), so
Q1 (t + 1) = Q1 (t) + A1 (t + 1),
Q2 (t + 1) = (Q2 (t) + A2 (t + 1) − a)+ .
If Q2 (t) + A2 (t + 1) ≥ a, then the second coordinate receives the full service amount a, and Gt+1 = Gt + a2 + A1 (t + 1) − aA2 (t + 1) ≤ 1 + a2 , because Gt ≤ 0, A1 (t + 1) ≤ 1, and A2 (t + 1) ≥ 0. If instead Q2 (t) + A2 (t + 1) < a, then Q2 (t) < a. Since Gt ≤ 0, we have Q1 (t) ≤ aQ2 (t) < a2 ≤ 1. The first queue is integer-valued, so Q1 (t) = 0, and hence Gt+1 = A1 (t + 1) ≤ 1 ≤ 1 + a2 . 54
2 Thus service of queue 2 also preserves the induction invariant G+ t+1 ≤ 1 + a . The induction closes and proves the first claim. We next prove the local drift statement. If MaxWeight serves queue 1, then Q1 (t) ≥ aQ2 (t). Since Yt ≥ 2, this forces Q1 (t) > 0; otherwise Q1 (t) = 0 would imply Q2 (t) = 0 and hence Yt = 0. Thus Q1 (t) ≥ 1, so the projection is inactive in the first coordinate and
Yt+1 = a(Q1 (t) + A1 (t + 1) − 1) + Q2 (t) + A2 (t + 1) = Yt − a + aA1 (t + 1) + A2 (t + 1). If MaxWeight serves queue 2, then Q1 (t) ≤ aQ2 (t), so Yt = aQ1 (t) + Q2 (t) ≤ (1 + a2 )Q2 (t). Thus Yt ≥ 2 implies
2 ≥ a. 1 + a2 The projection is therefore inactive in the second coordinate, and again Q2 (t) ≥
Yt+1 = a(Q1 (t) + A1 (t + 1)) + Q2 (t) + A2 (t + 1) − a = Yt − a + aA1 (t + 1) + A2 (t + 1). Therefore, on {Yt ≥ 2}, Yt+1 = Yt − a + aA1 (t + 1) + A2 (t + 1). Taking conditional expectations and using (9) gives E[Yt+1 − Yt | Ft ] ≤ −aε.
Proof of Proposition 4.1. Let Wt+1 := aA1 (t + 1) + A2 (t + 1). On {Yt ≥ 2}, Lemma 4.1 gives Yt+1 − Yt = Wt+1 − a. Moreover, by (9), mt := E[Wt+1 | Ft ] = a E[A1 (t + 1) | Ft ] + E[A2 (t + 1) | Ft ] ≤ a(1 − ε). Since 0 ≤ Wt+1 ≤ 1 + a ≤ 2 a.s., convexity of x 7→ eθx on [0, 2] gives eθx ≤ 1 +
x 2θ (e − 1), 2
0 ≤ x ≤ 2.
Thus
mt 2θ (e − 1). 2 Choose θ := ε/4 ≤ 1/4. Using log(1 + z) ≤ z and e2θ − 1 ≤ 2θ + 4θ2 for θ ∈ [0, 1/4], we obtain on {Yt ≥ 2} E[eθWt+1 | Ft ] ≤ 1 +
log E[eθ(Yt+1 −Yt ) | Ft ] = −aθ + log E[eθWt+1 | Ft ] mt 2θ ≤ −aθ + (e − 1) 2 ≤ −aθ + a(1 − ε)(θ + 2θ2 ) ≤ −aεθ + 2aθ2 = −
55
aε2 . 8
Hence Yt satisfies exponential drift above threshold 2 at parameter θ. Also (Yt+1 − Yt )+ ≤ Wt+1 ≤ 2, so the upward MGF condition holds with M+ (θ) ≤ e2θ . Since Y0 = 0 ≤ 2, Theorem B.1 gives max Yt ≲ 1 +
0≤t≤T
1 T +1 log ε δ
with probability at least 1 − δ.
To convert back to queue length, note that Q2 (t) ≤ Yt and the collapse bound gives Q1 (t) ≤ aQ2 (t) + 1 + a2 ≤ Yt + 2. Thus ∥Qt ∥2 ≤ ∥Qt ∥1 = Q1 (t) + Q2 (t) ≤ 2Yt + 2, which proves the proposition.
E.2
Theorem 4.1: finite-time state-space collapse under CRP
Proof of Theorem 4.1. The proof is a finite-horizon perpendicular-drift argument. The face margin gives a comparison point that rewards motion toward the active face, and the bottleneck projection removes the ordinary v-direction drift. The only difference from the classical stationary proof is that the comparison point is the predictable face point rt◦ , rather than a fixed nominal load; compare the drift decomposition in Eryilmaz and Srikant [5]. Let P⊥ z := z − ⟨v, z⟩v, Xt := Q⊥ = ∥P⊥ Qt ∥2 , Yt := ⟨v, Qt ⟩. t 2
We prove a negative drift for Xt above a deterministic threshold and then apply Theorem B.2. If ⊥ v ⊥ = {0}, then Q⊥ t = 0 for all t and the theorem is immediate; hence we assume below that v contains a unit vector. In this case the face margin is finite and satisfies δface ≤ 2Smax ≤ 2D.
(49)
Indeed, Π ⊆ {x ∈ Rd+ : ∥x∥2 ≤ Smax }: if x ∈ Π, then 0 ≤ x ≤ r coordinatewise for some r ∈ conv(S), so ∥x∥2 ≤ ∥r∥2 ≤ Smax . Fix any time t and work on a full-probability event on which Assumption 4.1 holds for rt◦ . For any ρ < δface and any unit vector e ⊥ v, the point rt◦ + ρe lies in H⋆ and hence, by the uniform relative-inradius condition, in F ⋆ ⊆ Π; also rt◦ ∈ F ⋆ ⊆ Π. Hence ρ = ∥(rt◦ + ρe) − rt◦ ∥2 ≤ 2Smax . Letting ρ ↑ δface gives (49). Fix t and work on the event Xt > 0. Put et := Q⊥ t /Xt and set ρ∗ := 3δface /4. Since et ⊥ v, the point rt◦ + ρ∗ et belongs to H⋆ and, because ρ∗ < δface and the fixed-face margin assumption is monotone in the radius, to F ⋆ ⊆ Π. Because MaxWeight maximizes the support function over Π for nonnegative queue weights, ⟨Qt , st ⟩ = H(Qt ) ≥ ⟨Qt , rt◦ + ρ∗ et ⟩ = ⟨Qt , rt◦ ⟩ + ρ∗ Xt . Since rt◦ ∈ F ⋆ , we have ⟨v, rt◦ ⟩ = µ. Using (10) and Qt = Yt v + Q⊥ t , we obtain ⟨Qt , λt − st ⟩ ≤ −ε⟨Qt , rt◦ ⟩ − ρ∗ Xt ◦ = −εµYt − ε⟨Q⊥ t , rt ⟩ − ρ∗ Xt ≤ −εµYt − ρ∗ − ε ∥rt◦ ∥2 Xt δface ≤ −εµYt − Xt 4
56
where the last step uses ε ≤ δface /(2Smax ) ≤ δface /(2 ∥rt◦ ∥2 ) and ρ∗ = 3δface /4. We next compare the drifts of the full quadratic Lyapunov function and its projection onto the bottleneck ray. Since coordinatewise projection onto Rd+ can only reduce squared norm, E[∥Qt+1 ∥22 − ∥Qt ∥22 | Ft ] ≤ 2⟨Qt , λt − st ⟩ + E[∥At+1 − St ∥22 | Ft ] δface ≤ −2εµYt − Xt + D2 . 2
(50)
For the parallel component, use v ≥ 0 to get + Yt+1 = ⟨v, (Qt + At+1 − St )+ ⟩ ≥ Yt + ⟨v, At+1 − St ⟩ . For every y ≥ 0 and every real z, ((y + z)+ )2 − y 2 ≥ 2yz. Therefore 2 E[Yt+1 − Yt2 | Ft ] ≥ 2Yt ⟨v, λt − st ⟩
≥ −2εµYt ,
(51) 2
2 2 because ⟨v, st ⟩ ≤ H(v) = µ and ⟨v, λt ⟩ = (1 − ε)µ. Since Q⊥ t 2 = ∥Qt ∥2 − Yt , subtracting (51) from (50) gives δface 2 E[Xt+1 − Xt2 | Ft ] ≤ − Xt + D2 . 2 For Xt > 0, X 2 − Xt2 . Xt+1 − Xt ≤ t+1 2Xt
Consequently, E[Xt+1 − Xt | Ft ] ≤ −
δface D2 + . 4 2Xt
Thus, whenever Xt ≥ x0 := 4D2 /δface , E[Xt+1 − Xt | Ft ] ≤ −
δface . 8
Finally, |Xt+1 − Xt | ≤ ∥Qt+1 − Qt ∥2 ≤ D a.s. Hence the centered increments satisfy the conditional Bernstein condition with variance proxy D2 and b = 0, and the upward MGF condition holds with M+ (θ) ≤ eθD . Applying Theorem B.2 with drift parameter ∆ = δface /8 yields, for a universal constant C, D2 e(T + 1) log max Xt ≤ x0 + D + C 0≤t≤T δface δ with probability at least 1 − δ. It remains only to absorb the two nonlogarithmic terms into the stated scale. We have x0 = 4D2 /δface , and (49) gives D ≤ 2D2 /δface . As log(e(T + 1)/δ) ≥ 1, increasing the universal constant gives (12).
E.3
Collapse-to-peak conversion near a ray
The proposition below isolates the only place where the peak proof uses collapse. No CRP geometry appears in the statement. One supplies a deterministic high-probability tube around a fixed ray; the proposition converts that tube into a one-dimensional peak estimate plus a deterministic residual term.
57
Fix v ∈ Rd+ with ∥v∥2 = 1 and set µ := H(v) > 0. Define ∥
Yt := ⟨v, Qt ⟩,
Qt := Yt v,
∥
Q⊥ t := Qt − Qt .
For this fixed direction, a deterministic number R⊥ (T, η) is a finite-horizon single-bottleneck collapse radius if P
max
0≤t≤T
Q⊥ t
2
≤ η.
> R⊥ (T, η)
(52)
Proposition E.1 (Peak law under finite-horizon single-bottleneck collapse). Consider MaxWeight scheduling under Assumptions 2.1 and 2.2. Let D := Amax + Smax . Fix v ∈ Rd+ with ∥v∥2 = 1, set µ := H(v) > 0, and use the projection decomposition above for this v. Fix T ≥ 1 and δ ∈ (0, 1). Suppose R⊥ (T, δ/2) is a finite deterministic single-bottleneck collapse radius, i.e., (52) holds with η = δ/2. Define ∆gap := min{µ − ⟨v, s⟩ : s ∈ S, ⟨v, s⟩ < µ}, with the convention ∆gap = ∞ if every schedule is v-optimal, and interpret a/∞ := 0 for finite a. Let vmin := min{vi : vi > 0} and set
xloc (T, δ) := max
4Smax R⊥ (T, δ/2) Smax + R⊥ (T, δ/2) , ∆gap vmin
.
Then, with probability at least 1 − δ, both bounds hold: PeakT ≲ and max ∥Qt ∥1 ≲
0≤t≤T
T +1 D log + xloc (T, δ) + R⊥ (T, δ/2), ε δ
√ ∥v∥1 D T +1 log + ∥v∥1 xloc (T, δ) + d R⊥ (T, δ/2). ε δ
If service is deterministic, St = st a.s., then the same two bounds hold with D replaced by Amax in the logarithmic coefficient. Proof. Set R := R⊥ (T, δ/2),
τ⊥ := inf{t ≥ 0 : Q⊥ t
2
> R} ∧ (T + 1).
The collapse estimate (52) gives P(τ⊥ ≤ T ) ≤ δ/2. Let Yet := Yt 1{t<τ⊥ } be the stopped bottleneck projection. We first use the collapse event deterministically. On {t < τ⊥ }, Qt = Yt v + Rt ,
Rt := Q⊥ t ,
∥Rt ∥2 ≤ R.
Let s⋆ ∈ arg maxs∈S ⟨v, s⟩, so ⟨v, s⋆ ⟩ = µ. If every schedule is v-optimal, the schedule-gap condition below is void. Otherwise, for any v-suboptimal schedule s, ⟨Qt , s⋆ − s⟩ = Yt µ − ⟨v, s⟩ + ⟨Rt , s⋆ − s⟩ ≥ Yt ∆gap − 2Smax R. Thus the first term in xloc rules out v-suboptimal MaxWeight maximizers. If R = 0, the no-waste threshold below implies Yt > 0, so the inequality is still strict whenever a suboptimal schedule exists. 58
The second term in xloc prevents bottleneck-relevant service from being lost. If Yt ≥
Smax + R , vmin
then every coordinate with vi > 0 satisfies Qt,i = Yt vi + Rt,i ≥ Smax + R − |Rt,i | ≥ Smax . Since ∥St ∥2 ≤ Smax , every coordinate of the realized service vector is at most Smax . The positive-part map is therefore inactive in all coordinates with vi > 0. Coordinates with vi = 0 do not affect Yt . Hence, on {t < τ⊥ , Yt ≥ xloc (T, δ)}, we have the exact projection recursion Yt+1 = Yt + ⟨v, At+1 − St ⟩.
(53)
On {Yet ≥ xloc (T, δ)}, the preceding recursion applies before stopping; if the stopping time occurs at t + 1, then Yet+1 = 0 ≤ Yt+1 . Therefore Yet+1 − Yet ≤ ⟨v, At+1 ⟩ + ⟨v, st − St ⟩ − µ, because the selected MaxWeight schedule is v-optimal on this event. For Lemma C.5, the conditional mean parameters satisfy mt (v) = ⟨v, λt ⟩ ≤ (1 − ε)µ,
gt (v) = ⟨v, st ⟩ = µ.
The first inequality is Assumption 2.1; the second is v-optimality. Thus, for every θ ∈ [0, 1/D), h i θ2 Dµ e e log E eθ(Yt+1 −Yt ) | Ft ≤ −θµ + θmt (v) + 2(1 − θD) 2 θ Dµ ≤ −θεµ + . 2(1 − θD) With θ := ε/(4D), the last display is at most −cθεµ for a universal constant c > 0. The upward increments obey (Yet+1 − Yet )+ ≤ ⟨v, At+1 ⟩ + ⟨v, st ⟩ ≤ Amax + Smax = D, where v ≥ 0 and ∥v∥ = 1 were used. Since Ye0 = 0, Theorem B.1 gives 2
max Yet ≲ xloc (T, δ) +
0≤t≤T
D T +1 log ε δ
with probability at least 1 − δ/2. If St = st a.s., the service-noise term vanishes. The deterministic-service part of Lemma C.5 and the upward envelope (Yet+1 − Yet )+ ≤ ⟨v, At+1 ⟩ ≤ Amax give the same estimate with D replaced by Amax in the logarithmic coefficient; if Amax = 0, the projection is nonincreasing above the entrance level and the conclusion is immediate. On {τ⊥ > T }, stopped and unstopped projections agree for all t ≤ T . Since ∥v∥2 = 1 and Yt ≥ 0, ∥ ∥Qt ∥2 ≤ Qt + Q⊥ ≤ Yt + R. t 2
2
Also, ∥
∥Qt ∥1 ≤ Qt
1
+ Q⊥ t
1
≤ ∥v∥1 Yt +
√ d R.
These two deterministic conversions, together with a union bound using P(τ⊥ ≤ T ) ≤ δ/2, prove both displayed bounds. 59
E.4
Theorem 4.2: local peak law under CRP
Proof of Theorem 4.2. Theorem 4.1 supplies exactly the tube required by Proposition E.1: the function R⊥ (T, η) in (12) is a deterministic single-bottleneck collapse radius for the CRP normal v. Applying the proposition with this radius gives the threshold xloc (T, δ) appearing in Theorem 4.2 and yields both displayed estimates. The deterministic-service improvement in the logarithmic coefficient is inherited from the same proposition.
F
Proofs for Section 5
F.1
Theorem 5.1: generalized IQS upper bound
Proof of Proposition 5.1. Every permutation matrix has exactly n ones, so its Frobenius norm is √ n. The inequality ∥Q∥1 ≤ n ∥Q∥2 is Cauchy–Schwarz in dimension n2 . For the lower bound on α(Π), let W ∈ Rn×n satisfy ∥W ∥F = 1, and let σ be a uniformly random + permutation. Then n X Z := Wi,σ(i) ≤ H(W ) a.s. i=1
Since W ≥ 0, all cross terms in Z 2 are nonnegative, and therefore n hX i 1X 1 2 E[Z 2 ] ≥ E Wi,σ(i) = Wij2 = . n n i,j
i=1
p √ Hence H(W ) ≥ E[Z 2 ] ≥ 1/ n. Equality is attained by a matrix supported on a single row or √ column with equal entries, so α(Π) = 1/ n. √ √ Proof of Theorem 5.1. Apply Theorem 2.1 (deterministic service part) with Amax = n, Smax = n, √ and α(Π) = 1/ n. This gives PeakT
√ n n3/2 T +1 ≲ + log ε ε δ
with probability at least 1 − δ.
Now multiply by n using Proposition 5.1.
F.2
Corollary 5.1: generalized IQS upper bound under CRP
Proof of Corollary 5.1. Assume, without loss of generality, that the unique bottleneck face is row ⋆ i⋆ ; the column case is identical. Let e(i ) denote the n × n row-indicator matrix for row i⋆ . The normalized bottleneck vector is 1 ⋆ v = √ e(i ) , n
∥v∥1 =
√
1 vmin = √ , n
n,
The corresponding face is n X F⋆ = r ∈ Π : ri⋆ j = 1 . j=1
60
∆gap = ∞.
The CRP assumption supplies a uniform lower bound on the relative distance from rt◦ to the boundary of this face. Pointwise in t, that distance is ( r n ◦ δt := min min rij (t), min r◦⋆ (t), ⋆ i̸=i , 1≤j≤n n − 1 1≤j≤n i j !) r n n X X n 1 ◦ ◦ √ min⋆ 1 − rij (t) , min 1 − rij (t) . n2 − 1 1≤j≤n n i̸=i j=1
i=1
Thus any deterministic constant satisfying 0 < δface ≤ ess inf inf δt (ω) ω
t≥0
is a valid face margin in Assumption 4.1. Here is the distance calculation. The tangent space of the supporting hyperplane is n X T := h : hi⋆ j = 0 . j=1
For a nonnegativity constraint outside the bottleneck row, the normal vector already lies in T , so ◦ (t). For a nonnegativity constraint in the bottleneck row, the normal e ⋆ the relative distance is rij i j p p ◦ projects onto T with norm (n − 1)/n, giving distance n/(n − 1) ri⋆ j (t). For a nonbottleneck √ row constraint, the row-indicator normal has norm n and lies in T , so the distance is the row √ slack divided by n. For a column constraint, the column-indicator normal has projection onto p 2 2 T of squared norm n − 1/n = (n − 1)/n, giving the factor n/(n − 1). Since each rt◦ lies in the relative interior of the face, the relative boundary is the union of these active supporting hyperplanes. Taking the deterministic lower bound over both sample paths and time gives the uniform margin used above. For the IQS, the ambient dimension is d = n2 , and the generalized arrival envelope gives √ √ √ Amax = n and Smax = n. Thus D = Amax + Smax = 2 n. Substituting this value into Theorem 4.1 gives a universal constant C0 such that R⊥ (T, δ) ≤
C0 n e(T + 1) log =: R⊥,IQS (T, δ). δface δ
For a row or column bottleneck, every full permutation schedule is v-optimal, so the schedule-gap term is absent. The local threshold in Theorem 4.2 satisfies √ √ √ xloc (T, δ) = n n + R⊥ (T, δ/2) ≤ C n + n R⊥,IQS (T, δ/2) , where R⊥,IQS (T, δ/2) is the displayed IQS upper bound on R⊥ (T, δ/2). Applying Theorem 4.2 and √ √ √ using ∥v∥1 = n, Amax = n, d = n2 , and xloc (T, δ) = O n + n R⊥,IQS (T, δ/2) yields n T +1 √ log + n xloc (T, δ) + n R⊥ (T, δ/2) ε δ n T +1 ≲ log + n3/2 + n R⊥,IQS (T, δ/2) ε δ
max ∥Qt ∥1 ≲
0≤t≤T
with probability at least 1 − δ.
61
F.3
Theorems 5.2 and 5.3: generalized IQS lower bounds
Proof of Theorems 5.2 and 5.3. Fix an arbitrary nonanticipative full-permutation deterministicservice scheduling rule and start from Q0 = 0. The lower-bound comparisons below use only that such a schedule can serve at most n queues in total and at most one queue in any fixed row. We first prove the all-ports lower bound. Fix n ≥ 4 and ε ∈ (0, 1/16]. Let J be the n × n all-ones matrix, and define i.i.d. arrivals by n−1/2 J, with probability p := 1√− ε , n At+1 = 0, with probability 1 − p. √ Then ∥At+1 ∥F ≤ n, and every row sum and every column sum of the mean arrival matrix is 1 − ε. Thus Assumption 5.1 holds in the all-ports-loaded slack form. Let Lt := ∥Qt ∥1 . A permutation schedule can reduce total backlog by at most n in one slot. Hence Lt dominates the reflected random walk Rt with R0 = 0 and increments n3/2 − n, with probability p, Xt+1 = −n, with probability 1 − p. After scaling by n, Yt := Rt /n has increments √ √ n − 1, with probability (1 − ε)/ n, Zt+1 = −1, otherwise, with mean −ε. Since n ≥ 4, this reflected walk is the one-dimensional construction with deterministic √ √ unit service and upward net-input scale A = n − 1 ≍ n. Applying Theorem 2.3 to this scaled walk and then multiplying by n gives h i n3/2 ε2 log 1 + √ T E max ∥Qt ∥1 ≳ 0≤t≤T ε n √ for T ≥ C n/ε2 , after adjusting constants. This proves (14); finitely many smaller values of n can be absorbed into the constants if desired. We now prove the CRP lower bound. The point is to keep the row bottleneck in the relative interior of its face while preserving rare row-wide bursts. Let E (1) be the matrix whose first row is all ones and whose other entries are zero, and set Ē (1) := E (1) /n. Define a strictly positive reference point on the row-one face by ρ1j =
1 , n
ρij =
1 4n
(i ≥ 2),
1 ≤ j ≤ n.
Then ρ ∈ ΠIQS , its first row sum is one, every other row sum is 1/4, and every column sum is 1 n−1 + < 1. n 4n Hence ρ belongs to the relative interior of the row-one facet. Let η := ε/4 and r◦ := (1 − η)Ē (1) + ηρ. 62
Then r◦ also lies in the relative interior of the row-one facet, and no other row or column constraint √ is tight. Thus the CRP assumption holds with the bottleneck vector v = E (1) / n. Define i.i.d. arrivals by (1 − ε)(1 − η) , E (1) , with probability p := n At+1 = ρ, with probability q := (1 − ε)η, 0, with probability 1 − p − q. The Frobenius norm is at most
√ √ √ n, since E (1) F = n and ∥ρ∥F ≤ n. Moreover E[At+1 ] = (1 − ε)r◦ ,
so the generalized IQS slack condition holds and the nominal capacity point satisfies the CRP assumption above. Let Rt be the total backlog in the first row. A permutation schedule can serve at most one first-row queue per slot. Since the background arrival ρ is nonnegative, Rt dominates the reflected random walk with increments n − 1, with probability p, ′ Zt+1 = −1, with probability 1 − p. The drift of this walk is pn − 1 = (1 − ε)(1 − η) − 1 =: −ε′ , where ε ≤ ε′ ≤ 5ε/4 for ε ∈ (0, 1/16]. In particular, ε′ ≤ 5/64 < 1/8, so the slack range in Theorem 2.3 applies. This is the one-dimensional construction with deterministic unit service and upward net-input scale A = n − 1 ≍ n. Applying Theorem 2.3 with slack ε′ gives h i h i n ε2 E max ∥Qt ∥1 ≥ E max Rt ≳ log 1 + T 0≤t≤T 0≤t≤T ε n for T ≥ C ′ n/ε2 . This proves (15).
F.4
Theorem 5.4: Bernoulli IQS upper bound
Proof. We apply Theorem 3.1 and the entrance-scale definition in Appendix D.2. Let X Nt := Aij (t + 1). i,j
The row and column assumptions imply λt ∈ (1 − ε)ΠIQS a.s. for every t. Thus the uniform conditional interior-slack condition holds. Service is deterministic in an input-queued switch, so νS = bS = 0. We first verify the queue-Bernstein condition for arrivals. Fix w ∈ [0, 1]n×n and write X Mw,t := ⟨w, λt ⟩ = λij (t)wij . i,j
By conditional independence, for |θ| < 1, h i Y E eθ⟨w,At+1 −λt ⟩ Ft = exp{−θλij (t)wij } 1 − λij (t) + λij (t)eθwij . i,j
63
For 0 ≤ wij ≤ 1, the scalar Bernoulli Bernstein bound gives h i log E eθ⟨w,At+1 −λt ⟩ Ft ≤
X θ2 Mw,t θ2 λij (t)wij = . 2(1 − |θ|) 2(1 − |θ|) i,j
Therefore At+1 is queue-Bernstein with parameters (νA , bA ) = (1, 1), uniformly in t. The canonical tilt θQB in (40) may hence be chosen as θ = cε for a sufficiently small universal constant c > 0. It remains to bound the two terms entering xQB . Every service schedule is a permutation matrix, so ∥St ∥2F = n. Since the arrivals are Bernoulli, ∥At+1 ∥2F = Nt . Thus, Jt2 := ∥At+1 − St ∥2F ≤ 2Nt + 2n. We next bound the curvature term. Since ρx (z) ≤ z 2 /(2x), for x ≥ 1, 2θ(Nt + n) κθ (x) ≤ sup ess sup log E exp Ft . x t≥0 Conditional on Ft , Nt is a Poisson-binomial random variable. Moreover, X mt := E[Nt | Ft ] = λij (t) ≤ n(1 − ε) ≤ n. i,j
Hence, for a ≥ 0, E[eaNt | Ft ] =
Y
(1 − λij (t) + λij (t)ea ) ≤ exp{(ea − 1)mt } ≤ exp{n(ea − 1)}.
i,j
Taking a = 2θ/x gives, for x ≥ 1 and θ ≤ 1, θn 2θ(Nt + n) 2θn Ft ≤ + n e2θ/x − 1 ≤ C . log E exp x x x √ Since α(Π) = 1/ n by Proposition 5.1, choosing x≥C
n3/2 ε
makes κθ (x) ≤ θεα(Π)/4. Hence xcurv (θ) ≤ C
n3/2 . ε
(54)
√ For the upward-jump envelope, Jt ≤ 2Nt + 2n ≤ Nt + n + 1. Since Kup (θ) is defined with the harmless factor 8 in (41), for 0 < θ ≤ 1/8, Kup (θ) ≤ exp(8θ(n + 1)) sup ess sup E[e8θNt | Ft ]. t≥0
Using the conditional Poisson-binomial MGF and mt ≤ n, E[e8θNt | Ft ] ≤ exp{n(e8θ − 1)}. 64
Hence log Kup (θ) ≤ Cθn. With θQB = cε, (54) and the preceding display give xQB ≤ Cn3/2 /ε. Theorem 3.1 then gives " # n3/2 1 T +1 max ∥Qt ∥2 ≤ C + log +n 0≤t≤T ε ε δ with probability at least 1 − δ. Since n ≤ n3/2 /ε for n ≥ 1 and ε ∈ (0, 1), this proves the Euclidean bound. Multiplying by n using ∥Q∥1 ≤ n ∥Q∥2 proves the total-backlog statement.
65