- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 5286 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 \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
2) 고정기준값 41에 대한 오차 제곱합 계산방법 이건 통계메뉴에서는 딱히 방법이 떠오르지 않네요. 질문하신 것과 같이 적은 갯수의 data라면 직접 입력하시는게 최선입니다. 하지만 DATA 갯수가 수십개 이상이라면? ㄴ 스프레드시트 기능을 이용하시는게 좋겠습니다. 【MENU】【8】 A열에 DATA 입력하고 B로 이동한 후 OPTN 【1】 Fill Formula 【ALPHA】키 방향키 숫자키 등을 이용해 수식 완성 C로 이동후 Formula 수식 입력 D의 빈공간으로 이동 후 OPTN 방향키 아래 누르다보면 Sum 보임 ALPHA 키 이용해서 수식 완성. : 기호는 MENU 버튼 바로 아래 있음 (ALPHA키로 입력) 【=】입력하면 최종결과 확인 * 주의 (B열, C열과 달리) D1 셀은 계산 결과인 951이 직접 입력된 상태이므로 DATA 수정후 recalculation 하여도 자동계산되지 않음. 자동계산을 위해서는 formula 형식으로 입력해야 함. 2026 10.27 1) 통계적 편차제곱합(평균 50.25기준) 입력 방법 【MENU】 【6】 【1】 로 1-var Stat 모드로 진입하여 【48】 【=】 【66】 【=】 【32】 【=】 【55】【=】 DATA 입력 【OPTN】 【3】 【▼】 【▼】 fx-570EX 기종에도 편차제곱합을 바로 보여주진 않습니다. 본문에 나온 것처럼 앞서 계산되어 저장된 각종 변수를 이용해 계산합니다. 【AC】【OPTN】【4】Statistics Calc 이 화면에서 다시 OPTN 하고 (메뉴가 3개로 줄어 있죠?) 여기서 방향키로 【▼】 아래를 내려보면 추가 메뉴가 있습니다. 4개 메뉴에는 각각 아래 하위 메뉴가 있습니다. 이 중에서 필요로 하는 것을 골라 계산하시면 되겠습니다. Variable 에 있는 값을 이용하면 다른 공식을 쓰셔도 됩니다. 2026 10.27 질문자님, 48,66,32,55 네 개 DATA 의 평균은 50.25라서 41은 평균이 아닙니다. 그래서 식을 두 가지로 나눠서 봐야 합니다. 1) 통계적 편차제곱합(평균 50.25기준)이면 답은 608.75 입니다. 2) 만약 41이라는 고정 기준값에 대한 제곱합을 구하시는 거면 식은 (48-41)²+... 이고 답은 951입니다. 원문에 +로 쓰신 건 -의 오타로 보입니다. 2026 10.27 본문의 변환 위젯에 사용된 전서체 폰트는 대만의 최고 학술 연구 기관인 중앙연구원(Academia Sinica)에서 제공하는 ‘숭희전체(崇羲篆體)’로 전통 한자 서체인 소전(小篆)을 현대 컴퓨터 폰트(글꼴)로 구축한 오픈소스 프로젝트로 개발되었습니다. https://xiaoxue.iis.sinica.edu.tw/chongxi/download.htm 2026 10.20 예제1) 예제2) 예제3) 추가옵션 2026 10.18