Реферат: 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] with essential supremum equal to 1 (a charge of 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) , 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.

Библиографическая ссылка: Foss S. , Konstantopoulos T. , Mallein B. , Ramassamy S.
Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
ALEA (Latin Americal Journal in Probability and Mathematical Statistics). 2023. V.20. N1. P.547. DOI: 10.30757/alea.v20-19 WOS Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	13 февр. 2022 г.
Принята к публикации:	1 февр. 2023 г.
Опубликована в печати:	1 февр. 2023 г.
Опубликована online:	1 февр. 2023 г.

Идентификаторы БД:

Web of science:	WOS:000972708200001
Scopus:	2-s2.0-85153728418
РИНЦ:	61206655
OpenAlex:	W3203048746

Цитирование в БД:

БД	Цитирований
Web of science	1
Scopus	1
OpenAlex	2

Альметрики: