Рубрики

День рождения парадокс

Сколько людей должно быть в комнате, чтобы сделать 100% вероятностью того, что по крайней мере два человека в комнате будут иметь одинаковый день рождения?
Ответ: 367 (поскольку существует 366 возможных дней рождения, включая 29 февраля).
Вышеуказанный вопрос был прост. Попробуйте вопрос ниже самостоятельно.

Сколько людей должно быть в комнате, чтобы сделать 50% вероятностью того, что по крайней мере два человека в комнате будут иметь одинаковый день рождения?
Ответ: 23
Число на удивление очень низкое. На самом деле, нам нужно всего 70 человек, чтобы вероятность составила 99,9%.

Обсудим обобщенную формулу.

Какова вероятность того, что два человека из n имеют одинаковый день рождения?
Пусть вероятность того, что два человека в комнате с n имеют одинаковый день рождения, будет P (одинаковой). P (один и тот же) можно легко оценить с точки зрения P (разного), где P (разный) — это вероятность того, что у всех них разный день рождения

P (то же самое) = 1 — P (другое)

P (разные) можно записать как 1 x (364/365) x (363/365) x (362/365) x…. х (1 — (н-1) / 365)

Как мы получили вышеуказанное выражение?
Люди от первого до последнего могут получить дни рождения в следующем порядке, чтобы все дни рождения были различны:
Первый человек может иметь любой день рождения среди 365
У второго человека должен быть день рождения, который не совпадает с первым человеком
Третий человек должен иметь день рождения, который не совпадает с первыми двумя людьми.
…………….
……………
У n-го человека должен быть день рождения, который не совпадает ни с одним из ранее рассмотренных (n-1) человек.

Аппроксимация вышеприведенного выражения
Приведенное выше выражение может быть аппроксимировано с использованием ряда Тейлора.

обеспечивает приближение первого порядка для ex для x << 1:

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

Вышеупомянутое выражение, полученное для p (другого), может быть записано как
1 х (1 — 1/365) х (1 — 2/365) х (1 — 3/365) х…. х (1 — (н-1) / 365)

Помещая значение 1 — a / 365 как e -a / 365 , мы получаем следующее.



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

р (одинаковый) = 1- р (разный)

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

р (то же самое)

Взяв Log с обеих сторон, мы получим обратную формулу.

Используя приведенную выше приблизительную формулу, мы можем приблизить количество людей для данной вероятности. Например, следующая функция C ++ find () возвращает наименьшее n, для которого вероятность больше заданного p.

Реализация приближенной формулы.
Ниже приведена программа приблизительного числа людей для данной вероятности.

C ++

// C ++ программа для приблизительного числа людей в парадоксе дня рождения
// проблема
#include <cmath>
#include <iostream>

using namespace std;

  
// Возвращает приблизительное количество людей для данной вероятности

int find(double p)

{

    return ceil(sqrt(2*365*log(1/(1-p))));

}

  

int main()

{

   cout << find(0.70);

}

Джава

// Java программа для приблизительного числа
// людей в проблеме парадокса дня рождения

class GFG {

      

    // Возвращает приблизительное количество людей

    // для заданной вероятности

    static double find(double p) {

          

        return Math.ceil(Math.sqrt(2

            365 * Math.log(1 / (1 - p))));

    }

      

    // Код драйвера

    public static void main(String[] args) 

    {

          

        System.out.println(find(0.70)); 

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 код для приблизительного числа
Количество людей в проблеме парадокса дня рождения

import math

  
# Возвращает приблизительное количество
# человек для данной вероятности

def find( p ):

    return math.ceil(math.sqrt(2 * 365 *

                     math.log(1/(1-p))));

  
Код водителя

print(find(0.70))

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # программа для приблизительного числа
// людей в проблеме парадокса дня рождения.

using System;

  

class GFG {

       

    // Возвращает приблизительное количество людей

    // для заданной вероятности

    static double find(double p) {

           

        return Math.Ceiling(Math.Sqrt(2 * 

            365 * Math.Log(1 / (1 - p))));

    }

       

    // Код драйвера

    public static void Main() 

    {         

    Console.Write(find(0.70)); 

    }

}

   
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для приближения
// количество людей в Дне Рождения
// Проблема парадокса

  
// Возвращает приблизительное число
// людей с заданной вероятностью

function find( $p)

{

    return ceil(sqrt(2 * 365 * 

                     log(1 / (1 - $p))));

}

  
// Код драйвера

echo find(0.70);

  
// Этот код предоставлен aj_36
?>


Выход :

30

Источник:
http://en.wikipedia.org/wiki/Birthday_problem

Приложения:
1) День рождения Paradox обычно обсуждается с хешированием, чтобы показать важность обработки коллизий даже для небольшого набора ключей.
2) Атака на день рождения

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

Рекомендуемые посты:

День рождения парадокс

0.00 (0%) 0 votes