Задача о дне рождения

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

В теория вероятности, проблема дня рождения или парадокс дня рождения касается вероятности, того что в наборе из n случайно выбранных людей, у некоторых из них будет один и тот же день рождения. Согласно принципу «голубятни», вероятность достигает 100%, когда число людей достигает 367 (поскольку существует только 366 преступников дней рождения, включая 29 февраля ). Однако вероятность 99,9% достигается всего с 70 людьми, а вероятность 50% - с 23 людьми. Эти выводы основаны на предположении, что каждый день в году (кроме 29 февраля) одинаково вероятен для дня рождения.

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

Может показаться удивительным, что группа всего из 23 человек требуется для достижения 50% вероятности того, что хотя бы два человека в группе имеют один и тот же день рождения: этот результат, возможно, станет более правдоподобным, если учесть, что сравнение дней рождения будет фактически сделано между всеми возможными парами людей = 23 × 22/2 = 253 сравнений, что намного больше половины количества дней в году (не более 183), в отличие от фиксации на одном человеке и сравнивая свой день рождения с днем рождения всех остальных. Проблема дня рождения не является «парадоксом » в буквальном логическом смысле противоречащей самому себе, но на первый взгляд просто не интуитивно понятна.

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

История проблемы неясна. Результат был приписан Гарольду Дэвенпорту ; однако версия того, что сегодня считается считается дня рождения, была предложена ранее Ричардом фон Мизесом.

• 1 Вычисление вероятности
• 2 Приближение
  • 2.1 Простое возведение в степень
  • 2.2 Аппроксимация Пуассона
  • 2.3 Квадратная аппроксимация
  • 2.4 Аппроксимация количества людей
  • 2.5 Таблица вероятностей
• 3 Верхняя граница вероятности и нижняя граница количества людей
• 4 Обобщения
  • 4.1 Общая проблема дня рождения
  • 4.2 Более двух человек
  • 4.3 Отражение как проблема столкновения
    • 4.3.1 Обобщение на несколько типов
• 5 Другие проблемы дня рождения
  • 5.1 Первое совпадение
  • 5.2 В тот же день рождения, что и вы
  • 5.3 Почти совпадения
  • 5.4 Подсчет столкновений
  • 5.5 Среднее количество людей
  • 5.6 Обратная задача
• 6 Проблема разделения
• 7 В художественной литературе
• 8 Примечания
• 9 Ссылки
• 10 Библиография <49>11 Внешние ссылки

Задача состоит в т ом, чтобы вычислить приблизительную вероятность того, что в группе из n человек, по крайней, двое одинаковый день рождения. Для простоты отклонения в распределении, таких как високосные годы, близнецы, сезонные изменения или вариации дня недели, не учитываются, что все 365 дней рождения равновероятны. (Распределение дней рождения в реальной жизни не является однородным, поскольку не все даты одинаково вероятны, но эти отклонения мало влияет на анализ. На самом деле, равномерное распределение дат рождения - худший случай.)

Цель в вычислении P (A), вероятности того, что по крайней мере два человека в комнате имеют одинаковый день рождения. Однако проще вычислить P (A ′), вероятность того, что у двух человек в комнате нет одного дня рождения. Тогда, поскольку A и A ′ - единственные возможности, а также взаимоисключающие, P (A) = 1 - P (A ′).

В соответствии с широко опубликованными решениями, согласно которому 23 человека - это минимальное количество людей, необходимое для того, чтобы P (A) превышал 50%, следующий расчет P (A) будет использовать 23 человека в качестве примера. Если пронумеровать 23 человека от 1 до 23, событие , что у всех 23 человек разные дни рождения, совпадает с событием, когда у человека 2 не тот же день рождения, что у человека 1, а у этого человека 3 есть не имеют того же дня рождения, что и человек 1 или человек 2, и, наконец, этот человек 23 не имеет того же дня рождения, что и любой из лиц с 1 по 22. «Событие 2», «Событие 3» ", и так далее. Также добавить« Событие 1 », событие дня рождения человека 1, которое происходит с вероятностью 1. Это сочетание событий может быть вычислено с использованием условной вероятности : вероятность события 2 равна 364/365, поскольку у человека 2 может быть любой день рождения, кроме дня рождения человека 1. Точно так же вероятность События 3 с учетом того, что Событие 2 произошло, составляет 363/365, поскольку у человека 3 может быть любой из дней рождения, которые еще не зарегистрированы людьми. 1 и 2. Это продолжается до тех пор, пока, наконец, вероятность события 23, учитывая, что все предыдущие события произошли, составляет 343/365. Наконец, принцип условной вероятности подразумевает, что P (A ′) равно произведению этих индивидуальных вероятностей:

$P\; (A\; \prime )\; =\; 365\; 365\; \times \; 364\; 365\; \times \; 363\; 365\; \times \; 362\; 365\; \times \; \cdots \; \times \; 343\; 365\; \{\backslash \; displaystyle\; P\; (A\; \text{'})\; =\; \{\backslash \; frac\; \{365\}\; \{365\}\}\; \backslash \; times\; \{\backslash \; frac\; \{364\}\; \{365\}\}\; \backslash \; times\; \{\backslash \; frac\; \{363\}\; \{365\}\}\; \backslash \; times\; \{\backslash \; frac\; \{362\}\; \{365\}\}\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; \{\backslash \; frac\; \{343\}\; \{365\}\}\}$

(1)

Из членов уравнения (1) можно получить:

$P\; (A\; \prime )\; =\; (1\; 365)\; 23\; \times \; (365\; \times \; 364\; \times \; 363\; \times \; \cdots \; \times \; 343)\; \{\backslash \; displaystyle\; P\; (A\; \text{'})\; =\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{365\}\}\; \backslash \; right)\; ^\; \{23\}\; \backslash \; times\; (365\; \backslash \; times\; 364\; \backslash \; times\; 363\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; 343)\}$

(2)

Вычисление уравнения (2) дает P (A ') ≈ 0,492703

Следовательно, P (A) ≈ 1 - 0,492703 = 0,507297 (50,7297%).

Этот процесс можно обобщить на группе из n человек, где p (n) - это вероятность того, что по крайней мере двое из n человек будут праздновать день рождения. Проще сначала вычислить вероятность p (n) того, что все n дней рождения разные. В соответствии с принципом, p (n) равно нулю, когда n>365. Когда n ≤ 365:

$p\; ¯\; (n)\; =\; 1\; \times \; (1–1\; 365)\; \times \; (1–2\; 365)\; \times \; \cdots \; \times \; (1\; -\; n\; -\; 1\; 365)\; =\; 365\; \times \; 364\; \times \; \cdots \; \times \; (365\; -\; п\; +\; 1)\; 365\; п\; =\; 365!\; 365\; н\; (365\; -\; н)!\; =\; п!\; \cdot \; (365\; n)\; 365\; n\; =\; 365\; P\; n\; 365\; n\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; bar\; \{p\}\}\; (n)\; =\; 1\; \backslash \; times\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{1\}\; \{365\; \}\}\; \backslash \; right)\; \backslash \; times\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{2\}\; \{365\}\}\; \backslash \; right)\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{n-1\}\; \{365\}\}\; \backslash \; right)\; \backslash \backslash \; [6pt]\; =\; \{\backslash \; frac\; \{365\; \backslash \; times\; 364\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; (365-n\; +\; 1)\}\; \{365\; ^\; \{n\}\}\}\; \backslash \backslash \; [6pt]\; =\; \{\backslash \; frac\; \{365\; !\}\; \{365\; ^\; \{n\}\; (365-n)!\}\}\; =\; \{\backslash \; Frac\; \{n!\; \backslash \; Cdot\; \{\backslash \; binom\; \{365\}\; \{n\}\}\}\; \{365\; ^\; \{n\}\}\}\; =\; \{\backslash \; frac\; \{\_\; \{365\}\; P\_\; \{n\}\}\; \{365\; ^\; \{n\}\}\}\; \backslash \; end\; \{align\}\}\}$

где! - оператор факториала, (. n)- биномиальный коэффициент и kPrобозначает перестановку.

Уравнение выражает тот факт, что первому человеку не с кем поделиться день рождения, у второго человека не может быть того же дня рождения, что и у первого (364/365), у третьего не может быть того же дня рождения, что у любого из первых двух (363/365), и в целом n-й день рождения не может совпадать с днем ​​рождения любой из n - 1 предшествующих дней рождения.

Событие по меньшей мере двух из n лиц, имеющих один и тот же день рождения, дополняет всем n разным дням рождения. Следовательно, его вероятность p (n) равна

$p\; (n)\; =\; 1\; -\; p\; ¯\; (n).\; \{\backslash \; displayst\; p\; (n)\; =\; 1\; -\; \{\backslash \; bar\; \{p\}\}\; (n).\}$

В этой таблице есть вероятность некоторых других значений n (для этой таблицы високосных лет игнорируется, и обяз, что каждый день рождения является равновероятным):

Вероятность того, что в группе из n человек не бывает дня рождения. Обратите внимание, что вертикальная шкала является логарифмической (каждый шаг вниз на 10 менее вероятен).

n	p (n)
1	00,0%
5	02,7%
10	11,7%
20	41,1%
23	50,7%
30	70,6%
40	89,1%
50	97,0%
60	99,4%
70	99,9%
75	99,97%
100	99,99997%
200	99.9999999999999999999999999998%
300	(100-6 × 10)%
350	(100 - 3 × 10)%
365	(100 - 1,45 × 10)%
≥ 366	100%

Високосные годы . Если мы заменим 366 на 365 в формуле для $p\; ¯\; (n)\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{p\}\}\; (n)\}$, аналогичный расчет покажет, что для високосных лет число людей, необходимых для вероятности совпадения более 50%, также 23; вероятность совпадения в этом случае составляет 50,6%.

Графики, приблизительную вероятность того, что показательная мере два человека разделяют день рождения (красный) и дополнительное средство (синий) График, обеспечивающий точность приближения 1 - e (красный)

Разложение в ряд Тейлора экспоненциальной функции (константа e ≈ 2,718281828)

$ex\; =\; 1\; +\; x\; +\; x\; 2\; 2!\; +\; \cdots \; \{\backslash \; displaystyle\; e\; ^\; \{x\}\; =\; 1\; +\; x\; +\; \{\backslash \; frac\; \{x\; ^\; \{2\}\}\; \{2!\}\}\; +\; \backslash \; Cdots\}$

обеспечивает приближение первого порядка для e для $|\; х\; |\; \ll \; 1\; \{\backslash \; displaystyle\; |\; х\; |\; \backslash \; ll\; 1\}$:

$е\; х\; \approx \; 1\; +\; х.\; \{\backslash \; displaystyle\; e\; ^\; \{x\}\; \backslash \; приблизительно\; 1\; +\; x.\}$

Чтобы применить это приближение к первому выражению, полученному для p (n), установить x = −a / 365. Таким образом,

$e\; -\; a\; /\; 365\; \approx \; 1\; -\; a\; 365.\; \{\backslash \; displaystyle\; e\; ^\; \{-\; a\; /\; 365\}\; \backslash \; приблизительно\; 1\; -\; \{\backslash \; frac\; \{a\}\; \{365\}\}.\}$

Затем замените неотрицательными целыми числами для каждого члена в формуле p (n) пока a = n - 1, например, когда a = 1,

$e\; -\; 1/365\; \approx \; 1\; -\; 1365.\; \{\backslash \; displaystyle\; e\; ^\; \{-\; 1/365\}\; \backslash \; приблизительно\; 1\; -\; \{\backslash \; frac\; \{1\; \}\; \{365\}\}.\}$

Первое выражение, полученное для p (n), можно аппроксимировать как

$p\; ¯\; (n)\; \approx \; 1\; \cdot \; e\; -\; 1/365\; \cdot \; e\; -\; 2/365\; \cdots \; e\; -\; (n\; -\; 1)\; /\; 365\; =\; е\; -\; (1\; +\; 2\; +\; \cdots \; +\; (n\; -\; 1))\; /\; 365\; =\; e\; -\; (n\; (n\; -\; 1)\; /\; 2)\; /\; 365\; =\; e\; -\; n\; (n\; -\; 1)\; /\; 730.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; bar\; \{p\}\}\; (n)\; \backslash \; приблизительно\; 1\; \backslash \; cdot\; e\; ^\; \{-\; 1/365\}\; \backslash \; cdot\; e\; ^\; \{-\; 2/365\}\; \backslash \; cdots\; e\; ^\; \{-\; (\; n-1)\; /\; 365\}\; \backslash \backslash \; [6pt]\; =\; e\; ^\; \{-\; \backslash \; left.\; \{\backslash \; big\; (\}\; 1\; +\; 2\; +\; \backslash ,\; \backslash \; cdots\; \backslash ,\; +\; (n-1)\; \{\backslash \; big)\}\; \backslash \; right\; /\; 365\}\; \backslash \backslash \; [6pt]\; =\; e\; ^\; \{-\; (n\; (n-1)\; /\; 2)\; /\; 365\}\; =\; e\; ^\; \{-\; n\; (n-1)\; /\; 730\}.\; \backslash \; End\; \{align\}\}\}$

Следовательно,

$p\; (n)\; =\; 1\; -\; p\; ¯\; (n)\; \approx \; 1\; -\; e\; -\; n\; (n\; -\; 1)\; /\; 730.\; \{\backslash \; displaystyle\; p\; (n)\; =\; 1\; -\; \{\backslash \; bar\; \{p\}\}\; (n)\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; (n-1)\; /\; 730\}.\}$

Еще более грубое приближение дается выражением

$p\; (n)\; \approx \; 1\; -\; e\; -\; n\; 2/730,\; \{\backslash \; displaystyle\; p\; (n)\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; ^\; \{2\}\; /\; 730\},\}$

что, как показано на графике, по-прежнему довольно точен.

Согласно подходу к любому количеству «людей» и «дней». Если 365 дней есть d, если есть n человек и если n ≪ d, то используя тот же подход, что и выше, мы достигаем результата, что если p (n, d) - это вероятность того, что по крайней мере двое из n у людей один и тот же день рождения из d доступных, тогда:

$p\; (n,\; d)\; \approx \; 1\; -\; e\; -\; n\; (n\; -\; 1)\; /\; (2\; d)\; \approx \; 1\; -\; e\; -\; n\; 2\; /\; (2\; г).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; p\; (n,\; d)\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; (n-1)\; /\; (2d)\}\; \backslash \backslash \; [6pt]\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; ^\; \{2\}\; /\; (2d)\}.\; \backslash \; End\; \{align\}\}\}$

Простое возведение в степень

Вероятность того, что у любых двух людей не один и тот же день рождения, равна 364/365. В комнате, содержащей n человек, есть (. 2)= n (n - 1) / 2 пар людей, то есть (. 2)событий. Вероятность того, что у двух людей не будет одного дня рождения, можно оценить предположив, что эти события, и, следовательно, умножив их вероятность вместе. Короче говоря, 364/365 можно умножить само на себя в (. 2)раз, что дает нам

$p\; ¯\; (n)\; \approx \; (364\; 365)\; (n\; 2).\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{p\}\}\; (n)\; \backslash \; приблизительно\; \backslash \; left\; (\{\backslash \; frac\; \{364\}\; \{365\}\}\; \backslash \; right)\; ^\; \{\backslash \; binom\; \{n\}\; \{2\}\}.\}$

Времена это вероятность того, что ни у кого не будет одного дня рождения, тогда вероятность того, что кто-то разделит день рождения, составляет

$p\; (n)\; \approx \; 1\; -\; (364\; 365)\; (n\; 2).\; \{\backslash \; displaystyle\; p\; (n)\; \backslash \; приблизительно\; 1-\; \backslash \; left\; (\{\backslash \; frac\; \{364\}\; \{365\}\}\; \backslash \; right)\; ^\; \{\backslash \; binom\; \{n\}\; \{2\}\}.\}$

Пуассоновское приближение

Применяя приближение Пуассона для бинома к из 23 человек,

$Poi\; \; ((23\; 2)\; 365)\; =\; Poi\; \; (253\; 365)\; \approx \; Poi\; \; (0,6932)\; \{\backslash \; displaystyle\; \backslash \; OperatorName\; \{Poi\; \}\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; binom\; \{23\}\; \{2\}\}\; \{365\}\}\; \backslash \; right)\; =\; \backslash \; operatorname\; \{Poi\}\; \backslash \; left\; (\{\backslash \; frac\; \{253\}\; \{365\}\}\; \backslash \; right)\; \backslash \; приблизительно\; \backslash \; operatorname\; \{Poi\}\; (0,6932)\}$

, поэтому

$Pr\; (X>0)\; =\; 1\; -\; Pr\; (X\; =\; 0)\; \approx \; 1\; -\; e\; -\; 0,6932\; \approx \; 1\; -\; 0,499998\; =\; 0,500002.\; \{\backslash \; displaystyle\; \backslash \; Pr\; (X>0)\; =\; 1-\; \backslash \; Pr\; (X\; =\; 0)\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; 0,6932\}\; \backslash \; приблизительно\; 1-0,499998\; =\; 0,500002.\}$

Результат более чем на 50% Это приближение такое же, как и приведенное выше, основанное на расширении Тейлора, в котором используется $ex\; \approx \; 1\; +\; x\; \{\backslash \; displaystyle\; e\; ^\; \{x\}\; \backslash \; приблизительно\; 1\; +\; x\}$.

Квадратное приближение

Хорошее практическое правило, которое можно использовать для мысленных вычислений - это отношение

$p\; (n)\; \approx \; n\; 2\; 2\; m\; \{\backslash \; displaystyle\; p\; (n)\; \backslash \; приблизительно\; \{\backslash \; frac\; \{n\; ^\; \{2\}\}\; \{2m\}\}\}$

, которое также можно записать как

$n\; \approx \; 2\; м\; \times \; p\; (n)\; \{\backslash \; displaystyle\; n\; \backslash \; приблизительно\; \{\backslash \; sqrt\; \{2m\; \backslash \; times\; p\; (n)\}\}\}$

, что хорошо работает для вероятностей, меньших или равных 1/2. в этих уравнениях m - количество дней в году.

Например, чтобы оценить количество людей, необходимых для 1/2 ch После общего дня рождения мы получаем

$n\; \approx \; 2\; \times \; 365\; \times \; 1\; 2\; =\; 365\; \approx \; 19\; \{\backslash \; displaystyle\; n\; \backslash \; приблизительно\; \{\backslash \; sqrt\; \{2\; \backslash \; times\; 365\; \backslash \; times\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\}\}\; =\; \{\backslash \; sqrt\; \{365\}\}\; \backslash \; приблизительно\; 19\}$

Что не так уж далеко от правильного ответа 23.

Приблизительное количество людей

Это также может быть использование следующего формулу для количества людей, необходимого для того, чтобы иметь хотя бы 1/2 шанса совпадения:

