Thermodynamic Limit of Interacting Particle Systems over Time-varying Sparse Random Networks
Augusto Almeida Santos Soummya Kar José M. F. Moura João Xavier


Supplemental material for “Correlators in simultaneous measurement of non-commuting qubit observables”
    Alexander N. Korotkov
    December 30, 2023
======================================================================================================

empty
plain


We establish a functional weak law of large numbers for observable macroscopic state variables of interacting particle systems (e.g., voter and contact processes) over fast time-varying sparse random networks of interactions. We show that, as the number of agents N grows large, the proportion of agents (Y_k^N(t)) at a certain state k converges in distribution – or, more precisely, weakly with respect to the uniform topology on the space of càdlàg sample paths – to the solution of an ordinary differential equation over any compact interval [0,T]. Although the limiting process is Markov, the prelimit processes, i.e., the normalized macrostate vector processes (𝐘^N(t))=(Y_1^N(t),…,Y_K^N(t)), are non-Markov as they are tied to the high-dimensional microscopic state of the system, which precludes the direct application of standard arguments for establishing weak convergence. The techniques developed in the paper for establishing weak convergence might be of independent interest.


Keywords: Interacting particle systems; large-scale systems; thermodynamic limit; functional weak law of large numbers; time-varying sparse random networks; fluid limits; non-Markovian processes

















§ INTRODUCTION


Systems of interacting agents – often abstracted as interacting particle systems – can model many applications of large-scale networked agents from voting processes to diffusion of opinions or epidemics in large populations; examples include the Harris contact process, the voter process, and the Glauber-Ising model <cit.> in statistical mechanics. Due to the large-scale of such systems, it is often not feasible to follow the pathwise dynamics of the high-dimensional microstate, i.e., of the collective state of all individuals in the population. As an alternative, one could attempt to study the evolution of the system by observing macroscopic quantities, that is, the state variables defined as global averages or low-resolution functionals of the microstate. For instance, in epidemics, observing the binary state of each individual – infected or not infected – is prohibitive in a large population; instead, one often tracks the fraction of infected nodes in the population – a macroscopic observable. However, and in light of the discussion in the introduction of <cit.>, while the microstate of a system and the local rules of interaction completely determine its evolution (determinism principle), two systems at the same macrostate may evolve very differently. For instance, two distinct communities A and B may each have 50% of infected individuals, but community A may have a large number of contacts intertwining infected and healthy individuals – a microscopic information – as opposed to community B that may have a more clustered configuration. These microscopic configurations cause very different evolutions of the system at the macroscale: for example, the infected population will tend to increase at a much faster rate in community A. Fig. <ref> illustrates this example.

It remains a major challenge in statistical mechanics to understand how the microscopics are exactly quotiented out, in the limit of large-scale interacting agents, to engender deterministic laws at the macroscale (a.k.a. fluid limit dynamics) without resorting to simplifying hypothesis of: i) full mixing: where the underlying network of interactions is complete[Any agent can interact with any other agent at any time.]; ii) ideal gases: no interaction among agents or iii) ergodicity. In such cases, the macrostates are overall Markov.

More formally, and for the sake of clarity, we introduce the concept of realization. Let (X(t)) be Markov. We say that the stochastic process (X(t)) is a refinement of the process (Y(t)) if (Y(t)) is measurable with respect to (X(t)). We say that (Y(t))=(F(X(t))) realizes its refinement (X(t)) when (Y(t)) is Markov, i.e., its local (in time) evolution at each time t depends on the finer process (X(t)) only through (Y(t)) itself at each time t. For instance, if F is bijective, then (Y(t)) trivially realizes (X(t)). In statistical mechanics, (X(t)) plays the role of the high-dimensional microscopic process conveying all the information of the interacting particle system and (Y(t)) plays the role of the low-dimensional macroscopic observable. In such framework, F is not bijective – many different microstate configurations yield the same macroscopic observation.

In general, even though the microstate (X(t)) is Markov, the macrostates (Y(t)) are not as they are tied to the microstate, i.e., they do not realize the microstate. This paper proves that, in interacting particle systems over appropriate fast time-varying networks, the macrostates asymptotically realize the microstate and become Markov: as the number of agents grows large, knowledge of the macrostates Y(t) at present t becomes sufficient to foresee their immediate future. In other words, the determinism principle is recovered in the limit of large scale (time-varying) networks for the macrostate quantities. Formally, we prove that a sequence of non-Markov macrostate processes (𝐘^N(t)) converges in distribution – i.e., weakly with respect to the uniform topology on the space of càdlàg sample paths – to a process (𝐲(t)) that is the solution to an ordinary differential equation whose vector field only depends on (𝐲(t)), and thus, the limiting process (𝐲(t)) is Markov. In other words, the process (Y^N(t)) realizes the microstate (X^N(t)) asymptotically in N (though not for finite N).

When the exact ODE fluid limit dynamics associated with macroscopic state variables of a complex system exists, it provides a means to study interacting particle systems at the low-dimensional macroscale without keeping track of their microscopics; in particular, fluid limits are relevant to study the stability and metastability – often observed in dynamical systems exhibiting multiple equilibria with large basins of attraction – of systems at the macroscale, e.g., <cit.> and, it is useful to study the qualitative dynamics of such large-scale systems outside their thermo-equilibrium (if there is one). These in turn maps to questions of determining thresholds and conditions on the parameters of the dynamical system under which this is ergodic or not (due to having multiple invariant measures). Hence it is worth seeking conditions on the underlying dynamics of the network (if not static) and of the interactions among agents that yield an exact fluid dynamics. To the best of our knowledge, such conditions are still sparse in the literature and exact concentration results for macroscopic variables associated with stochastic processes over networks are still a very open question in the literature: they are only available for complete networks, or trivial variants, e.g., supernetwork of densely connected cliques (a.k.a., network of communities), or complete-multipartite networks. The major reason lies in the fact that in such densely connected cases, the macroscopic variables of interest realize the microscopics, i.e., they are Markov and convergence results follow as corollary to now standard arguments such as Kurtz Theorem <cit.> (for weak convergence on the sample path), or Stein's method (for weak convergence of some limiting distribution, e.g., Gibbs measure), whereas for other settings, involving non-Markovian prelimit processes, asymptotic properties are relatively less explored. For instance, a complete network assumption is crucial to prove the limiting theorems in <cit.> as it leads to full-exchangeability of the underlying macroscopic quantities (which in turn allows to resort to Stein's method). In our model we do not assume any of the densely connected type of networks mentioned and the underlying process is not exchangeable (though partial exchangeability is present as we will remark momentarily). In fact, in our case, the network will vary over time preserving its low-sparsity – the number of edges is ∼ O(N).
Note that one may also establish relevant bounds on macroscopic quantities – instead of seeking exact fluid limits – via stochastic domination on sparse networks by bounding the corresponding processes over complete network counter-parts as, e.g., in <cit.>. That is not the goal in the current paper. In this work, we show that for a particular dynamics of the network of contacts, namely, whenever there is an interaction between two agents, the agents randomly shuffle, then we obtain an exact fluid limit concentration. It lays still open, the question of determining the broadest class of network dynamics that leads to an exact fluid limit.

