315
ПРЕДПОЛОЖЕНИЕ A.14 (граница Чернова) Зафиксируем ε>0 и b∈
{0, 1}, и пусть
{Xi} будут независимыми 0/1-случайными величинами Pr[Xi = b] = 1/2 + ε для всех i. Веро-
ятность того, что значение большинства из них b составляет не более e−ε m/2.
Проблема «парадокса дней рождения»
Если выбрать q элементов y1, . . . , yq равномерно из множества размера N ,
то какова вероятность того, что существуют различные i, j при yi = yj ? Мы на-
зываем указанное событие коллизией и обозначаем вероятность этого события
как coll(q, N ).
Эта проблема относится к, так называемому, парадоксу дней
рождения, когда задают вопрос о том, какого размера группа людей нужна, что-
бы с вероятностью 1/2 у некой пары людей в группе совпадал день рождения.
Чтобы увидеть это отношение, пусть yi обозначает день рождения i-го человека
в группе. Если в
группе есть q человек, то мы имеем q значений y1, . . . , yq вы-
бранных равномерно из {1, . . . , 365}, делая упрощающее предположение, что
дни рождения равномерно и независимо распределены среди 365 дней не висо-
косного года. Кроме того, совпадающие дни рождения соответствуют коллизии,
т.е., отличию i, j при yi = yj. Таким образом, нужное решение для пробле-
мы дней рождения задается минимальным (целым) значением q, для которого
coll(q, 365) ≥ 1/2. (Ответ может удивить—достаточно q = 23 человек!)
В этом разделе мы докажем нижние и верхние границы coll(q, N ). Взятые
вместе и обобщенные на высоком уровне, они показывают, что если q <√N, то
вероятность коллизии составляет Θ(q2/N ); иначе, для q = Θ(√N) вероятность
коллизии является константой.
Верхнюю границу для вероятности коллизии легко получить.
Достарыңызбен бөлісу: