Limit theorems for a random directed slab graph

DOI10.1214/11-AAP783MaRDI QIDQ417081zbMATH OpenOpenAlexFDO

Authors Denis E. Denisov, Sergey Foss, T. Konstantopoulos

Publication date 13 May 2012

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.4806, https://projecteuclid.org/euclid.aoap/1333372011

zbMATH Keywords

random graphfunctional central limit theorempartial orderlast passage percolationGUE

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Partial orders, general (06A06) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Functional limit theorems; invariance principles (60F17)

Abstract: We consider a stochastic directed graph on the integers whereby a directed edge between $i$ and a larger integer $j$ exists with probability $p_{j-i}$ depending solely on the distance between the two integers. Under broad conditions, we identify a regenerative structure that enables us to prove limit theorems for the maximal path length in a long chunk of the graph. The model is an extension of a special case of graphs studied by Foss and Konstantopoulos, Markov Process and Related Fields, 9, 413-468. We then consider a similar type of graph but on the `slab' $$, where $I$ is a finite partially ordered set. We extend the techniques introduced in the in the first part of the paper to obtain a central limit theorem for the longest path. When $I$ is linearly ordered, the limiting distribution can be seen to be that of the largest eigenvalue of a $|I|imes|I|$ random matrix in the Gaussian unitary ensemble (GUE).

Recommendations

• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
• Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges
• Chain Lengths in Certain Random Directed Graphs
• scientific article; zbMATH DE number 3915300
• Convergence of directed random graphs to the Poisson-weighted infinite tree

Cites work

• scientific article; zbMATH DE number 5130631 (Why is no real title available?)
• scientific article; zbMATH DE number 1193442 (Why is no real title available?)
• scientific article; zbMATH DE number 3753740 (Why is no real title available?)
• scientific article; zbMATH DE number 1195782 (Why is no real title available?)
• scientific article; zbMATH DE number 2051870 (Why is no real title available?)
• scientific article; zbMATH DE number 2174437 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A representation for non-colliding random walks
• A universality property for last-passage percolation paths close to the axis
• An introduction to random matrices
• Chain Lengths in Certain Random Directed Graphs
• Departures from many queues in series
• Ergodicity and Stability Theorems for a Class of Stochastic Equations and Their Applications
• Foundations of Modern Probability
• GUEs and queues
• Last-passage percolation with general weight distribution
• Level-spacing distributions and the Airy kernel
• Limit theorems for height fluctuations in a class of discrete space and time growth models
• Limiting shape for directed percolation models
• Linear extensions of a random partial order
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• On the distribution of the length of the longest increasing subsequence of random permutations
• Perfect simulation and backward coupling^∗
• Processes with long memory: Regenerative construction and perfect simulation
• Shape fluctuations and random matrices
• Simulating the Invariant Measures of Markov Chains Using Backward Coupling at Regeneration Times
• Speed of parallel processing for random task graphs
• Stochastically recursive sequences and their generalizations
• The arctic circle boundary and the Airy process
• Two ergodicity criteria for stochastically recursive sequences
• Universality for mathematical and physical systems

Cited in

(14)

• scientific article; zbMATH DE number 6718588 (Why is no real title available?)
• Limiting properties of random graph models with vertex and edge weights
• Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
• On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph
• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models
• On representations and simulation of conditioned random walks on integer lattices
• Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges
• Long-range last-passage percolation on the line
• Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph
• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• Stochastic Sequences with a Regenerative Structure that May Depend Both on the Future and on the Past
• Barak-Erdős graphs and the infinite-bin model
• Two-sided infinite-bin models and analyticity for Barak-Erdős graphs

This page was built for publication: Limit theorems for a random directed slab graph

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