Дискретная математика
Дискретная вероятность
В комнате 23 человека - вероятность совпадения дней рождения выше 50%. Это не ошибка интуиции, а следствие парадокса дня рождения: вероятностный метод превращает случайность в инструмент доказательства существования объектов, которые иначе не найти.
- Bloom-фильтры в Cassandra и Redis используют $k$ независимых хэш-функций: вероятность ложноположительного ответа $\approx (1-e^{-kn/m})^k$ при $m$ битах и $n$ элементах - оптимальное $k = (m/n)\ln 2$ даёт баланс памяти и точности.
- MinHash для Locality-Sensitive Hashing: вероятность совпадения MinHash двух множеств равна их сходству Жаккара $P(h(A)=h(B)) = |A\cap B|/|A\cup B|$. Spotify и YouTube используют это для быстрого поиска похожего контента.
- Вероятностный метод Эрдёша: существование раскраски графа без монохроматических клик доказывается через ненулевую вероятность - без явной конструкции.
Цели урока
- Вычислять вероятности через линейность математического ожидания и индикаторные переменные
- Применять вероятностный метод для доказательства существования комбинаторных объектов
- Анализировать вероятностные структуры данных: Bloom-фильтр, MinHash
Предварительные знания
- Основы комбинаторики: биномиальные коэффициенты, перестановки
- Аксиомы вероятности и условная вероятность
Парадокс дня рождения и коллизии
При $n$ людях и $m$ равновероятных днях рождения вероятность хотя бы одного совпадения: $P \approx 1 - e^{-n^2/(2m)}$. При $m=365$ уже $n=23$ даёт $P > 0.5$. Этот результат критичен для хэш-функций: при $m=2^{128}$ состояний первая коллизия ожидается через $\approx 2^{64}$ попыток - именно поэтому SHA-256 (256-бит) имеет 128-битную коллизионную стойкость.
Вероятностный метод Эрдёша (1947): если случайный объект из некоторого вероятностного пространства имеет нужное свойство с положительной вероятностью - объект с этим свойством существует. Применение: раскраска $K_n$ в 2 цвета без монохроматической клики $K_k$ существует при $n < 2^{k/2}$. Конструктивный поиск таких раскрасок - открытая задача для больших $k$.
Вероятностные структуры данных
Bloom-фильтр хранит множество в битовом массиве размера $m$, используя $k$ хэш-функций. Элемент добавляется установкой $k$ битов; проверка - все $k$ битов установлены? Ложноотрицательных ответов нет (элемент в множестве = все биты установлены). Ложноположительные: $P_{FP} \approx (1/2)^k$ при оптимальном $m/n \approx 1.44 k$. При 1% FP достаточно ~9.6 бит на элемент против ~64 бит для хэш-таблицы.
Bloom-фильтр не поддерживает удаление элементов в базовой версии - сброс бита может затронуть другие элементы. Для удаления используют Counting Bloom Filter (заменяет биты счётчиками) или Cuckoo Filter, который при том же FP rate использует меньше памяти.
Пол Эрдёш - самый плодовитый математик XX века (>1500 статей, ~511 соавторов)
Пол Эрдёш - самый плодовитый математик XX века (>1500 статей, ~511 соавторов). Вероятностный метод он изобрёл в 1947 году, доказав нижние оценки на числа Рамсея. Число Эрдёша - расстояние до него в графе соавторства - стало математическим фольклором. Эрдёш говорил: «Математик - это машина, превращающая кофе в теоремы».
Пространство исходов и парадокс дней рождения
Quicksort со случайным выбором pivot: ожидаемое число сравнений O(n log n) - вот вероятностный анализ алгоритмов. Bloomberg Terminal в 2013 году упал из-за ошибки в random number generator их торговой системы. Дискретная вероятность - это не абстракция, это баги в production.
Аксиомы Колмогорова: P(A) >= 0, P(Omega) = 1, P(A union B) = P(A)+P(B) при A,B несовместных. Всё остальное выводится: P(A^c) = 1 - P(A), P(A union B) = P(A) + P(B) - P(A intersect B), P(empty) = 0.
Birthday bound объясняет длину digest в современных hash функциях. Нужно 2^128 операций для взлома? Делай digest 256 бит (2^128 = 2^{256/2}). MD5 (128 бит): достаточно 2^64 - это уже взломано (Flame malware, 2012, Microsoft certificate collision).
SHA-1 имеет 160-бит digest. Сколько хешей нужно для 50% вероятности коллизии?
Парадокс дней рождения: вероятность коллизии в пространстве N достигает 50% после sqrt(N) попыток. Для SHA-1 с N=2^160: 2^80. На GPU это ~30 лет, но SHAttered (2017) использует структуру SHA-1 и снижает сложность до 2^63.
Линейность ожидания: мощный инструмент
E[X+Y] = E[X] + E[Y] даже если X и Y зависимы. Это контринтуитивно и невероятно мощно. Анализ Quicksort, хеш-таблиц, skip-lists - всё через линейность ожидания. Без этого инструмента анализ рандомизированных алгоритмов был бы невозможен.
Анализ хеш-таблиц: E[число элементов в ячейке] = n/m при n элементах и m ячейках (load factor alpha). E[время поиска] = O(1 + alpha). При alpha = O(1): O(1) поиск. Вывод через линейность: E[элементов в ячейке j] = sum_i P(i попадает в j) = n/m.
Почему линейность ожидания работает даже для зависимых случайных величин?
Доказательство прямое: E[X+Y] раскладывается через совместное распределение P(X=x,Y=y). Маргинализация по одной переменной даёт P(X=x) и P(Y=y) независимо от зависимости между X и Y. Ковариация входит только в E[X*Y].
Вероятностный метод: существование через случайность
Erdos, 1947: если случайный граф имеет некоторое свойство с положительной вероятностью, то граф с таким свойством существует. Метод доказывает существование объекта, не конструируя его явно. Числа Рамсея, низкохроматические графы с большим обхватом, expander graphs в криптографии.
Применение в computer science: expander graphs (используются в error-correcting codes и routing). Доказательство существования expanders через вероятностный метод - затем только потом найдены эффективные конструкции (Ramanujan graphs, zigzag product). Сначала - вероятностный аргумент, потом - явная конструкция.
В чём суть вероятностного метода доказательства существования?
Вероятностный метод Эрдёша - неконструктивный: если случайный объект имеет нужное свойство с вероятностью > 0, то такой объект существует. Пространство вероятностей непусто на этом событии, значит событие реализуемо.
Рандомизированные алгоритмы: Quicksort, Bloom filter, MinHash
Bloom filter в Apache Cassandra, Redis и BigTable: тест принадлежности множеству за O(1), без хранения элементов. False positive rate контролируется теорией вероятности. MinHash в Spotify для рекомендаций: оценка Jaccard similarity за O(1) вместо O(n).
MinHash в LSH (Locality-Sensitive Hashing): Spotify и YouTube используют LSH для поиска похожих песен/видео в базе из миллиардов элементов. Точный поиск O(n*d) невозможен. MinHash+LSH: O(n^{1/rho}) где rho < 1 зависит от параметров. На практике - миллисекунды вместо часов.
Почему P(MinHash(A) = MinHash(B)) = J(A,B) - ключевое свойство MinHash?
MinHash(S) = min h(e) для e in S. MinHash(A) = MinHash(B) тогда и только тогда, когда элемент с минимальным хешем в A union B принадлежит обоим - т.е. лежит в A intersect B. Вероятность этого = |A intersect B|/|A union B| = J(A,B).
Линейность ожидания: задача о шляпах
N человек сдают шляпы. Сколько в среднем получат свою? Пусть $X_i = 1$ если $i$-й получает свою шляпу. $E[X_i] = 1/n$. По линейности: $E[\sum X_i] = \sum E[X_i] = n \cdot (1/n) = 1$. Независимо от $n$! Линейность работает даже для зависимых $X_i$ - это её главная сила. В задачах ML: ожидаемое число ошибок суммируется по отдельным примерам.
Итоги
- Парадокс дня рождения объясняет коллизионную стойкость хэш-функций.
- Линейность ожидания работает для зависимых переменных и упрощает большинство вычислений.
- Вероятностный метод доказывает существование без конструкции.
- Bloom-фильтр и MinHash - промышленные применения дискретной вероятности.
Связь с другими темами
Вероятностный метод тесно связан с теорией графов (dm-18): многие комбинаторные утверждения о графах доказываются именно через случайные конструкции. В ML вероятностные структуры данных появляются в системах рекомендаций, дедупликации и approximate nearest neighbor поиске.
- Dm 18 — связан
Вопросы для размышления
- MinHash утверждает: $P(\min_h(A) = \min_h(B)) = |A \cap B|/|A \cup B|$. Попробуйте доказать это от первых принципов: рассмотрите случайный порядок элементов $A \cup B$ и найдите вероятность того, что минимальный элемент принадлежит $A \cap B$.?