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

Foss, Sergey, Konstantopoulos, Takis, Mallein, Bastien and Ramassamy, Sanjay (2021) Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation. [Preprint]

Access the full-text of this item by clicking on the Open Access link.

	Text 2110.01559v1.pdf - Submitted version Download (521kB) \| Preview
	Text 2110.01559v1.pdf - Submitted version Download (521kB) \| Preview

Official URL: http://dx.doi.org/10.30757/ALEA.v20-19

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 $[-\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\H{o}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.

Item Type:	Preprint
Additional Information:	17 pages, 3 figures. Final accepted version
Uncontrolled Keywords:	math.PR, math.PR, 82M31, 60K15, 60G10, 05C80
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	07 Oct 2021 15:31
Last Modified:	05 Oct 2023 06:50
Open Access URL:	http://arxiv/
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3139622