Другие статьи


Операции с матрицами на C++.   Класс DMatrix



 

 

Limiting behavior for the distance of a random walk

(Предельное поведение расстояния при случайном блуждании)

 

Nathanael Berestycki,  Rick Durrett

 

2008

 

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

 

ЧИТАТЬ  СТАТЬЮ