Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation

Abstract

Our object of study is the asymptotic growth of heaviest paths in a charged (weighted with signed weights) complete directed acyclic graph. Edge charges are i.i.d. random variables with common distribution $F$ supported on $[-\infty ,1]$ with essential supremum equal to $1$ (a charge of $-\infty$ is understood as the absence of an edge). The asymptotic growth rate is a constant that we denote by $C(F)$. Even in the simplest case where $F=p{\delta }_1+(1-p){\delta }_{-\infty }$, corresponding to the longest path in the Barak-Erdős random graph, there is no closed-form expression for this function, but good bounds do exist. In this paper we construct a Markovian particle system that we call "Max Growth System" (MGS), and show how it is related to the charged random graph. The MGS is a generalization of the Infinite Bin Model that has been the object of study of a number of papers. We then identify a random functional of the process that admits a stationary version and whose expectation equals the unknown constant $C(F)$. Furthermore, we construct an effective perfect simulation algorithm for this functional which produces samples from the random functional.

arXiv comment17 pages, 3 figures. Final accepted version

References in corpus (7)

• Processes with Long Memory: Regenerative Construction and Perfect Simulation
• RSK in last passage percolation: a unified approach
• Coupling any number of balls in the infinite-bin model
• Limiting properties of random graph models with vertex and edge weights
• Barak-Erdős graphs and the infinite-bin model
• Two-sided infinite-bin models and analyticity for Barak-Erdős graphs
• On Limit Constants in Last Passage Percolation in Transitive Tournaments

Cited by in corpus (2)

• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models
• Freezing in the Infinite-Bin Model