Аннотация:
В классе упорядоченных направленных конечных графов мы введём пути
наибольшей длины и изучим их асимптотические свойства типа закона больших
чисел и (функциональной) центральной предельной теоремы. Мы введём
вспомогательную бесконечную урновую модель и покажем, как с её помощью эти
свойства доказываются.
Кроме этого, мы предложим алгоритм точного моделирования (perfect simulation)
для оценивания скорости роста пути наибольшей длины.
Затем мы рассмотрим некоторые обобщения предложенной модели
(рёбра имеют случайные веса с различными распределениями, отношение полного порядка заменяется на отношение частичного порядка и т.д.).
В частном случае параметрического двухточечного семейства распределений мы обсудим занятные свойства (не)дифференцируемости по параметру.
Если время позволит, то мы также обсудим, как в этих моделях возникают пуассоновские леса, распределение Трейси–Видома и другая экзотика.
|
