{'fraction_non_alphanumeric': 0.05963065842185341, 'fraction_numerical': 0.01592663418991918, 'mean_word_length': 3.867975810287423, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fluctuation Bounds for the Max-Weight Policy, with Applications to State Space Collapse

We consider a multi-hop switched network operating under a Max-Weight (MW) scheduling policy, and show that the distance between the queue length process and a fluid solution remains bounded by a constant multiple of the deviation of the cumulative arrival process from its average. We then exploit this result to prove matching upper and lower bounds for the time scale over which additive state space collapse (SSC) takes place. This implies, as two special cases, an additive SSC result in diffusion scaling under non-Markovian arrivals and, for the case of i.i.d. arrivals, an additive SSC result over an exponential time scale.


Introduction
The subject of this paper is a new line of analysis of the maximum-weight (MW) scheduling policy for singlehop and multihop networks. The main ingredient is a purely deterministic qualitative property of the queue dynamics: the trajectory followed by the queue vector under an MW policy tracks the trajectory of an associated deterministic fluid model within a constant multiple of the cumulative fluctuation of the arrival processes. With this property at hand, it is then a conceptually simple matter to translate concentration properties of the arrival processes to concentration properties for the queue vector. As a consequence, we can obtain the following: a. New, simple derivations of existing results on the convergence to a fluid solution/trajectory and on state space collapse (SSC).
b. Stronger versions of existing SSC results, involving more general arrival processes and tighter concentration bounds.
c. An approach to obtaining new results that would seem rather difficult to establish with existing methods. The core of our approach is the trajectory tracking result mentioned. The latter is, in turn, an adaptation of a similar result established in  for a general class of continuous-time hybrid systems that move along the subdifferential of a piecewise linear convex potential function with finitely many pieces; other than an additional restriction to the positive orthant, a continuous-time variant of the MW dynamics turns out to be exactly of this type. However, a fair amount of additional work is needed to translate the general result to the standard, discrete-time, MW setting; see Theorem 2 and its proof.

General Background
We consider a multihop switched network with fixed routing, such as those arising in wireless networks (Lin et al. 2006) or switch fabrics (Ji et al. 2009). The network operates in discrete time and is driven by jobs (or packets) that arrive according to a stochastic, deterministic, or adversarial process. There is a scheduler that, at each time step, selects one of finitely many possible service vectors. These service vectors can be fairly arbitrary, reflecting interdependence constraints between different servers, for example, interference constraints in the context of wireless networks.
We focus on the popular MW scheduling policy (Tassiulas and Ephremides 1992), which operates as follows. At any time step, an MW policy associates to each queue a weight proportional to its length and selects a service vector that maximizes the total weighted service. MW policies are known to have a number of attractive properties, such as maximal throughput (Tassiulas and Ephremides 1992, Eryilmaz et al. 2005, Georgiadis et al. 2006). In addition, under certain conditions, for example, a resource pooling assumption, they minimize the workload in the heavy traffic regime (Stolyar 2004). On the other hand, the queue size dynamics under MW policies are quite complex, and a detailed analysis is difficult.
A common way of reducing the complexity of the analysis involves a fluid approximation, also known as a fluid model. The fluid model relies on two simplifications that lead to a description in terms of a set of differential equations (see Section 2.3): (a) the dynamics evolve in continuous-rather than discrete-time and (b) the arrival process is replaced by a constant flow with the same average. The fluid model underlies a general technique for dealing with discrete-time networks: approximate the queue lengths by fluid solutions and then analyze the fluid model. This approach has proved useful in the study of the MW dynamics, leading to results on stability Prabhakar 2000, Andrews et al. 2004), SSC (Stolyar 2004;Dai and Lin 2005;Wischik 2006, 2012), and delay stability under heavy-tailed arrivals (Markakis et al. 2016(Markakis et al. , 2018.
A key ingredient behind such results is an understanding of the accuracy with which fluid solutions approximate the original queue length processes; this paper contributes to this understanding.

State Space Collapse Literature
A prominent application of fluid models is in establishing SSC, that is, that, in the heavy traffic regime, the queue length process stays close to a low-dimensional set for a long time and with high probability. 1 Seminal SSC results for communication networks were given in the works of Reiman (1984), Bramson (1998), and Williams (1998). Subsequently, several works (Stolyar 2004;Wischik 2006, 2012;Kang et al. 2009) followed the general framework of Bramson (1998) to prove SSC under different scheduling policies, including for the case of MW policies. The general approach involves splitting an O(r 2 )-long interval into intervals of length O(r) and then showing that the fluid-scaled processes (i.e.,q(t) 1 r Q(⌊rt⌋)) stay close to the fluid solutions in each one of these smaller intervals. The SSC results then follow from the property that the fluid solutions are attracted to a low-dimensional set, called the set of invariant points.
For single-hop networks with Markovian arrivals operating under a generalization of the MW policy, SSC was proved in Stolyar (2004). It was also shown, in Stolyar (2004), as a consequence of SSC, that the workload process converges to a reflected Brownian motion and that every MW-α policy 2 with α > 0 minimizes this workload among all scheduling algorithms. The results of Stolyar (2004) were extended to multihop networks in Dai and Lin (2008) and to another generalization of MW policies in Shakkottai et al. (2004). For multihop networks with non-Markovian arrivals operating under MW-α, SSC under diffusion scaling was studied in Shah and Wischik (2012). Several works (Shah et al. 2010, Kang andWilliams 2012) then used the results of Shah and Wischik (2012) to provide diffusion approximations for the MW dynamics. Finally, SSC has also facilitated the study of the steady-state expectation of the number of jobs in a network (Eryilmaz and Srikant 2012;Maguluri et al. 2014Xie and Lu 2015;Wang et al. 2018).

Preview of Results
Our approach to the analysis of MW policies relies on a bound on the distance of the queue length processes from the fluid solutions in terms of the fluctuations of the cumulative arrival processes. In more detail, we consider a queue length process Q(·) driven by an arrival process A(·) with average rate λ and compare Q(·) with a fluid solution q(·) driven by a steady arrival stream with the same rate λ under the same initial conditions q(0) Q(0).
We already know that, under suitable scaling, the trajectories of the original discrete-time process remain close to the fluid solutions. Furthermore, the fluid model is well known to be nonexpansive 3 (Subramanian 2010). By combining these facts, it is quite plausible that one should be able to derive bounds of the form where A(t) is the vector of arrivals at each one of the queues at time t and c is a constant that is independent of A(·). However, our goal is to derive a stronger bound of the form for some constants c and C, independent of A(·) and λ. The bounds in Equations (1) and (2) are qualitatively different. Under common probabilistic assumptions and with high probability, Sharifnassab, Tsitsiklis, and Golestani: Fluctuation Bounds for the Max-Weight Policy The sensitivity bound (2) allows us to make several contributions to the study of the MW policy. a. We obtain a very simple proof of the convergence of fluid-scaled processes to fluid solutions; see Corollary 1.
b. We establish a strong SSC result for the MW policy. In particular, we derive an upper bound and a matching lower bound on the time scale over which additive SSC takes place; see Theorem 3. As a corollary, when the arrivals are independent and identically distributed (i.i.d.), we establish SSC for the processq(t) Q(⌊e αr t⌋)/r for some constant α, that is, over an exponentially long time scale; see Corollary 2.
c. In another corollary, we establish an additive SSC result in diffusion scaling and under non-Markovian arrivals, which strengthens the currently available diffusion scaling results under the MW policy in several respects; see Section 2.4 for more details.
d. As is reported elsewhere, the sensitivity bound (2) provides tools that allow us to resolve an open problem from Markakis et al. (2018), on the delay stability in the presence of heavy-tailed traffic.
On the technical side, the proof of the sensitivity bound (2) exploits a similar bound from our earlier work  on the sensitivity of a class of hybrid subgradient dynamical systems to fluctuations of external inputs or disturbances. The main challenges here concern the transition from discrete to continuous time as well as the presence of boundary conditions as queue sizes are naturally constrained to be nonnegative. For the proof of our SSC results, we follow the general framework of Bramson (1998) while also taking advantage of the sensitivity bound (2). We believe that our tight characterization of the time scale over which SSC holds would have been very difficult without the strong sensitivity bound (2).

Outline
The rest of the paper is organized as follows. In the next section, we describe the network model and our conventions along with some background on fluid models and SSC. In Section 3, we present our central result, which is an inequality of the form (2); see Theorem 2. Then, in Section 4, we present our SSC results. We provide the proofs of our results in Sections 5 and 6 while relegating some of the details to the appendices for improved readability. Finally, in Section 7, we offer some concluding remarks and discuss possible extensions.

System Model and Preliminaries
In this section, we list our notational conventions, define the network model that we study, and go over the necessary background on fluid models and SSC.

Notation and Conventions
We denote by R, R + , R ++ , Z, Z + , and N the sets of real numbers, nonnegative reals, positive reals, integers, nonnegative integers, and positive integers, respectively.
A vector v ∈ R n , is always treated as a column vector with components v i for i 1, . . . , n. We use v T and ⃦ ⃦ v ⃦ ⃦ 2 to denote the transpose and the Euclidean norm, respectively, of v. For any two vectors v and u in R n , the relation v ≼ u indicates that v i ≤ u i for all i. Furthermore, we use min (v, u) to denote the componentwise minimum, that is, the vector with components min(v i , u i ). For a vector µ ∈ R n and a set J of indices, we use σ −J (µ) to denote the vector whose ith entry is equal to the ith entry of µ if i / ∈ J and is equal to zero if i ∈ J. Finally, we let l n be the n-dimensional vector with all components equal to one.
The notation Conv(·) stands for the convex hull of a set of vectors in R n . Given a vector v ∈ R n and a set }be the image of the set A under the linear transformation associated with W. Given a vector v ∈ R n , diag(v) denotes the n × n diagonal matrix with the entries of v on its main diagonal.
Finally, for a function f : R → R and with a slight departure from standard conventions, we use eitherḟ (t) or d + f (t)/dt to denote the right derivative of f at t, assuming that it exists.

Network Model and the MW Policy
A discrete-time multihop network with fixed deterministic routing is specified by n queues, a nonnegative n × n routing matrix R, and a finite set 6 ⊂ R n + of actions (or service vectors) that correspond to the different schedules that can be applied at any time.
The input to a network is a collection of n discrete-time, nonnegative arrival processes, described by functions A i : Z + → R + , where A i (t) stands for the workload that arrives to queue i during the tth time slot. Whenever the arrival processes are ergodic stochastic processes, we define the arrival rate vector λ ∈ R n + as the vector whose ith component is the average of the process A i (·). We use Q i (t) to denote the (always nonnegative) workload at queue i at time t and Q(t) to denote the corresponding workload vector. In the sequel, we use the terms workload, queue size, and queue length interchangeably. The evolution of Q(t) is determined by the particular policy used to operate the network.
Given a network and an arrival process A(·), the evolution of the queue lengths is given by where µ(t) is the service vector chosen by the policy at time t, and as mentioned earlier, min µ(t), Q(t) ( ) is to be interpreted componentwise. Equation (3) corresponds to the situation in which a time slot begins with a queue vector Q(t), and then a service vector µ(t) is chosen and applied. Finally, the new arrivals A(t) are recorded at the end of the time slot and contribute to the new queue vector Q(t + 1). Note that the routing matrix R is deterministic and prespecified and is not affected by the queue sizes or the scheduling policy. Single-hop networks correspond to the special case in which R is the zero matrix. More generally, the most common case (single-path routing) is one in which the routing matrix has entries in {0, 1} with at most one nonzero entry in each column and in which the ijth entry being one indicates that any work completed at queue j is transferred to queue i for further processing. However, we allow for more general nonnegative matrices R because this additional freedom does not affect the main proofs and also allows for a simpler treatment of weighted MW policies; see Lemma 4 in the proof of Theorem 2.
The following assumption is in effect throughout the paper and is naturally valid in typical application contexts.
Assumption 1. For any µ ∈ 6 and any i ∈ {1, . . . , n}, the set 6 also contains the vector σ −{i} (µ), that is, the vector obtained by setting the ith component of µ to zero.
According to Assumption 1, if a certain service vector µ is allowed, it is also possible to follow µ at all queues other than queue i while providing no service to queue i. In particular, the zero vector is always an element of 6. On the technical side, Assumption 1 appears innocuous; however, it is indispensable for the proof technique used in this paper and has also been made in earlier works (see section 4.1 of Stolyar (2005) and assumption 2.3 of Shah and Wischik (2012)).
We now proceed to define weighted max-weight (WMW) policies, which can be viewed as either a generalization of MW policies or as a special case of the broader class of MW-f policies 4 considered in Eryilmaz et al. (2005) and back-pressure-based utility maximization algorithms 5 considered in Stolyar (2005), Georgiadis et al. (2006), andNeely (2010). We are given a multihop network with n queues, as described, along with a positive vector w ∈ R n ++ and the associated diagonal matrix W diag(w). For any Q ∈ R n + , we let 6 w (Q) be the set of maximizers of Q T W I − R ( )µ: A WMW policy associated with w (or w-WMW, for short) chooses, at each time t, an arbitrary service vector µ(t) ∈ 6 w Q(t) ( ). 6 An MW policy is a special case of a WMW policy, in which w l n . When dealing with MW policies, we drop the subscript w and write 6(Q) instead of 6 l n (Q).
Consider an ergodic and Markovian arrival process with arrival rate vector λ ∈ R n + for which there exists some scheduling policy that stabilizes the network, that is, results in a positive recurrent process. The closure of the set of all such vectors λ is called the capacity region and is denoted by #.
We now record a fact that is used later in the proofs of Lemma 5 and Claim 4. Fix some λ ∈ # in the capacity region and consider a stabilizing policy. We define f i as the average departure rate from queue i. Then, the flow conservation property f λ + R f implies that λ I − R ( )f . Moreover, following an argument similar to the one in section 3.C of Tassiulas and Ephremides (1992), there exists a vector c such that f ≼ c ∈ Conv(6). Assumption 1 then implies that f ∈ Conv(6), and as a result, λ ∈ I − R ( )Conv(6). In conclusion, A remarkable property of MW and WMW policies is that they are throughput optimal in the sense that, for any λ in the interior of # and any ergodic Markovian arrival process with average arrival rate vector λ, the resulting process is positive recurrent (Tassiulas and Ephremides 1992). Similar throughput optimality results are available for extensions of MW, for example, for the so-called f -MW policies (Eryilmaz et al. 2005).

Fluid Model
The fluid model associated with the MW policy is a deterministic dynamical system that runs in continuous time and in which the arrival stream is replaced by a steady "fluid" arrival stream with rate vector λ. We are working with the following definition of the fluid model; somewhat different but equivalent definitions can be found in Shah and Wischik (2012) and Markakis et al. (2018).
Definition 1 (Fluid Solutions). We are given an arrival rate vector λ and an initial queue length vector q(0) ∈ R n + . A fluid model solution (or, simply, fluid solution) is an absolutely continuous function q : R + → R n + that, together with a collection of functions s µ : R + → [0, 1] for µ ∈ 6 and another function y : R + → R n + , satisfies the following relations almost everywhere:q It is known that for any multihop network and any initial condition, a fluid solution always exists (see appendix A of Dai and Lin (2005) and lemma 9 of Markakis et al. (2018)) and is unique (see lemma 10 of Markakis et al. (2018)) even though the corresponding s µ (·) and y(·) need not be unique. Moreover, for q(0) ≽ 0, (6)-(10) imply that q(t) remains nonnegative for all subsequent times t. Later, in Proposition 2, we show that fluid solutions admit an alternative description as the trajectories of a related subgradient dynamical system. 7 We are particularly interested in the set of invariant states of the fluid model, which, for any λ in the capacity region, is defined by (see theorem 5.4(iv) of Shah and Wischik (2012)) Our notation is chosen to emphasize the dependence on λ of the set of invariant states. We note that, if λ belongs to the interior of the capacity region, then ((λ) is a singleton equal to {0}. Thus, ((λ) can be nontrivial only if λ lies on the boundary of #. We now record a scaling property of the set of fluid solutions.
Proof. Note that the set of maximizing schedules in Equation (4) does not change when we scale the queue vector by a positive constant. Therefore, for any t ≥ 0, Consider the functions y(·) and s µ (·) that, together with q(·), satisfy the fluid model relations (6)-(10). Let y(t) y(rt) andŝ µ (t) s µ (rt) for all t ≥ 0 and all µ ∈ 6. Then, it is easy to verify thatq(·),ŷ(·), andŝ µ (·) also satisfy (6)-(10). Therefore,q(·) is also a fluid solution. □ Suppose that λ is in the capacity region and that q 0 ∈ ((λ) so that q(t) q 0 is a fluid solution. Then, Lemma 1 implies that, for any scalar r > 0, q(t) q 0 /r is also a fluid solution, and therefore, q 0 /r ∈ ((λ). Furthermore, it is not hard to see that the identically zero function is also a fluid solution so that 0 ∈ ((λ). We conclude that ((λ) is a cone, that is, The interest in fluid solutions stems from the fact that they provide approximations to suitably scaled versions (i.e., under "fluid scaling") of the original process. We summarize here one such result, which is a special case of theorem 4.3 in Shah and Wischik (2012); similar results are given in Dai and Lin (2005), lemmas 4 and 5.
Proposition 1. Fix some λ ∈ R n + , T > 0, and q 0 ∈ R n + . Letting r range over the positive integers, consider a sequence of arrival processes A r (·) that satisfies almost surely. Let Q r (·) be the process generated according to Equation (3) when the arrival process is A r (·) and the initial condition is Q r (0) rq 0 . We define the continuous-time scaled processesq r (t) Q r (⌊rt⌋)/r and note thatq r (0) q 0 for all r. Finally, let q(·) be a fluid solution under that particular vector λ, initialized with q(0) q 0 . Then, almost surely.
Condition (14) is typically satisfied under common probabilistic assumptions, for example, when A r (·) is an i.i.d. process with mean λ and bounded domain or more generally of exponential type. Thus, loosely speaking, convergence of the arrival processes leads to convergence of the queue processes.
As we see in Section 3, our results allow for stronger statements; namely we show that the rate of convergence in Equation (14) provides bounds on the rate of convergence to the fluid solution in Equation (15); see Corollary 1.

State Space Collapse
In this section, we discuss known results about SSC under an MW policy, thus setting the stage for a comparison with the results we present in Section 4.
We consider the heavy traffic regime, in which the arrival rate vector gets arbitrarily close to some point λ on the outer boundary of the capacity region. In this regime, the average queue lengths typically tend to infinity, yet it is often the case that the queue length vector stays close to the set of invariant states, ((λ). This phenomenon is called SSC and has been studied extensively, mostly under the so-called diffusion scaling. In this scaling, we start with a sequence Q r (·) of stochastic processes, indexed by r ∈ N, and then proceed to study a sequence of scaled processesq r (·), referred to as diffusion-scaled processes, defined bŷ The extent to which the queue length process stays close to the set of invariant states is, in general, determined by the magnitude of the fluctuations of the arrival process. It is, therefore, natural to start the analysis with some assumptions on these fluctuations. General SSC results, under the MW policy and some of its extensions, were provided in Shah and Wischik (2012) under the following assumption. 8 Assumption 2 (Shah and Wischik (2012), assumption 2.5). Let A r (·) be a sequence of arrival processes indexed by r ∈ N. We assume that, for each r, A r (·) is stationary 9 with mean λ r and that λ r → λ as r → ∞. We, furthermore, assume that there exists a sequence δ r ∈ R + converging to zero as r → ∞ such that r · log 2 r · P max Note that Assumption 2 is quite general, not requiring the arrival processes to be i.i.d. or Markovian. Theorem 7.1 of Shah and Wischik (2012), slightly rephrased, 10 establishes that, for a network operating under an MW-f policy (a generalization of WMW policies and under certain conditions on f ) for any T > 0 and under Assumption 2, the diffusion-scaled queue length processesq r (·) satisfy, for any δ > 0, when lim r→∞q r (0) q 0 for some q 0 ∈ ((λ).

Sharifnassab, Tsitsiklis, and Golestani: Fluctuation Bounds for the Max-Weight Policy
The bound in (18) is referred to as multiplicative SSC. Yet there is a stronger notion, called additive SSC, which involves a bound similar to (18) but with the term max(q r (t), 1) absent from the denumerator and which is known to hold under i.i.d. arrivals.
Theorem 1 (Shah et al. (2010), theorem 7.7). Consider a network operating under an MW-α policy with α ≥ 1 with i.i.d. and uniformly bounded arrivals with rate λ r → λ for some λ ∈ # and the associated diffusion-scaled queue length processeŝ q r (·). Assume that lim r→∞q r (0) q 0 for some q 0 ∈ ((λ). Then, 11 for any δ > 0, P sup Compared with the literature, our results only apply to the case in which α 1 (i.e., the MW policy) but allow for queue-dependent weights so that the weight of queue i is w i Q i . More crucially, our results (see Section 4 and Theorem 3, in particular) a. remain valid as long as lim r→∞ d(q r (0), ((λ)) 0, which is a weaker condition than lim r→∞q r (0) q 0 , for a fixed q 0 ∈ ((λ); 12 b. unlike Shah et al. (2010), we do not require the arrival process to be i.i.d. or bounded as long as the arrival process has certain concentration properties. Furthermore, the concentration properties that we require (see Definition 2) are weaker than Assumption 2 for the case of diffusion scaling (see Corollary 3); and c. apply to scalings other than diffusion scaling and include a converse result that characterizes the possible scalings for which additive SSC holds. We finally note another related line of work that studies a property similar to SSC, namely the extent to which the steady-state distribution is concentrated in a neighborhood of the set of invariant points. In particular, Maguluri and Srikant (2015) and  have characterized the tail of the steady-state distribution of the distance from the set of invariant points for the case of an input-queued switch.

Main Result: Sensitivity
The backbone behind all of the results is the following main theorem.
Theorem 2 (Sensitivity of WMW Policy). For a network operating under a WMW policy, there exists a constant C, to be referred to as the sensitivity constant, that satisfies the following. Consider an arrival process A(·) and the corresponding queue length process Q(·). Let q(·) be a fluid solution corresponding to some λ ≽ 0 and initialized with q(0) Q(0). Then, for any k ∈ Z + , Note that the result holds without having to assume that λ lies inside the capacity region. The proof is given in Section 5, and the key steps are as follows. We show that the study of WMW policies can be reduced to the study of MW policies. Furthermore, given a network operating in discrete time under the MW policy, we introduce an associated continuous-time dynamical system, which we call the induced dynamical system. Next, we show that the fluid solutions and the queue length processes of the network can be viewed as unperturbed and perturbed trajectories of the induced dynamical system, respectively. We finally argue that the induced dynamical system falls within the class of subgradient systems that were studied in  and apply the main result in that reference to prove (20). The reductions that are developed in the course of the proof may be of independent interest.

Convergence to Fluid Model Solutions
An immediate consequence of Theorem 2, together with Lemma 1, is a bound on the distance of the fluidscaled processq r (t) Q(⌊rt⌋)/r from a fluid solution q(·).
Corollary 1. Consider a network operating under the WMW policy and let C be the constant in Theorem 2. Fix an arrival function A(·) and some q 0 ∈ R n + . Let Q r (·) be the process generated according to Equation (3) when the arrival process is A(·) and the initial condition is Q r (0) rq 0 . Letq r (t) Q r (⌊rt⌋)/r. Let q(·) be a fluid solution corresponding to some λ ∈ R n + and initialized at q(0) q 0 . Then, for any T > 0, Corollary 1 strengthens (15) significantly. Any statistical assumptions on the fluctuations of the arrival process A(·) readily yield concrete upper bounds on the distance of the original process from its fluid counterpart.

State Space Collapse
In this section, we apply Theorem 2 to establish a general additive SSC result; see Theorem 3. We then continue with some corollaries on exponential scaling or diffusion scaling. Our approach can also be used to obtain results that apply in steady state. However, we do not go into that latter topic because such results can also be proved using simpler, more direct methods as in Maguluri and Srikant (2015) and .

Definitions and Preliminaries
At the core of our proofs lies the following lemma, which asserts that fluid solutions are attracted to the set ((λ) of invariant states, which was defined in Equation (11). The proof of the lemma is given in Appendix A.
Lemma 2 (Attraction to the Set of Invariant States). Consider a network operating under the MW policy and a vector λ in its capacity region. There exists a constant α(λ) > 0 such that, for any fluid solution q(·) associated with λ and any time t, with this right-derivative being guaranteed to exist.
We continue with a definition that quantifies the rate at which a family of processes concentrates on its mean.
Definition 2 (f-Tailed Sequence of Random Processes). Consider a function f : N × R + → R+ and a vector λ ∈ R n . Let A r (·) be a sequence of random processes indexed by r ∈ N. Assume that, for each r, A r (·) is stationary and has expected value λ r and that lim r→∞ λ r λ. Suppose that, for every δ > 0, Then, A r (·) is said to be an f -tailed sequence of random processes with limit mean λ, and we refer to f as the concentration rate function.
Later, we show that the time scale over which SSC holds is almost proportional to the best possible concentration rate function f . We observe that any sequence of random processes that satisfies Assumption 2 is a sequence of f -tailed processes with f (r, δ) r · log 2 r. However, the reverse is not true: Assumption 2 involves an additional requirement of uniform convergence over all values of an additional indexing parameter z, whereas Definition 2 essentially only considers the case z r. Thus, Definition 2 is less restrictive and easier to check and also seems more natural.
There are many processes whose concentration properties are well understood and that translate to the requirements in Definition 2 for a suitable concentration rate function f . We record one such fact in Lemma 3, which deals with bounded i.i.d. arrival processes and which is proved in Appendix B.
Lemma 3 (Bounded I.I.D. Processes are Exponential-Tailed). Fix a vector λ ∈ R n + and a constant a > 0. Consider a sequence of random processes A r (·) indexed by r ∈ N. Suppose that, for every r, the random variables A r (t) are i.i.d. and that A r (t) ∈ [0, a] n for all t. Denote the mean of A r (t) by λ r and suppose that lim r→∞ λ r λ. Take any constant β ∈ (0, 2) and let f (r, δ) exp(βrδ/na 2 ). Then, A r (·) is an f -tailed sequence of random processes with limit mean λ.
Similar results are possible for arrival processes that are modulated by a finite and ergodic Markov chain. The boundedness assumption can also be removed under standard conditions on the moment-generating function of A r (t).
We now define processes involving a more general scaling of time as a generalization of the fluid and diffusion-scaled processes.
Definition 3 (g-Time-Scaled Processes). Consider an increasing function g : N → R + and a sequence Q r (·) of random processes. Then, the corresponding sequence of g-time-scaled processesq r (·) is defined aŝ for all r ∈ N and all t ∈ R + .
The fluid scaling and the diffusion scaling of a random process are particular g-time-scaled processes corresponding to g(r) r and g(r) r 2 , respectively. Definition 3 allows for a more general scaling of time.

Main SSC Result
We now present our main SSC result.
Theorem 3 (Strong State Space Collapse). Consider a network operating under a WMW policy and a vector λ in its capacity region with a corresponding set of invariant states ((λ). Fix some T ∈ R + and let {λ r } be a sequence that converges to λ.
Consider two functions f : N × R + → R + and g : N → R + with lim inf r→∞ g(r)/r > 0. Let A r (·) be an f -tailed sequence of arrival processes with limit mean λ and letq r (·) be a corresponding sequence of g-time-scaled queue length processes. Suppose that d(q r (0) , ((λ)) → 0 as r → ∞.
a. Suppose that, for every ϵ > 0, we have lim inf r→∞ rf r, ϵ ( )/g(r) > 0. Then, for any δ > 0, P sup b. Under the same assumptions as in part (a), we can also bound the rate of convergence in (24): for any δ > 0, there exists an ϵ > 0 such that Moreover, for the case of an MW policy, (25) holds for every ϵ ≤ min δ, α ( )/2C, where C is the sensitivity constant of the network (see Theorem 2) and α α(λ) is the constant in Lemma 2.
c. Conversely, suppose that f : N × R + → R + and g : N → R + are such that lim r→∞ rf r, ϵ ( )/g(r) 0 for every ϵ > 0 and lim r→∞ g(r)/r ∞. Then, for any network operating under an MW policy, any arrival rate λ in its capacity region (excluding its extreme points), and any q 0 ∈ ((λ), there exists an f -tailed sequence of arrival processes satisfying (22) and a corresponding sequence of g-time-scaled processesq r (·), r ∈ N, initialized atq r (0) q 0 such that P sup The proof of Theorem 3 is given in Section 6. Part (b) relies on a reduction of WMW dynamics to MW dynamics together with the facts that the queue length process stays close to a fluid solution (Theorem 2) and that a fluid solution is attracted to the invariant set ( (Lemma 2). The proof of part (c) relies on an explicit construction.
We note that part (a) is a straightforward corollary of part (b). Nevertheless, we have included the statement of part (a) because it is in a form comparable to SSC results in the literature and also because it facilitates a comparison with the converse result in part (c).
Theorem 3 ties together the time scaling g over which SSC occurs and the concentration rate function, f , of the arrival processes. The underlying intuition is that, if the queue length process is initialized sufficiently close to (, then it stays in an rδ-neighborhood of ( with high probability for a period of time proportional to g(r). This enables us to prove additive SSC over time scales much longer than those underlying the diffusion scaling as in the next section.

Special Cases of SSC
In this section, we apply Theorem 3 to obtain more concrete SSC results. The first result concerns SSC over an exponentially large time scale. Although it refers to bounded i.i.d. processes, it admits straightforward Sharifnassab, Tsitsiklis, and Golestani: Fluctuation Bounds for the Max-Weight Policy Stochastic Systems, 2020, vol. 10, no. 3, pp. 223-250, © 2020 extensions to arrival processes with a concentration rate function f that grows exponentially with r as is the case whenever a suitable large deviations principle holds.
Corollary 2 (Bounded I.I.D. Arrivals: SSC over an Exponential Time Scale). Consider a network operating under an MW policy, a vector λ in its capacity region, a δ > 0, and a sequence A r (·) of arrival processes that satisfy the assumptions of Lemma 3. Consider a γ < min(δ, α)/(2Cna 2 ), where C is the input sensitivity constant of the network, α α(λ) is the constant in Lemma 2, and a is an upper bound on the size of arriving jobs (see Lemma 3). Consider the e γr -time scaling of the queue length processes,q and suppose that d(q r (0) , ((λ)) → 0 as r → ∞. Then, for any T ∈ R + , e γr P sup Proof. Let β γ/[min(δ, α)/(2Cna 2 )]. Then, β < 1, and Lemma 3 implies that A r (·) is an f -tailed sequence of processes for f r, ϵ ( ) exp 2βrϵ/na 2 ( ) . Let ϵ min δ, α ( )/2C. Then, γ βϵ/na 2 . Let g(r) exp(γr) exp(βrϵ/na 2 ) be the time scaling in the definition (27) ofq r (t). Then, Therefore, the assumptions in part (b) of Theorem 3 are satisfied, and lim sup r→∞ e γr P sup Thus, (28) holds, which is the desired result. □ We note that part (c) of Theorem 3 provides a partial converse to Corollary 2: under i.i.d. arrivals with nonzero variance, additive SSC does not hold over a superexponential time scale.
The next corollary of Theorem 3(a) concerns additive SSC under diffusion scaling.
Corollary 3 (State Space Collapse in Diffusion Scaling). Consider a network operating under a WMW policy and a function f : N × R + → R + such that lim inf r→∞ f (r, δ)/r > 0 for all δ > 0. Consider a λ in the capacity region, an f -tailed sequence of arrivals A r (·) with limit mean λ, and a corresponding diffusion-scaled queue length processesq r (·) (see (16)). Suppose that dq r (0) , ((λ) ( ) → 0 as r → ∞. Then, for any T ∈ R + , P sup Corollary 3 strengthens Theorem 1 for the case of WMW policies in that the assumption of i.i.d. arrivals is removed. We only require a concentration property for the arrival process, such as which is even weaker than Assumption 2. Moreover, under an MW policy and i.i.d. arrivals, our Corollary 2 extends Theorem 1 by establishing SSC over an exponential time scale (as opposed to the diffusion scaling). For further perspective with respect to existing results, please refer to the discussion following the statement of Theorem 1 in Section 2.4.

Proof of Theorem 2
In this section, we present the proof of Theorem 2, organized in a sequence of four subsections. We first show in Section 5.1 that, for any network operating under a WMW policy, there is another network operating under an MW policy whose queue length process is a linear transformation of the queue length process of the original network. Thus, we can just focus on the MW policy. In Section 5.2, we review a general sensitivity result on a class of dynamical systems with piecewise constant drift. Next, in Section 5.3, we introduce an induced continuous-time dynamical system that provides the bridge between the original discrete-time process under an MW policy and the fluid model. The proof concludes in Section 5.4 by applying the general sensitivity result to the induced system.

From WMW to MW
In order to leverage the tools that we develop for MW policies and apply them to the more general WMW policies, we start with a reduction from WMW policies to an MW policy. This is accomplished through the following lemma, which shows that the queue lengths and fluid solutions under a WMW policy are linear transformations of queue lengths and fluid solutions under an MW policy in a transformed network.
Lemma 4 (Reduction of WMW Dynamics to MW Dynamics). Consider a network N with action set 6 and a routing matrix R. Fix a weight vector w, an arrival function A(·), and an arrival rate vector λ. Let Q(·) be a queue length process of N corresponding to the arrival A(·) under a w-WMW policy. Let W diag(w),λ W 1/2 λ, andÃ(t) W 1/2 A(t) for all t ∈ Z + . LetÑ be a network with action set6 W 1/2 6 and routing matrixR W 1/2 RW −1/2 . Then, a.Q(t) W 1/2 Q(t) is a queue length process ofÑ corresponding to the arrivalÃ(·) under an MW policy. b.q(t) W 1/2 q(t) is a fluid solution ofÑ corresponding to arrival rateλ and unit weights (as in MW) if and only if q(t) is a fluid solution of N corresponding to arrival rate λ and WMW weights w.

Finitely Piecewise Constant Subgradient Dynamical Systems
In this section, we review some definitions and results from . A dynamical system is identified with a set-valued function F : R n → 2 R n and the associated differential inclusionẋ(t) ∈ F(x(t)). We start with a formal definition, which allows for the presence of perturbations.
Definition 4 (Trajectories of a Dynamical System). Consider a dynamical system F : R n → 2 R n and let U : R → R n be a right-continuous function, which we refer to as the perturbation. Suppose that X(·) and ζ(·) are measurable functions of time that satisfy We then call X a perturbed trajectory corresponding to U. In the special case in which U is identically zero, we also refer to X as an unperturbed trajectory.
For a convex function Φ : R n → R, we denote its subdifferential by ∂Φ(x). We say that F is a subgradient dynamical system if there exists a convex function Φ : R n → R such that, for any for some µ i ∈ R n , b i ∈ R, and with i ranging over a finite set, we say that F is a finitely piecewise constant subgradient (FPCS) system. Note that, for such systems, F(x) is always equal to the convex hull of the vectors µ i that maximize −µ T i x + b i . FPCS systems admit a very special sensitivity bound.
Theorem 4 , theorem 1). Consider an FPCS system F. Then, there exists a constant C such that, for any unperturbed trajectory x(·) and for any perturbed trajectory X(·) with corresponding perturbation U(·) and the same initial conditions X (0) Moreover, for any λ ∈ R n , the bound (35) applies to the (necessarily FPCS) system F(·) + λ with the same constant C.

Reduction of the MW Dynamics to an FPCS System
Throughout this section, we restrict attention to a network operated under an (unweighted) MW policy. In order to take advantage of Theorem 4, we show that a discrete-time network can also be represented as an associated (induced) FPCS dynamical system.
Definition 5 (Induced FPCS System). For a network with action set 6 and routing matrix R, the induced FPCS system is the subgradient dynamical system F associated with the convex function In particular, F(x) is the convex hull of the image of 6(x) under the linear transformation R − I, where 6(x) is the set of vectors µ ∈ 6 that maximize ((I − R)µ) T x.
We start with the observation that fluid solutions of a network are trajectories of the induced FPCS system. Roughly speaking, this is because the service vectors chosen by the MW policy in (4) are maximizers of the set of linear functions ((I − R)µ) T Q over µ ∈ 6, and the fluid solution moves along the negative of a convex combination of such maximizing service vectors. Thus, fluid solutions move along the subgradients of Φ [defined in (36)] and are, therefore, trajectories of the induced FPCS system.
Proposition 2 (Fluid Model Solutions as Trajectories of the Induced FPCS System). Consider a network and its induced FPCS system F. Let q(·) be a fluid solution of the network corresponding to arrival rate λ. Then, q(·) is an unperturbed trajectory of the dynamical systemq ∈ F(q) + λ. Conversely, any unperturbed trajectory x(·) of F(·) + λ with x(0) ∈ R n + is a fluid solution corresponding to λ.
Proof. For a vector µ ∈ R n + and a set J ⊆ 1, . . . , n { }of indices, we let Equivalently, where σ −K (µ) is a vector whose ith entry is equal to the ith entry of µ if i / ∈ K and equal to zero if i ∈ K. Recall that 6(q) is defined as the set of all µ ∈ 6 that maximize ((I − R)µ) T q; see (4).
Claim 1. Fix a q ∈ R n + and a µ ∈ 6(q). Let J j | q j 0 { } . Then, Proof of Claim 1. Note that, for any µ ∈ 6 and any set K of indices, the vector σ −K (µ) also belongs to 6 because of Assumption 1. We now fix some q and the set J as in the statement of the claim. For any K ⊆ J, we have σ −K (µ) ≼ µ. Furthermore, because the entries of R and µ are nonnegative, we have q T R σ −K (µ) ≤ q T R µ. Therefore, where the second equality holds because q j 0 whenever the jth entry of σ −K (µ) is not equal to µ j . We have, therefore, established that, if µ ∈ 6(q), then σ −K (µ) ∈ 6(q). Because F(q) is the image under R − I of the convex hull of 6(q), we obtain Therefore, where the first equality is due to (38), and the last relation is due to (40) and the convexity of F(q). This establishes the validity of the claim (39). □ We now return to the proof of the proposition. Consider a function y(·) and a set of functions s µ (·), µ ∈ 6, that, together with q(·), satisfy the fluid model Equations (6)-(10). We show that q(·) satisfies the differential inclusionq ∈ F(q) + λ. Fix some t ≥ 0 and let y y(t). For any µ ∈ 6, let s µ s µ (t) and consider an n-dimensional vector y µ with entries Then, ∑ µ∈6 s µ y µ y.
It then follows from the first part of this proposition that q(·) is also an unperturbed trajectory of F(·) + λ. On the other hand, it is shown in Rockafellar (1970) that any subgradient dynamical system is a maximal monotone map. 13 Then, corollary 4.6 of Stewart (2011) implies that there is a unique unperturbed trajectory with initial point x(0). Therefore, x(t) q(t) for all t ≥ 0, and the desired result follows. □ Proposition 2 has established that a fluid solution is a trajectory of the induced FPCS system. We now show, in the next proposition, that the actual discrete-time queue length process is close to a perturbed trajectory of the induced FPCS system. Note that, even if the discrete-time system has completely deterministic and steady arrivals (no stochastic fluctuations) it can still "chatter" around the boundary separating two regions with different drifts. The idea behind the proof is that this chattering can also be viewed as a perturbation of a straight trajectory. This is conceptually straightforward, but some of the details of the behavior in the vicinity of such boundaries are tedious.
Proposition 3 (Queue Length Processes as Trajectories of the Induced FPCS System). For any network, there exists a constant β that satisfies the following statement. Fix a λ ∈ R n + and let A(·) be an arrival function and Q(·) be a corresponding queue length process. Then, there exists a right-continuous (perturbation) function U(·) : R + → R n satisfying and a corresponding perturbed trajectory X(·) of F(·) + λ such that It is possible to strengthen Proposition 3 and ensure that we actually have X(k) Q(k) for every k ∈ Z + , thus strengthening (46). However, this stronger result is not needed for our future development and would require a much more tedious construction of U(·). It is also worth pointing out here that the perturbed trajectory X(·) in our construction is always nonnegative. Before presenting the detailed proof, we provide some intuition on the issues that arise. Recall the network evolution rule Q(k + 1) Q(k) + A(k) + (R − I) min(µ(k), Q(k)) in (3). Consider a time k at which there is a unique maximizer µ(k) so that F(Q(k)) is a singleton, consisting of the single element (R − I)µ(k). Suppose, furthermore, that µ(k) ≼ Q(k). In this case, (3) becomes Q(k + 1) Q(k) + A(k) + (R − I)µ(k). Let for t k + 1.

{
In the interval t ∈ (k, k + 1), we haveU(t) −[(R − I)µ(k) + λ] ∈ −F(Q(k)) − λ. Suppose now that X(k) Q(k). From the dynamics of X(·) (see Definition 4), we havė and the perturbed trajectory remains constant: X(t) Q(k) for t ∈ (k, k + 1). Finally, a discontinuity in U(·) at t k + 1 forces X(t) to jump to the new value Q(k + 1). Thus, in this example, we have a perturbed trajectory that agrees with the queue process at integer times. This argument, however, fails when min(µ(k), Q(k)) ̸ µ(k) because the received service in time slot k, that is, (R − I) min(µ(k), Q(k)), needs not belong to F(Q(k)). To circumvent this problem, we find a nearby point y(k) such that (R − I) min(µ(k), Q(k)) ∈ F(y(k)). We then construct U(·) so that it forces X(t) to jump to y(k) at time t k and stay there for t ∈ [k, k + 1).
Proof. We now provide the detailed proof of Proposition 3. We make use of the following known result: Lemma 5 (Mannor and Tsitsiklis (2005), lemma 5.1). Given a finite collection of half spaces H i ⊂ R n with nonempty intersection, there exists a constant c > 0 such that We begin with a claim.
Claim 2. There exists a constant κ that satisfies the following. Consider any x ∈ R n + and any µ ∈ 6(x). Let Then, there exists a y ∈ R n + such that ∥y − x∥ ≤ κ and where D J (µ) is defined in (37).
Proof of Claim 2. We leverage Lemma 5 to find y and then use Claim 1 to prove (48). To every µ ∈ 6, we associate an effective region R µ : Fix some x ∈ R n + and some µ ∈ 6(x). The effective region R µ is then the intersection of half spaces of the form Because µ ∈ 6(x), we have x ∈ H π and d x, H π ( ) 0 for all π ∈ 6. Let be the maximum service capacity of any queue over all service vectors. We also define, for every i ≤ n, two half spaces H j + {z ∈ R n | z j ≥ 0} and H j − {z ∈ R n | z j ≤ 0}. It follows from the definition of J that, for any j ∈ J, d(x, H j − ) ≤ b, and from x ∈ R n + that d x, H i + ( ) 0 for all i ≤ n. We define a set B, which is determined by the chosen x ∈ R n + and µ ∈ 6(x), as follows: Note that the set B is the intersection of finitely many half spaces of the form H π , H j + , and H j − . Note, furthermore, that B contains the origin and is, therefore, nonempty. Finally note that x has a distance of at most b from each of the half spaces defining B. Therefore, Lemma 5 implies that for some constant c. In general, the constant c depends on the particular x and µ under consideration. Note, however, that the set B is completely determined by µ ∈ 6 and the set of indices J j | x j ≤ µ j { } . There are finitely many choices for µ and for J, hence, finitely many possible sets B. By taking the largest of the constants c associated with different sets B, we see that c in (52) can be taken to be an absolute constant, independent of x and µ. Let y be the closest point to x in the set B. Letting κ cb, (52) implies that where κ is an absolute constant. Golestani: Fluctuation Bounds for the Max-Weight Policy Stochastic Systems, 2020, vol. 10, no. 3, pp. 223-250, © 2020 The Author(s) Because y ∈ B, we have y ∈ R µ so that µ ∈ S(y). Moreover, for any j ∈ J, that is, if x j ≤ µ j , we have y j 0. Let J ′ {j | y j 0}. We then have J ⊆ J ′ . We now apply this inclusion together with Claim 1 with y and J ′ playing the role of q and J in the statement of the claim to obtain This completes the proof of the claim. □ For every t ∈ Z + , let µ(t) ∈ 6 Q(t) ( ) be the action taken by the scheduler at time t, J(t) j | Q j (t) ≤ µ j (t) { } , and y(t)∈ R n + be a vector that satisfies as in Claim 2. We now proceed to the main part of the proof of the proposition. With a slight abuse of notation, we write expressions such as ∑ k<t even if t is noninteger, which we interpret as ∑ {k∈Z + |k<t} . We define the rightcontinuous perturbation function U(·) as which is a finite constant. For any t ∈ R + , Hence, (45) follows for β κ + b. For every t ∈ R + , let Because ∥y(t) − Q(t)∥ ≤ κ, by construction, the desired equality (46) at integer times is trivially true with κ playing the role of β. It remains to show that X(·) is a perturbed trajectory. Let Because min(µ(⌊t⌋), Q(⌊t⌋)) ∈ D J(⌊t⌋) (µ(⌊t⌋)), it follows from (54) and (58) that ξ(t) ∈ F X(t) ( )+ λ for all t ∈ R + . We now show that For where the third equality follows from the evolution rule (3). Moreover, for any t / ∈ Z, Then, a simple induction based on (61) and (62) implies (60), and therefore, X(·) is a perturbed trajectory of F(·) + λ corresponding to U(·), which is the desired result. □

Proof of Theorem 2
Having established a reduction from WMW policies to an MW policy (in Lemma 4) and a reduction from a network, operating under MW policy, to its induced FPCS system (see Propositions 2 and 3), we can now leverage Theorem 4 to prove Theorem 2.
Proof of Theorem 2. Consider a network N that operates under a w-WMW policy. Let W diag(w). Consider a queue length process Q(·) of N corresponding to an arrival A(·) and a fluid solution q(·) of N corresponding to an arrival rate vector λ initialized at q(0) Q(0). For each time t, letQ(t) W 1/2 Q(t),q(t) W 1/2 q(t),Ã(t) W 1/2 A(t), andλ W 1/2 λ. Let θ min ≜ min i w 1/2 i and θ max ≜ max i w 1/2 i . Then, for any time t ∈ Z + , and LetÑ be, as in Lemma 4, a network that operates under an MW policy and for whichQ(·) andq(·) are a queue length process and a fluid solution, respectively. Consider the induced FPCS system F ofÑ. It follows from Proposition 3 that there exists a right-continuous perturbation function U(·) satisfying, for any t ∈ R + , and a corresponding perturbed trajectory X(·) of F(·) +λ such that where β is a constant independent ofλ. Moreover, from Proposition 2,q(·) is an unperturbed trajectory of F(·) +λ. Then, applying Theorem 4 for the FPCS sytem F, we obtain, for any t ∈ R + , Sharifnassab, Tsitsiklis, and Golestani: Fluctuation Bounds for the Max-Weight Policy Stochastic Systems, 2020, vol. 10, no. 3, pp. 223-250, © 2020 for some constantC ≥ 1 that is independent of λ. Let C C max(θ max , 2β) /θ min . Then, for any t ∈ Z + , where the relations are due to (63), (66), (67),C ≥ 1, (65), (64), and the definition of C, respectively. □

Proof of Theorem 3
In this section, we present the proof of Theorem 3. Part (a) is a corollary of part (b). In the following, we first prove part (b) and then part (c).

Proof of Part (b).
We first consider an MW policy. We then use Lemma 4 to extend the result to the case of WMW policies. The proof for an MW policy goes along the following lines. We break down a g(r)-long interval into subintervals of length r. We define a "good" event % r such that the aggregate arrival in each r-long interval does not deviate much from its average and show that this event happens with high probability. We then use Theorem 2 to show that % r implies that the queue length process stays close to a fluid solution in every subinterval. These fluid solutions are attracted to ((λ) (see Lemma 2) and, hence, also keep the queue length process near ((λ).
We now present a detailed proof. We fix some δ > 0 and some ϵ > 0 such that where C is the sensitivity constant provided by Theorem 2 and α α(λ) is the constant in Lemma 2 associated with λ. For r ∈ N, we define a good event % r as follows: We denote the complement of an event % by % c . Then, for any r, where the inequality is due to the union bound, the second equality holds because A r (·) is a stationary process, and the last equality is because A r (·), r ∈ N, is an f -tailed sequence of processes (see Definition 2). Also note that, in the last line, ϵ is a fixed constant, and the o(·) notation is with respect to r as r goes to infinity.
From now on and because λ is fixed, we use the simpler notation ( instead of ((λ). Consider an r 0 ∈ N such that, for every r ≥ r 0 , Such an r 0 exists because of the convergence assumptions in the statement of the theorem, which also imply that λ r is a bounded sequence. For every r, i ∈ Z + , we define the following two events, E r,i and E ′ r,i : where Q r (·) is the queue length process corresponding to the arrival A r (·). Using Theorem 2, we now show that, for any r ≥ r 0 , % r implies E r,i and E r,i for all i < g(r)T/r.
Claim 3. Fix some r ≥ r 0 . The occurrence of the event % r implies the occurrence of the events E r,i and E ′ r,i for all i < g(r)T/r.
Proof of Claim 3. The proof is by induction on i. For the base case, E r,0 follows from (72), because of Q r (0) rq r (0) and the conic property of ( in (13). For the induction step, we show that, for any i < g(r)T/r, the events % r and E r,i imply E r,i+1 and E ′ r,i . For any r ∈ Z + , let q r i (t) be the fluid solution corresponding to arrival rate λ r and initialized with q r i (ir) Q r (ir) at time ir. Fix an arbitrary t 0 ≥ ir and let q(·) be a fluid solution corresponding to arrival rate λ, initialized at q(t 0 ) q r i (t 0 ). From Proposition 2, q(·) and q r i (·) are solutions ofq ∈ F(q) + λ andq r i ∈ F(q r i ) + λ r , respectively, where F is the induced FPCS system of the network. It then follows from lemma 4.5 of Stewart (2011) that, for any t ≥ t 0 , Suppose that q r i (t 0 ) / ∈ (. Then, we also have q(t 0 ) / ∈ (, and Lemma 2 implies that where the second inequality is from (75), and the fourth inequality is due to (68). Moreover, under E r,i , we have Then, for any r, i ∈ Z + and under E r,i , Golestani: Fluctuation Bounds for the Max-Weight Policy Stochastic Systems, 2020, vol. 10, no. 3, pp. 223-250, © 2020 The Author(s) where the second inequality is due to Theorem 2 and the last inequality follows from (73) and % r . This implies E r,i+1 . Moreover, where the second inequality is due to (77), the third inequality follows from Theorem 2, the fourth inequality is from (73) and % r , and the last inequality is due to the definition of ϵ in (68). This implies E ′ r,i and completes the proof of the claim. □ Back to the proof of the theorem, let us again fix some r ≥ r 0 . We have P sup where the second equality is due to (13), the first inequality is from the definition of E ′ r,i , and the last inequality is due to Claim 3. Thus, where the first two inequalities are due to (79) and (70), respectively, and the equality follows from the assumption lim inf r→∞ g(r)/r > 0. This completes the proof of part (b) for the case of an MW policy. We now present the proof of part (b) for WMW policies. Suppose that a network N operates under a w-WMW policy and consider an associated networkÑ as in Lemma 4 along with the variables and processes therein. It follows from Lemma 4 that, if the constant function q(t) q 0 is a fluid solution for network N, then the constant functionq(t) W 1/2 q 0 is a fluid solution forÑ under an MW policy and vice versa. Therefore, ( W 1/2 ( is the set of invariant states forÑ, corresponding to arrival rateλ W 1/2 λ. Let θ min ≜ min i w 1/2 i and θ max ≜ max i w i 1/2 . Letq(·) W 1/2q (·), which is the scaled version of the MW-driven processQ(·). Then, for any r ∈ N and any time t, In the same vein, As a result,Ã r (·), r ∈ N, is a (θ max f )-tailed sequence of processes. As in (68), fix some δ > 0 and some ϵ > 0 such that ϵ ≤ min δθ min , α ( ) /4C, where C is the sensitivity constant of the network operating under a MW policy (see Theorem 2) and α α(λ) is the constant in Lemma 2 associated withλ. Using what we have already established for MW policies, it follows that This, together with (80), implies that and part (b) of the theorem follows.
Proof of Part (c). Throughout this proof, we assume that we have fixed a network operated under an MW policy as well as functions f (·) and g(·) with the properties in the statement of the result, namely lim r→∞ rf r, ϵ ( )/g(r) 0 for all ϵ > 0 and lim r→∞ g(r)/r ∞. It is not hard to see that these properties guarantee that there exists a function h : Leth(r) rg(r)/h(r). Then, Before continuing with the main part of the proof, we establish that ((λ) is contained in a low-dimensional subspace. The intuition behind this fact is that ((λ) is contained in the intersection of different effective regions, each of which is a polyhedron. Recall that # stands for the capacity region of the network.
Claim 4. Suppose that λ ∈ # but λ is not an extreme point of #. Then, there exists a nonzero vector v ∈ R n such that v T ((λ) {0}.
Proof of Claim 4. Because λ ∈ #, it follows from (5) that λ ∈ I − R ( )Conv(6). Therefore, for some nonnegative coefficients α µ that sum to one. Let us assume that we have fixed one particular set of such coefficients.
Consider some x ∈ ((λ) and let F be the induced dynamical system of the network. It follows from Proposition 2 and the definition of ((λ) that 0 ∈ F(x) + λ. Therefore, λ ∈ −F(x). because F(x) is the convex hull of the vectors µ that maximize x T (I − R)µ, we have Sharifnassab, Tsitsiklis, and Golestani: Fluctuation Bounds for the Max-Weight Policy Stochastic Systems, 2020, vol. 10, no. 3, pp. 223-250, © 2020 for some nonnegative coefficients β ν that sum to one. This, together with (89), implies that and as a result, ∑ Because 6(x) is the set of maximizers of x T I − R ( )ν over ν ∈ 6, it follows from (92) that, if α µ > 0, then and this relation is true for all x ∈ ((λ). This is because, otherwise, the left-hand side of (92) would be strictly smaller than the right-hand side.
On the other hand, because λ is not an extreme point of #, it follows from (5) that λ is not an extreme point of I − R ( )Conv(6). Then, there are at least two service vectors µ, ν ∈ 6 for which α µ , α ν > 0 and I − R , which is a nonzero vector. As already shown in (93), for any x ∈ ((λ), we have µ, ν ∈ 6(x). Therefore, for any x ∈ ((λ), we have x T I − R ( )µ x T I − R ( )ν, that is, v T x 0, and the claim follows. □ Using this claim, consider an (n − 1)-dimensional subspace Z containing ((λ) and let w be a vector in R n + \Z. By suitably scaling w, we can assume that d w, Z ( ) 1. Then, w can be decomposed as w z + v for some z ∈ Z and some v ̸ 0 that is orthogonal to Z and has unit norm v 1. We also let which is the maximum instantaneous change in the queue lengths resulting from service, where R and 6 are the routing matrix and the set of service vectors, respectively. It follows from (87) and (88) that there exists some r 0 ∈ N such that, for any r ≥ r 0 , For every r ∈ N, let A r (·) be an i.i.d. process with values Because w ∈ R n + , A r (t) is nonnegative for all r and t, and from (88), For any r ∈ N and any T ∈ Z + , consider an event E r T : E r T : the event that A r (t) λ +h(r) w, for at least one t ∈ 0, T [ ).
Consider some r ≥ r 0 . If E r r does not occur, then, for any t < r and any δ > 0, where the second inequality follows from (96) and the union bound. Thus, for any δ > 0, where the equality is due to (84). Hence, A r (·), r ∈ N, is an f -tailed sequence of processes. According to our definition of v, we have v w − z, v is orthogonal to the subspace Z containing ((λ), and ⃦ ⃦ v ⃦ ⃦ d w, Z ( ) 1. Therefore, for any r ≥ r 0 , if A r (t) λ +h(r) w for some t, then where the inequalities are due to (94), (95), respectively. Now, recall that v is orthogonal to the subspace Z containing ((λ). Whenever we have A r (t) λ +h(r) v, we have a jump of size at least 2rδ in a direction orthogonal to ((λ) from which it is not hard to see that This implies that, for any r ≥ r 0 , if the event E r g(r)T occurs, then sup where the last equality is due to (85). This completes the proof of part (c).
Remark 1. The requirement, in part (c) of the theorem, that λ is not an extreme point of # cannot be removed. For a trivial example, consider a single queue with a single (one-dimensional) service vector µ 1. Then, # [0, 1]. If λ 1, then every q ≥ 0 is an invariant state: ((1) [0, ∞). The conclusion of Claim 4 fails to hold, and it is certainly impossible for the state to be outside ((1).
Remark 2. The process A r (t), used in the proof of part (c) is not uniformly bounded as it can have bursts of sizeh(r). With some additional effort and a slightly more complicated proof, it is possible to carry out a construction under which each component of A r (t) is bounded by some constant, independent of r or t. The basic idea is that having excess arrivals (but of bounded size) over a time period of length O(h(r)) has an effect comparable to a single burst of size O(h(r)).

Discussion
In this section, we review our main results, their implications, and directions for future research.

Main Results
We have established a deterministic bound on the sensitivity of queue length processes with respect to arrivals under a max-weight policy. In particular, we showed that the distance between a queue length process and a fluid solution remains bounded by a constant multiple of the deviation of the aggregate arrival process from its average. The bound allows for tight approximations of the queue lengths in terms of fluid solutions, which are much easier to analyze, and leads to a simple derivation of a fluid limit result; see Corollary 1. We then exploited this sensitivity result to prove matching upper and lower bounds for the time scale over which additive SSC occurs under a MW policy. As a corollary, we established strong (additive) SSC of MW dynamics in diffusion scaling under conditions more general than previously available. For the case of i.i.d. arrivals, we established additive SSC over time intervals whose length scales exponentially with r. Such a result could also be proved with a more elementary argument by viewing the distance from the invariant set as a Lyapunov function and using the drift properties that we established; see Lemma 2. Nonetheless, such Lyapunov-based approaches are hard to generalize to broader classes of arrival processes. In contrast, our sensitivity bounds in Theorem 2 allow for the arrival processes to be arbitrary and yield strong approximation results as long as the driving process has some reasonable concentration properties.

Other Applications and Extensions
A similar sensitivity bound can also be proved, using the same line of argument for continuous time networks, for example, with Poisson arrivals, operating under an MW policy. Similarly, for a more general class of stochastic processing networks, and under assumption 1 of Dai and Lin (2005), it is not hard to see that the fluid dynamics again are a subgradient flow and that our results can be extended to such systems.
In the same spirit, we believe that the results, including additive SSC, can be extended to the case of backpressure policies 14 (Tassiulas and Ephremides 1992, Georgiadis et al. 2006, Neely 2010 for networks in which the routing is no longer fixed and in which the different vectors µ determine the set of links to be activated. Another direction concerns SSC results in steady state, that is, the extent to which the steady-state distribution is concentrated in a neighborhood of the invariant set. Following a Lyapunov-based approach, several works (Maguluri and Srikant 2015, Shah et al. 2016) have proved exponential tail bounds for the steady-state distribution for the case of i.i.d. arrivals. We believe that Theorem 2 provides an approach for establishing similar bounds for the case of non-i.i.d. and non-Markovian arrivals.
Finally, another problem in which the fluid model turns out to be analytically beneficial concerns delay stability under an MW policy in the presence of heavy-tailed traffic. Markakis et al. (2016Markakis et al. ( , 2018 studied the question of whether a certain queue has finite expected delay ("delay stability") in the presence of other queues that are faced with heavy-tailed arrivals. They provided a necessary condition for this to be the case in terms of certain properties of the associated fluid model and raised the question of whether, under some assumptions, this condition is also sufficient. Using the sensitivity results of the current paper, we are able to resolve a variant of this question as will be reported in a forthcoming publication.

Open Problems
The sensitivity bound in Theorem 2 applies only to MW and WMW policies. It is not clear whether a similar bound holds for the more general classes of MW-α and MW-f policies. A similar question also arises about SSC: does Theorem 3 hold under a MW-α policy?
On the other hand, we have Φ λ (0) 0. It follows that the set of minimizers of Φ λ , denoted by Γ, is We use the shorthand notation ( for ((λ). We now develop a characterization and a simple polyhedral description of the set (. Recall that ( is the set of all x 0 ∈ R n + for which the constant trajectory q(t) x 0 is a fluid solution. As pointed out earlier, fluid solutions are the same as the nonnegative unperturbed trajectories of the system F(·) + λ, where F + λ −∂Φ λ . In particular, q(t) x 0 is a constant trajectory of this system if and only if ∂Φ λ (x 0 ) contains the zero vector, which is the case if and only if x 0 is a minimizer of Φ λ , that is, x 0 ∈ Γ. Therefore, For any µ ∈ 6, we define the half space H µ {x ∈ R n | ((I − R)µ) T x ≤ λ T x}. We also let, for i 1, . . . , n, H i x ∈ R n | x i ≥ 0 { } . We now show that Suppose that x 0 ∈ (. Then, x 0 ∈ R n + , that is, x 0 ∈ H i for all i. Furthermore, x 0 ∈ Γ and, from (A.2), Φ λ (x 0 ) 0. From (A.1), this implies that max µ∈6 ((I − R)µ T )x 0 λ T x 0 so that ((I − R)µ) T x 0 ≤ λ T x 0 or, equivalently, x 0 ∈ H µ , for all µ. This argument can be reversed. If x 0 belongs to all of the half spaces H µ , we have Φ λ (x 0 ) ≤ 0, which, in light of (A.1) implies that Φ λ (x 0 ) 0 or x 0 ∈ Γ. If, in addition, x 0 ∈ R n + , then, from (A.3), we obtain x 0 ∈ (. This concludes the proof of (A.4). Having characterized the set (, we now turn our attention to the dynamics that drive trajectories toward (. Fix some µ ∈ 6. For any x / ∈ H µ , the closest point to x in H µ lies on the boundary of H µ , that is, on the subspace W µ {z ∈ R n | g T µ z 0}, where g µ (I − R)µ − λ. For any x ∈ R n and µ ∈ 6, either d(x, H µ ) 0 (which includes the case in which g µ 0 so that W µ H µ R n ) or g µ ̸ 0 and x / ∈ H µ , in which case which is the length of the projection of x on the normal vector to W µ . Thus, in both cases, we have Then, for any x ∈ R n , Let ϵ min ∥g µ ∥ : µ ∈ 6, g µ ̸ 0 { } . Without loss of generality, we assume that ϵ > 0; otherwise, we would be dealing with a trivial system in which every g µ is zero, and Φ λ is identically zero. Note that, for any x ∈ R n + , we have where the equality is because, when x ∈ R n + , we have d x , H i ( ) 0 for all i.
Consider a fluid solution x(·) and fix a time t such that x(t) / ∈ (. Let x 0 x(t) and let z be the element of ( that is closest to x 0 . Then, at time t, Putting everything together, we obtain where the second inequality is because −ẋ(t) is a subgradient of Φ λ at x 0 ; the equality is because z ∈ ( and Φ λ vanishes on ( by (A.3), (A.2); the third inequality is due to (A.7) and (A.4); and the last inequality follows from Lemma 5 for the constant c therein. This completes the proof of Lemma 2 with α(λ) c ϵ.

Appendix B. Proof of Lemma 3
Let X 1 , . . . , X t be i.i.d. random variables, taking values in [0, a] and let X X 1 + · · · + X t ( ) /t. Then, for any δ > 0, Hoeffding's (1963) inequality yields For any fixed r ∈ N and t ≤ r, where the first inequality holds because if the Euclidean norm is above δ, then at least one of the components must be above δ/ ̅̅ n √ , together with the union bound, and the third inequality is due to (B.1). As in the statement of the lemma, let β ∈ (0, 2) and f (r, δ) exp βrδ/na 2 ( ) . We then have f r, δ ( )P 1 r sup where the second inequality is due to (B.2), and the last implication is because β < 2.
Endnotes 1 We note here the important distinction between multiplicative and additive (or strong) state space collapse, which is discussed further in Section 2.4. The literature review here is mostly about multiplicative state space collapse. 2 For any given α > 0, the MW-α policy is an extension of the MW policy in which the "weight" of queue i is proportional to Q α i , where Q i is the length of the queue at node i. 3 A dynamical system is called nonexpansive if, for any two trajectories, x(·) and y(·), we have d dt ⃦ ⃦ x(t) − y(t) ⃦ ⃦ ≤ 0.
4 A MW-f policy is obtained by replacing Q T W in (4) by f (Q), where f : R n → R n is a function in an appropriate class.
5 Max-weight is a special case with the utility function equal to zero.
6 For a concrete example, if µ corresponds to serving only queue j with unit service rate and if work completed at queue j is routed to queue i, the term Q T W(I − R)µ is of the form w j Q j − w i Q i . 7 This alternative description also explains why uniqueness holds in contrast to the case of more general multiclass queueing networks; see the last paragraph of the proof of Proposition 2. 8 In our statement of the assumption, we modify the notation of Shah and Wischik (2012), interchanging the roles of z and r to preserve consistency with the rest of this paper. 9 "Stationary" means that the A r (t) have the same distribution for all t but without necessarily being independent.
11 The result in Shah et al. (2010) assumed that q 0 0; however, the proof extends to the case of general q 0 .
12 As pointed out by a reviewer, a further extension appears possible, in which q 0 is not an element of ((λ) with the results holding over intervals of the form [ϵ, T] for any ϵ > 0 in the spirit of similar results in Williams (1998) and Stolyar (2004). 13 A set-valued function F : R n → 2 R n is a monotone map if, for any x 1 , x 2 ∈ R n and any v 1 ∈ F(x 1 ) and v 2 ∈ F(x 2 ), we have v 1 − v 2 ( ) T x 1 − x 2 ( )≤ 0. It is called a maximal monotone map if it is monotone, and for any monotone mapF that satisfies F(x) ⊆F(x) for all x, we haveF F. 14 Back-pressure policies are extensions of the MW policy in which routing is no longer fixed. In particular, there is a fixed set of service vectors, in which each service vector µ associates a rate µ ij to each link ij. A back-pressure policy then chooses at each time a service vector µ that maximizes ∑ ij µ ij (Q i − Q j ), where the sum is taken over all links ij.