#import "../../utils/core.typ": *

== Случайные блуждания

#th[
  Случайное блуждание в соседние точки на прямой возвртано тогда и только тогда, когда $p = 1/2$.
]

#proof[
  Не будем рассматривать дурацкие ситуации, когда $p = 0$ или $p = 1$. Тогда все состояние сообщающиеся, поэтому достаточно рассмотреть одно конкретное состояние. Например $0$. $p_(0, 0) (n) = 0$ если $n$ --- нечетное. $p_(0, 0) (2n) = C_(2n)^n p^n (1 - p)^n$. Тогда
  $
    sum_(n = 1)^oo p_(0, 0) (n) = sum_(n = 1)^oo p_(0, 0) (2n) = sum_(n = 1)^oo C_(2n)^n (p (1 - p))^n.
  $
  Знаем $C_(2n)^n sim 4^n/(sqrt(pi n))$. Тогда 
  $
    C_(2n)^n (p (1 - p))^n sim 1/sqrt(pi n) (4 p (1 - p))^n <= (4 p (1 - p))^n.
  $
  Тогда
  - $4 p (1 - p) = 1$, если $p = 1/2$, и ряд $sim sum 1/sqrt(pi n)$ и расходится.
  - $4 p (1 - p) < 1$, если $p != 1/2$, и ряд $sum (4p (1 - p))^n$ сходится.
]

#th[
  Рассмотрим произвольное симметричное случайное блуждание по $ZZ$  (не обязательно в соседние точки). $xi_1$, $xi_2$, ... --- независимые одинаково распределенные симметричные случайные величины. $S_n = xi_1 + xi_2 + ... + xi_n$.

  Пусть $E abs(xi_1) < +oo$. Тогда такое случайное блуждание возвратно.
]

#proof[
  $p_(0, 0) (n) = P(S_n = 0)$. Будем проверять условие возвратности. Распишем производящую функцию
  $
    G(z) := sum_(n = -oo)^(oo) P (xi_1 = n) z^n.
  $
  Это ряд Лорана, и, вообще говоря, мы такие не исследовали, но пофиг. При суммировании независимых случайных величин производящие ряды все равно перемножаются, поэтому $G_(S_n) (z) = G^n (z)$.

  Теперь следующая проблема: мы хотим узнать $P(S_n = 0)$, но $0$ мы подставить не можем (мы на $z$ делим). Поэтому пишем теорему Коши:
  $
    P(S_n = 0) = 1/(2pi i) integral_(abs(z) = 1) (G^n (z)) / z dif z.
  $

  И тогда нам нужен ряд

  $
  1/(2pi i) sum_(n = 0)^oo integral_(abs(z) = 1) (G^n (z))/z dif z
  $

  Обосновать почему законно переставлять сумму с интегралом мы не можем, потому что нет равномерной сходимости. Поэтому рассмотрим такой ряд $0 <= x < 1$:
  $
    sum_(n = 0)^(oo) P(S_n = 0) x^n =
    1/(2pi i) sum_(n = 0)^oo integral_(abs(z) = 1)  underbrace((G^n (z))/z, "по модулю" <= 1) x^n dif z newline(=^"Фубини")
    1/(2pi i) integral_(abs(z) = 1) 1/z sum_(n = 0)^oo x^n G^n (z) dif z =
    1/(2pi i) integral_(abs(z) = 1) (dif z)/(z (1 - x G(z))).
  $
  Знаем $E abs(xi_1) < +oo$, $sum_(n = -oo)^oo P(xi_1 = n) = 1$. Что мы знаем про $G$?
  $
    G' (z) = sum_(n = -oo)^oo n z^(n - 1) P(xi_1 = n), quad G' (1) = sum_(n = -oo)^oo n P(xi_1 = n) = 0.
  $
  Причем $G(1) = 1$, поэтому $G(z) = 1 + o(1 - z)$, и $G(e^(i t)) = 1 + o(1 - e^(i t)) = 1 + o(t)$ при $t --> 0$.

  Подставляем, и оцениваем $o(t) <= c t$:
  $
    1/(2pi i) integral_(abs(z) = 1) (dif z)/(z (1 - x G(z))) =
    1/(2pi) integral_0^(2pi) (dif t)/(1 - x G(e^(i t))) =
    1/(2pi) integral_0^(2pi) (dif t)/(1 - x (1 + o(t))) >=
    1/(2pi) integral_0^(2pi) (dif t)/(1 - x (1 - c t)).
  $
  Этот интеграл считается.
  $
    1/(2pi) integral_0^(2pi) (dif t)/(1 - x (1 - c t)) =
    lr(ln(1 - x + c t x)/(2pi c x) |)_(t = 0)^(t = 2pi) =
    1/(2pi c x) ln (1 - x + 2pi c x)/(1 - x) -->_(x -> 1-) +oo.
  $
  Значит $sum_(n = -oo)^oo P(S_n = 0) = +oo$. Значит каждая точка возвратна.
]

