- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 1843 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 \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
쌀집계산기로 연립방정식 계산하기 - 크래머/크레이머/크라메르 공식 적용 https://allcalc.org/56739 3. 'x' 값 구하기 계산기 조작법 목표: x = Dx / D = [(c×e) - (b×f)] / [(a×e) - (b×d)] 계산하기 1단계: 분모 D 계산 (메모리 활용) 1 * 1 M+ : 메모리(M)에 1를 더합니다. (현재 M = 1) -0.1 * -0.2 M- : 메모리(M)에서 0.02를 뺍니다. (현재 M = 0.98 = 0.98) 이로써 메모리(MR)에는 분모 0.98가 저장됩니다. 2단계: 분자 Dx 계산 후 나누기 78000 * 1 : 78000를 계산합니다. = : GT에 더합니다. -0.1 * 200000 : -20000를 계산합니다. ± = : 부호를 뒤집어 GT에 넣습니다. // sign changer 버튼 사용 GT : GT를 불러옵니다. GT는 98000 (분자 Dx) 값입니다. ÷ MR = : 위 결과(98000)를 메모리(MR)에 저장된 분모 D(0.98)로 나누어 최종 x값 100,000를 구합니다. 4. 'y' 값 구하기 계산기 조작법 목표: y = Dy / D = [(a×f) - (c×d)] / [(a×e) - (b×d)] 계산하기 1단계: 분모 D 계산 (메모리 활용) 'x'에서와 분모는 동일하고 메모리(MR)에 0.98가 저장되어 있으므로 패스합니다. 2단계: 분자 Dy 계산 후 나누기 GT ± = : GT를 불러오고 부호를 뒤집어 GT에 더합니다. GT가 0으로 리셋됩니다. 【AC】를 누르면 M은 유지되고 GT만 리셋되는 계산기도 있으니 확인해 보세요. 1 * 200000 : 200000를 계산합니다. = : GT에 더합니다. 78000 * -0.2 : -15600를 계산합니다. ± = : 부호를 뒤집어 GT에 넣습니다. GT : GT를 불러옵니다. 215600 (분자 Dy) 값입니다. ÷ MR = : 위 결과(215600)를 메모리(MR)에 저장된 분모 D(0.98)로 나누어 최종 y값 220,000를 구합니다. x, y 값을 이용해 최종 결과를 구합니다. 2026 01.18 크레이머 = 크레머 = 크라메르 공식 = Cramer's Rule https://allcalc.org/8985 2026 01.18 부호 변경 버튼 https://allcalc.org/52092 2026 01.18 [fx-570 CW] 와의 차이 CW에 【×10x】버튼이 사라진 것은 아닌데, 버튼을 누를 때 [ES][EX] 처럼 특수기호 뭉치가 생성되는 것이 아니고, 【×】【1】【0】【xㅁ】 버튼이 차례로 눌린 효과가 발생됨. ※ 계산 우선순위 차이가 발생할 수 있으므로 주의. 괄호로 해결할 것! 2026 01.18 26년 1월 기준 국가 전문자격 종류 가맹거래사 감정사 감정평가사 검량사 검수사 경매사 경비지도사 경영지도사 공인노무사 공인중개사 관광통역안내사 관세사 국가유산수리기능자(24종목) 국가유산수리기술자 국내여행안내사 기술지도사 농산물품질관리사 물류관리사 박물관 및 미술관 준학예사 변리사 사회복지사 1급 산업보건지도사 산업안전지도사 세무사 소방시설관리사 소방안전교육사 손해평가사 수산물품질관리사 정수시설운영관리사 주택관리사보 청소년상담사 청소년지도사 한국어교육능력검정시험 행정사 호텔경영사 호텔관리사 호텔서비스사 2026 01.17