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

Sergey Foss*, Takis Konstantopoulos, Bastien Mallein, Sanjay Ramassamy

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)547-560
Number of pages14
JournalALEA: Latin American Journal of Probability and Mathematical Statistics
Volume20
DOIs
Publication statusPublished - 2023

Keywords

  • coupling (from the past)
  • last passage percolation
  • Markov process
  • perfect simulation
  • random graph
  • stationarity

ASJC Scopus subject areas

  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation'. Together they form a unique fingerprint.

Cite this