Note that one can obtain the limiting Partial Differential Equation dynamics of exclusion processes over lattices via the framework of hydrodynamics, e.g., <cit.>: where one seeks to determine the PDE thermodynamic limit associated with the evolution of the number of particles locally in space (e.g., following exclusion processes dynamics). In particular, one is interested in the limiting behavior of a process (η^N(x,t)) – the number of particles in a small interval or patch of space about x, whose length is of order O(1/N), – whereas we are interested in the evolution over time (without spatial dependence, i.e., ODE instead of a general PDE) of the fraction of agents at a particular state. The above framework is different from the one studied in this paper, e.g., the former requires a local renormalization of the scale of time and each vector-process (η^N(x,t)) – where the vector entries collect the number of particles at each patch of the discretized space – in the sequence is Markov.











To summarize, this paper shows that under a time-varying random rewiring dynamics of the sparse network of contacts or interactions (described in Section <ref>), one can obtain exact weak convergence of the macrostate quantities, and, in particular, characterize their macroscale dynamics (ODE fluid limit). This work thus helps in filling the gap on the characterization of exact fluid limit dynamics on processes over large sparse random networks of contacts. As explained more formally in Section <ref>, besides classical interacting particle systems examples, the model adopted here may be applicable to other scenarios of practical interest, such as the case of malware spread in mobile communication networks, an application of increasing relevance given the emergence of large-scale distributed denial of service (DDoS) attacks <cit.>.


Outline of the paper. Section <ref> introduces the main definitions and the dynamics assumed; Section <ref> formalizes the main goal of the paper; Section <ref> establishes an important result on the concentration of a rate process; Section <ref> finally establishes the weak convergence of the macroprocess and illustrates a simulation result; and Section <ref> concludes the paper.



§ PROBLEM FORMULATION






In this section, we present the general class of interacting particle systems denoted as Finite Markov Information-Exchange (FMIE) introduced in <cit.>, and we define the model and dynamics we assume.



 §.§ Main Constructs


Consider N agents and let X^N_ik(t)∈{0,1} be the indicator that node i is in state k∈𝒳:={1,2,…,K} at time t, where K<∞ is fixed. We represent by

    𝐗^N(t)=(X_ik^N(t))_ik,  X_ik^N(t)∈{0,1}

the matrix microstate collecting the state of each of the N agents at time t. Each node can only be at one particular state at a time, i.e., the rows of (𝐗^N(t)) sum to 1. The underlying network of potential interactions, at time t, is captured by the binary adjacency matrix on N nodes A^N(t)∈{0,1}^N × N. Let

    𝐗_k^N(t)=(X_1k^N(t),…,X_Nk^N(t))∈{0,1}^N

be the k-column of the matrix 𝐗^N(t).
We consider the macroscopic state variables

    Y_k^N(t)=∑_i=1^N X_ik^N(t)=1^⊤𝐗_k^N(t)

to be the number of agents at the state k∈𝒳 at time t and its normalized counterpart

    Y_k^N(t)=1/N1^⊤𝐗_k^N(t)

to be the fraction of nodes at the state k∈𝒳. Also, denote by

    𝐘^N(t)=(Y_1^N(t),…,Y_K^N(t)),

the vector process representing the empirical distribution of nodes across states 𝒳.

The microstate (𝐗^N(t)) is updated by two distinct processes: i) the peer-to-peer interactions given by the microscopic dynamics; and ii) the network random rewiring. Both are described in the next two subsections.



 §.§ Peer-to-peer Interaction Dynamics


We assume d_i(t) clocks at each node i, where d_i(t) is the degree of node i at time t and each clock is dedicated to a current neighbor of i: once a clock ticks, agent i interacts with the corresponding neighbor (in the current network topology or geometry). The clocks are independent and exponentially distributed – hence, (𝐗^N(t)) is Markov. The state 𝐗^N(t) is updated by these local interactions. If i interacts with j (as the clock of i pointing to j rings) at time t, the state of i and j are updated as

    (𝐞_i^⊤𝐗^N(t),𝐞_j^⊤𝐗^N(t))=G(𝐞_i^⊤𝐗^N(t_-),𝐞_j^⊤𝐗^N(t_-))

where 𝐞_ℓ is the canonical vector with 1 at the ℓth entry, and zero otherwise, and G : ℰ×ℰ→ℰ×ℰ is the update function with

    ℰ:= {𝐞_1,𝐞_2,…,𝐞_K}.

G is a function that maps the state of the interacting nodes onto the new state, similar to as defined in <cit.>. For instance, if a node from state 3 interacts with a node in state 5 then, the new state for both nodes will be given by the tuple G(𝐞_3,𝐞_5).

From the peer-to-peer dynamics described, the updates in the microstate (𝐗^N(t)) change the macrostate (𝐘^N(t)) according to the following Martingale problem <cit.> pathwise dynamics

    Y_k^N(ω,t)  =  Y_k^N(ω,0)+M_k^N(ω,t) + 1/N∫_0^t ∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) 𝐗_m^N ⊤(s_-) A^N(s_-)𝐗_ℓ^N(s_-)_=:ℱ^N_k(𝐗^N(t_-),A^N(t_-)) ds

