Закон больших чисел

Закон больших чисел (ЗБЧ) — фундаментальный результат теории вероятностей: среднее большого числа независимых случайных величин сходится к их математическому ожиданию. Это математическое основание статистики.

Слабый и сильный ЗБЧ

Слабый ЗБЧ (Чебышёв, 1866): Для i.i.d. X₁,...,Xₙ с E[Xᵢ]=μ и Var[Xᵢ]=σ² < ∞: X̄ₙ = (X₁+...+Xₙ)/n →_P μ (сходимость по вероятности). Доказательство через Чебышёв: P(|X̄ₙ-μ| ≥ ε) ≤ σ²/(nε²) → 0.

Сильный ЗБЧ (Колмогоров): При тех же условиях: X̄ₙ → μ почти наверное (P(lim X̄ₙ = μ) = 1). Сильнее слабого (п.н. → по вероятности, но не наоборот).

ЗБЧ без конечной дисперсии (Хинчин): Достаточно конечности E[|X|]. При Var[X]=∞ ЗБЧ всё равно выполнен!

Исключения: Распределение Коши — нет конечного среднего → ЗБЧ не выполнен! X̄ₙ остаётся Коши.

Применения ЗБЧ

Метод Монте-Карло: E[f(X)] ≈ (1/n)Σ f(Xᵢ). При n→∞ оценка точна. Применяется для сложных интегралов: ∫_D f(x)dx ≈ Vol(D)·(1/n)Σ f(xᵢ) при xᵢ ~ U[D].

Частота как вероятность: Относительная частота события A за n экспериментов: f_n(A) = N_n(A)/n → P(A) (ЗБЧ). «Вероятность = предел частоты» — операциональное определение.

Задание: (а) Симулируйте ЗБЧ: генерируйте Exp(1) и накапливайте X̄ₙ для n=1,...,10000. Постройте график X̄ₙ vs n. (б) Для Cauchy: симулируйте X̄ₙ для Cauchy(0,1). Как ведёт себя среднее? Объясните. (в) Монте-Карло для π: генерируйте точки в квадрате [-1,1]², считайте долю внутри единичного круга → π/4. Постройте сходимость.

Закон итерированного логарифма

Помимо ЗБЧ (X̄ₙ → μ) и ЦПТ ((X̄ₙ−μ)√n → N(0,σ²)), существует более точный результат — закон итерированного логарифма (ЗИЛ): lim sup_{n→∞} (Sₙ − nμ)/(σ√(2n ln ln n)) = 1 п.н. Это описывает точную скорость максимальных флуктуаций частичных сумм. Скорость расходимости: O(√n ln ln n) — чуть быстрее √n. Доказательство использует неравенство Хёффдинга и принцип Бореля-Кантелли.

Практическое следствие: при мониторинге случайного процесса «необычным» следует считать отклонения, превышающие 2σ√(ln ln n/n) — это объективный порог для аномалий.

Сильный vs. слабый ЗБЧ

Слабый ЗБЧ (Чебышёв, 1866): X̄ₙ →_P μ (по вероятности). Для любого ε>0: P(|X̄ₙ−μ|>ε) → 0. Требует лишь E[X]<∞ и конечного второго момента (в варианте Чебышёва).

Сильный ЗБЧ (Бореля, Колмогорова): X̄ₙ →_{п.н.} μ (почти наверное). P(X̄ₙ→μ) = 1. Требует E[|X|]<∞. Значительно сильнее: не просто каждый фиксированный n-хвост маленький, а вся траектория почти наверное сходится.

Различие принципиально: слабый ЗБЧ не утверждает сходимость траекторий, только маргинальных распределений. Пример: при ε=0.01 после 10⁶ опытов «хвост», где |X̄ₙ−μ|>0.01, мал, но ненулевой. Сильный ЗБЧ говорит: почти наверное ни одно будущее отклонение не превысит ε для достаточно больших n.

Применения ЗБЧ в вычислениях