#th(name: "Пойя о возвращении")[
  Теперь рассмотрим случайное блуждание в $ZZ^d$, где вероятность попасть в соседнюю точку $1/(2d)$. То есть мы ходим по сетке, и равновероятно выбираем соседа, в которого мы переходим.

  Такое случайное блуждание возвратно при $d = 1$ и $d = 2$. Иными словами, если у нас есть пьяный мужик, то он выйдя из дома домой наверняка вернется, а если пьяная ворона --- то уже не факт.
]

#proof[
  При $d = 2$ повернем оси на 45#sym.degree. Рассмотрим $xi_n = (xi'_n, xi''_n)$ --- шаги в исходных координатах, и $eta_n = (eta'_n, eta''_n)$ --- в новых. Тогда $P(eta'_n = 1) = 1/2 = P(eta'_n = -1)$, и $P(eta''_n = 1) = 1/2 = P(eta''_n = -1)$. То есть теперь обе проекции смещаются, причем независимо. Тогда это просто 2 параллельных случайных блуждания по одномерной прямой. Формально,
  $
    P(S_(2n) = 0) = P(tilde(S)_(2n) = 0) = P(S'_(2n) = 0, S''_(2n) = 0) = P(S'_(2n) = 0) P(S''_(2n) = 0) newline(=) (C_(2n)^n dot 1/4^n)^2 sim (1/sqrt(pi n))^2 = 1/(pi n).
  $
  Ряд расходится.

  Понятно, что при $d > 3$ можно следить только за какими-то тремя координатами. Мы не всегда будем по ним ходить, ну и ладно, это возвратимость не улучшит. Поэтому достаточно доказать невозвратность при $d = 3$. Берем ноги в руки и пишем вероятность:
  $
    p_(0,0) (2n) = sum_(k + j <= n) binom(2n, k, k, j, j, n - k - j, n - k - j) dot 1/(6^(2n)) = С^n_(2n)/6^(2n) sum_(k + j <= n) binom(n, k, j, n - k - j)^2,
  $
  так как
  $
    binom(2n, k, k, j, j, n - k - j, n - k - j) = (2n!)/((k!)^2 (j!)^2 ((n - k - j)!)^2) = binom(n, k, j, n - k - j)^2 C_(2n)^n.
  $
  Причем мы знаем из комбинаторики,
  $
    sum_(k + j <= n) binom(n, k, j, n - k - j) = 3^n.
  $
  Надо только разобраться с квадратами. Оценим максимумом:
  $
    С^n_(2n)/6^(2n) sum_(k + j <= n) binom(n, k, j, n - k - j)^2 <=
    C_(2n)^n/(6^(2n)) dot 3^n dot max_(k + j <= n) binom(n, k, j, n - k - j) approx (C^n_(2n))/(12^n) binom(n, n/3, n/3, n/3)
  $
  и применим Стирлинга:
  $
    (C^n_(2n))/(12^n) binom(n, n/3, n/3, n/3) sim 1/12^n dot 4^n/sqrt(pi n) dot (sqrt(2 pi n) (n/e)^n)/((sqrt(2 pi n/3)(n/(3e))^(n/3))^3) = 1/cancel(3^n) dot 1/sqrt(pi n) dot 3^(cancel(n) + 3/2)/(2 pi n) = C/(n^(3/2)).
  $

  Ряд с такими коэффициентами сходится, а значит состояние невозвратно по критерию#rf("recurrent-criterion").

  Доказательство того, что если $binom(n, k_0, j_0, n - k_0 - j_0) = max$, то
  $
    n - k_0 - 1 &<= 2 j_0 &<= n - k_0 + 1 \
    n - j_0 - 1 &<= 2 k_0 &<= n - j_0 + 1 \
  $
  остается читателю.
]