where Y_k^N(ω,t) is the fraction of agents at the state k at time t for the realization ω, (M_1^N(t),…,M_K^N(t)) is a normalized martingale process (refer to equation (<ref>)), γ_mℓ is the rate of the exponential clocks from nodes at the state m to contact nodes at the state ℓ, and c_mℓ(k)∈{-2,-1,0,1,2} gives the increment in the number of nodes at state k due to the interaction between nodes in states m and ℓ. For instance, if whenever node i in state 1 interacts with node j at state 2 causes both i and j to turn to state 4, then c_12(4)=2. The terms c_mℓ(k) are uniquely determined from the given update function G. Note also that the clock-rates γ_mℓ may or may not depend upon the states m and ℓ of the interacting nodes. For instance, for the analysis of contact processes, γ_mℓ is often assumed independent of the states and represented simply as γ (rate of infection).

Remark on c_mℓ(k). Note that, if two nodes at state k interact, than the number of nodes in state k cannot be incremented as a result of this interaction (the two nodes interacting are already at this state). Hence, tensor 𝐜 is constrained to c_kk(k)≤ 0 for all k. This leads, on the other hand, to the fact that the hyper-cube [0,1]^K is invariant under the stochastic dynamics (<ref>).



 §.§ Rewiring Network Dynamics


Once an update on the microstate happens, the edges of the network are randomly rewired, i.e.,

    A^N(t)=P^⊤ A^N(t_-) P,

where P∈𝒫_ er(N) is drawn uniformly randomly from the set of N× N permutation matrices 𝒫_ er(N) – each time an update occurs.

An alternative representation to the random rewiring is the following:

    𝐗_m^N ⊤(t_-)(P^⊤A^N(t_-)P)𝐗_ℓ^N(t_-)=(P𝐗_m^N(t_-))^⊤A^N(t_-)(P𝐗_ℓ^N(t_-)),

in other words, we can consider equivalently that the network A^N is fixed and that the position of the nodes permute just after an update. This interpretation is assumed throughout the paper. And in fact, such partial exchangeability allows us to consider any network A^N with a fixed number of edges. For each N, we consider a regular network with degree d^N and thus, the degree, in a sense, controls the sparsity of the network – or, if we will, the real-time bandwith of nodes for peer-to-peer contact. Note that, given any even number N and an arbitrary degree d<N, one can always draw a regular bipartite graph from it. In other words, and for the sake of our problem, we can assume that the graph is regular bipartite (which will be convenient momentarily).












§ SUMMARY AND GOAL OF THE PAPER


The model introduced in Section <ref> arises from the fact that often agents wander around as their state evolves, instead of being static. The macroscopic dynamical laws derived may be useful, e.g., to study large-scale interacting particle systems supported in sparse dynamical network environments. One particular application is malware propagation <cit.> in mobile devices networks. Mobile devices move around fast in an ad-hoc manner – hence, the underlying network of contacts changes fast over time in an ad-hoc manner – and their real-time bandwith for peer-to-peer communication is usually low <cit.> – hence, the geometry of the support network of interactions is sparse – nevertheless, the massive amount of infected mobile devices corresponds to a large-scale (botnet) network that may launch, for instance, DDoS attacks <cit.>, a modern threat over the Internet-of-Things (IoT) of increasing importance <cit.> and that may display non-trivial metastable behavior <cit.>.

One can partition the class of interacting particle systems into three broad categories:

  
  * Fast network mixing dynamics: the support network dynamics, i.e., the movement of the interacting agents runs at a much faster time-scale than the interactions among the agents themselves;
  
  * Static network: interactions among agents run at a much faster rate than the network dynamics;
  
  * Mesoscale: both dynamics run at comparable speeds.

The fluid limit paradigm varies greatly depending on the class under analysis. Our work sits primarily upon the first category: fast network mixing dynamics.

To summarize, the microstate (𝐗^N(t)) is updated in two ways: i) peer-to-peer interactions given by the microscopic dynamics; and ii) network random rewiring just described. Fig. <ref> summarizes the model for the case of a contact process and assuming that (the fixed) A^N is a cycle network.




Note from equation (<ref>) that the empirical process (𝐘^N(t)) is not Markov as it is tied to the finer microscopics (𝐗^N(t)). Our goal is to prove that the non-Markovian sequence (𝐘^N(t)) converges weakly as N goes to infinite, with respect to the uniform topology on the space of càdlàg sample paths, to the solution (𝐲(t)) of the ODE

    ẏ_k(t) = d ∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) y_m(t)y_ℓ(t),

for k∈𝒳={1,…,K}, where d is the asymptotic average degree of the limiting network, and γ_mℓ is the rate of the exponential clocks from nodes at state m to contact nodes at state ℓ. More compactly, the limiting equation is given by the ODE

    ẏ_k(t) = d   𝐲(t)^⊤(Γ⊙ C(k)) 𝐲(t)=:f_k(𝐲(t)),

where C(k):=(c_mℓ(k))_mℓ, Γ:=(γ_mℓ)_mℓ, and ⊙ is the pointwise Hadamard product. Recall that the constraints on C, in order to make the microscopic model physically meaningful (as referred at to the end of Subsection <ref>) imply that the hyper-cube [0,1]^K is invariant under the ODE dynamics (<ref>).

This tacitly implies that, in order to perform macroscopic analysis in the large-scale, one can replace the complex stochastic microscopic dynamics in equation (<ref>) by the lower-dimensional ODE in equation (<ref>).

In the next sections, we prove weak convergence by establishing four major results:

i) (Convergence on the line – Subsection <ref>). The quadratic rate in the pathwise dynamics

    |𝐗_m^N ⊤(t) A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)| ℙ⟹ 0

concentrates on the line (i.e., at each time t) in probability exponentially fast. To prove this step, it is crucial to introduce and prove the result for an auxiliary process (𝐗^N(t)) that is coupled with the original one (𝐗^N(t)), which is done in Subsection <ref>.

ii) (Tightness – Subsection <ref>). Since, for each time t, the quadratic rate converges exponentially fast, then it is tight via Theorem <ref> – note that simply convergence on the line does not imply tightness <cit.>.

iii) (Martingale converges to zero in probability – Subsection <ref>). We show that

    ||M_k^N(t)||_sup[0,T]ℙ⟶ 0,

for every k∈𝒳, where ||·||_sup[0,T] is the sup-norm on the space of sample paths over the interval [0,T].

iii) (Weak convergence – Section <ref>). Relying on points i), ii) and iii), and by a standard evocation of the Skorokhod Representation Theorem <cit.>, one can show weak convergence of the empirical process (𝐘^N(t)) to the solution of an ODE over each compact interval [0,T].

In what follows, we refer to the process

    R^N_mℓ(t):=𝐗_m^N ⊤(t) A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)

