Описание тега birthday-paradox

Описание тега Вопросы с тегом

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

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

Обзор

Первоначально проблема определялась как вероятность того, что любые два человека в комнате живут в один день рождения. Ключевым моментом является то, что любые два человека в комнате могут иметь один день рождения. Люди склонны наивно неверно истолковывать проблему как вероятность того, что кто-то в комнате разделит день рождения с конкретным человеком, что является источником когнитивной предвзятости, которая часто заставляет людей недооценивать вероятность. Это неверное предположение - совпадение не обязательно с конкретным человеком, и любые два человека могут совпадать.

Вероятность совпадения между любыми двумя людьми намного выше, чем вероятность совпадения с конкретным человеком, поскольку совпадение не обязательно должно быть до определенной даты. Скорее всего, вам нужно найти только двух людей с одинаковым днем рождения. Из этого графика (который можно найти на странице википедии по этой теме) мы видим, что нам нужно всего 23 человека в комнате, чтобы с 50% вероятностью найти двух таких совпадений таким образом.

Некоторые приложения

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

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