Foss, Sergey, Konstantopoulos, Takis, Mallein, Bastien and Ramassamy, Sanjay
(2023)
Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation.
ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 20 (1).
pp. 547-560.
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 [-∞1; 1] with essential supremum equal to 1 (a charge of ∞1 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δ1 + (1 - p)δ-∞1, corresponding to the longest path in the Barak-Erdos 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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | perfect simulation, coupling (from the past), random graph, Markov process, stationarity, last passage percolation |
| Divisions: | Faculty of Science and Engineering > School of Physical Sciences |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 02 Oct 2023 14:51 |
| Last Modified: | 02 Oct 2023 14:51 |
| DOI: | 10.30757/ALEA.v20-19 |
| Open Access URL: | https://arxiv.org/abs/2110.01559 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3173308 |
Dimensions
Dimensions
