Weighted dependency graphs

DOI10.1214/18-EJP222zbMATH Open1414.60014arXiv1605.03836OpenAlexW2962821232MaRDI QIDQ1990226FDOQ1990226

Authors: Valentin Féray 

Publication date: 25 October 2018

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: The theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. In this article, we introduce a more general notion of weighted dependency graphs and give normality criteria in this context. We also provide generic tools to prove that some weighted graph is a weighted dependency graph for a given family of random variables. To illustrate the power of the theory, we give applications to the following objects: uniform random pair partitions, the random graph model $G(n,M)$, uniform random permutations, the symmetric simple exclusion process and multilinear statistics on Markov chains. The application to random permutations gives a bivariate extension of a functional central limit theorem of Janson and Barbour. On Markov chains, we answer positively an open question of Bourdon and Vall'ee on the asymptotic normality of subword counts in random texts generated by a Markovian source.

Full work available at URL: https://arxiv.org/abs/1605.03836

Recommendations

• Weighted dependency graphs and the Ising model
• Central limit theorems for patterns in multiset permutations and set partitions
• Normal approximation for generalized \(U\)-statistics and weighted random graphs
• On normal approximations of distributions in terms of dependency graphs
• Central limit type theorems in the generalized random graphs with random vertex weights

zbMATH Keywords

spanning treesMarkov chainsrandom graphscumulantsrandom permutationsdependency graphssimple exclusion processcombinatorial central limit theorems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Classical dynamic and nonequilibrium statistical mechanics (general) (82C05)

Cites Work

• Random Geometric Graphs
• A Combinatorial Central Limit Theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to algorithms.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic theory of statistics and probability
• On the Markov chain central limit theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs
• Two moments suffice for Poisson approximations: The Chen-Stein method
• The central limit theorem for dependent random variables
• On a Method of Calculation of Semi-Invariants
• Motif statistics.
• Gaussian limit for determinantal random point fields.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Zeros of Gaussian analytic functions and determinantal point processes
• Title not available (Why is that?)
• When are small subgraphs of a random graph normally distributed?
• Logarithmic combinatorial structures: A probabilistic approach
• Normal approximation under local dependence.
• Cumulants in noncommutative probability theory. I: Noncommutative exchangeability systems
• Exact solution of a 1D asymmetric exclusion model using a matrix formulation
• Moderate deviations via cumulants
• Crossings and nestings of matchings and partitions
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• A central limit theorem for m-dependent random variables with unbounded m
• Non-equilibrium steady states: fluctuations and large deviations of the density and of the current
• Large deviations for sums of partly dependent random variables
• Crossings and alignments of permutations
• On the relation between the multidimensional moment problem and the one-dimensional moment problem.
• On a Theorem of Janson
• Entropy of open lattice systems
• Central limit theorems for Gaussian polytopes
• Orthogonal decompositions and functional limit theorems for random graph statistics
• On central limit theorems in geometrical probability
• Asymptotic normality of statistics on permutation tableaux
• Asymptotic behavior of some statistics in Ewens random permutations
• Title not available (Why is that?)
• Error bound in a central limit theorem of double-indexed permutation statistics
• Formulae for Askey-Wilson moments and enumeration of staircase tableaux
• On normal approximations of distributions in terms of dependency graphs
• Gaussian fluctuations of characters of symmetric groups and of Young diagrams
• An estimate of the remainder in a combinatorial central limit theorem
• Central limit theorems for some set partition statistics
• On pattern frequency occurrences in a Markovian sequence
• Hidden word statistics
• A functional limit theorem for random graphs with applications to subgraph count statistics
• Terminal chords in connected chord diagrams
• Title not available (Why is that?)
• Mod-\(\Phi\) convergence. Normality zones and precise deviations
• Fluctuations in the weakly asymmetric exclusion process with open boundary conditions
• Relations between cumulants in noncommutative probability
• Pattern Matching Statistics on Correlated Sources
• A functional combinatorial central limit theorem
• On three different notions of monotone subsequences
• The Central Limit Theorem for a Sequence of Random Variables with a Slowly Growing Number of Dependences

Cited In (17)

• Beyond Dependency Graphs
• Asymptotic normality in random graphs with given vertex degrees
• A central limit theorem for descents of a Mallows permutation and its inverse
• Central limit theorems for patterns in multiset permutations and set partitions
• The method of cumulants for the normal approximation
• A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph
• Weighted dependency graphs and the Ising model
• Mod-\(\phi\) convergence. II: Estimates on the speed of convergence
• Berry-Esseen-type estimates for random variables with a sparse dependency graph
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Normal approximation for U- and V-statistics of a stationary absolutely regular sequence
• On the asymptotic normality conditions for the number of repetitions in a stationary random sequence
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Central limit theorem for statistics of subcritical configuration models
• Dependencies for Graphs
• The volume of simplices in high-dimensional Poisson-Delaunay tessellations
• Asymptotic normality of pattern counts in conjugacy classes

Uses Software

• SageMath

This page was built for publication: Weighted dependency graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990226)