An official website of the United States government
Abstract We study the asymptotics of the point process induced by an interacting particle system with mean-field drift interaction. Under suitable assumptions, we establish propagation of chaos for this point process: It has the same weak limit as the point process induced by i.i.d. copies of the solution of a limiting McKean–Vlasov equation. This weak limit is a Poisson point process whose intensity measure is related to classical extreme value distributions. In particular, this yields the limiting distribution of the normalized upper order statistics.
more »
« less
Propagation of chaos for maxima of particle systems with mean-field drift interaction
Abstract We study the asymptotic behavior of the normalized maxima of real-valued diffusive particles with mean-field drift interaction. Our main result establishes propagation of chaos: in the large population limit, the normalized maxima behave as those arising in an i.i.d. system where each particle follows the associated McKean–Vlasov limiting dynamics. Because the maximum depends on all particles, our result does not follow from classical propagation of chaos, where convergence to an i.i.d. limit holds for any fixed number of particles but not all particles simultaneously. The proof uses a change of measure argument that depends on a delicate combinatorial analysis of the iterated stochastic integrals appearing in the chaos expansion of the Radon–Nikodym density.
more »
« less
- Award ID(s):
- 2206062
- PAR ID:
- 10425190
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Probability Theory and Related Fields
- Volume:
- 187
- Issue:
- 3-4
- ISSN:
- 0178-8051
- Format(s):
- Medium: X Size: p. 1093-1127
- Size(s):
- p. 1093-1127
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study a class of linear-quadratic stochastic differential games in which each player interacts directly only with its nearest neighbors in a given graph. We find a semiexplicit Markovian equilibrium for any transitive graph, in terms of the empirical eigenvalue distribution of the graph’s normalized Laplacian matrix. This facilitates large-population asymptotics for various graph sequences, with several sparse and dense examples discussed in detail. In particular, the mean field game is the correct limit only in the dense graph case, that is, when the degrees diverge in a suitable sense. Although equilibrium strategies are nonlocal, depending on the behavior of all players, we use a correlation decay estimate to prove a propagation of chaos result in both the dense and sparse regimes, with the sparse case owing to the large distances between typical vertices. Without assuming the graphs are transitive, we show also that the mean field game solution can be used to construct decentralized approximate equilibria on any sufficiently dense graph sequence.more » « less
-
Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2=(1011) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization. While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with G2 such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are (in our view) also much simpler and modular. Key to our proof is a notion of local polarization that only depends on the evolution of the martingale in a single time step. Our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels.more » « less
-
For normalized sums Zn of i.i.d. random variables, we explore necessary and sufficient conditions, which guarantee the normal approximation with respect to the Rényi divergence of infinite order. In terms of densities pn of Zn, this is a strengthened variant of the local limit theorem taking the form sup (pn(x)− ϕ(x))/ϕ(x)→0 as n→∞.more » « less
-
Abstract Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis and can be computed efficiently by Sinkhorn–Knopp (SK) iterations. This paper proves the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates, when $$n$$ data points are i.i.d. sampled from a general $$d$$-dimensional manifold embedded in a possibly high-dimensional space. Under certain joint limit of $$n \to \infty $$ and kernel bandwidth $$\epsilon \to 0$$, the point-wise convergence rate of the graph Laplacian operator (under 2-norm) is proved to be $$ O( n^{-1/(d/2+3)})$$ at finite large $$n$$ up to log factors, achieved at the scaling of $$\epsilon \sim n^{-1/(d/2+3)} $$. When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency which matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors among themselves and with data vectors. Motivated by our analysis, which suggests that not exact bi-stochastic normalization but an approximate one will achieve the same consistency rate, we propose an approximate and constrained matrix scaling problem that can be solved by SK iterations with early termination. Numerical experiments support our theoretical results and show the robustness of bi-stochastically normalized graph Laplacian to high-dimensional outlier noise.more » « less
