[확통]Birthday Problem과 확률의 특성

Birthday Problem, Properties of Probability

본 포스팅은 하버드 대학교의 강의를 듣고 정리한 내용입니다.

https://youtu.be/LZ5Wergp_PA?si=da5qZG2CrjE8Y7e2

---

1️⃣Birthday Problem

어떤 파티에서 그룹이 있을때 최소한 2명의 생일이 같을 확률을 구한다고 해보자.

최소 몇 명이 있어야 생일이 같은 사람의 비율이 50%가 있을까?

• k 명이 있다고 했을때, 이 그룹 내에서 생일이 같을 확률을 찾는것과 같다.
• 가정
  • 1년 365일 이 동일한 확률 가진다고 가정,
  • 각각의 출생이 서로 독립적이라고 가정
  • = 모든 사람의 탄생이 다른 사람의 탄생에 관여 x (옆집 아기가 나왔다고 다른집도 낳는다는 설정 X)

풀이

2가지의 경우로 나누어서 풀 수 있다.

1. k > 365 경우
   • k가 365명보다 많을 경우의 최소한 2명의 생일이 같을 확률 ⇒ p = 1
   • 상자보다 많은 사람이 존재하기 때문에 상자에 최소한 한 명쯤은 들어감 ⇒ 비둘기 집의 원리
2. k ≤ 365 일 경우
   • 결론부터 말하자면, k = 23 즉, 그룹에 23만 있어도 그룹 내 생일이 같은 사람이 2명 이상일 확률이 50%임
   • (엄밀히 따지면 50.7%)
   • 이를 아래에서 증명해보자.

2-1. 모두 생일이 같지 않을 확률(여사건)

• A : $365 * 364 * … (365 - k + 1)$
  • 첫번째 사람이 365일 중에 한 날에 태어나고,,
  • 두번째 사람이 첫번째 사람이 태어나지 않은 날에 태어나고 ,,
• B : $ 365^k $
  • k명의 사람들이 365일 중 한 날에 태어나는 모든 사건

2-2. 생일이 같을 확률

• 아래의 식을 계산하면

• k = 23 → 50.7%
• k = 50 → 97%
• k = 100 → 99.999…%

갑자기 아래의 식을 계산하면 k = 23일 때 이런 확률이 나오고 ~ 라고 말하면 받아들이기 힘들 것이다.
실제로 수학적으로 계산기를 사용해 계산한다면 k의 값이 23이 나오긴 하지만, 좀 더 와닿도록 직관적인 방법으로 아래에서 이를 증명해보고자 한다.

 

👁️Intuitive Way

• 이 문제에서 가장 중요한 값은 k가 아니다!
• 이 문제에서의 가장 핵심은 k에서 생일이 같은 2명을 고르는 경우의 수이다. (즉, 2명을 뽑는 경우의 수가 더 중요하다는 뜻!)
• 아래의 식은 k명 중에서 생일이 같은 2명을 뽑을 확률이다. (왜 이런식이 나오는지 의문이 든다면, 중학교 때 배운 자격이 같은 대표를 뽑는 경우의 수를 구하는 법을 생각하면 된다.)https://calcproject.tistory.com/687

$$\frac{k(k-1)}{2}$$

• k = 23명이라고 했을 때 위의 식에 숫자를 대입해 풀어본다면

• 253이 나온다. 즉, 23명 중에 2명을 뽑았을 때 그 둘의 생일이 같을 경우의 수가 253이라는 뜻이다.

이처럼 23명만 있어도 이 중 2명을 무작위로 뽑았을 때 2명의 생일이 같은 경우의 수가 365일의 절반보다도 많다.

이 문제를 보통 사람들이 birthday 문제를 봤을 때 통상적으로 365의 절반인 180명 등의 많은 수를 떠오르곤 하는데 실제로 계산해본다면 23명만으로도 “우연히” 2명의 생일이 같을 수 있다는 사실을 보여준다. 확률을 배운다면 우리가 칭하는 모든 “우연”이라는 것들은 증명될 수 있다는 사실!

이처럼 재미있는 확률을 통해 우리가 칭하는 여러 우연들을 증명해보자.

---

2️⃣두 사람의 생일이 하루 차이나는 경우(birthday problem의 파생 문제)

(생일이 같거나 하루 차이 나는 경우도 포함)

⇒ k = 14로 감소

계산 과정은 아래와 동일하지만 더욱 복잡해진다.

앞서 해왔던 방식처럼 여사건을 사용해서 이 문제를 풀 경우 분모와 분자는 아래와 같다.

• A : $363 * 362 * … (365 - k + 1)$
  • 첫번째 사람이 365일 중에 한 날에 태어나고,,
  • 두번째 사람이 첫번째 사람이 태어나지 않은 날에 태어나며 그 전날 그 다음날에도 태어나지 않고 ,,
• B : $365^k$
  • k명의 사람들이 365일 중 한날에 골라서 태어나는 모든 사건

---

3️⃣Axioms: 확률의 기본 정리

💡 확률이란 아래의 두 가지 조건을 만족하는 0부터 1 사이의 숫자