$n\; \approx \; 1\; 2\; +\; 1\; 4\; +\; 2\; \times \; ln\; \; (2)\; \times \; 365\; =\; 22,999943.\; \{\backslash \; displaystyle\; n\; \backslash \; приблизительно\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; +\; \{\backslash \; sqrt\; \{\{\backslash \; tfrac\; \{1\}\; \{4\}\}\; +\; 2\; \backslash \; times\; \backslash \; ln\; (2)\; \backslash \; times\; 365\}\}\; =\; 22,999943.\; \}$

Это результат хорошего приближения, соответствующего которому с вероятностью 1 / k будет иметь 1/2 шанса произойти хотя бы один раз, если оно повторяется k ln 2 раз.

Таблица вероятностей

длина. шестнадцатеричной строки	№. из. бит. (b)	хэш-пространство. размер. (2)	Количество хешированных элементов, такая что вероятность хотя бы одного хэш-коллизии ≥ p
			p = 10	p = 10	p = 10	p = 10	p = 10	p = 0,001	p = 0,01	p = 0,25	p = 0,50	p = 0,75
8	32	4,3 × 10	2	2	2	2,9	93	2,9 × 10	9,3 × 10	5,0 × 10	7,7 × 10	1,1 × 10
(10)	(40)	(1,1 × 10)	2	2	2	47	1,5 × 10	4,7 × 10	1,5 × 10	8,0 × 10	1,2 × 10	1,7 × 10
(12)	(48)	(2,8 × 10)	2	2	24	7,5 × 10	2,4 × 10	7,5 × 10	2,4 × 10	1,3 × 10	2,0 × 10	2,8 × 10
16	64	1, 8 × 10	6,1	1,9 × 10	6,1 × 10	1,9 × 10	6,1 × 10	1,9 × 10	6,1 × 10	3,3 × 10	5,1 × 10	7,2 × 10
(24)	(96)	(7,9 × 10)	4. 0 × 10	1,3 × 10	4,0 × 10	1,3 × 10	4,0 × 10	1,3 × 10	4,0 × 10	2,1 × 10	3,3 × 10	4,7 × 10
32	128	3,4 × 10	2,6 × 10	8,2 × 10	2,6 × 10	8,2 × 10	2,6 × 10	8,3 × 10	2,6 × 10	1,4 × 10	2,2 × 10	3,1 × 10
(48)	(192)	(6,3 × 10)	1,1 × 10	3,5 × 10	1,1 × 10	3,5 × 10	1,1 × 10	3,5 × 10	1,1 × 10	6,0 × 10	9,3 × 10	1,3 × 10
64	256	1,2 × 10	4,8 × 10	1, 5 × 10	4,8 × 10	1,5 × 10	4,8 × 10	1,5 × 10	4,8 × 10	2,6 × 10	4,0 × 10	5,7 × 10
(96)	(384)	(3,9 × 10)	8,9 × 10	2,8 × 10	8, 9 × 10	2,8 × 10	8,9 × 10	2,8 × 10	8,9 × 10	4,8 × 10	7,4 × 10	1,0 × 10
128	512	1,3 × 10	1,6 × 10	5,2 × 10	1,6 × 10	5,2 × 10	1,6 × 10	5,2 × 10	1,6 × 10	8,8 × 10	1,4 × 10	1,9 × 10

Более светлые поля в этой таблице показывают количество хешей необходимо для достижения заданной вероятности столкновения (столбец) с заданным хеш-пространством определенного размера в битах (строка). Используя аналог с днем ​​рождения: «размер хеш-пространства» похож на «доступные дни», «вероятность столкновения» похожа на «вероятность общего дня рождения», а «необходимое количество хешированных элементов» похоже на «необходимое количество людей в группе». Также использовать эту диаграмму для определения минимального размера хэша (с учетом верхних границ хэшей и вероятности ошибки) или вероятности коллизии (для фиксированного количества хешей и вероятности ошибки).

Для сравнения, от 10 до 10 - это Теоретически 128-битные хэш-функции, такие как MD5, должны оставаться в этом диапазоне примерно до 8,2 × 10 документов, даже если их использует выходов намного больше.>

Приведенный ниже аргумент адаптирован из аргумента Пола Халмоса.

Как указано выше, вероятность что никакие два дня рождения не совпадают адают, это

$1\; -\; p\; (n)\; =\; p\; ¯\; (n)\; =\; \prod \; k\; =\; 1\; n\; -\; 1\; (1\; -\; k\; 365).\; \{\backslash \; displaystyle\; 1-p\; (n)\; =\; \{\backslash \; bar\; \{p\}\}\; (n)\; =\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n-1\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{k\}\; \{365\}\}\; \backslash \; right).\}$

Как и в предыдущих параграфах, представляет интерес наименьшее n такое, что p (n)>1/2; или, что то же самое, наименьшее n такое, что p (n) < 1/2.

Используя неравенство 1 - x < e in the above expression we replace 1 − k/365 with e. This yields

Следовательно, выражение выше является не только приближением, но также границей p (n). Из неравенства

следует p (n) < 1/2. Solving for n gives

$n\; 2\; -\; n>730\; ln\; \; 2.\; \{\backslash \; displaystyle\; n\; ^\; \{2\}\; -n>730\; \backslash \; ln\; 2.\}$

Теперь 730 ln 2 составляет примерно 505,997, что чуть меньше 506, значение n - n достигается при n = 23. Следовательно, 23 человека достаточно. n дает приблизительную формулу Фрэнка Х. Мэтиса, процитированную выше.

Этот вывод показывает только, что для обеспечения совпадения по случаю дня рождения с равной вероятностью требуется не более 23 человек;

Обобщенная задача дня рождения

Учитывая год с d днями, обобщенная задача дня рождения запрашивает минимальное число n (d) такое, что в наборе из n случайно выб ранных людей вероятность совпадения днейрождения не менее т 50%. Другими словами, n (d) - это минимальное целое число n такое, что

$1\; -\; (1\; -\; 1\; d)\; (1-2\; d)\; \cdots \; (1\; -\; n\; -\; 1\; d)\; \ge \; 1\; 2.\; \{\backslash \; displaystyle\; 1\; -\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{1\}\; \{d\}\}\; \backslash \; right)\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{2\}\; \{d\}\}\; \backslash \; right)\; \backslash \; cdots\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{n-\; 1\}\; \{d\}\}\; \backslash \; right)\; \backslash \; geq\; \{\backslash \; frac\; \{1\}\; \{2\}\}.\}$

