Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation - Université Paris 8 Vincennes - Saint-Denis Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

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

Résumé

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.
Fichier principal
Vignette du fichier
BE_perfsim11.pdf (449.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03364751 , version 1 (04-10-2021)
hal-03364751 , version 2 (18-08-2023)

Identifiants

  • HAL Id : hal-03364751 , version 1

Citer

Sergey Foss, Takis Konstantopoulos, Bastien Mallein, Sanjay Ramassamy. Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation. 2021. ⟨hal-03364751v1⟩
75 Consultations
33 Téléchargements

Partager

Gmail Facebook X LinkedIn More