as the gap process.




§ WEAK CONVERGENCE OF THE GAP PROCESS








In this section, we prove the following concentration in probability for the gap process (refer to Theorem <ref> for its formal statement)

    ||𝐗_m^N ⊤(t) A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)||_sup[0,T]ℙ⟹ 0




where Y_k^N(t) is the fraction of nodes at the state k∈𝒳 at time t∈[0,T]. In other words, the gap process is tight and this will be crucial to establish weak convergence of the macroscopic process (𝐘^N(t)). To prove such tightness result, we first establish it on the line for an auxiliary process that is coupled to our original microscopic process 𝐗^N(t).
























 §.§ Conditional Large Deviation on the Line for an Auxiliary Process


Let (𝐗_m^N(t))=(X_1m^N(t),…,X_Nm^N(t)) be defined as follows: whenever there is an interaction at t-, and assuming we have α_m N nodes at state m just after that interaction, the coordinates X_im^N(t) are updated by the realization of N i.i.d. Bernoulli random variables (conditioned on 𝐘^N(t)) with conditional-law

    ℙ(X_im^N(t)=1|Y_m^N(t_-)=α_m.)=α_m.


Remark. One can partition the set of edges E^N comprising A^N into sets of independent edges E^N=⋃_k E^N_k (a.k.a., matchings <cit.>), i.e., edges that do not share nodes in common. In other words,

    i_1 i_2, i_3 i_4 ∈ E^N_k ⇒ i_m≠ i_nm≠ n, m,n∈{1,2,3,4},

and note from the definition of 𝐗_m^N(t) that X_i_1m(t)X_i_2m(t) and X_i_3m(t)X_i_4m(t) are independent (given 𝐘^N(t)) if i_1 i_2, i_3 i_4 ∈ E_k for some k. A matching that pairs all nodes is called a perfect matching. It is a rather simple to prove and well-known fact that the set of edges of a d^N-regular bipartite graph admits a partition into d^N perfect matchings of size N (number of nodes), e.g., refer to <cit.>.

The following lemma follows from a Bernstein concentration inequality <cit.> for independent random variables (refer to Corollary <ref> in the Appendix). For simplicity, in what follows, we denote α_mℓ:=α_mα_ℓ. Let [α] round α>0 so that [α N]∈ℕ is the closest integer (from above) to α N.


Let t∈[0,T] be fixed. For any ϵ>0, there is N_0,k>0 so that

    ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d [α_mℓ]|>ϵ|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)≤ 2e^-kN,

for all N>N_0, where k does not depend on α_mℓ (this latter information is relevant for Theorem <ref> and follows from Corollary <ref> in the Appendix).



As discussed in the Subsection <ref>, without loss of generality, we assume that A^N is a regular bipartite network with degree d^N. One can thus partition the quadratic term 𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t) into d^N sums of N independent terms

    𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)= ∑_i_1 j_1∈ E_1X^N_i_1 mX^N_j_1 ℓ +… + ∑_i_d j_d ∈ E_dX^N_i_dmX^N_j_dℓ

where each sum runs over a perfect matching and comprises N independent terms (as remarked before), where each term has mean α_mℓ. Thus,

    ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N [α_mℓ]|>ϵ|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)    ≤   
    ℙ(|∑_i_1 j_1∈ E_1X^N_i_1 mX^N_j_1 ℓ +… + ∑_i_d j_d ∈ E_dX^N_i_dmX^N_j_dℓ/N-d^N [α_mℓ]|>ϵ|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)    ≤   
    ℙ(|∑_i_1 j_1X^N_i_1 mX^N_j_1 ℓ/N-[α_mℓ]| +… + |∑_i_d j_dX^N_i_d mX^N_j_d ℓ/N-[α_mℓ]|>ϵ|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)    ≤   
    ℙ(|∑_i_1 j_1X^N_i_1 mX^N_j_1 ℓ/N-[α_mℓ]|>ϵ/d^N|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)+…      
    
    +… + ℙ(|∑_i_d j_dX^N_i_d mX^N_j_d ℓ/N-[α_mℓ]|>ϵ/d^N|Y_m^N(t_-)=[α_m],Y_ℓ^N(t_-)=[α_ℓ].)    ≤   
    
    2d^N e^-kN

for N large enough, where k is a function of the degree d^N and ϵ, but it does not depend on α_mℓ (refer also to Corollary <ref> in the Appendix); and the last inequality follows from the Bernstein concentration inequality.




 §.§ Large Deviations on the Line for the Gap Process


Now, we observe that the main process (𝐗^N(t)) can be obtained (in distribution) from (𝐗^N(t)) as follows: for any m∈𝒳

  
  * if 1^⊤𝐗_m^N(t) > 1^⊤𝐗_m^N(t), then choose randomly 1^⊤𝐗_m^N(t)-1^⊤𝐗_m^N(t) of the 1's of (𝐗_m^N(t)) to flip to zero and declare the new vector as 𝐙_m^N(t);
  
  * if 1^⊤𝐗_m^N(t) < 1^⊤𝐗_m^N(t), then choose randomly 1^⊤𝐗_m^N(t)- 1^⊤𝐗_m^N(t) of the zero's of (𝐗_m^N(t)) to flip to one and declare the new vector as 𝐙_m^N(t);
  
  * if 1^⊤𝐗_m^N(t) = 1^⊤𝐗_m^N(t), then set 𝐙_m^N(t)=𝐗_m^N(t).

Clearly, 𝐙^N(t)d=𝐗^N(t) and the above construction couples both processes 𝐗^N(t) and 𝐗^N(t) as we can write

    𝐗_m^N(t)+𝐄_m^N(t)d=𝐗_m^N(t)

where the vector 𝐄_m^N(t)∈{-1,0,1}^N flips the appropriate entries of the vector 𝐗_m^N(t), and the above equality holds in distribution for each m∈{1,…,K}. We have the theorem.


The following holds

    ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N|> ϵ|𝐘^N(t_-).)≤ 2e^-kN.

where k does not depend on 𝐘^N(t).




