Схема Бернулли: случайные блуждания и графы

Случайное блуждание и случайные графы как модели схемы испытаний Бернулли

Ключевые тезисы

Схема испытаний Бернулли служит основой для многих важных вероятностных моделей.
Случайное блуждание на прямой — классическая модель, описывающая движение "пьяницы" из кабака.
Модель случайного графа Эрдёша–Реньи описывает возникновение связей между объектами (например, компьютерами или людьми).
Для анализа схемы Бернулли при больших n существуют предельные теоремы: теорема Пуассона и теорема Муавра–Лапласа.

Случайное блуждание

Описание модели:

На прямой в точке 0 (кабак) находится "пьяница".
За каждый шаг он с вероятностью p смещается на +1 (вправо), а с вероятностью q = 1-p на -1 (влево).
Если дорога ровная, то p = q = 1/2.
Процессом управляет схема испытаний Бернулли: n независимых шагов.

Вероятность нахождения в точке k после n шагов:

Пусть X — число шагов вправо. Тогда положение: 2X - n = k.
Отсюда X = (k + n)/2.
Ответ: Если (k + n) — нечётное, вероятность равна 0. Если чётное, то:

P = C_n^x * p^x * q^(n-x), где x = (k + n)/2.

Это классическая биномиальная вероятность. Интересный вопрос — какова вероятность сильно удалиться от начала? Для оценки таких вероятностей понадобятся вероятностные неравенства.

Модель случайного графа (Эрдёша–Реньи)

Определение графа:
Граф — это пара (V, E), где V — конечное множество вершин, а E — набор неупорядоченных пар вершин (рёбер). Рассматриваются обыкновенные графы (без петель, кратных рёбер и ориентации).

Построение случайного графа G(n, p):

Берётся полный граф на n вершинах (все возможные рёбра, их количество C_n^2).
Каждое возможное ребро проводится независимо с вероятностью p (успех) и не проводится с вероятностью q = 1-p (неудача).
Это прямое применение схемы испытаний Бернулли к каждому из C_n^2 потенциальных рёбер.

Вероятность конкретного графа:

Если граф имеет ровно m рёбер, то вероятность его реализации:

P = p^m * q^(C_n^2 - m).
Если же важен лишь тип графа (например, цикл), то вероятность умножается на количество способов его реализации на n вершинах.

Пример: Вероятность того, что граф — это цикл на всех n вершинах:

P(цикл) = ( (n-1)! / 2 ) * p^n * q^(C_n^2 - n).

Предельные теоремы для схемы Бернулли

Для оценки вероятностей при больших n используются аппроксимации.

Теорема Пуассона

Условие: n велико, а p мало, причём n * p → λ = const (т.е. p ~ λ / n).
Утверждение: Вероятность получить ровно k успехов асимптотически приближается к:

P(μ_n = k) ~ (λ^k * e^(-λ)) / k!
Это формула распределения Пуассона. Доказательство использует разложение биномиального коэффициента и замечательный предел.

Теорема Муавра–Лапласа (локальная)

Условие: n велико, p — константа (не стремится к 0).
Утверждение: Вероятность того, что число успехов μ_n лежит между a и b, асимптотически равна:

P(a ≤ μ_n ≤ b) ~ 1/√(2π) * ∫_[α]^[β] e^(-x²/2) dx,
где α = (a - np)/√(npq), β = (b - np)/√(npq).
Интеграл в правой части — это вероятность попадания в отрезок для стандартного нормального распределения.

Пример применения: Задача о гардеробах в театре

Постановка задачи:

В театр на 1000 мест (n = 1000) приходит аншлаг.
У театра два входа (левый и правый), каждый со своим гардеробом на x мест.
Каждый человек независимо выбирает вход с вероятностью p = q = 1/2.
"Файл" (плохое событие) — если гардероб у выбранного входа переполнен.
Вопрос: Каким сделать x, чтобы вероятность "файла" была около 1/365 (раз в год)?

Решение с помощью теоремы Муавра–Лапласа:

Пусть μ_1000 — число людей, пошедших направо. "Хорошо", если μ_1000 ≤ x и 1000 - μ_1000 ≤ x (оба гардероба не переполнены).
Преобразуем условие к виду, удобному для теоремы: 500 - x ≤ μ_1000 - 500 ≤ x - 500.
Поделим на √(npq) = √(1000 * 1/2 * 1/2) = √250 ≈ 15.8.
Нам нужно, чтобы вероятность попадания нормированной величины в симметричный интервал [-t, t] была ≈ 1 - 1/365 ≈ 0.997.
Из свойств нормального распределения известно, что ∫_(-3)^(3) e^(-x²/2) dx ≈ 0.997. Значит, t ≈ 3.
Получаем уравнение: (x - 500) / √250 ≈ 3 → x ≈ 500 + 3*15.8 ≈ 548.

Вывод: Достаточно сделать гардероба на ~548 мест каждый, чтобы сбои происходили в среднем раз в год. Это значительно меньше интуитивных оценок в 750 или 950 мест, и демонстрирует силу концентрации вероятности вокруг среднего значения в схеме Бернулли.

Итог: Схема испытаний Бернулли — мощный инструмент, порождающий разнообразные и практически полезные модели. Предельные теоремы (Пуассона и Муавра–Лапласа) позволяют эффективно работать с этими моделями при больших объёмах данных.