Максимальные энтропийные случайные блуждания в Z: Случайные и неслучайные окружения

Основная информация

• ID статьи: 2503.15957
• Название: Maximal Entropy Random Walks in Z: Random and non-random environments
• Авторы: Thibaut Duboux (Université Bourgogne Europe), Lucas Gerin (École Polytechnique), Yoann Offret (Université Bourgogne Europe)
• Классификация: math.CO (комбинаторика), math.PR (теория вероятностей)
• Дата подачи: 20 ноября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2503.15957

Аннотация

Максимальные энтропийные случайные блуждания (MERW) — это естественный процесс на конечных графах, введённый несколько лет назад с мотивацией из теоретической физики. Конструкция этого процесса зависит от теории Перрона-Фробениуса матрицы смежности. Обобщение на бесконечные графы весьма тонко, и в данной работе подробно изучается модель MERW на целочисленной решётке Z с петлями, охватывающая как случайные, так и неслучайные окружения. Благодаря явному комбинаторному представлению соответствующих собственных векторов Перрона-Фробениуса авторы могут точно определить асимптотическое поведение этих блуждений. В частности, доказано, что почти все MERW с петлями на Z обладают положительной скоростью.

Исследовательский контекст и мотивация

Постановка проблемы

1. Ограничения стандартного случайного блуждания: Традиционное стандартное случайное блуждание является фундаментальным случайным процессом в теории вероятностей, статистической физике и анализе сетей, с вероятностями переходов $p_{i,j} = a_{i,j}/\sum_\ell a_{i,\ell}$. Однако такое блуждание не обязательно максимизирует энтропию траектории.
2. Физическая мотивация MERW: MERW возникает из формулировки интегралов по траекториям в квантовой механике, где вероятности переходов имеют вид $p_{i,j} = a_{i,j}\psi_j/(\lambda\psi_i)$, где $\psi$ — положительный собственный вектор, соответствующий спектральному радиусу $\lambda$. Такая конструкция обеспечивает максимизацию скорости энтропии MERW на конечных графах.
3. Вызовы на бесконечных графах:
   • На бесконечных графах теория Перрона-Фробениуса не применяется непосредственно
   • Необходимо различать случаи R-возвратности и R-переходности
   • В случае R-переходности положительный собственный вектор не единственен, существует выпуклое множество экстремальных решений
4. Исследовательский пробел: Несмотря на то что MERW на конечных графах хорошо изучены, систематическое исследование бесконечных графов, особенно с случайными возмущениями, отсутствует.

Значимость исследования

1. Теоретическое значение: Связывает комбинаторную вероятность, случайные процессы и теорию андерсоновской локализации
2. Прикладная ценность: Потенциальные приложения в алгоритмах обнаружения сообществ в сложных сетях
3. Методологический вклад: Предоставляет новые инструменты для анализа MERW на бесконечных графах

Основные вклады

Основные вклады данной работы включают:

1. Явное представление собственных векторов (теорема 2.9): Для хороших окружений дано полное явное комбинаторное описание двух экстремальных собственных векторов $\psi^+$ и $\psi^-$:\beta_{-1}\cdots\beta_i, & i < 0\\ 1, & i = 0\\ (\beta_0\beta_1\cdots\beta_{i-1})^{-1}, & i > 0 \end{cases}$$ где $\beta_i$ и $\alpha_i$ выражаются через производящие функции или цепные дроби.
2. Полная характеризация детерминированных окружений (предложения 2.3, 2.5):
   • Доказано, что матрица $A$ является R-переходной
   • Точно описана монотонность и предельное поведение экстремальных собственных векторов
   • Доказано, что все MERW в хороших окружениях являются переходными
