probability-theory.md

Теорвер для алгоритмистов

Вы, наконец, узнаете, почему ДД работает за логарифм, почему быстрая сортировка быстрая, какой модуль нужно выбирать для хэшей, сколько сэмплов нужно выбирать для монте-карло и т. д.

Следующие строчки позволят нам генерировать распределения и рисовать графики, не обращайте внимание.

import numpy as np

import matplotlib as plt
%matplotlib inline

import seaborn as sns
sns.set()

Аксиоматика

В вузах теорвер очень долго аксиоматизируют перед тем, как перейти к чему-то полезному. Сейчас поясним, зачем.

[Парадокс Бертрана](https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%91%D0%B5%D1%80%D1%82%D1%80%D0%B0%D0%BD%D0%B0_(%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C%29):

Рассмотрим равносторонний треугольник, вписанный в окружность. Наудачу выбирается хорда окружности. Какова вероятность того, что выбранная хорда длиннее стороны треугольника?

Оказывается, можно придумать хотя бы три способа решать задачу, которые выглядят адекватно, но все дают разные ответы.

1. Наудачу выберем две точки на окружности и проведём через них хорду. Чтобы посчитать искомую вероятность, представим, что треугольник повёрнут так, что одна из его вершин совпадает с концом хорды. Заметим, что если другой конец хорды лежит на дуге между двумя другими вершинами треугольника, то длина хорды больше стороны треугольника. Длина рассмотренной дуги равна трети длины окружности, значит искомая вероятность равна $\frac13$.

2. Зафиксируем радиус окружности, наудачу выберем точку на радиусе. Построим хорду, перпендикулярную зафиксированному радиусу, проходящую через выбранную точку. Для нахождения искомой вероятности, представим, что треугольник повёрнут так, что одна из его сторон перпендикулярна зафиксированному радиусу. Хорда длиннее стороны треугольника, если её центр ближе к центру, чем точка пересечения треугольника с зафиксированным радиусом. Сторона треугольника делит пополам радиус, следовательно вероятность выбрать хорду длиннее стороны треугольника $\frac12$.

3. Выберем наудачу произвольную точку внутри круга и построим хорду с центром в выбранной точке. Хорда длиннее стороны равностороннего треугольника, если выбранная точка находится внутри круга, вписанного в треугольник. Площадь вписанного круга есть $\frac14$ от площади большего, значит исходная вероятность равна $\frac14$.

Как мы увидели, от формального определения «случайной хорды» непосредственно зависит ответ.

Каждый раз, когда в истории математики появляется подобный приводящий к протеворечиям парадокс, математики паникуют и начинают всё формализовывать и аксиоматизировать. Так появилась теория вероятностей (внимание: не «ти», а «тей»).

Перейдем к самим определениям:

Функцию $X : \Omega \to R$ будем называть случайной величиной. Она сопостав- ляет каждому элементарному исходу какое-то число.

Распределения

Геометрическое распределение.

Парадокс дней рождений

Пусть $f(n, d)$ это вероятность того, что в группе из $n$ человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от $1$ до $d$.

$$f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d})$$

Попытаемся оценить $f$:

$$ \begin{align} \begin{aligned} e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)} \\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)} \\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)} \\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} & \\ & = e^{-\frac{n(n-1)}{2d}} & \\ & \simeq e^{-\frac{n^2}{2d}} & \\ \end{aligned} \end{align} $$

Матожидание

Математическим ожиданием случайной величины $X$, которая принимает значения $x_1, x_2, \ldots$ называется

$$ E[X] = \sum_{x \in S} p_S(x) \cdot x $$

Самое главное для нас свойство — ожидание линейно:

$$ \begin{align*} E[X+Y] & = \sum_{x, y} (x+y) p(x, y) \ & = \sum_{x, y} x p(x, y) + \sum_{x, y} y p(x, y) \ & = \sum_x x p(x) \sum_y p(y) + \sum_y y p(y) \sum_x p(x) \ & = \sum_x x p(x) + \sum_y y p(y) \ & = E[X] + E[Y] \end{align*} $$

Акцентируем внимание: $X$ и $Y$ вообще не важно какие. Возможно, они связаны как-то очень сложно, но это не важно. Как мы потом, увидем, это свойство очень упрощает вычисление матожиданий каких-то очень сложных шняг.

Также, в частности его можно домножать на константу.

Теперь можно перейти к практическим задачам.

Геометрическое распределение

Петя кидает монету, с вероятностью $p$ выпадает орел и он прекращает кидать ее, с вероятностью $1-p$ выпадает решка и он кидает ее еще раз. Пусть $X$ - это количество бросков. Найдите $\rho_X(x)$ и $F_X(x)$.

Неподвижные точки в перестановке

Когда автор пришел на первое занятие по английскому в МФТИ, препод устроила следующую игру на знакомство: разделила всех студентов на две команды. В каждой команде про своих членов загадываются факты: кто-то мечтал стать акробатом, кто-то смотрит анимэ и всё в таком духе. Команде соперников сообщались только эти факты, и им нужно было отгадать, кому какой принадлежит. Побеждает команда, которая отгадала больше фактов о соперниках. Нас было 11 — простое число, никак не делящееся на равные команды, и поэтому в одной команде было 5 человек, а в другой 6. Автору стало интересно: если отбросить все психологические аспекты и делать все рандомно, у какой команды вероятность победить выше?

