Монотонность вероятностей состояний случайного блуждания на конечных решетках

Abstract

Рассматриваются два способа упорядочить вершины графа относительно некоторой его фиксированной вершины, связанных со случайными блужданиями на нем. Первый способ – порядок вершин в соответствии с вероятностью того, что случайное блуждание фиксированной длины закончится в каждой из них. Исследуемое в этой части блуждание является «ленивым», т. е. вместо очередного шага может оставаться на месте. Выделен класс графов, для которых такой порядок совпадает со слабым порядком по геодезическим расстояниям до соответствующих вершин. Приведены примеры представителей данного класса – n-мерные решетки. Второй способ упорядочивания – резисторные расстояния до выбранной вершины. Для класса графов установлена пара вершин, между которыми достигается максимальное по всему графу резисторное расстояние. Приведены примеры представителей этого класса, включая n-мерные решетки.