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 -