3. Линейная скорость в случайных окружениях (теорема 3.1): Для независимых одинаково распределённых случайных окружений экстремальные MERW обладают постоянной положительной скоростью: $\lim_{n\to\infty} \frac{X^+_n}{n} = v > 0 \quad \text{(почти наверное)}$ где $v = 1/\mathbb{E}_\mu[S]$, $S$ имеет явное выражение.
4. Анализ связи неэкстремальных MERW (теорема 3.4): Для MERW, соответствующих смешанным собственным векторам $\psi^{(\kappa)} = \kappa\psi^+ + (1-\kappa)\psi^-$, доказана линейная скорость $v$ при условии $X^{(\kappa)}_n \to +\infty$.
5. Точные вычисления для окружений Бернулли (предложение 3.6): Когда окружение имеет вид $P(w_k=M)=p$, доказано: $\lim_{p\to 0} v_{p,M} = \sqrt{1-\frac{4}{(2+M)^2}} > 0$ что показывает разрывность скорости при $p\to 0$.
6. Контраст с периодическими окружениями (предложение A.1): Доказано, что MERW в периодических детерминированных окружениях являются нулевозвратными и сильно локализованы, что контрастирует со случайными окружениями.

Подробное описание методов

Определение задачи

Входные данные:

• Окружение $w = (w_i)_{i\in\mathbb{Z}}$, где $w_i \geq 0$ — вес петли в вершине $i$
• Матрица смежности $A$, определённая следующим образом: рёбра между соседними вершинами имеют вес 1, петля в вершине $i$ имеет вес $w_i$

Выходные данные:

• Комбинаторный спектральный радиус $\lambda$
• Положительный $\lambda$-собственный вектор $\psi$ (удовлетворяющий $A\psi = \lambda\psi$)
• Асимптотическое поведение соответствующего MERW $(X_n)_{n\geq 0}$

Ограничения:

• Окружение является M-хорошим: ограничено, не тождественно $M$, и для любых $\varepsilon>0$ и $r\geq 0$ существует $i$ такое, что $w_i,\ldots,w_{i+r}$ все $\geq M-\varepsilon$

Архитектура основного метода

1. Вычисление комбинаторного спектрального радиуса (лемма 2.2)

Доказательство того, что $\lambda = 2+M$ через подсчёт путей:

Схема доказательства нижней границы:

• Рассмотрим число путей от $i$ к $i$, остающихся на $i$ и выше, $u^{i\circlearrowleft i}_r$
• Используем производящую функцию $H^{[\geq i],w}_{i,i}(z) = \sum_{r\geq 0} d^{0\circlearrowleft 0}_r z^r$
• Через разложение на арки (arch-decomposition) получаем: $H^{[\geq i],w}_{i,i}(z) = \frac{1}{1-(M-\varepsilon)z - z^2H^{[\geq i],w}_{i,i}(z)}$
• Решая, находим главную особенность в $z^* = (2+M-\varepsilon)^{-1}$
• Используя теорему переноса получаем $d^{0\circlearrowleft 0}_r \geq c(2+M-\varepsilon)^r r^{-3/2}$

2. Конструкция экстремальных собственных векторов (предложение 2.3)

Метод усечённого приближения:

• Для $k\leq 0$ определим $\psi^{(k,\varepsilon)}$, удовлетворяющий граничным условиям: 0, & n\leq k-2\\ \varepsilon, & n=k-1\\ 2\varepsilon, & n=k \end{cases}$$ и рекуррентному соотношению $\psi_{n+1} + w_n\psi_n + \psi_{n-1} = \lambda\psi_n$
• Подбираем $\varepsilon_k$ так, чтобы $\psi^{(k,\varepsilon_k)}_0 = 1$
• Через диагональный аргумент получаем сходящуюся подпоследовательность
• Используя оценки выпуклости доказываем $\lim_{n\to\infty}\psi^+_n = \infty$

3. Вывод комбинаторного представления (теорема 2.9)

Ключевые шаги:

Определим производящие функции: $\beta_i = \frac{1}{\lambda}H^{[\leq i],w}_{i,i}\left(\frac{1}{\lambda}\right), \quad \alpha_i = \frac{1}{\lambda}H^{[\geq i],w}_{i,i}\left(\frac{1}{\lambda}\right)$

