Search for: All records

Let (kn)n∈N be a sequence of positive integers growing to infinity at a sublinear rate, kn → ∞ and kn/n → 0 as n → ∞. Given a sequence of n-dimensional random vectors {Y (n)}n∈N belonging to a certain class, which includes uniform distributions on suitably scaled ℓnp -balls or ℓnp -spheres, p ≥ 2, and product distributions with sub-Gaussian marginals, we study the large deviations behavior of the corresponding sequence of kn-dimensional orthogonal projections. For almost every sequence of projection matrices, we establish a large deviation principle (LDP) for the corresponding sequence of projections, with a fairly explicit rate function that does not depend on the sequence of projection matrices. As corollaries, we also obtain quenched LDPs for sequences of ℓ2-norms and ℓ∞-norms of the coordinates of the projections. Past work on LDPs for projections with growing dimension has mainly focused on the annealed setting, where one also averages over the random projection matrix, chosen from the Haar measure, in which case the coordinates of the projection are exchangeable. The quenched setting lacks such symmetry properties, and gives rise to significant new challenges in the setting of growing projection dimension. Along the way, we establish new Gaussian approximation results on the Stiefel manifold that may be of independent interest. Such LDPs are of relevance in asymptotic convex geometry, statistical physics and high-dimensional statistics. 

Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of N parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-of-d-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as the size of the system goes to infinity, the state dynamics converge to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when d=2, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case [Formula: see text], which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the N-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful. 

Consider an interacting particle system indexed by the vertices of a (possibly random) locally finite graph whose vertices and edges are equipped with weights or marks that represent parameters of the model, such as the environment and initial conditions. Each particle takes values in a countable state space and evolves according to a pure jump process whose jump rates depend only on its own state (or history) and marks, and states (or histories) and marks of particles and edges in its neighborhood. Under mild conditions on the jump rates, it is shown that if the sequence of (marked) interaction graphs converges in probability in the local weak sense to a limit (marked) graph that satisfies a certain finite dissociability property, then the corresponding sequence of empirical measures of the particle trajectories converges weakly to the law of the marginal dynamics at the root vertex of the limit graph. The proof of this hydrodynamic limit relies on several auxiliary results of potentially independent interest. First, such interacting particle systems are shown to be well-posed on (almost surely) finitely dissociable graphs, which include graphs with uniformly bounded maximum degrees and any Galton-Watson tree whose offspring distribution has a finite first moment. A counterexample is also provided to show that well-posedness can fail for dynamics on graphs outside this class. Next, given any sequence of graphs that converges in the local weak sense to a finitely dissociable graph, it is shown that the corresponding sequence of jump processes also converges in the same sense to a jump process on the limit graph. Finally, the dynamics are also shown to exhibit an (annealed) asymptotic correlation decay property. These results complement recent work on hydrodynamic limits of locally interacting probabilistic cellular automata and diffusions on sparse random graphs. However, the analysis of jump processes requires very different techniques, including percolation arguments and notions such as consistent spatial localization and causal chains. 

We establish a central limit theorem for the eigenvalue counting function of a matrix of real Gaussian random variables.