We get successively

    ℙ(|𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)/N-𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)/N|> ϵ|𝐘^N(t_-)=α.)     = 
       ℙ(|(𝐗_m^N ⊤(t)+𝐄_m^N(t))^⊤A (𝐗_ℓ^N ⊤(t)+𝐄_ℓ^N(t))/N-𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)/N|> ϵ|𝐘^N(t_-)=α.)     =
       ℙ(|𝐄_m^N ⊤(t)A 𝐗_ℓ^N(t)/N+𝐗_m^N ⊤(t)A 𝐄_ℓ^N(t)/N+𝐄_m^N ⊤(t)A 𝐄_ℓ^N(t)/N|> ϵ|𝐘^N(t_-)=α.)    ≤
       ℙ(|𝐄_m^N ⊤(t)A 𝐗_ℓ^N(t)/N| >ϵ/3|𝐘^N(t-)=α.)+ℙ(|𝐗_m^N ⊤(t)A 𝐄_ℓ^N(t)/N| >ϵ/3|𝐘^N(t_-)=α.)    
        + ℙ(|𝐄_m^N ⊤(t)A 𝐄_ℓ^N(t)/N| >ϵ/3|𝐘^N(t_-)=α.)    ≤
       ℙ(d^N |𝐄_m^N ⊤(t)1/N| >ϵ/3|𝐘^N(t_-)=α.)+ℙ(d^N |1^⊤𝐄_ℓ^N(t)/N| >ϵ/3|𝐘^N(t_-)=α.)    
        + ℙ(d^N |𝐄_m^N ⊤(t)1/N| >ϵ/3|𝐘^N(t_-)=α.).

Each term on the right hand side of the last inequality can be bounded as follows

    ℙ(d^N|𝐄_i^N ⊤(t)1/N|> ϵ/3|𝐘^N(t_-)=α.)     =
       ℙ(|1^⊤(𝐗_i^N(t)-𝐗_i^N(t))/N|> ϵ/3 d^N|𝐘^N(t_-)=α.)     =
       ℙ(|(1^⊤𝐗_i^N(t)- α_i N)/N|> ϵ/3 d^N|𝐘^N(t_-)=α.)     =
       ℙ(|(1^⊤𝐗_i^N(t) )/N-α_i|> ϵ/3 d^N|𝐘^N(t_-)=α.)    ≤
        2 e^-kN

for any α, where k does not depend on α. And the theorem follows.


The next theorem follows as corollary to Lemma <ref> and Theorem <ref>.


We have

    ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)|>ϵ)≤ M e^-kN,

for all t≥ 0, and some M>0.




    ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)|>ϵ)     = 
        E[ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)|>ϵ| 𝐘^N (t_-) .)]     =
        E[ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)-𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N+𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)|>ϵ| 𝐘^N(t_-) .)]    ≤
        E[ℙ(|𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)-𝐗_m^N ⊤(t)A 𝐗_ℓ^N(t)/N|>ϵ| 𝐘^N(t_-) .)]    
        +E[ℙ(|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t)Y_ℓ^N(t)|>ϵ| 𝐘^N(t_-) .)]    ≤
        M e^-kN,

where the last inequality follows from Lemma <ref>, Theorem <ref>, and the fact that k does not depend on (𝐘^N(t_-)).






















 §.§ Tightness of the Gap Process


The following theorem is crucial to what follows

Let M^Nd∼𝒩_N(0,1) be a Poisson random variable with parameter N. Let (Z^N_i)_i=1^∞ be a sequence of independent (and independent of M^N) Bernoulli random variables with law

    ℙ(Z^N_i=1)=1/N^α,

for all i∈ℕ, with α>1. Then,

    ∑_i=0^M^N Z^N_iℙ⟶ 0,

or equivalently,

    ℙ(∑_i=0^M^N Z^N_i≥ 1)⟶ 0.

as N goes to infinite.

The idea behind this theorem is that Z^N_i will play the role of the indicator of an ϵ-deviation in our gap process

    (R^N_mℓ(t))=(𝐗_m^N(t)A^N𝐗_ℓ^N(t)/N-Y_m^N(t)Y_ℓ^N(t)).

Thus, the theorem states that the probability that there will be at least one ϵ-deviation during the whole time interval [0,T] (i.e., across all shuffles in [0,T]) decreases to zero as N grows large (as stated formally in Theorem <ref>).


First note that

    ℙ(.∑_i=0^M^N Z^N_i≥ 1|M^N)     =     1-ℙ(.∑_i=0^M^N Z^N_i = 0|M^N)= 1-ℙ(.Z^N_i = 0  ∀i≤ M^N|M^N)
        =     1-(1-1/N^α)^M^N = 1-((1-1/N^α)^N^α)^M^N/N^α
        =     1-e(N)^M^N/N^α,

where we defined

    e(N):=(1-1/N^α)^N^α.

Now,

    ℙ(∑_i=0^M^N Z^N_i≥ 1)= E[ℙ(.∑_i=0^M^N Z^N_i≥ 1|M^N)]=
    ∑_k≥ 0(1-e(N)^k/N^α) N^k e^-N/k!.

We have that

    e^-N∑_k(1-e(N)^k/N^α) N^k/k!    =     e^-N(∑_kN^k/k! - ∑_ke(N)^k/N^αN^k/k!)
        =     1-e^-N∑_ke(N)^k/N^αN^k/k!=1-e^-N× e^e(N)^1/N^αN
        =     1-e^-N× e^(1-1/N^α)N
        =     1- e^-N/N^α
       N→∞⟶    0,

for any α>1.


The next theorem is the main result of this section.


We have

    lim_N→∞ℙ(sup_t∈[0,T]|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t) Y_ℓ^N(t)|>ϵ)=0,

for any ϵ>0.



Let M^N ∼𝒩_d^N N(0,T) be a Poisson random variable with parameter d^N N and let M^N count the number of interactions (i.e., a state change happens) across the time interval [0,T]. Set

    Z^N(t):=1_{|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t) Y_ℓ^N(t)|>ϵ}(t)

to be the indicator of an ϵ-deviation in the gap process. Now, note that under an appropriate coupling

    M^N:=[0,T] ≤_a.s. M^N d∼𝒩_λ(N)(0,T)

where λ(N)=d^N N, and d^N is the degree of the network A^N. In particular, the intensity λ of the Poisson upper-bounding the number of shuffles on the interval increases linearly with N. It follows that

    ℙ(sup_t∈[0,T]|𝐗_m^N ⊤(t)A^N 𝐗_ℓ^N(t)/N-d^N Y_m^N(t) Y_ℓ^N(t)|>ϵ)     =    ℙ(∑_i=1^M^NZ^N(t_i)≥ 1) 
       ≤   ℙ(∑_i=0^M^N Z^N_i≥ 1) N→∞⟶ 0