Таким образом, классическая задача дня рождения соответствует определению n (365). Здесь приведены первые 99 значений n (d) (последовательность A033810 в OEIS ):

d	1–2	3–5	6 –9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
n (d)	2	3	4	5	6	7	8	9	10	11	12

Аналогичный расчет показывает, что n (d) = 23, когда d находится в диапазоне 341–372.

Был опубликован ряд оценок и формул для n (d). Для любого d ≥ 1 число n (d) удовлетворяет

Эти границы оптимальны в том смысле, что последовательность n (d) - √2d ln 2 становится сколь угодно близкой к

$3\; -\; 2\; ln\; \; 2\; 6\; \approx \; 0,27,\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{3-2\; \backslash \; ln\; 2\}\; \{6\}\}\; \backslash \; приблизительно\; 0,27,\}$

, в то время как у него

$9\; -\; 86\; ln\; \; 2\; \approx \; 1,28\; \{\backslash \; displaystyle\; 9\; -\; \{\backslash \; sqrt\; \{86\; \backslash \; ln\; 2\}\}\; \backslash \; приблизительно\; 1,28\}$

в качестве максимума, взятого для d = 43.

Границы достаточно жесткие, чтобы дать точное значение n (d) в 99% всех случаев, например, n (365) = 23. В общем, из этих оценок следует, что n (d) всегда равно либо

$\lceil \; 2\; d\; ln\; \; 2\; \rceil ,\; либо\; \lceil \; 2\; d\; пер\; \; 2\; \rceil \; +\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; \backslash ,\; \backslash \; right\; \backslash \; rceil\; \backslash \; quad\; \{\backslash \; text\; \{или\}\}\; \backslash \; quad\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; \backslash ,\; \backslash \; right\; \backslash \; rceil\; +1\}$

где ⌈ · ⌉ обозначает функцию потолка. Формула

$n\; (d)\; =\; \lceil \; 2\; d\; ln\; \; 2\; \rceil \; \{\backslash \; displaystyle\; n\; (d)\; =\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; \backslash ,\; \backslash \; right\; \backslash \; rceil\}$

для 73 % всех целых чисел d. Формула

$n\; (d)\; =\; \lceil \; 2\; d\; ln\; \; 2\; +\; 3\; -\; 2\; ln\; \; 2\; 6\; \rceil \; \{\backslash \; displaystyle\; n\; (d)\; =\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; +\; \{\backslash \; frac\; \{3-2\; \backslash \; ln\; 2\}\; \{6\}\}\; \backslash \; right\; \backslash \; rceil\}$

выполняется для почти всех d, т. е. для набора целых чисел d с асимптотической плотностью 1.

Формула

$n\; (d)\; =\; \lceil \; 2\; d\; ln\; \; 2\; +\; 3\; -\; 2\; ln\; \; 2\; 6\; +\; 9-4\; (ln\; \; 2)\; 2\; 72\; 2\; d\; пер\; \; 2\; \rceil \; \{\backslash \; displaystyle\; n\; (d)\; =\; \backslash \; слева\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; +\; \{\backslash \; frac\; \{3-2\; \backslash \; ln\; 2\}\; \{6\}\}\; +\; \{\backslash \; frac\; \{9-4\; (\backslash \; ln\; 2)\; ^\; \{2\}\}\; \{72\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\}\}\; \backslash \; right\; \backslash \; rceil\}$

верно для всех d ≤ 10, но обязана, что бесконечно много контрпримеров к формуле.

Формула

$N\; (d)\; знак\; равно\; \lceil \; 2\; d\; пер\; 2\; +\; 3\; -\; 2\; пер\; \; 2\; 6\; +\; 9-4\; (пер\; \; 2)\; 2\; 72\; 2\; d\; пер\; \; 2-2\; (пер\; 2)\; 2\; 135\; d\; \rceil \; \{\backslash \; Displaystyle\; n\; (d)\; =\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\; +\; \{\backslash \; frac\; \{3-2\; \backslash \; ln\; 2\}\; \{6\}\}\; +\; \{\backslash \; frac\; \{9-\; 4\; (\backslash \; ln\; 2)\; ^\; \{2\}\}\; \{72\; \{\backslash \; sqrt\; \{2d\; \backslash \; ln\; 2\}\}\}\}\; -\; \{\backslash \; frac\; \{2\; (\backslash \; ln\; 2)\; ^\; \{2\}\}\; \{135d\}\}\; \backslash \; right\; \backslash \; rceil\}$

выполнено для всех d ≤ 10, и обязана эта формула верна для всех d.

Более 2 человек

Это p расширить задачу, чтобы спросить, сколько человек в группе необходимо для того, чтобы была более 50% вероятности, что по крайней мере 3/4/5 / и т. д. имеют группы один день рождения.

Первые несколько значений следующих:>50% вероятность того, что 3 человека дадут день рождения - 88 человек;>50% вероятность того, что 4 человека разделят день рождения - 187 человек. Полный список можно найти как последовательность A014088 в онлайн-энциклопедии целочисленных последовательностей.

Отобразить как проблему столкновения

Задачу дня рождения можно обобщить следующим образом:

Дано случайных целых чисел взятый из дискретного равномерного распределения с диапазоном [1, d], какова вероятность p (n; d) того, что по крайней мере два совпадения? (d = 365 дает обычную проблему дня рождения.)

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

$p\; (n;\; d)\; =\; \{1\; -\; \prod \; k\; =\; 1\; n\; -\; 1\; (1\; -\; kd)\; n\; \le \; d\; 1\; n>d\; \approx \; 1\; -\; e\; -\; n\; (n\; -\; 1)\; 2\; d\; \approx \; 1\; -\; (d\; -\; 1\; d)\; n\; (n\; -\; 1)\; 2\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; p\; (n;\; d)\; =\; \{\backslash \; begin\; \{cases\}\; 1-\; \backslash \; displaystyle\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n-\; 1\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{k\}\; \{d\}\}\; \backslash \; right)\; n\; \backslash \; leq\; d\; \backslash \backslash \; 1\; n>d\; \backslash \; end\; \{case\}\}\; \backslash \backslash \; [8px]\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; \{\backslash \; frac\; \{n\; (n-1)\}\; \{2d\}\}\}\; \backslash \backslash \; \backslash \; приблизительно\; 1-\; \backslash \; left\; (\{\backslash \; frac\; \{d-1\}\; \{d\}\}\; \backslash \; right)\; ^\; \{\backslash \; frac\; \{n\; (\; n-1)\}\; \{2\}\}\; \backslash \; end\; \{align\}\}\}$

