C++で解く誕生日のパラドックス（誕生日問題）｜確率の仕組みと実装例

誕生日のパラドックスとは

誕生日のパラドックス（Birthday Paradox）は、確率論において非常に有名な問題の一つです。この問題は次のように定式化されます。

「ある誕生日パーティーに複数の人が集まっている。この中に同じ誕生日の人同士が存在するとして、その確率をもとに、必要な人数のおおよその値を求めよ」

直感的には「365日もあるのだから、同じ誕生日の人がいるのは珍しい」と感じるかもしれません。しかし実際には、驚くほど少ない人数でも高い確率で誕生日が重なることが数学的に証明されています。これが「パラドックス」と呼ばれる所以です。

コイン投げとの類似点

確率論では、コインを1回投げて表が出る確率は 1/2 です。これを応用すると、10回連続で表が出る確率はおよそ 1/1000（0.001）程度になります。このように、独立した事象が重なる確率は掛け合わせで計算できるというのが基本の考え方です。

確率計算の考え方

まず、2人の誕生日が異なる確率を考えてみましょう。平年（365日）の場合、次のように表せます。

364 / 365 ＝ 1 − 1/365

ここで、最初の人の誕生日は何日であっても構わないため、その確率は「1」です。2人目以降については、すでに登場した誕生日と重ならない確率を掛け合わせていきます。

P(異なる) ＝ 1 × (1 − 1/365) × (1 − 2/365) × (1 − 3/365) × (1 − 4/365) × …

そして、「同じ誕生日の人が存在する確率」は、全体の確率1から「全員が異なる確率」を引けば求められます。

P(同じ) ＝ 1 − P(異なる)

具体例：確率70%に必要な人数

同じ誕生日を持つ人が存在する確率が 0.70（70%）になるときの人数 N を求めてみます。近似的に次の公式が使えます。

N ＝ √(2 × 365 × log(1/(1−p)))

p = 0.70 を代入すると、

N ＝ √(2 × 365 × log(1/(1−0.70))) ≒ 30

つまり、約30人集まれば、70%の確率で同じ誕生日の人が存在することになります。23人でも50%を超えるというのが、この問題が有名になった大きな理由です。

C++での実装例

上記の公式をC++で実装すると、以下のようになります。

#include<bits/stdc++.h>
using namespace std;
int findPeople(double p){
    return ceil(sqrt(2*365*log(1/(1-p))));
}
int main(){
    printf("%d",findPeople(0.70));
}

コードのポイント

• log() は自然対数（底 e の対数）を計算します。
• ceil() は小数点以下を切り上げる関数で、人数は整数であるため使用しています。
• sqrt() で平方根を取り、公式どおりの計算を行っています。

出力結果

30

このように、確率70%に対してプログラムは「30人」という答えを出力します。誕生日のパラドックスは、直感と確率のギャップを実感できる興味深いテーマであり、ハッシュ衝突の発生確率など、コンピュータサイエンスの分野にも応用される重要な概念です。