where the last inequality follows from Theorem <ref> and the large deviation on the line, Theorem <ref>.




























 §.§ Martingale Converges in Probability to Zero


In this subsection, we prove the following theorem.

For any ϵ>0, the following holds

    ℙ(sup_[0,T]|M_k^N(t)|>ϵ)N→∞⟶ 0

for each k∈𝒳 and T≥ 0.



We prove that for each T≥ 0, we have

    E(M_k^N(T))^2 N→∞⟶ 0,

that is, the martingale vanishes in ℒ^2 on the line. The theorem will follow as corollary to Doob's inequality, i.e.,

    P(sup_0≤ t≤ T|M_k^N(t)|>ϵ)≤ E(M_k^N(T))^2/ϵ^2N→∞⟶ 0,   ∀ϵ>0,   ∀ T≥0.

For each k∈𝒳, the martingale is given by

    M^N_k(t)=∑_mℓ∈𝒳^2∑_n=0^d^N N∫_0^t c_mℓ(k) 1_{X_m^N⊤(s_-)A^N X_ℓ^N(s_-)=n }(𝒩^(m,ℓ,n)_γ_mℓn(ds)-γ_mℓ n  ds)

where {𝒩^(m,ℓ,n)_γ_mℓn}_(m,ℓ,n) is a family of pair-wise independent Poisson processes indexed by the triple (m,ℓ,n) and each with mean or parameter γ_mℓn.
We have

    E(M_k^N(T))^2   =    E(∑_mℓ∈𝒳^2∑_n∫_0^T c_mℓ(k) 1_{X_m^N⊤(s_-)A^N X_ℓ^N(s_-)=n }(𝒩^(m,ℓ,n)_γ_mℓn(ds)-γ_mℓ n  ds))^2
       =   ∑_mℓ∈𝒳^2∑_n E(∫_0^T c_mℓ(k) 1_{X_m^N⊤(s_-)A^N X_ℓ^N(s_-)=n }(𝒩^(m,ℓ,n)_γ_mℓn(ds)-γ_mℓ n  ds))^2
       =   ∑_mℓ∈𝒳^2∑_n E(∫_0^T c^2_mℓ(k) 1_{X_m^N⊤(s_-)A^N X_ℓ^N(s_-)=n }γ_mℓ n ds)
       ≤   ∑_mℓ∈𝒳^2 E(∫_0^T∑_n1_{X_m^N⊤(s_-)A^N X_ℓ^N(s_-)=n } 4 γ d^N N ds)
       ≤    4 K^2 γ d^N N T,

where γ:=max_mℓγ_mℓ; the second equality (<ref>) follows from Theorem <ref> and the independence of all the underlying Poisson processes involved (hence, the cross terms in the square are zero-mean martingales). The third equality (<ref>) is due to the Itô isometry Theorem (refer to <cit.> or <cit.>) and the fact that the quadratic variation of a compensated Poisson martingale is given by

    ⟨𝒩_γ(t)-γ t ⟩=γ t.

The first inequality (<ref>) is due to

    c^2_mℓ(k)≤ 4;    n≤  d^N N = 2 ×#.

The last inequality (<ref>) holds since the family of subsets of the interval [0,T]

    I_n(ω):={s∈[0,T] :  X_m^N⊤(ω,s_-)A^N X_ℓ^N(ω,s_-)=n},

for each fixed pair (m,ℓ), indexed by n, are realization-wise disjoint and thus for each pair (m,ℓ)

    ∑_n 1_{X_m^N⊤(ω,s_-)A^N X_ℓ^N(ω,s_-)=n}=
     1_⋃_n{X_m^N⊤(ω,s_-)A^N X_ℓ^N(ω,s_-)=n}≤ 1_[0,T](ω,s_-).

for all ω∈Ω.

Therefore, for the normalized martingale, we have for all fixed T

    E(M_k^N(T))^2=1/N^2 E(M_k^N(T))^2≤4K^2 γ d^N T/N⟶ 0.

and the result now follows from Doob's inequality (<ref>).




§ WEAK CONVERGENCE OF THE MACROPROCESS














The stochastic dynamical system for the macroscopics (<ref>) can be rewritten as follows

    Y_k^N(t)     =    Y_k^N(0)+M_k^N(t) + d^N∫_0^t ∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) Y_m^N(s_-)Y_ℓ^N(s_-) ds
            + ∫_0^t ∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) (𝐗_m^N ⊤(s_-) A^N𝐗_ℓ^N(s_-)- d^N Y_m^N(s_-)Y_ℓ^N(s_-))ds.

for each k∈𝒳. The next theorem follows from the equicontinuity condition in the Arzelà-Ascoli Theorem (refer to Theorem <ref> in the Appendix).


The sequence of macro-processes (𝐘^N(t))=(Y_1^N(t),…,Y_K^N(t)) is C-tight, i.e., its set of weak-accumulation points is nonempty and lie almost surely in C_[0,T], that is,

    {(𝐘^N_k(t))⇒(𝐘(t))}⇒ℙ((𝐘(t))∈ C_[0,T])=1.




We show that (𝐘^N(t)) fulfills the bound and equicontinuity conditions in equations (<ref>)-(<ref>) in the Arzelà-Ascoli Theorem, Theorem <ref>.
Indeed, we have

    ℙ(sup_0≤ t≤ TY_m^N(t)≥ k)=0, ∀ k>1,

and the first condition holds since 0 ≤Y_m^N(t)≤ 1 almost surely for all t∈[0,T] and m∈𝒳 (as referred in the end of Subsection <ref>).

For the equicontinuity condition, for every k∈𝒳, we have

    ω(Y_k^N, δ, T)   =   sup_|u-v|≤δ, u,v∈[0,T]{|Y_k^N(u)-Y_k^N(v)|}
       =   sup_|u-v|≤δ, u,v∈[0,T]{|M_k^N(u)-M_k^N(v)..
          ..+d^N∫_u^v∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) Y_m^N(s_-)Y_ℓ^N(s_-) ds..
           +..∫_u^v ∑_mℓ∈𝒳^2γ_mℓ c_mℓ(k) (𝐗_m^N ⊤(s_-)A^N𝐗_ℓ^N(s_-)/N-d^N Y_m^N(s_-)Y_ℓ^N(s_-)) ds|}
       ≤   sup_0≤ t≤ T|M_k^N(t)|+γ^(k) d^N δ+γ^(k)δsup_0≤ t≤ T|R_mℓ^N(t)|
       =:   ω_2(Y_k^N,δ,T),












