Limit theorems for a random directed slab graph

DOI10.1214/11-AAP783zbMATH Open1241.05132arXiv1005.4806OpenAlexW2122690806MaRDI QIDQ417081FDOQ417081

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)

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).

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

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

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)

Cites Work

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

Cited In (14)

• Title not available (Why is that?)
• Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
• Limiting properties of random graph models with vertex and edge weights
• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models
• On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph
• 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
• Stochastic Sequences with a Regenerative Structure that May Depend Both on the Future and on the Past
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• 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)