Случайные величины

«В среднем O(n log n)» для quicksort - это не магия, а математическое ожидание случайной величины. Load factor хеш-таблицы - это E[длина цепочки]. Retry-политика в microservices - это геометрическое распределение. SLA в 99.9% uptime - это хвостовая вероятность. Случайные величины дают точный язык для всего этого.

• **Quicksort:** E[сравнений] = O(n log n) доказывается через линейность E[] и индикаторные переменные для каждой пары элементов
• **Хеш-таблицы:** E[длина цепочки] = load factor = n/m. При load factor > 0.7 производительность деградирует нелинейно
• **Retry logic:** число попыток до успеха следует геометрическому распределению: E[попыток] = 1/p_success
• **SLA и SLO:** P(задержка > t) ограничивается неравенством Маркова/Чебышёва при знании μ и σ

Предварительные знания

• Discrete Probability

Случайная величина: PMF, E[X], Var[X]

Cloudflare фильтрует 72 млрд запросов в сутки с помощью фильтров Блума - вероятность ложного срабатывания 1% достигается всего при 10 битах на элемент. Случайная величина X - это функция X: Ω → R, отображающая элементарные исходы в числа. Дискретная случайная величина принимает конечное или счётное множество значений. Основные характеристики: PMF (функция вероятности масс), математическое ожидание E[X] и дисперсия Var[X].

**Основные определения:** - **PMF:** P(X=k) - вероятность того, что X принимает значение k. Сумма по всем k равна 1. - **Математическое ожидание:** E[X] = Σₖ k · P(X=k) - средневзвешенное значение - **Дисперсия:** Var[X] = E[(X−E[X])²] = E[X²] − (E[X])² - мера разброса - **Среднеквадратичное отклонение:** σ = √Var[X]

**Практический смысл:** если quicksort выполняет сравнения, и число сравнений - случайная величина X, то E[X] даёт ожидаемое число операций. Для случайного массива из n элементов E[X] = O(n log n) - именно это мы называем «в среднем O(n log n)».

Удобная формула для дисперсии: Var[X] = E[X²] − (E[X])². Часто проще вычислить E[X²] отдельно, чем раскрывать квадрат в определении E[(X−μ)²].

Линейность математического ожидания

Линейность математического ожидания - мощнейший инструмент теории вероятности: E[X + Y] = E[X] + E[Y] и E[cX] = c·E[X] для любых случайных величин X, Y (даже зависимых!) и константы c. Это позволяет вычислять E[X] через разложение на простые части.

**Линейность E[]:** - E[X + Y] = E[X] + E[Y] (для ЛЮБЫХ X, Y, независимо от зависимости) - E[c·X] = c·E[X] - E[X₁ + X₂ + ... + Xₙ] = E[X₁] + E[X₂] + ... + E[Xₙ] Внимание: E[X·Y] = E[X]·E[Y] только если X и Y независимы!

**Задача о хеш-таблице:** при n элементах в таблице размера m каждая ячейка получает в среднем n/m элементов (load factor). Ожидаемое число коллизий при вставке (i+1)-го элемента = i/m. По линейности: общее ожидаемое число коллизий = Σᵢ i/m = n(n-1)/(2m).

Трюк с индикаторными переменными: если нужно найти E[количество событий], введите Xᵢ = 1 если i-е событие произошло. Тогда X = ΣXᵢ и E[X] = ΣP(Xᵢ=1). Это работает даже если события зависимы!

Биномиальное и геометрическое распределения

Два фундаментальных дискретных распределения: **биномиальное** B(n,p) описывает число успехов в n независимых испытаниях с вероятностью успеха p, **геометрическое** Geom(p) - число испытаний до первого успеха.

**Биномиальное B(n,p):** P(X=k) = C(n,k)·pᵏ·(1-p)^(n-k) - E[X] = n·p - Var[X] = n·p·(1-p) **Геометрическое Geom(p):** P(X=k) = (1-p)^(k-1)·p - E[X] = 1/p - Var[X] = (1-p)/p² Геометрическое обладает **свойством отсутствия памяти:** P(X>s+t | X>s) = P(X>t)

**Retry logic в системах:** если HTTP-запрос имеет вероятность успеха p = 0.9, то E[попыток до успеха] = 1/p ≈ 1.11. При p = 0.5 (нестабильный сервис) нужно в среднем 2 попытки. При exponential backoff геометрическое распределение используется для моделирования времени до успешного соединения.

Свойство отсутствия памяти геометрического распределения: P(X > s+t | X > s) = P(X > t). Это значит: прошлые неудачные попытки не делают следующую попытку более вероятной. Это отличает геометрическое от распределений с «усталостью» (например, Weibull для аппаратных отказов).

Неравенства Маркова и Чебышёва

Неравенства Маркова и Чебышёва дают верхние оценки на вероятность «отклонения» случайной величины без знания полного распределения. Это инструмент анализа алгоритмов и верификации систем.

**Неравенство Маркова** (для X >= 0): P(X >= a) <= E[X] / a **Неравенство Чебышёва:** P(|X − E[X]| >= k·σ) <= 1/k² Или в эквивалентной форме: P(|X − μ| >= t) <= Var[X] / t² Чебышёв сильнее Маркова: использует и E[X], и Var[X].

**Закон больших чисел:** для n независимых одинаково распределённых величин X₁,...,Xₙ с E[Xᵢ]=μ, среднее X̄ₙ = (X₁+...+Xₙ)/n стремится к μ при n→∞. Это следует из неравенства Чебышёва: Var[X̄ₙ] = Var[X]/n → 0, значит X̄ₙ → μ по вероятности.

Неравенство Маркова - очень грубое (использует только E[X]), зато работает для любой неотрицательной случайной величины. Чебышёв точнее, но требует конечной дисперсии. В анализе алгоритмов чаще используют гораздо более точные хвостовые оценки (Chernoff bounds).

Ключевые идеи

• **E[X] = Σ k·P(X=k):** математическое ожидание - взвешенное среднее. Var[X] = E[X²] − (E[X])².
• **Линейность E[]:** E[X+Y] = E[X] + E[Y] всегда, даже для зависимых X, Y. Позволяет разбивать сложные задачи на простые части.
• **Биномиальное B(n,p):** E[X]=np, Var[X]=np(1-p). Число успехов в n испытаниях.
• **Геометрическое Geom(p):** E[X]=1/p, нет памяти. Число попыток до успеха - основа retry-логики.
• **Неравенства Маркова/Чебышёва:** верхние оценки на хвостовые вероятности без знания полного распределения.

Связанные темы

Случайные величины - мост между теорией вероятности и анализом алгоритмов:

• Дискретная вероятность — Случайные величины строятся на вероятностном пространстве и аксиомах Колмогорова
• Discrete Math в CS — Вероятностные алгоритмы анализируются через ожидаемое время работы и хвостовые оценки
• Discrete Math на собеседовании — Задачи на E[X] и индикаторные переменные - классика FAANG-интервью

Вопросы для размышления

• Почему линейность E[X+Y] = E[X]+E[Y] выполняется даже для зависимых случайных величин, тогда как E[X·Y] = E[X]·E[Y] требует независимости?
• Если load factor хеш-таблицы равен 0.75, и функция хеширования случайна, каково ожидаемое число шагов при поиске элемента методом цепочек? Как это число растёт при переполнении до load factor 2?
• Сервис делает retry при неудаче с p_failure = 0.3 и exponential backoff. Как геометрическое распределение помогает рассчитать ожидаемое суммарное время ожидания до успеха?

Связанные уроки

• prob-06-random-vars