- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 1813 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/9677 2025 12.11 다른 계산기의 경우와 비교 1. TI-nspire CAS ㄴ CAS 계산기는 가능한 경우 부정적분을 먼저하고, 그 값에 구간을 대입해 최종값을 얻습니다. ㄴ 부정적분이 불가능할 때는 수치해석적 방법을 시도합니다. 2. CASIO fx-991 ES Plus ㄴ CASIO 계산기의 경우, 적분할 함수에 따라 시간이 달라지는 것으로 알고 있는데, 정밀도를 확보할 별도의 알고리즘을 채택하고 있는 것이 아닐까 생각되네요. 2025 12.11 일반 계산기는 보통 리셋기능이 따로 없기 때문에, 다른 요인에 영향을 받을 가능성은 없어 보이구요. '원래는 잘 되었는데, 지금은 설정 값이 날아간다'면 메모리 값을 유지할만큼 배터리가 꾸준하게 공급되지 않기 때문일 가능성이 높다고 봐야겠습니다. - 태양광이 있을 때는 계산은 가능하지만, 서랍등에 넣으면 배터리가 없어서 리셋 https://blog.naver.com/potatoyamyam/223053309120 (교체 사진 참조) 1. 배터리 준비: * 다이소 등에서 LR54 (LR1130) 배터리를 구매합니다. (보통 4개 들이 1,000원에 판매됩니다. LR44와 높이가 다르니 혼동하시면 안됩니다.) 2. 준비물: * 작은 십자드라이버 (계산기 뒷면 나사용. 이것도 없으시면 다이소에서...) 3. 커버 분해: * 계산기 뒷면의 나사를 풀고, 머리 부분(윗부분)의 커버를 조심스럽게 분해합니다. (참고해주신 블로그 사진을 보시면 이해가 빠르실 겁니다.) 4. 배터리 교체: * 기존 배터리를 빼냅니다. * 새 LR54 배터리의 '+'극 방향을 정확히 확인하여 제자리에 넣어줍니다. (대부분의 경우 '+'극이 위로 보이도록 넣습니다.) 5. 조립: * 커버를 다시 닫고 나사를 조여줍니다. * 블로그 사진을 보니 배터리 연결선 등이 눌려서 씹혀 있네요. 원래 씹히도록 설계를 안하는데, 원래 그렇게 만들어 놓은 건지? 모르겠네요. 여튼 씹히면 단선될 가능성이 있으니, 잘 보시고 플라스틱 틈새 등으로 적절히 배치해서 안씹히게 하는 것이 좋습니다. 6. TAX 재설정: * 계산기의 전원을 켜고 TAX 요율을 10%로 다시 설정합니다. 2025 12.10 TI-nspire 입력 방법 solve({x+a+b=5,x)|a=1 and b=2 2025 12.01 질문하실 때는 항상 계산기 모델명을 정확하게 적으셔야 합니다. 2025 12.01