Конспект: марковские цепи, случайные блуждания и MCMC

ШАГ ЦЕПИ:  новое[j] = сумма по i:  r[i] · P[i][j]        через t шагов:  r · Pᵗ
сложение - по взаимоисключающим предыдущим состояниям;  умножение - переход не зависит от пути

сервер:            в строю   тормозит   лежит
  в строю            0,90      0,08      0,02          с любого начала через 20 шагов:
  тормозит           0,30      0,50      0,20          0,7911   0,1266   0,0823
  лежит              0,50      0,00      0,50
то же число - доля времени на одной длинной траектории:  0,797   0,124   0,079 за 20 000 шагов

СТАЦИОНАРНОЕ РАСПРЕДЕЛЕНИЕ
уравнения равновесия: приток в состояние = отток;  одно уравнение заменить на «сумма равна 1»
π₁ = 0,16·π₀,   π₂ = 0,104·π₀,   π₀ = 1 / 1,264 = 0,7911
два состояния, a туда и b обратно:  π = (b/(a+b), a/(a+b))
среднее время возвращения в i:  1 / π[i]

существует      всегда, если состояний конечно
единственно     если цепь неприводима                    два острова: любое распределение стационарно
цепь сходится   если ещё и апериодична                   маятник: [0, 1] ↔ [1, 0] вечно
лекарства       случайный прыжок - связность;   шанс остаться на месте - апериодичность

РАНЖИРОВАНИЕ СТРАНИЦ, d = 0,85
новый ранг = (1 − d)/n  +  d · сумма по ссылающимся:  ранг / число исходящих ссылок
шаг - проход по ссылкам, матрица не строится
страница без входящих ссылок:  (1 − d)/n             пять страниц:  0,364  0,185  0,365  0,056  0,030

БЛУЖДАНИЕ ПО НЕОРИЕНТИРОВАННОМУ ГРАФУ, m рёбер
π[v] = deg(v) / 2m          каждое ребро в каждую сторону - с частотой 1/2m
среднее возвращение в v: 2m / deg(v); двудольный граф - период 2
путь длины n:  от i до i + 1 в среднем 2i + 1 шаг;  от 0 до n:  n²       коридор 12:  145,2 при 144
за t шагов - расстояние порядка √t
ожидаемый обход всех вершин:  ≤ 2m(n − 1);   полный граф - n·ln n;   клубок с хвостом - порядка n³

ЧЕСТНАЯ ИГРА: капитал i, до n или до нуля
выигрыш с вероятностью i/n;   длительность i·(n − i)        3 из 12:  0,26 и 28,2 при 0,25 и 27
при 49% на ход шансы дойти от 50 до 100 - 12%

2-SAT БЛУЖДАНИЕМ
пока есть ложная скобка: поменять случайную из двух её переменных
X = число совпадений с решением S;  в ложной скобке хотя бы одна переменная расходится с S
вперёд ≥ 1/2  →  путь длины n  →  ≤ n² шагов;   2kn² шагов - неудача ≤ 1/2ᵏ
три литерала:  вперёд ≥ 1/3  →  снос назад  →  порядка 2ⁿ;   с перезапусками через 3n шагов - (4/3)ⁿ
ответ «невыполнима» - Монте-Карло;  найденное решение проверяется подстановкой

АЛГОРИТМ МЕТРОПОЛИСА: цепь под заданные веса w(x)
предложить соседа y симметрично;  принять с вероятностью min(1, w(y)/w(x));  иначе остаться
нужно только отношение весов - сумма по всем состояниям не требуется
веса 1 2 3 4 10:  доли 0,048  0,099  0,152  0,204  0,497

ВРЕМЯ СМЕШИВАНИЯ, 16 состояний, ленивая цепь, расстояние по вариации
шагов      1       4       16      64
кольцо     0,81    0,62    0,35    0,05
полный     0,44    0,04    0,00    0,00
правило говорит, К ЧЕМУ сходится цепь, и не говорит КОГДА;  решают узкие места