Через разложение на арки получаем рекуррентные соотношения: $\beta_i = \frac{1}{\lambda - w_i - \beta_{i-1}}, \quad \alpha_i = \lambda - w_i - \frac{1}{\alpha_{i+1}}$

Это эквивалентно разложению в цепную дробь: $\alpha_i = \cfrac{1}{\lambda - w_i - \cfrac{1}{\lambda - w_{i+1} - \cfrac{1}{\ddots}}}$

Проверяем, что $\psi^+_i = \beta_{-1}\cdots\beta_i$ (при $i<0$) действительно удовлетворяет характеристическому уравнению.

4. Анализ скорости в случайных окружениях

Идентификация цепи Маркова:

• Когда $(w_i)$ независимы и одинаково распределены, $(\beta_i)_i$ и $(\alpha_{-i})_i$ являются стационарными эргодическими цепями Маркова
• Экстремальные MERW — это случайные блуждания в эргодическом случайном окружении

Формула скорости (уравнение 3.4): $v = \frac{1}{\mathbb{E}_\mu[S]}, \quad S = \sum_{n\geq 0} P^w_0(X^+_n = 0)$

Доказательство конечности: Используем оценку: $\beta_i \leq 1_{\{w_i\leq M-\delta\}} g_{M-\delta}(\beta_{i-1}) + 1_{\{w_i>M-\delta\}}$

получаем: $\mathbb{E}_\mu[\beta_0\beta^2_{-1}\cdots\beta^2_{-i}] \leq \mathbb{E}_\mu[Z^2_0]^i < 1$

Следовательно, $\mathbb{E}_\mu[S] < \infty$, что гарантирует положительную скорость.

Технические инновации

1. Метод производящих функций путей: Преобразование задачи о собственных векторах в задачу подсчёта путей с использованием инструментов аналитической комбинаторики.
2. Техника переменных Риккати: Рекуррентные соотношения для $\alpha_i$ и $\beta_i$ связаны с переменными Риккати в теории андерсоновской локализации, устанавливая связь между MERW и случайными операторами Шрёдингера.
3. Аргумент связи: Для неэкстремальных MERW через построение связи с экстремальными MERW и использование конечности множества "плохих времён" доказывается согласованность скоростей.
4. Граничный анализ производящих функций: Через точное управление поведением производящей функции в главной особенности получаются асимптотические оценки числа путей.

Экспериментальная установка

Параметры численного моделирования

Хотя работа в основном теоретическая, она включает численную верификацию:

1. Рисунок 1: Моделирование MERW в окружении Бернулли
   • Параметры: $M=20$, $p=0.02$ и $p=0.05$
   • 200 независимых траекторий, временные шаги $n=600$
   • Верификация того, что скорость $v_{p,M}$ убывает по $p$
2. Рисунок 3: Изменение скорости $v_{p,M}$ в зависимости от $p$
   • Моделирование Монте-Карло формулы (3.21)
   • Различные значения $M$: $M=0.1, 1, 10$
   • Верификация асимптотического поведения предложения 3.6
3. Рисунок 4: Изменение скорости $v_{p,M}$ в зависимости от $M$
   • Параметры: $p=0.3, 0.5, 0.8$
   • Показывает немонотонность скорости по $M$

Теоретическая верификация

Точные вычисления для окружений Бернулли:

• Использование комбинаторных тождеств, связанных с числами Мотцкина
• Верификация $\lim_{p\to 0} v_{p,M} = \sqrt{1-4/(2+M)^2}$
• Доказательство асимптотики $v_{p,M} \sim 3(1-p)/(2+M)$ при $p\to 1$

Результаты экспериментов

Основные результаты

1. Детерминированные окружения (раздел 2)

Верификация теоремы 2.9:

• Даны полные явные выражения для $\psi^+$ и $\psi^-$
• Граничные оценки: $\gamma \leq \alpha_i, \beta_i \leq 1$, где $\gamma = (\lambda-\sqrt{\lambda^2-4})/2$

Игрушечный пример (конец раздела 2.3): Для ступенчатого окружения ($w_i=M$ при $i\leq 0$, $w_i=0$ при $i\geq 1$):