- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 1906 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 \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
기본 어댑터 MODEL : AD0301-1202500GB INPUT : 100~240V, 50~60Hz, 0.8A Max OUTPUT : 12.0V, 2.5A, 30.0W ㄴ 측정시 플러그 외경/내경 : 5.5mm / 2mm 2026 02.15 엑셀 파일로 만드니 전체 160~200MB 정도 나옵니다. 읽고 / 저장하는데 한참 걸리네요. 컴 사양을 좀 탈 것 같습니다. -> 엑셀/한셀에서 읽히지만, 구글 스프레드시트에서는 열리지 않네요. 100만 개 단위로 끊어서 20MB 정도로 분할해 저장하는 편이 오히려 속 편할 것 같습니다. -> 이건 구글 스프레드시트에서도 열리긴 하네요. (약간 버퍼링?이 있습니다) 2026 02.10 엑셀 / 행의 최대 개수, 열의 최대 개수, 셀의 최대 개수 엑셀의 행 개수 제한은 파일 형식에 따라 다르며, 최신 .xlsx 파일 형식은 시트당 최대 1,048,576행까지 지원하지만, 구형 .xls 파일은 65,536행으로 제한됩니다. 따라서 대용량 데이터를 다룰 때는 반드시 최신 파일 형식(.)으로 저장해야 하며, 행과 열의 총 수는 1,048,576행 x 16,384열이 최대입니다. 주요 행 개수 제한 사항: 최신 파일 형식 (.xlsx, .xlsm, .xlsb 등): 시트당 1,048,576행 (2^20). 구형 파일 형식 (.xls): 시트당 65,536행 (2^16). 그 외 알아두면 좋은 점: 최대 행 수: 1,048,576행 (100만여개) 최대 열 수: 16,384열 (XFD) 대용량 데이터 처리: 65,536행을 초과하는 데이터를 다루려면 반드시 .xlsx 형식으로 저장하고 사용해야 합니다. 문제 해결: 데이터가 많아 엑셀이 멈추거나 오류가 발생하면, 불필요한 빈 행을 정리하거나 Inquire 추가 기능을 활용하여 파일을 최적화할 수 있습니다. 2026 02.10 [일반계산기] 매출액 / 원가 / 마진율(=이익율)의 계산. https://allcalc.org/20806 2026 02.08 V2 갱신 (nonK / K-Type 통합형) 예전에는 직접 코드작성 + AI 보조 하여 프로그램 만들었었는데, 갈수록 복잡해져서 손 놓고 있었습니다. 이번에 antigravity 설치하고, 테스트 겸 새로 V2를 올렸습니다. 직접 코드작성하는 일은 전혀 없었고, 바이브 코딩으로 전체 작성했습니다. "잘 했다 / 틀렸다 / 계산기와 다르다." "어떤 방향에서 코드 수정해 봐라." AI가 실물 계산기 각정 버튼의 작동 방식에 대한 정확한 이해는 없는 상태라서, V1을 바탕으로 여러차례 수정해야 했습니다만, 예전과 비교하면 일취월장 했고, 훨씬 쉬워졌습니다. 2026 02.04