TY - JOUR

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

AU - Foss, Sergey

AU - Konstantopoulos, Takis

AU - Mallein, Bastien

AU - Ramassamy, Sanjay

N1 - Funding Information:
Received by the editors February 13th, 2022; accepted February 1st, 2023. 2020 Mathematics Subject Classification. 82M31, 60K15, 60G10, 05C80. Key words and phrases. perfect simulation, coupling (from the past), random graph, Markov process, stationarity, last passage percolation. SF was partially supported by the RFBR collaborative grant 19-51-15001 and TK, BM and SR were partially supported by the CNRS PRC collaborative grant CNRS-193-382 with the common title “Asymptotic and analytic properties of stochastic ordered graphs and infinite bin models”.
Publisher Copyright:
© 2022 American Psychological Association

PY - 2023

Y1 - 2023

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

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

KW - coupling (from the past)

KW - last passage percolation

KW - Markov process

KW - perfect simulation

KW - random graph

KW - stationarity

UR - http://www.scopus.com/inward/record.url?scp=85153728418&partnerID=8YFLogxK

U2 - 10.30757/ALEA.V20-19

DO - 10.30757/ALEA.V20-19

M3 - Article

AN - SCOPUS:85153728418

SN - 1980-0436

VL - 20

SP - 547

EP - 560

JO - ALEA: Latin American Journal of Probability and Mathematical Statistics

JF - ALEA: Latin American Journal of Probability and Mathematical Statistics

ER -