- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 1710 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 \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
HP-39gII 에 ExistOS 설치하기 https://allcalc.org/38526 2025 11.07 1. 왜 검은색이 아닌 다른 색으로 보일까? (제공된 LUT 필터) 제가 제공해 드린 magenta_lens.cube LUT 필터는 540~560nm(녹색-노란색) 파장대의 색상을 '완전히 제거(검은색으로 만듦)'하는 대신, '다른 색상으로 왜곡/변환'하도록 설계되었습니다. * 원리: LUT(Look-Up Table)는 특정 입력 색상(Input RGB)을 미리 정해진 다른 출력 색상(Output RGB)으로 매핑하는 테이블입니다. 이 LUT는 540~560nm에 해당하는 RGB 값들이 들어오면, 검은색(0, 0, 0)이 아닌, 매우 어둡거나 채도가 낮은 특정 색(예: 어두운 올리브색, 갈색 등)으로 변환하라고 지시합니다. * 의도: * 현실적인 물리 필터 시뮬레이션: 실제 고가의 색약 보정 안경도 특정 파장을 100% 완벽하게 차단하지는 못합니다. 빛의 일부를 흡수하고 일부는 통과시키거나 변환하는데, 이 LUT는 그러한 현실 세계의 필터 효과를 더 비슷하게 흉내 냈을 수 있습니다. * 시각적 정보 유지: 특정 색을 완전히 검게 만들면 그 부분의 형태나 질감 정보가 완전히 사라집니다. 하지만 다른 어두운 색으로 대체하면, 색상 정보는 왜곡되더라도 밝기나 형태 정보는 어느 정도 유지되어 전체적인 이미지가 덜 어색하게 보일 수 있습니다. 결론적으로, 스펙트럼 그림에서 해당 대역의 색이 갑자기 '다른 색으로 툭 바뀌는' 현상은, LUT 필터가 "이 파장대의 색은 앞으로 이 색으로 표시해!"라고 강제적으로 지시한 결과이며, 이것이 바로 이 필터가 작동하는 방식 그 자체입니다. 2. 왜 'Color Vision Helper' 앱은 검은색으로 보일까? 비교하신 'Color Vision Helper' 앱은 노치 필터의 원리를 더 이상적(Ideal)이고 교과서적으로 구현했을 가능성이 높습니다. * 원리: "L-콘과 M-콘의 신호가 겹치는 540~560nm 파장의 빛은 '완전히 차단'되어야 한다"는 개념에 매우 충실한 방식입니다. * 구현: 따라서 해당 파장에 해당하는 색상 정보가 들어오면, 어떠한 타협도 없이 그냥 '검은색(RGB 0, 0, 0)'으로 처리해 버립니다. 이는 "이 파장의 빛은 존재하지 않는 것으로 처리하겠다"는 가장 강력하고 직접적인 표현입니다. 2025 11.06 적용사례 4 - 파장 스펙트럼 https://news.samsungdisplay.com/26683 ㄴ (좌) 연속되는 그라데이션 ➡️ (우) 540 이하 | 구분되는 층(색) | 560 이상 - 겹치는 부분, 즉 540~560 nm 에서 색상이 차단? 변형? 된 것을 확인할 수 있음. 그럼 폰에서 Color Vision Helper 앱으로 보면? ㄴ 540~560 nm 대역이 검은 띠로 표시됨. 완전 차단됨을 의미 2025 11.05 빨간 셀로판지로도 이시하라 테스트 같은 숫자 구분에서는 유사한 효과를 낼 수 있다고 합니다. 색상이 다양하다면 빨강이나, 노랑, 주황 등도 테스트해보면 재밌겠네요. 2025 11.05 안드로이드 앱 - "Color Vision Helper" 다운받아 본문 내용을 카메라로 찍어 보니, 본문 프로그램에서는 애매하게 보이던 부분에서도 구분이 완전 확실하게 되네요. 숫자 구분 능력 & 편의성 면에서 압도적이라고 할 수 있겠습니다. 2025 11.05