where we defined γ^(k):=∑_mℓ∈𝒳^2γ_mℓ|c_mℓ(k)|. Now, for any ϵ>0, we have

    ℙ(ω(Y_i^N,δ,T)≥ϵ)≤ℙ(ω_2(Y_i^N,δ,T)≥ϵ).





Moreover,

    ℙ(ω_2(Y_k^N,δ,T)≥ϵ)    ≤   ℙ(sup_0≤ t≤ T|M_k^N(t)|>ϵ/3)+ℙ(γ^(k) d^N δ >ϵ/3)
           +ℙ(γ^(k)δsup_0≤ t≤ T|R_mℓ^N(t)| >ϵ/3).

By applying the lim sup_N on both sides of the inequality (<ref>)-(<ref>), we obtain

    lim sup_N→∞ℙ(ω_2(Y_k^N,δ,T)≥ϵ)≤ℙ(γ d δ >ϵ/3),

from Theorem <ref>, the martingale convergence Theorem <ref>, and the assumption d^NN→∞⟶ d. Therefore, we can apply lim_δ→ 0 to equation (<ref>)

    lim_δ→ 0lim sup_N→∞ℙ(ω_2(Y^N,δ,T)≥ϵ)≤lim_δ→ 0ℙ(γ d δ>ϵ/3)=0,

and thus,

    lim_δ→ 0lim sup_N→∞ℙ(ω(Y_k^N,δ,T)≥ϵ)≤lim_δ→ 0lim sup_N→∞ℙ(ω_2(Y_k^N,δ,T)≥ϵ)=0.



We conclude that (𝐘^N(t)) is a tight family with almost surely continuous weak-accumulation points,

    (𝐘^N_n(t))n→∞⇒(𝐘(t))

with

    ℙ((𝐘(t))∈ C_[0,T])=1.




Let 𝐘^N(0)⇒𝐘(0). Any weak accumulation process (𝐘(t)) of (𝐘^N(t)) obeys the integral equation

    Y_k(ω,t)=Y_k(ω,0)+d ∑_mℓ∈𝒳^2∫_0^tγ_mℓ c_mℓ(k) Y_m(ω,s)Y_ℓ(ω,s)ds,

for k∈𝒳 and almost all ω∈Ω.



Define the functional

    ℱ_k : D^K× K_[0,T]× D^K_[0,T]⟶ℝ

with

    ℱ_k((𝐫(t),𝐲(t)))     :=     y_k(t)-y_k(0)+d ∑_mℓ∈𝒳^2∫_0^tγ_mℓ c_mℓ(k) y_m(s) y_ℓ(s)ds
           +∑_mℓ∈𝒳^2∫_0^tγ_mℓ c_mℓ(k) r_mℓ(s)ds.

where D^K_[0,T] stands for the space of càdlàg sample paths from the interval [0,T] to the cube [0,1]^K endowed with the Skorokhod metric (it is a Polish space, refer to <cit.>). The functional ℱ_k is measurable: indeed, the sum `+' operator is measurable (with respect to the product topology D_[0,T]× D_[0,T]); the integral operator `(∫_0^t (·)ds)' is measurable; and composition of measurable operators is measurable (for these observations, refer to <cit.>).

Let (𝐘^N_n(t))⇒(𝐘(t)) and remark from Theorem <ref> that (𝐑^N_n(t))⇒0. We now prove that

    ℱ_k(𝐑^N_n(t),𝐘^N_n(t))⇒ℱ_k(0,𝐘(t)).

From the Skorokhod's Representation Theorem <cit.>,

    [                  ∃(𝐘^n(t)), (𝐑^n(t)), (𝐘(t)) :   (𝐘^n(t))d= (𝐘^N_n(t)), (𝐑^n(t))d= (𝐑^N_n(t));                                                                                (𝐘(t))d=(𝐘(t));                                                (𝐘^n(ω,t))U[0,T]⟶(𝐘(ω,t)), (𝐑^n(ω,t))U[0,T]⟶0. ]

for almost all ω∈Ω, where U[0,T] stands for uniform convergence in the interval [0,T]. Since,

    (𝐘^n(ω,t))⟶(𝐘(ω,t))

a.s. uniformly over the compact interval [0,T], we can interchange the limit with the integral via the Dominated Convergence Theorem (e.g., <cit.>),

    ∫_0^tY_m^n(ω,s)Y_ℓ^n(ω,s)ds    ⟶   ∫_0^t Y_m(ω,s) Y_ℓ(ω,s) ds
    ∫_0^tR_mℓ^n(ω,s) ds    ⟶    0.

Therefore,

    ℱ_k(𝐑^N_n(t),𝐘^N_n(t))d= ℱ_k(𝐑^n(t),𝐘^n(t))⟶ℱ_k(0,𝐘(t))d= ℱ_k(0,𝐘(t))

