Введение: почему несколько случайных удач на старте превращаются в необратимый разрыв?
Два видеоролика или стандарта одинакового качества запускаются одновременно: благодаря крошечному перевесу на старте один из них за счет положительной обратной связи захватывает рынок (эффект Матфея), а другой остается в тени. Однако усиленный закон больших чисел (SLLN) утверждает обратное: в независимых (i.i.d.) испытаниях Бернулли начальные флуктуации размываются при \(n \to \infty\), и доля почти наверное сходится к константе \(p\).
Многие реальные процессы являются случайными процессами с подкреплением, где наступление события повышает вероятность его повторения. В 1923 году Джордж Пойа и Флориан Эггенбергер предложили модель урны Пойи, открыв два парадокса:
- Первый парадокс (Перестановочность): Хотя состав урны меняется на каждом шаге, \(\mathbb{P}(I_n = 1) = \frac{r}{r+b}\) постоянна для всех \(n\), а вероятность любой последовательности зависит только от числа красных и синих шаров, но не от их порядка (перестановочность).
- Второй парадокс (Случайный предел): При \(n \to \infty\) доля красных шаров \(X_n\) почти наверное сходится к случайной величине \(X_\infty \sim \mathrm{Beta}(r, b)\). При \(r=1, b=1\) предел имеет равномерное распределение \(\mathrm{Uniform}(0, 1)\) на \([0, 1]\)!
Глава 1: Три вселенные урн — исчерпание, отсутствие памяти и подкрепление Пойи
При \(n = 0\) в урне \(R_0 = r\) красных и \(B_0 = b\) синих шаров (\(N_0 = r + b\)). На каждом шаге извлекается один шар и возвращается вместе с \(c\) шарами того же цвета: 1. Без возвращения (\(c = -1\)) (отрицательная связь, гипергеометрическое), 2. С возвращением (\(c = 0\)) (без памяти i.i.d. \(\mathrm{Binomial}(n, \frac{r}{r+b})\)), 3. Урна Пойи (\(c = +1\)) (положительная связь: шар плюс \(1\) шар того же цвета).
flowchart TD
Start["Старт (n = 0): Красные r, Синие b, X₀ = r/(r+b)"]
Draw["Шаг n+1: Извлечь 1 шар, P(Iₙ₊₁ = 1 | Fₙ) = Xₙ"]
BranchW["1. Без возвращения (c = -1)"]
BranchB["2. С возвращением (c = 0)"]
BranchP["3. Урна Пойи (c = +1)"]
LimW["Остановка при n = r+b на r/(r+b)"]
LimB["SLLN: Xₙ → r/(r+b) п.н."]
LimP["Дуб: Xₙ → X_∞ ~ Beta(r, b) п.н."]
Start --> Draw
Draw --> BranchW --> LimW
Draw --> BranchB --> LimB
Draw --> BranchP --> LimP
Пусть \(I_n \in \{0, 1\}\) и \(S_n = \sum_{k=1}^n I_k\), тогда \(R_n = r + S_n\) и \(N_n = r + b + n\):
\[X_n := \frac{R_n}{N_n} = \frac{r + S_n}{r + b + n}, \qquad \mathbb{P}(I_{n+1} = 1 \mid \mathcal{F}_n) = X_n, \qquad |X_{n+1} - X_n| \le \frac{1}{r + b + n + 1}\]| Характеристика | 1. Без возвращения (\(c = -1\)) | 2. С возвращением (\(c = 0\)) | 3. Урна Пойи (\(c = +1\)) |
|---|---|---|---|
| Обратная связь | Отрицательная (исчерпание) | Отсутствует (без памяти) | Положительная (самоподкрепление) |
| Зависимость | Отрицательная корреляция | Независимость (i.i.d.) | Бесконечно перестановочна |
| Распределение \(S_n\) | \(\mathrm{Hypergeom}(N_0, r, n)\) | \(\mathrm{Binomial}(n, \frac{r}{r+b})\) | \(\mathrm{BetaBinom}(n, r, b)\) |
| Предел \(X_\infty\) | Константа \(\frac{r}{r+b}\) | Константа \(\frac{r}{r+b}\) п.н. | Величина \(X_\infty \sim \mathrm{Beta}(r, b)\) п.н. |
Глава 2: Перестановочность и бета-биномиальное распределение
Для любой последовательности \((i_1, \dots, i_n) \in \{0, 1\}^n\) с \(k = \sum_{j=1}^n i_j\) красными шарами произведение знаменателей равно \((r+b)^{(n)}\), а числителей коммутативно равно \(r^{(k)} b^{(n-k)}\):
\[\mathbb{P}(I_1 = i_1, \dots, I_n = i_n) = \frac{r^{(k)} \, b^{(n-k)}}{(r+b)^{(n)}}, \qquad \mathbb{P}(S_n = k) = \binom{n}{k} \frac{\mathrm{B}(r+k, \, b+n-k)}{\mathrm{B}(r, \, b)}\]При \(r = 1, b = 1\) факториалы сокращаются в дискретное равномерное распределение \(\mathbb{P}(S_n = k) = \frac{1}{n + 1}\) (\(k = 0, 1, \dots, n\)).
Глава 3: Мартингал Дуба и предел \(\mathrm{Beta}(r,b)\)
Так как \(\mathbb{E}[R_{n+1} \mid \mathcal{F}_n] = R_n + X_n = (N_n + 1)X_n\), доля \(X_n\) образует ограниченный мартингал на \([0, 1]\):
\[\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = \frac{R_n + \mathbb{E}[I_{n+1} \mid \mathcal{F}_n]}{N_n + 1} = \frac{(N_n + 1) X_n}{N_n + 1} = X_n\]По теореме Дуба о сходимости мартингалов, \(X_n \xrightarrow{\text{п.н.}} X_\infty\). Асимптотика \(\frac{\Gamma(z+\alpha)}{\Gamma(z+\beta)} \sim z^{\alpha-\beta}\) при \(k = \lfloor np \rfloor\) доказывает, что \(X_\infty\) имеет бета-распределение \(\mathrm{Beta}(r, b)\):
\[\boxed{f_{X_\infty}(p) = \frac{\Gamma(r+b)}{\Gamma(r)\Gamma(b)} \, p^{r-1} (1-p)^{b-1} \quad (0 < p < 1), \qquad \mathbb{E}[X_\infty] = \frac{r}{r+b}, \qquad \mathrm{Var}(X_\infty) = \frac{rb}{(r+b)^2(r+b+1)} > 0}\]Глава 4: Теорема де Финетти, нелинейные переходы и приложения
- Теорема представления де Финетти (1931): Любая бесконечно перестановочная последовательность есть смесь независимых испытаний Бернулли с априорной мерой \(\mathrm{Beta}(r,b)\): \(\mathbb{P}(I_1 = i_1, \dots, I_n = i_n) = \int_0^1 p^k (1-p)^{n-k} \, \frac{\Gamma(r+b)}{\Gamma(r)\Gamma(b)} p^{r-1}(1-p)^{b-1} \, dp\)
- Нелинейные урны (\(f(x) = \frac{x^\gamma}{x^\gamma + (1-x)^\gamma}\)): \(X_{n+1} - X_n = \frac{1}{N_n+1}[(f(X_n)-X_n) + \xi_{n+1}]\) порождает три режима:
flowchart TD
Root["Нелинейная урна: f(x) = x^γ / (x^γ + (1-x)^γ)"]
Sub["1. Сублинейный (0 < γ < 1)"]
Lin["2. Линейный (γ = 1): g(x) ≡ 0"]
Sup["3. Суперлинейный (γ > 1)"]
ResSub["Сосуществование: Xₙ → 1/2 п.н."]
ResLin["Зависимость от пути: Xₙ → Beta(r, b) п.н."]
ResSup["Winner-Take-All: P(X_∞ ∈ {0, 1}) = 1"]
Root --> Sub --> ResSub
Root --> Lin --> ResLin
Root --> Sup --> ResSup
- Приложения и ограничения: W. Brian Arthur (1989) объясняет Lock-In (\(\gamma > 1\), QWERTY, VHS); предпочтительное присоединение (Юл–Саймон / Барабаши–Альберт) порождает \(P(k) \sim k^{-(2 + \frac{1}{1-\alpha})}\); цвета с весом \(\theta > 0\) из \(H_0\) сходятся к процессу Дирихле \(\mathrm{DP}(\theta, H_0)\) (CRP); MusicLab (Salganik et al. 2006) выделяет четыре границы: качество \(\eta_i\), насыщение, память и сеть.