아래의 두 조건을 통해 확률에 관련된 모든 정리들은 유도 가능하다.

• 정리1 P(∅) = 0, P(S) = 1
  • P(∅) = 0 : 아무것도 발생하지 않은 것은 0 (공사건)
  • P(S) = 1 : 모든 사건의 집합 = 1 (전사건)
• 정리2

• $p(∪ A_n) = n$이 1부터 무한대일때 $P(A_n)$값의 합
• A1, A2 ..가 서로 겹치지 않는 서로소여야 됨

---

4️⃣Properties: 확률의 특징

위의 정리로 모든 확률의 특징들을 증명할 수 있다.

(1) 여사건

Proof

• $1 = P(s) = P(A ∪ A^C)$
• $P(A ∪ A^C) = P(A) + P(A^C)$ ($A, A^C$는 서로소이기 때문) → 정리 2 를 사용한 증명

(2) if A ⊂ B, then P(A) ≤ P(B) (A Occurs B occurs)

Proof

• $B = A ∪ (B ∩ A^C)$
• 이 집합들은 서로소임 → $P(B) = P(A) + P(B ∩ A^C) ≥ P(A)$

(3) P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

Proof

정리 2를 사용하기 위해선 → 각각의 사건을 서로소로 만들어야 한다.

서로소로 만들기 위해 → B에 포함되지만 A에 포함되지 않은 부분을 보자.

• $P(A ∪ B) = P(A ∪ (B ∩ A^C))$
• $P(A ∪ B) = P(A ∪ (B ∩ A^C)) ⇒ P(A) + P(B ∩ A^C)$
• $P(A) + P(B ∩ A^C) = P(A) + P(B) - P(A ∩ B)$
  • 우리는 위의 식을 유도하고자 한다 (wishful thinking 🔮); 이게 정답이길 바라는 마음으로 오른쪽 항에 증명할 식을 두었다.
• $P(A) + P(B ∩ A^C) = P(A) + P(B) - P(A ∩ B)$ 위의 식을 정리하면
• $P(A ∩ B) + P(B ∩ A^C) = P(B)$ 이와 같이 되고,
  • 위의 식이 참인지 확인해보자 !
• 결론부터 말하자면 위의 식은 참이다.
  • 위의 식이 참인 이유: 정리2에 의해 참임을 바로 알 수 있음
  • $P(A ∩ B),P(B ∩ A^C)$ 는 서로소 : $A$와 $A^C$ 두 집합에 동일한 원소가 포함되는 것은 불가능하기 때문이다.
  • 이들의 합집합은 B와 같다 : $A ∩ B, B ∩ A^C$ 는 B를 둘로 쪼갠 것이나 다름 없기 때문이다.
    • $A ∩ B$ : A에 포함되는 B의 부분
    • $A^C ∩ B$ : A에 포함되지 않는 B의 부분

이처럼 확률의 정리를 활용하여 모든 확률의 특징을 증명할 수 있다.

---

5️⃣포함배제의 원리

포함배제: 개별 사건을 다 더해줌 → 서로 다른 두 사건의 교사건의 확률을 뺀다 → 3개의 교사건을 더한다

• $P(A ∪ B ∪ C) = P(A) + P(B) + P(C) - P(A ∩ B) - P(A ∩ C) - P(C ∩ B) + P(A ∩ B ∩ C)$
  • 위의 식은 아래의 그림을 참고하면 된다.
  • 하나의 집합에 A, B, C 집합의 합집합을 계산하기 위해선 위와 같은 수식이 사용된다.
  • 이를 참고하여 3개 이상의 집합의 합집합을 구하는 경우는 아래의 수식과 같다. 
• Equation

이러한 원리를 활용하여 아래의 문제를 풀어보자.

---

6️⃣Demontimort’s problem (matching problem)

n장의 카드가 있습니다. 1부터 n까지 적힌 숫자입니다. 카드를 한 장씩 뒤집는 게임을 진행합니다. 카드를 한 장씩 뒤집을 때마다 여러분은 1부터 n까지의 숫자를 세는 겁니다. 제가 뒤집은 카드의 숫자가 여러분이 센 숫자와 같으면 여러분이 이기는 겁니다.

문제: 최소 한 장의 카드에 적힌 숫자가 카드 뭉치의 위치와 같을 확률

(카드의 숫자는 뒤섞여 있는데 그 중에서 내가 말한 숫자와 뒤집힌 카드의 숫자가 같을 확률)

• $A_j$ = j번째 카드에 j라고 적혀 있을 확률
• $P(A_1 ∪ A_2 ∪ … A_n)$ = 최소 한 장의 카드가 매칭될 확률의 수학적 표현
  • $P(A_1)$ = 1번 카드가 1번에 있을 확률
  • $P(A_1 ∪ A_2 ∪ … A_n)$ = 각각의 숫자가 각각의 숫자 번째에 있을 확률
• 포함배제의 원리 활용하여 문제를 풀어보자.

 

 

---

지금까지 확률의 기본 정의에 대해서 살펴 보았다. 

이를 바탕으로 다음 글은 조건부 확률에 대해 정리해보도록 하겠다.