- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 1647 5
https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
카드가 있습니다.
- 카드는 총 n 종류이고, 1회에 1번 카드 덱에서 카드를 받습니다.
(단, 쿠폰을 뽑는 쿠폰박스의 쿠폰 갯수는 무한대로, 이전에 뽑은 쿠폰의 종류에 영향을 받지 않습니다.) - 이 때, 임의의 한 종류 카드가 뽑힐 확률은 1/n 로 모든 종류의 카드가 동일합니다.
- 중복되는 카드는 다른 사람과 교환할 수 없습니다.
질문 :
What is the probability that more than t sample trials are needed to collect all n coupons?
Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once?
모든 종류의 카드를 모으기 위해서,
몇번 정도를 카드를 뽑아야 할 것으로 기대할 수 있는가?
-
25
댓글5
-
세상의모든계산기
48장의 카드라면
48 * H(48) = 48 * 4.458797175064 = 214.02226440307 회<48장 모으기 시도횟수 샘플, 1000회>
-
세상의모든계산기
ChatGPT-4o mini 답변
이 문제는 고전적인 "Coupon Collector's Problem"에 해당합니다. 이 문제는 주어진 종류의 모든 카드를 수집하는 데 필요한 평균적인 시도를 계산하는 문제입니다. 각 종류의 카드를 한 번씩 수집하는 데 필요한 평균적인 시도 횟수를 구하는 것이 목표입니다.
1. 기대값 계산 (Expected Value)
이 문제를 해결하기 위해서는 각 카드 종류를 수집하는 데 필요한 평균적인 시도 횟수를 계산해야 합니다. 이를 위해 다음과 같은 단계를 따릅니다.
문제 정의
- 총 카드 종류: \( n \)
- 각 카드가 뽑힐 확률: \( \frac{1}{n} \)
- 각 카드가 수집될 때까지의 시도 횟수:\( T_i \)를 \( i \)-번째 새로운 카드가 수집될 때까지의 시도 횟수라고 합시다. \( T_i \)는 기하 분포를 따릅니다. \( i \)-번째 카드가 수집되기까지 \( T_i \)번 시도해야 할 확률은 \( \frac{n}{n - (i - 1)} \)입니다.
기대값 계산
1. 기대값 구하기
- 첫 번째 카드가 수집될 때까지의 시도 횟수는 항상 1입니다.
- 두 번째 카드가 수집될 때까지의 추가 시도 횟수는 \( \frac{n}{n - 1} \)입니다.
- 일반적으로 \( i \)-번째 카드가 수집될 때까지의 추가 시도 횟수는 \( \frac{n}{n - (i - 1)} \)입니다.따라서, 전체 카드 종류를 수집하는 데 필요한 총 시도 횟수의 기대값 \( E[T] \)는 다음과 같습니다:
\[
E[T] = \sum_{i=1}^{n} \frac{n}{i} = n \cdot \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right)
\]여기서 \( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \)는 \( n \)번째 하르디노 수열 (Harmonic number)로, 약 \( \ln(n) + \gamma \) (여기서 \( \gamma \)는 오일러-마스케로니 상수, 약 0.577)로 근사할 수 있습니다.
따라서:
\[
E[T] \approx n \cdot (\ln(n) + \gamma)
\]2. 확률 계산
특정한 시도 횟수 \( t \)를 초과하여 모든 카드를 수집할 확률을 구하는 것은 좀 더 복잡합니다. 이를 계산하기 위해서는 대개 정확한 확률을 구하기 위한 조합론적 접근과 시뮬레이션을 사용합니다.
예시
- 예를 들어, 10개의 카드 종류가 있을 때, 모든 카드를 수집하는 데 예상되는 시도 횟수는:
\[
E[T] \approx 10 \cdot (\ln(10) + 0.577) \approx 10 \cdot (2.302 + 0.577) \approx 10 \cdot 2.879 = 28.79
\]즉, 평균적으로 약 29번의 시도가 필요합니다.
결론
- 기대값: 모든 종류의 카드를 수집하기 위해서는 평균적으로 약 \( n \cdot (\ln(n) + \gamma) \)번의 시도가 필요합니다.
- 확률: 특정한 시도 횟수 \( t \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
낮에 TV에서 영화 '말모이' 해주더라구요. 그래서 한번 물어 봤습니다. 2025 10.10 마지막 발언이 마지막 힌트이자 문제의 핵심이군요. 처음 들은 달이 8월이었다면 (15일인지 17일인지 확신할 수 없어서) 마지막 대사를 할 수 없지만, 처음 들은 달이 7월이었다면 (선택지가 16일 하나라서 확신이 가능하므로) 마지막 대사를 할 수 있다. 대사를 했으니 7월이다. 이제 이해되었습니다. 지금 보니까 이해가 되는데, 당시에는 왜 이해가 안됐을까요? 세가지 전제 하에 문제를 풀면 A는 마지막 대화 2줄만으로 C의 생일을 알 수 없어야 정상인데, 무슨 이유에서인지 "그럼 나도 앎!"이라고 선언해 버립니다. 알게 된 이유를 대화 속에서 찾을 수는 없습니다. 이 편견에 사로잡혀 빠져나오지 못하고 다른 길로 계속 샜나봅니다. 2025 10.09 (장*훈)님 (+10,000원) 계좌 후원(2025/10/09) 감사 드립니다. 2025 10.09 원래 식이 풀어진 상태에서는 두번째 인수 v가 분모, 분자에 섞여 있어서 계산기가 처리하지 못하는 듯 합니다. 이 때는 위에서와 반대로 분모 부분만 다른 문자(w)로 치환한 다음 completesquare(,v^2) 처리를 하면 일부분은 묶이는 듯 합니다. 하지만 여기서 처음 모양으로 더 이상 진행되진 않네요. 2025 10.08 전체 식에서 일부분(분모, 루트 내부)만 적용할 수는 없습니다. 번거롭더라도 해당 부분만 따로 끄집어 내서 적용하셔야 합니다. https://allcalc.org/30694#comment_30704 2025 10.08