Следует заметить, что все-таки ожидание правильно отгаданных вопросов не очень помогает выяснить, у какой команды есть преимущество и какое.

Высота декартова дерева

Высота дерева. Высота в среднем логарифмическая. Любознательные могут ознакомиться с типа доказательством, но это не обязательно.

Глубина вершины — это количество родителей (прим. К. О.). Введем индикатор. $E[h] = \sum \frac{1}{k} \approx \log n $.

Асимптотика quicksort-а

Тут на самом деле будет примерно так же, как с ДД. Нас интересует суммарное число сравнений. Просуммируем для каждой пары элементов вероятность, что они будут сравнены.

Как для пары определить эту вероятность? Посмотрим на все элементы между ними, будь они в отсортированном массиве.

Внезапно возникает гармонический ряд, ну а дальше мы знаем.

Дисперсия

Дисперсия — это количественная метрика. Это не что-то абстрактное, как могли рассказать в школе на теорвере, а формально определенная величина, имеющая кучу всяких полезных свойств.

Дисперсия определяется как средний квадрат отклонения случайной величины от ее матожидания:

$$ D[X] = E[(X − E[X])^2] $$

Её проще считать по другой формуле, разложив квадрат внутри ожидания:

$$ \begin{align} D[X] &= E[(X − E[X])^2] \ &= E[X^2 - 2 \cdot X \cdot E[X] + E[X]^2] \ &= E[X^2] - E [\underbrace{2 \cdot E[X]}_{const} \cdot X ] + E[E[X]^2] \ &= E[X^2] - 2 E[X]^2 + E[X]^2 \ &= E[X^2] - E[X]^2 \end{align} $$

Эту формулу мы будем использовать для вывода разных свойств.

У дисперсии очень много крутых свойств.

$$ D[k X] = E[k^2 X^2] - E[k X]^2 = k^2 (E[X^2] - E[X]^2) = k^2 D[X] $$

Предполагаем, что $X$ и $Y$ независимы.

$$ \begin{align} D[X + Y] &= E[(X+Y)^2] - E[X+Y]^2 \ &= E[X^2 + X Y + Y^2] - (E[X] + E[Y])^2 \ &= E[X^2] + E[Y^2] - E[X]^2 - E[Y]^2 \ &= D[X] + D[Y] \end{align} $$

Важное отличие от свойств матожидания: дисперсию так просто можно считать только для независимых величин.

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

Закон больших чисел — принцип, который описывает результат выполнения одного и того же эксперимента много раз. Согласно закону, среднее значение конечной выборки из фиксированного распределения близко к математическому ожиданию этого распределения.

У матожидания (константы) стандартное обозначение $\mu$ (мю), а у дисперсии $\sigma$ (сигма).

$$ M_n = \frac{X_1 + \ldots + X_n}{n} $$

$$ E[M_n] = \frac1n E[X_1 + \ldots + X_n] = \mu $$

Это немного очевидное равенство. Теперь нас интересует, насколько точно оно в реальности достигается:

$$ D[M_n] = \frac{1}{n^2} D[X_1 + \ldots + X_n] = \frac{\sigma}{n} $$

С одной стороны, оно домножается на $\frac{1}[n^2}$ из-за усреднения, с другой — на $n$ из-за суммирования.

Нормальное распределение

Когда вы в каких-нибудь библиотеках для анализа данных просите показать какой-то summary, то чаще всего вы увидите два числа: матожидание и дисперсию.

Центральная предельная теорема названа так пафосно вполне обоснованно.

Она говорит, что нам достаточно про каждое слагаемое знать всего два числа — ожидание и дисперсию.

$$ f(x) = \frac{1}{2\sqrt{\pi}} e^{-\frac{(x-\mu)^2}{\sigma^2}} $$

Доказать это очень трудно. Даже со ссылками на мощные теоремы оно займёт не одну страницу. Обычно доказательство рассказывают в середине второго курса.

Трудно даже доказать, что это распределение, т. е. что $\int_{-\inf}^\inf f(x) dx = 1$.

Метод Монте-Карло

Алгоритмы вида «давайте посчитаем значения в разных случайных точках и усредним» называются методами монте-карло.

Пусть у нас есть единичный квадрат и несколько сотен кружков. Нам нужно посчитать долю области квадрата, которая не покрывается ни одним из кругов, с точностью до 1%.

Можно просто делать так: тыкать в 10000 случайных точек и проверять для каждой, является ли она «хорошей», а затем вывести $\frac{\text{хорошие}}{\text{хорошие} + \text{плохие}}$ в качестве ответа.

Сдать можно сюда.

Хэш-таблицы

Вообще, хэш — это такая функция, которая сопоставляет элементу какой-то другой элемент. С точки зрения криптоанализа, она должна быть трудно обратимой, а с точки зрения алгоритмиста — генерирующей равномерные игреки.

Можно делать так если мы планируем хранить $n$ элементов, то нужно завести $\Theta(n)$ ячеек, каждая из которых будет на самом деле односвязным списокм.

Это будет работать, потому что из-за рандома в среднем в каждой ячейке будет по одному элементу. Но константа у такого решения большая.

Стандартная хэш-таблица из STL по непонятным автору причинам работает очень медленно. Во многих задачах она является самой нагруженной структурой. Её можно написать в 3-5 раз быстрее.