И наоборот, если n (p; d) обозначает количество случайных целых чисел, взятых из [1, d] для достижения вероятности p того, что хотя бы два числа совпадают, то

$n\; (p;\; d)\; \approx \; 2\; d\; \cdot \; ln\; \; (1\; 1\; -\; п).\; \{\backslash \; Displaystyle\; n\; (p;\; d)\; \backslash \; приблизительно\; \{\backslash \; sqrt\; \{2d\; \backslash \; cdot\; \backslash \; ln\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{1-p\}\}\; \backslash \; right)\}\}.\}$

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

Теория проблемы дня рождения была применена Зои Шнабель под названием статистика отлова-повторной поимки для оценки численности популяции рыб в озерах.

Обобщение на несколько типов

Степень вероятности по крайней мере одного общего дня по крайней мере между одним мужчиной и одной женщиной

Основная оценка считает, что все испытания к одному "типу". Задача дня рождения была обобщена для рассмотрения произвольного числа типов. В простейшем расширении существует два типа людей, скажем, мужчин и женщин, и проблема заключается в том, чтобы характеризовать вероятность общего дня рождения хотя бы одного мужчины и одной женщины. (Общие дни рождения двух мужчин или двух женщин не учитываются.) Вероятность общих дней рождения здесь составляет

$p\; 0\; =\; 1\; dm\; +\; n\; i\; =\; 1\; m\; \sum \; j\; =\; 1\; n\; S\; 2\; (m,\; i)\; S\; 2\; (\; N,\; J)\; \prod \; К\; знак\; равно\; 0\; я\; +\; J\; -\; 1\; d\; -\; К\; \{\backslash \; Displaystyle\; p\_\; \{0\}\; =\; \{\backslash \; frac\; \{1\}\; \{d\; ^\; \{m\; +\; n\}\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{m\}\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{n\}\; S\_\; \{2\}\; (m,\; i)\; S\_\; \{2\}\; (n,\; j)\; \backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{i\; +\; j-1\}\; dk\; \}$

, где d = 365 и S 2 - числа Стирлинга второго рода. Следовательно, желаемая вероятность равна 1 - p 0.

Этот вариант задачи о дне рождения интересен тем, что не существует единственного решения для общего числа людей m + n. Например, обычное значение вероятности 50% реализуется как для группы из 32 человек, состоящей из 16 мужчин и 16 женщин, так и для группы из 49 человек, состоящей из 43 женщин и 6 мужчин.

Первое совпадение

Смежный вопрос: когда люди входят в комнату по одному, кто из них, скорее всего, первым получит в тот же день рождения, что и кто-то уже в номере? То есть для какого максимального значения p (n) - p (n - 1)? Ответ - 20. Если есть приз за первый матч, лучшая позиция в строке - 20-е.

Тот же день рождения, что и вы

Сравнение p (n) = вероятность совпадения дня рождения с q (n) = вероятность совпадения с вашим днем ​​рождения

В задаче о дне рождения ни один из двух человек не выбирается заранее. Напротив, вероятность q (n) того, что кто-то в комнате из n других людей имеет тот же день рождения, что и конкретный человек (например, вы), определяет как

$q\; (n)\; =\; 1\; -\; (365\; -\; 1\; 365)\; n\; \{\backslash \; displaystyle\; q\; (n)\; =\; 1-\; \backslash \; left\; (\{\backslash \; frac\; \{365-1\}\; \{365\}\}\; \backslash \; right)\; ^\; \{n\}\}$

и для общего d на

$q\; (\; п;\; г)\; =\; 1\; -\; (г\; -\; 1\; г)\; п.\; \{\backslash \; displaystyle\; q\; (n;\; d)\; =\; 1-\; \backslash \; left\; (\{\backslash \; frac\; \{d-1\}\; \{d\}\}\; \backslash \; right)\; ^\; \{n\}.\}$

В стандартном случае d = 365, заменяя n = 23 дает около 6,1%, что меньше, чем 1 шанс из 16. Для более чем 50% вероятности того, что у человека в комнате, заполненной, такой же день рождения, как и у вас, n должно быть не менее 253. Это число должно быть не менее 253. Значительно выше, чем 365/2 = 182,5: причина в том, что, вероятно, есть совпадение дней рождения среди других людей в комнате.

Близкие совпадения

Другое обобщение состоит в том, чтобы спросить о вероятности найти хотя бы одну пару в группе из n человек, дни рождения которых находятся в пределах k календарных дней друг от друга, если есть d одинаково вероятных дни рождения.

$p\; (n,\; k,\; d)\; =\; 1\; -\; (d\; -\; nk\; -\; 1)!\; d\; n\; -\; 1\; (d\; -\; n\; (k\; +\; 1))!\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; p\; (n,\; k,\; d)\; =\; 1\; -\; \{\backslash \; frac\; \{(d-nk-1)!\}\; \{d\; ^\; \{n-1\}\; \{\backslash \; bigl\; (\}\; dn\; (k\; +1)\; \{\backslash \; bigr)\}!\}\}\; \backslash \; End\; \{align\}\}\}$

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

k	n. для d = 365
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

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

Подсчет столкновений

Вероятность того, что k-е целое число, случайно выбранное из [1, d], повторит хотя бы один предыдущий выбор, равна q (k - 1; г) выше. Ожидаемое общее количество раз, когда выбор будет повторять предыдущий выбор при выборе n таких целых чисел, равно

$\sum \; k\; =\; 1\; n\; q\; (k\; -\; 1;\; d)\; =\; n\; -\; d\; +\; d\; (d\; -\; 1\; d)\; n.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; q\; (k-1;\; d)\; =\; nd\; +\; d\; \backslash \; left\; (\{\backslash \; frac\; \{d-1\}\; \{d\}\}\; \backslash \; right)\; ^\; \{n\}.\; \}$

Среднее количество людей

В альтернативной формулировке задачи о дне рождения задают среднее количество людей, необходимое для поиска пары с одинаковым днем ​​рождения. Если мы рассмотрим функцию вероятности Pr [n людей имеют хотя бы один общий день рождения], это среднее значение определяет среднее распределение, в отличие от обычной формулировки, медианы. Проблема актуальна для алгоритмов хеширования, проанализированных Дональдом Кнутом в его книге Искусство компьютерного программирования. Может быть показано, что если выполнить выборку однородно, с заменой, из популяции размером M, количество испытаний, необходимое для первой повторной выборки некоторого индивида, будет иметь ожидаемое значение n = 1 + Q (M), где

