- 세상의 모든 계산기 수학, 과학, 공학 이야기 확률통계 ()
Coupon collector's problem 쿠폰 수집 문제
-
- 2024.08.12 - 18:39 2015.09.12 - 13:25 2244 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 \)를 초과하여 모든 카드를 수집할 확률은 조합론적 접근 또는 시뮬레이션을 통해 계산할 수 있습니다.
세상의모든계산기 님의 최근 댓글
뉴턴-랩슨 적분 방정식 시각화 v1.0 body { font-family: 'Pretendard', -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif; display: flex; flex-direction: column; align-items: center; background: #f8f9fa; padding: 40px 20px; margin: 0; color: #333; } .container { background: white; padding: 40px; border-radius: 20px; box-shadow: 0 15px 35px rgba(0,0,0,0.08); max-width: 900px; width: 100%; } header { border-bottom: 2px solid #f1f3f4; margin-bottom: 30px; padding-bottom: 20px; } h1 { color: #1a73e8; margin: 0 0 10px 0; font-size: 1.8em; } p.subtitle { color: #5f6368; margin: 0; font-size: 1.1em; } .equation-box { background: #f1f3f4; padding: 15px; border-radius: 10px; text-align: center; margin-bottom: 30px; font-size: 1.3em; } canvas { border: 1px solid #e0e0e0; border-radius: 12px; background: #fff; width: 100%; height: auto; display: block; } .controls { margin-top: 30px; display: flex; gap: 15px; align-items: center; justify-content: center; flex-wrap: wrap; } button { padding: 12px 25px; border: none; border-radius: 8px; background: #1a73e8; color: white; cursor: pointer; font-weight: 600; font-size: 1em; transition: all 0.2s; box-shadow: 0 2px 5px rgba(26,115,232,0.3); } button:hover { background: #1557b0; transform: translateY(-1px); box-shadow: 0 4px 8px rgba(26,115,232,0.4); } button:active { transform: translateY(0); } button.secondary { background: #5f6368; box-shadow: 0 2px 5px rgba(0,0,0,0.2); } button.secondary:hover { background: #4a4e52; } .status-badge { background: #e8f0fe; color: #1967d2; padding: 8px 15px; border-radius: 20px; font-weight: bold; font-size: 0.9em; } .explanation { margin-top: 40px; padding: 25px; background: #fff8e1; border-left: 5px solid #ffc107; border-radius: 8px; line-height: 1.8; } .explanation h3 { margin-top: 0; color: #856404; } .math-symbol { font-family: 'Times New Roman', serif; font-style: italic; font-weight: bold; color: #d93025; } .code-snippet { background: #202124; color: #e8eaed; padding: 2px 6px; border-radius: 4px; font-family: monospace; } 📊 Newton-Raphson 적분 방정식 시뮬레이터 미분적분학의 기본 정리(FTC)를 이용한 수치해석 시각화 목표 방정식: ∫₀ᴬ (2√x) dx = 20 을 만족하는 A를 찾아라! 계산 시작 (A 추적) 초기화 현재 반복: 0회 💡 시각적 동작 원리 (Newton-Raphson & FTC) Step 1 (오차 측정): 현재 A까지 쌓인 파란색 면적이 목표치(20)와 얼마나 차이나는지 계산합니다. Step 2 (FTC의 마법): 면적의 변화율(미분)은 그 지점의 그래프 높이 f(A)와 같습니다. Step 3 (보정): 다음 A = 현재 A - (면적 오차 / 현재 높이) 공식을 사용하여 A를 이동시킵니다. 결론: 오차를 현재 높이로 나누면, 오차를 메우기 위해 필요한 가로 길이(ΔA)가 나옵니다. 이 과정을 반복하면 정답에 도달합니다! const canvas = document.getElementById('graphCanvas'); const ctx = canvas.getContext('2d'); const iterText = document.getElementById('iterText'); // 수학 설정 const targetArea = 20; const f = (x) => Math.sqrt(x) * 2; // 피적분 함수 f(x) = 2√x const F = (x) => (4/3) * Math.pow(x, 1.5); // 정적분 결과 F(x) = ∫ 2√x dx = 4/3 * x^(3/2) let A = 1.5; // 초기값 let iteration = 0; let animating = false; // 그래프 드로잉 설정 const scale = 50; const offsetX = 60; const offsetY = 380; function drawGrid() { ctx.strokeStyle = '#f1f3f4'; ctx.lineWidth = 1; ctx.beginPath(); for(let i=0; i 2026 04.11 참값 : A = ±2√5 근사값 : A≈±4.472135954999579392818347 2026 04.10 fx-570 ES 입력 결과 초기값 입력 반복 수식 입력 반복 결과 2026 04.10 파이썬 코드 검증 결과 초기값: 5.0 반복 1회차: 4.5000000000 반복 2회차: 4.4722222222 반복 3회차: 4.4721359558 반복 4회차: 4.4721359550 반복 5회차: 4.4721359550 초기값: 10.0 반복 1회차: 6.0000000000 반복 2회차: 4.6666666667 반복 3회차: 4.4761904762 반복 4회차: 4.4721377913 반복 5회차: 4.4721359550 2026 04.10 감사합니다. 주말 잘 보내세요. 2026 03.06