Limiting behavior for the distance of a random walk
(Предельное поведение расстояния при случайном блуждании)

Nathanael Berestycki,  Rick Durrett

2008

В работе исследованы некоторые аспекты поведения случайного блуждания на больших, но конечных графах до наступления равновесного состояния. Данное исследование мотивировано нашим недавним результатом для перестановочного случайного блуждания: расстояние от точки старта совершает фазовый переход из линейного режима в сублинейный режим по прошествии времени n/2. Теперь мы рассмотрим случаи случайных 3-регулярных графов, случайных смежных перестановок и перетасовок колоды. В случае случайного 3-регулярного графа имеет место фазовый переход с изменением скорости от 1/3 до 0 за время 3*log₂n. Похожий результат доказан для перетасовок колоды, в этом случае скорость меняется от 1 до 0 за время log₂n. В обоих случаях изменение происходит, когда достигается расстояние, равное среднему диаметру графа. Однако, в случае случайных смежных перестановок поведение является более сложным. Мы пришли к выводу, что в этом случае нет фазового перехода, даже не смотря на то, что расстояние имеет различный масштаб в трех разных режимах.

Текст полностью:  здесь и здесь.