$Q\; (M)\; =\; \sum \; k\; =\; 1\; мм!\; (М\; -\; к)!\; М\; к.\; \{\backslash \; Displaystyle\; Q\; (M)\; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{M\}\; \{\backslash \; frac\; \{M!\}\; \{(Mk)!\; M\; ^\; \{k\}\}\}.\}$

Функция

$Q\; (М)\; знак\; равно\; 1\; +\; М\; -\; 1\; М\; +\; (М\; -\; 1)\; (М\; -\; 2)\; М\; 2\; +\; \cdots \; +\; (М\; -\; 1)\; (\; М\; -\; 2)\; \cdots \; 1\; ММ\; -\; 1\; \{\backslash \; Displaystyle\; Q\; (M)\; =\; 1\; +\; \{\backslash \; frac\; \{M-1\}\; \{M\}\}\; +\; \{\backslash \; frac\; \{(M-1)\; (M-2)\}\; \{M\; ^\; \{2\}\}\}\; +\; \backslash \; cdots\; +\; \{\backslash \; frac\; \{(M-1)\; (M-2)\; \backslash \; cdots\; 1\}\; \{M\; ^\; \{M-1\}\}\}\}$

было изучено Шринивасой Рамануджаном и имеет асимптотическое разложение :

$Q\; (M)\; \sim \; \pi \; M\; 2\; -\; 1\; 3\; +\; 1\; 12\; \pi \; 2\; M\; -\; 4\; 135\; M\; +\; \cdots .\; \{\backslash \; displaystyle\; Q\; (M)\; \backslash \; sim\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{\backslash \; pi\; M\}\; \{2\}\}\}\; -\; \{\backslash \; frac\; \{1\}\; \{3\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{12\}\}\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{\backslash \; pi\}\; \{2M\}\}\}\; -\; \{\backslash \; frac\; \{4\}\; \{135M\}\}\; +\; \backslash \; cdots.\}$

При M = 365 дней в году среднее количество людей, необходимое для поиска пары с тем же днем Рождения n = 1 + Q (M) ≈ 24,61659, что несколько больше 23, число необходимое для 50% вероятности. В лучшем случае хватит двух человек; в худшем случае нужно максимально возможное количество M + 1 = 366 человек; но в среднем 25 человек

Анализ с использованием индикаторных случайных величин может обеспечить эту более простой, но приблизительный анализ проблемы. Для пары (i, j) для k человек в комнате мы определяем каждую индикаторную случайную позицию X ij, для $1\; \le \; i\; \le \; j\; \le \; k\; \{\backslash \; displaystyle\; 1\; \backslash \; leq\; i\; \backslash \; leq\; j\; \backslash \; leq\; k\}$, по

$X\; ij\; =\; I\; \{человек\; i\; и\; человек\; j\; имеют\; одинаковый\; день\; рождения\}\; =\; \{1,\; если\; человек\; i\; и\; человек\; j\; имеют\; одинаковый\; день\; рождения;\; 0\; в\; противном\; случае.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{alignat\}\; \{2\}\; X\_\; \{ij\}\; =\; I\; \backslash \; \{\{\backslash \; text\; \{person\}\}\; i\; \{\backslash \; text\; \{и\; person\}\}\; j\; \{\backslash \; text\; \{имеют\; одинаковый\; день\; рождения\}\}\; \backslash \}\; \backslash \backslash \; =\; \{\backslash \; begin\; \{cases\}\; 1,\; \{\backslash \; text\; \{if\; person\}\}\; i\; \{\backslash \; text\; \{and\; person\}\}\; j\; \{\backslash \; text\; \{имеют\; одинаковый\; день\; рождения;\}\}\; \backslash \backslash \; 0,\; \{\backslash \; text\; \{иначе.\}\}\; \backslash \; end\; \{cases\}\}\; \backslash \; end\; \{alignat\}\}\}$

$E\; [X\; ij]\; =\; Pr\; \{у\; человека\; i\; и\; человека\; j\; один\; день\; рождения\}\; =\; 1\; /\; n\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{\; выровнено\}\; \{2\}\; E\; [X\_\; \{ij\}]\; =\; \backslash \; Pr\; \backslash \; \{\{\backslash \; text\; \{person\}\}\; i\; \{\backslash \; text\; \{и\; person\}\}\; j\; \{\backslash \; text\; \{имеют\; один\; и\; тот\; же\; день\; рождения\}\}\; \backslash \}\; \backslash \backslash \; =\; 1\; /\; n\; \backslash \; end\; \{alignat\}\}\}$

Пусть X будет случайной величиной, подсчитывающей пары людей с одним днем ​​рождения.

$Икс\; знак\; равно\; \sum \; я\; знак\; равно\; 1\; К\; \sum \; J\; знак\; равно\; я\; +\; 1\; К\; Икс\; ij\; \{\backslash \; Displaystyle\; X\; =\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{k\}\; \backslash \; sum\; \_\; \{j\; =\; i\; +\; 1\}\; ^\; \{k\}\; X\_\; \{ij\}\}$

$E\; [X]\; =\; \sum \; i\; =\; 1\; k\; \sum \; j\; =\; i\; +\; 1\; k\; E\; [X\; ij]\; =\; (k\; 2)\; 1\; n\; =\; k\; (k\; -\; 1)\; 2\; n\; \{\backslash \; displaystyle\; \{\; \backslash \; begin\; \{alignat\}\; \{3\}\; E\; [X]\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{k\}\; \backslash \; sum\; \_\; \{j\; =\; i\; +\; 1\}\; ^\; \{k\}\; E\; [X\_\; \{ij\}]\; \backslash \backslash \; =\; \{\backslash \; binom\; \{k\}\; \{2\}\}\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \backslash \; =\; \{\backslash \; frac\; \{k\; (k-1)\}\; \{2n\}\}\; \backslash \backslash \backslash \; end\; \{alignat\}\}\}$

Для n = 365, если k = 28, ожидаемое число с таким же днем ​​рождения будет $(28\; \cdot \; 27)\; /\; (2\; \cdot \; 365)\; \approx \; 1,0356.\; \{\backslash \; displaystyle\; (28\; \backslash \; cdot\; 27)\; /\; (2\; \backslash \; cdot\; 365)\; \backslash \; приблизительно\; 1.0356.\}$Следовательно, мы можем ожидать хотя бы одну подходящую пару с как минимум 28 людьми.