Метод Монте-Карло прямо опирается на ЗБЧ: θ = ∫ f(x)dx = E[f(X)] ≈ (1/n)Σf(Xᵢ). Скорость сходимости — O(1/√n) по ЦПТ, независимо от размерности пространства! Это главное преимущество перед детерминированными методами квадратуры (которые страдают «проклятием размерности»).

Quasi-Monte Carlo: использует детерминированные низкодискрепантные последовательности (Холтона, Соболя) вместо случайных. Скорость сходимости O((log n)^d/n) — лучше чем O(1/√n) при малом d, хуже при больших d. На практике: QMC эффективнее случайного MC для d ≤ 20.

Ergodic theorem и сильный ЗБЧ для зависимых данных

Теорема Биркгофа (Birkhoff's Ergodic Theorem): Для эргодического меры-сохраняющего преобразования T: (1/n)Σᵢ₌₀^{n-1} f(Tᵢω) → ∫ f dμ п.н. Это обобщение ЗБЧ на зависимые данные. MCMC использует эту теорему: длинная цепь Маркова → интеграл по инвариантному распределению.

Метод характеристических функций в ЗБЧ

Доказательство слабого ЗБЧ через ХФ: φ_{X̄ₙ}(t) = (φ_X(t/n))ⁿ. При E[X]=μ: φ_X(t/n) = 1 + iμ(t/n) + o(1/n). Тогда φ_{X̄ₙ}(t) → e^{iμt} = φ_{δ_μ}(t) — ХФ точечной массы в μ. По теореме непрерывности Леви: X̄ₙ → μ по вероятности.

Вероятностный метод в комбинаторике

Теорема Эрдёша: Если P(нет монохромного k-клика) > 0, то такой граф существует. Применение: R(k,k) > n при 2C(n,k)/2^{C(k,2)} < 1. Отсюда R(k,k) > (1+o(1))k·2^{k/2}/e√2. Это доказательство существования экспоненциально: первые нижние оценки Рамсея. Вероятностный метод — Эрдёш доказал существование объектов, которые нельзя построить конструктивно.

Неравенства для суммы случайных переменных

Неравенство Хёффдинга для ограниченных СВ (aᵢ ≤ Xᵢ ≤ bᵢ): P(Σ(Xᵢ−EXᵢ) ≥ t) ≤ exp(−2t²/Σ(bᵢ−aᵢ)²). Применяется для ε-δ оценок в обучении с учителем. Неравенство Азумы: для мартингальных разностей |Xₖ−Xₖ₋₁| ≤ cₖ: P(|Mₙ| ≥ t) ≤ 2exp(−t²/(2Σcₖ²)). Используется в доказательствах о концентрации в случайных графах и алгоритмах.

Численный пример: ЗБЧ на подбрасывании монет

Задача: X₁,...,Xₙ ~ Bernoulli(p=0.5). Найти P(|X̄ₙ−0.5|>0.02) при n=100 и n=10 000.

Шаг 1: Var[X̄ₙ] = p(1−p)/n = 0.25/n. Стандартное отклонение: σ[X̄ₙ] = 0.5/√n.

Шаг 2 (n=100): σ[X̄₁₀₀]=0.5/10=0.05. P(|X̄−0.5|>0.02)≈2(1−Φ(0.02/0.05))=2(1−Φ(0.4))≈2·0.345=0.690. Примерно 69% — вполне вероятное отклонение.

Шаг 3 (n=10 000): σ[X̄₁₀₀₀₀]=0.5/100=0.005. P(|X̄−0.5|>0.02)≈2(1−Φ(0.02/0.005))=2(1−Φ(4.0))≈2·0.000032=0.000064. Менее 0.007% — ЗБЧ в действии.

Шаг 4: При n=10 000 среднее практически всегда в [0.48, 0.52]. Слабый ЗБЧ (Хинчин): для любого ε>0, P(|X̄ₙ−p|>ε)→0. Сильный ЗБЧ (Колмогоров): X̄ₙ→p почти наверное. Казино при миллионах ставок знает свой доход с точностью до долей процента.