Введение: почему несколько случайных удач на старте превращаются в необратимый разрыв?
Два видеоролика или стандарта одинакового качества запускаются одновременно: благодаря крошечному перевесу на старте один из них за счет положительной обратной связи захватывает рынок (эффект Матфея), а другой остается в тени. Однако усиленный закон больших чисел (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$, насыщение, память и сеть.