Неформальная демонстрация проблемы может быть сделана из списка премьер-министров Австралии, которых на 2017 год было 29, в котором Пол Китинг, 24-й премьер-министр, и Эдмунд Бартон, первый премьер-министр, разделяют один день рождения, 18 января.

На Чемпионате мира по футболу FIFA 2014 в каждой из 32 команд было по 23 игрока. Анализ официальных списков команд показал, что у 16 ​​команд были пары игроков, у которых были дни рождения, и из этих 5 команд было две пары: Аргентина, Франция, Иран, Южная Корея и Швейцария имели по две пары, а Австралия, Босния и Герцеговина, Бразилия., Камерун, Колумбия, Гондурас, Нидерланды, Нигерия, Россия, Испания и США - каждая по одной паре.

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

Обратная задача

Обратная задача состоит в том, чтобы найти для фиксированной вероятности p наибольшее n, для которого вероятность p (n) меньше заданного p, или наименьшее n, для которого вероятность p (n) больше заданного р.

Принимая приведенную выше формулу для d = 365, получаем

$n\; (p;\; 365)\; \approx \; 730\; ln\; \; (1\; 1\; -\; p).\; \{\backslash \; displaystyle\; n\; (p;\; 365)\; \backslash \; приблизительно\; \{\backslash \; sqrt\; \{730\; \backslash \; ln\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{1-p\}\}\; \backslash \; right)\}\}.\}$

В приведенных ниже приведенных примерах расчетов.

p	n	n↓	p (n ↓)	n↑	p (n ↑)
0,01	0,14178√365 = 2,70864	2	0,00274	3	0,00820
0,05	0,32029 √365 = 6,11916	6	0,04046	7	0,05624
0,1	0,45904√365 = 8,77002	8	0,07434	9	0,09462
0,2	0,66805√365 = 12,76302	12	0,16702	13	0,19441
0,3	0,84460√365 = 16,13607	16	0,28360	17	0,31501
0,5	1,17741√365 = 22,49439	22	0,47570	23	0,50730
0,7	1,55176√365 = 29,64625	29	0, 68097	30	0,70632
0,8	1,79412√365 = 34,27666	34	0,79532	35	0,81438
0,9	2,14597√365 = 40,99862	40	0,89123	41	0,90315
0,95	2,44775√365 = 46,76414	46	0,94825	47	0,95477
0,99	3,03485√365 = 57,98081	57	0,99012	58	0,99166

Некоторые значения, выходящие за границы, были окрашены, чтобы показать, что приближение не всегда точно.

Связанная проблема - проблема с разделением, вариант задачи о рюкзаке из исследования операций. Некоторые гири помещаются на весы весов ; каждый вес представляет собой целое число граммов, случайно выбранных от одного грамма до одного миллиона граммов (одна тонна ). Вопрос в том, можно ли обычно (то есть с вероятностью, близкой к 1) переносить вес между левой и правой рукой, чтобы сбалансировать весы. (В случае, если сумма всех весов - нечетное количество граммов, отклонение в один грамм.) Если есть только два или три веса, ответ, безусловно, отрицательный; Хотя есть некоторые комбинации, которые работают, большинство случайно выбранных комбинаций трех весов не работают. Если весов очень много, ответ однозначно положительный. Вопрос в том, сколько всего достаточно? То есть, какое количество гирь такое, что уравновесить их с равной вероятностью можно будет, поскольку это невозможно?

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

Причина в том, что правильное сравнение - это количество разделов весов на левое и правое. Есть 2 разных раздела для N весов, и левую сумму за вычетом правой суммы можно рассматривать как новую случайную часть для каждого раздела. Распределение суммы весов приблизительно равно по Гауссу с пиком на уровне 1000000N и шириной 1000000√N, так что, когда 2 приблизительно равно 1000000√N, переход происходит. 2 составляет около 4 миллионов, тогда как ширина распределения составляет всего 5 миллионов.

Роман Артура Кларка Падение лунной пыли, опубликовано в 1961 году, содержит раздел, где главные герои, запертые под землей на неопределенное время, празднуют день рождения и обсуждают актуальность проблемы дня рождения. Как заявлено пассажир-физик: «Если у вас есть группа из более чем двадцати четырех человек, шансы даже выше, чем у двоих из них в один день рождения». В конце концов, из 22 присутствующих электрическняется, что у двух персонажей один день рождения, 23 мая.

• Abramson, M.; Мозер, В. О. Дж. (1970). «Еще сюрпризы на день рождения». Американский математический ежемесячник. 77(8): 856–858. DOI : 10.2307 / 2317022. JSTOR 2317022.
• Блум, Д. (1973). «Проблема дня рождения». Американский математический ежемесячник. 80(10): 1141–1142. DOI : 10.2307 / 2318556. JSTOR 2318556. CS1 maint: ref = harv (ссылка )
• Кемени, Джон Дж.; Снелл, Дж. Лори; Томпсон, Джеральд (1957). Введение в конечную математику (Первое изд.).
• Кламкин, М.; Ньюман, Д. (1967). «Расширения сюрприза ко дню рождения». Журнал комбинаторной теории. 3 (3): 279–282. doi : 10.1016 / s0021-9800 (67) 80075-9.
• МакКинни, Э.Х. (1966). «Общая проблема дня рождения». American Mathematical Monthly. 73(4): 385–387. doi : 10.2307 / 2315408. JSTOR 2315408.
• Шнепс, Лейла ; Колмез, Корали (Основные Книги. ISBN 978-0-465-03292., 2013). -1.
• Sy M. Blinder (2013). Руководство по основам математики: обзор для-физиков, химиков и студентов инженеров. Elsevier. Стр. 5–6. ISBN 978-0-12-407163-6.

• The B День рождения Парадокс с учетом дней рождения в високосном году
• Вайсштейн, Эрик У. «Проблема дня рождения». MathWorld.
• Юмористическая статья, объясняющая парадокс.
• Эксперимент по случаю дня рождения SOCR EduMaterials
• Понимание проблемы дня рождения (лучше объяснение)
• Eurobirthdays 2012. Проблема дня рождения. Практический футбольный пример парадокс дня рождения.
• Грайм, Джеймс. «23: Вероятность дня рождения». Numberphile. Брэди Харан. Архивировано с оригинального 25 февраля 2017 года. Проверено 2 апреля 2013 г.
• Вычисление вероятностей проблемы рождения в WolframAlpha