where the first and last equality are due to the measurability of ℱ_k; and the convergence `⟶' is in a realization-wise sense with respect to the uniform topology on the space of sample paths. In particular, this implies convergence in probability, and thus, convergence (<ref>) holds in a weak sense (refer to Corollary 1.6 from <cit.>), i.e.,

    ℱ_k(𝐑^N_n(t),𝐘^N_n(t))⇒ℱ_k(0,𝐘(t)).

Remark that (𝐘^N(t)) obeys the following stochastic dynamics

    ℱ_k(𝐑^N(ω,t),𝐘^N(ω,t))=M_k^N(ω,t),

and since

    (𝐌^N(t))⇒ 0

we have

    ℱ_k(0,𝐘(ω,t))d= 0,

or in other words,

    Y_k(ω,t)=Y_k(ω,0)+d ∑_mℓ∈𝒳^2∫_0^tγ_mℓ c_mℓ(k) Y_m(ω,s)Y_ℓ(ω,s)ds,

for almost all ω∈Ω.








Now, from the uniqueness of the integral equation (the vector field is Lipschitz) we conclude uniqueness of the accumulation point and the following result follows.


Let 𝐘^N(0)⇒𝐲(0). We have

    (𝐘^N(t))⇒(𝐲(t))=(y_1(t),…,y_k(t))

where (𝐲(t)) is the solution to the ODE

    ẏ_k(t) = d   𝐲(t)^⊤(Γ⊙ C(k)) 𝐲(t)k={1,2,…,K}

with initial condition 𝐲(0), Γ=[γ_mℓ]_mℓ, C(k)=[c_mℓ(k)]_mℓ and ⊙ is the pointwise Hadamard product.



Since the vector field is Lipschitz, the continuous (and thus, differentiable) solution (𝐘(t)) of (<ref>) is unique. Thus, any weak limit of (𝐘^N(t)) with initial condition given by 𝐘^N(0) and converging in distribution to 𝐘(0) is equal to the unique solution (𝐘(t)) of (<ref>) with initial condition (𝐘(0)). Therefore, by Prokhorov's Theorem <cit.>, the whole sequence converges

    (𝐘^N(t))⇒(𝐘(t))

to the solution of (<ref>). Equation (<ref>) is the integral version of the ODE (<ref>).


Fig. <ref> depicts a numerical simulation illustrating the concentration result proved for the case of a binary state {0,1} contact process, where A^N was assumed to be a cycle network (i.e., d^N=2) for all N=100,1000,4000. We observe that as the number of nodes increase, the stochastic dynamics (captured by the blue noisy curves) concentrates about the solution to the limiting ODE (captured by the red smooth curves).




§ CONCLUDING REMARKS


Deriving the exact macroscopic dynamical laws from the microscopic laws of interacting particle systems is challenging when outside the scope of: uncoupled systems (a.k.a., ideal gases), full network of contacts, or network of communities. Within such frameworks, low-resolution macroscopic state variables, such as the fraction of nodes at a particular state, realize the system.

In this paper, we proved that under a time-varying random rewiring dynamics of the sparse network of contacts (described in Subsection <ref>), the non-Markov macro-state variables associated with the fraction of nodes at each state k realize the system asymptotically in N. That is, one can obtain the exact fluid limit macroscopic dynamics associated with general FMIE interacting particle systems. To establish such result, one has to primarily prove the tightness and finite-dimensional distribution convergence of built-in rate processes (e.g., the gap process converges to zero on the line) of the macroscopic process (e.g., the fraction of nodes at a particular state). The main difficulty in establishing such result for interacting particle systems over networks – or general systems whose rules are set at the microscopics and respect the peer-to-peer disposition of nodes – is that the pre-limit macroscopic processes are non-Markov (unless the underlying network of contacts is complete or it is a network of communities), and one of two steps is often hard: i) tightness of the rates; ii) convergence on the line of the rates. By introducing an intermediate process (𝐗^N(t)), appropriately coupled with the original process (𝐗^N(t)), we were able to address both steps mentioned above. A natural future direction is to characterize more general classes of dynamical networks for which such exact concentration results are attainable.



 

The next theorem provides with an important concentration inequality <cit.>.

Let (Z_i) be a sequence of zero-mean independent random variables bounded by some constant c>0, i.e., |Z_i|≤ c a.s. for all i. Let

    σ^2(N)= 1/N∑_i=1^N Var(Z_i)

be the sample mean variance. Then, for any ϵ>0,

    ℙ(1/N∑_i=1^N Z_i≥ϵ)≤ e^-Nϵ^2/2σ(N)^2+2 c ϵ/3


We restate the previous theorem into a more useful corollary, as follows.

Under the same assumptions as in Theorem <ref>, we have

    ℙ(|1/N∑_i=1^N Z_i |≥ϵ)≤ 2 e^-Nϵ^2/2σ(N)^2+2 c ϵ/3




Note that

    ℙ(-1/N∑_i=1^N Z_i≤ -ϵ)≤ e^-Nϵ^2/2σ(N)^2+2 c ϵ/3

and by symmetry in the assumptions of the theorem – namely, if (Z_i)_i fulfills the conditions, then (-Z_i)_i fulfills as well – we have

    ℙ(1/N∑_i=1^N Z_i≤ -ϵ)≤ e^-Nϵ^2/2σ(N)^2+2 c ϵ/3

and therefore,

    ℙ(|1/N∑_i=1^N Z_i| ≥ϵ)     =    ℙ({1/N∑_i=1^N Z_i ≥ϵ}∪{1/N∑_i=1^N Z_i≤ -ϵ})
       ≤   ℙ({1/N∑_i=1^N Z_i ≥ϵ}) + ℙ( {1/N∑_i=1^N Z_i≤ -ϵ})
       ≤    2 e^-Nϵ^2/2σ(N)^2+2 c ϵ/3




If in addition to the assumptions in Theorem <ref>, we have bounded variance, i.e.,

    Var(Z_i)≤ v,  ∀i∈ℕ

for some v>0, then

    ℙ(|1/N∑_i=1^N Z_i |≥ϵ)≤ 2 e^-kN

with

    k=-ϵ^2/2v^2+2 c ϵ/3.




Let (Z^N(t)) be a sequence of càdlàg processes. Then, the sequence of probability measures ℙ_Z^N induced on D_[0,T] by (Z^N(t)) is tight and any weak limit point of this sequence is concentrated on the subset of continuous functions C_[0,T]⊂ D_[0,T] if and only if the following two conditions hold for each ϵ>0:

    lim_k→∞lim sup_N→∞ℙ(sup_0≤ t≤ T|Z^N(t)|≥ k)    =    0
    lim_δ→ 0lim sup_N→∞ℙ(ω(Z^N,δ,T)≥ϵ)   =    0

where we defined the modulus of continuity

    ω(x, δ, T)=sup{|x(u)-x(v)| : 0≤ u,v≤ T, |u-v|≤δ}.




Let (𝐘(t)) be an (ℱ_t)-adapted càdlàg process with discrete range and piecewise constant (i.e., constant when it does not jump). Let 𝒩_λ(t) and 𝒩_μ(t) be two independent (ℱ_t)-adapted Poisson processes (hence their compensated versions are (ℱ_t)-martingales, as it is trivial to establish). Assume the rates λ,μ are nonnegative. Let f, g be two bounded functions defined over the discrete range of 𝐘(t). Then,

    (∫_0^t f(𝐘(s-))(𝒩_λ(ds)-λ ds) ∫_0^t g(𝐘(s-))(𝒩_μ(ds)-μ ds))

is an (ℱ_t)-martingale.





IEEEtran


