Оценка асимптотической скорости роста самых тяжелых путей во взвешенном полном ориентированном ац...

Выступление (11-ого октября) Сергея Фосса в рамках онлайн семинара "Вероятность и математическая статистика". Нас интересует асимптотика роста самых тяжелых путей во взвешенном (со знакопеременными весами) полном ориентированном ациклическом графе. Веса ребер - это i.i.d. случайные величины с общим распределением F, носитель которого сосредоточен на интервале [-\infty,1] с существенным максимумом, равным 1. Здесь вес -\infty можно понимать как отсутствие ребра. Известно, что асимптотическая скорость роста - это константа, которую мы будем обозначать C(F). Даже в простейшем случае двухточечного распределения F, сосредоточенного в 1 и в -\infty (этот случай соответствует самому длинному пути в графе Барака-Эрдоша), явный вид константы C(F) неизвестен, но известны достаточно точные верхние и нижние оценки её оценки. В этом докладе мы предложим некоторую марковскую систему, которую мы называем "Max Growth System" (MGS), и поясним её связь со взвешенным случайным графом. MGS является обобщением т.н. Infinite Bin Model, которая изучалась в ряде недавних работ. Затем мы опишем случайный функционал процесса, у которого существует стационарная версия, математическое ожидание которой равно неизвестной константе C(F). Кроме того, мы предложим алгоритм т.н. точного моделирования для этого функционала. Доклад основан на совместной работе с Takis Konstantopoulos, Bastien Mallein и Sanjay Ramassami.