쿠폰 수집 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

쿠폰 수집 문제는 무작위로 쿠폰을 뽑을 때 모든 종류의 쿠폰을 한 번 이상 수집하는 데 필요한 시행 횟수를 다루는 확률론적 문제이다. 이 문제는 기댓값, 분산, 꼬리 추정 등의 수학적 분석을 통해 연구되며, 일반화 및 확장을 통해 다양한 상황에 적용될 수 있다. 특히, 각 쿠폰의 복사본을 여러 개 수집해야 하는 경우나, 쿠폰이 뽑힐 확률이 균등하지 않은 경우에도 적용 가능하다. 또한, 극한 정리를 통해 시행 횟수의 분포를 예측할 수 있으며, 귐벨 분포와 관련이 있다.

쿠폰 수집 문제

문제 개요

이름	쿠폰 수집가 문제
분야	확률론
관련 항목	몬테카를로 방법

문제 설명

내용	n 종류의 쿠폰이 있을 때, 모든 종류의 쿠폰을 적어도 한 번 이상 수집하기 위해 필요한 쿠폰 수의 기댓값은 얼마인가?
수학적 정의	무작위로 쿠폰을 선택할 때, 각 쿠폰은 동일한 확률로 선택된다고 가정한다. X를 모든 n 종류의 쿠폰을 수집하기 위해 필요한 쿠폰 수라고 하자. 그러면 X의 기댓값 E(X)는 다음과 같이 주어진다. E(X) = nHn ≈ n log n + γn + 1/2 + o(1) 여기서 Hn은 n번째 조화수, γ는 오일러-마스케로니 상수이다.
점근적 행동	수집해야 하는 쿠폰 수의 분포는 n이 무한대로 갈 때 다음과 같은 점근적 행동을 보인다. Pr(T ≤ n log n + cn) → exp(−e−c) 여기서 T는 모든 쿠폰을 수집하는 데 필요한 시간이고, Pr은 확률을 나타낸다.

변형

일반화된 문제	n개의 쿠폰 중 k개를 수집하는 데 필요한 시간을 묻는 문제
적용	소프트웨어 테스트에서 테스트 케이스를 생성하는 데 사용될 수 있다.

알고리즘

몬테카를로 방법	쿠폰 수집가 문제를 해결하기 위해 몬테카를로 방법을 사용할 수 있다. 이 방법은 무작위 표본을 추출하여 결과를 추정하는 방식으로, 수집해야 할 쿠폰 수의 기댓값을 추정하는 데 활용된다.

📚 더 읽어볼만한 페이지

도박의 수학 - 도박사의 오류
도박사의 오류는 독립적인 확률 사건에서 이전 사건 결과가 이후 사건 결과에 영향을 준다고 믿는 오류로, 인지 편향과 관련되어 비합리적인 판단을 초래하며 확률적 사고 강화와 객관적 데이터 기반 의사 결정으로 극복할 수 있다.
도박의 수학 - 격추확률
확률론 정리 - 베이즈 정리
베이즈 정리는 조건부 확률을 계산하는 방법으로, 사건 A가 일어났을 때 사건 B가 일어날 확률과 사건 B가 일어났을 때 사건 A가 일어날 확률 사이의 관계를 나타내며 사전 확률과 가능도를 이용하여 사후 확률을 계산하고 다양한 분야에서 활용된다.
확률론 정리 - 중심 극한 정리
중심 극한 정리는 독립적인 확률 변수들의 합이 특정 조건에서 정규 분포에 가까워지는 현상을 설명하는 확률론 및 통계학의 중요 정리로, 통계적 추론, 가설 검정 등 다양한 분야에 활용되며 여러 변형이 존재한다.
확률론 - 확률 밀도 함수
확률 밀도 함수는 연속 확률 변수의 확률 분포를 나타내는 함수로, 특정 구간에서 확률 변수가 값을 가질 확률은 해당 구간에 대한 함수의 적분으로 계산되며, 통계적 특성 계산 및 변수 변환 등에 활용되어 불확실성 모델링 및 분석에 중요한 역할을 한다.
확률론 - 체비쇼프 부등식
체비쇼프 부등식은 확률 변수가 평균에서 얼마나 멀리 떨어져 있는지에 대한 확률의 상한을 제공하는 부등식으로, 이레네-쥘 비네메가 처음 공식화하고 체비쇼프와 안드레이 마르코프에 의해 일반화 및 증명되었으며, 확률론적 표현 외에도 측도 공간에 대한 명제로 확장될 수 있다.

1. 개요
2. 수학적 분석
3. 일반화 및 확장
- 3.1. m개씩 수집
- 3.2. 불균등 확률 분포
4. 극한 정리

2. 수학적 분석

쿠폰 수집가 문제의 핵심은 모든 종류의 쿠폰을 수집하는 데 필요한 뽑기 횟수의 기댓값을 구하는 것이다.

이미 쿠폰을 일부 수집한 경우, k를 이미 수집한 쿠폰의 개수라고 하면 기댓값은 다음과 같이 계산된다.

: $\operatorname{E}(T_k) = n \cdot H_{n-k}$

$k=0$ 이면, 즉 처음부터 쿠폰을 수집하는 경우, 원래의 기댓값 계산 결과를 얻는다.

피에르시몽 라플라스, 에르되시 팔과 레니 알프레드는 T의 분포에 대한 극한 정리를 증명했다.

:: $\operatorname{P}(T < n\log n + cn) \to e^{-e^{-c}}, \text{ as } n \to \infty.$

이는 귐벨 분포이다.

도널드 J. 뉴먼과 로렌스 솅은 각 쿠폰의 m개의 복사본을 수집해야 하는 경우로 문제를 일반화했다. T_m을 각 쿠폰의 m개 복사본을 처음 수집하는 시간이라고 할 때, 기댓값은 다음을 만족한다.

:: $\operatorname{E}(T_m) = n \log n + (m-1) n \log\log n + O(n), \text{ as } n \to \infty.$

여기서 m은 고정되어 있다. m = 1일 때, 우리는 기댓값에 대한 이전 공식을 얻는다.

에르되시와 레니는 다음과 같이 더 일반적인 경우를 증명했다.

:: $\operatorname{P}\left(T_m < n\log n + (m-1) n \log\log n + cn\right) \to e^{-e^{-c}/(m-1)!}, \text{ as } n \to \infty.$

필립 플라조레 등은 불균등 확률 분포의 일반적인 경우에 대해 다음과 같은 결과를 얻었다.

:: $\operatorname{E}(T)=\int_0^\infty \left(1 - \prod_{i=1}^m \left(1-e^{-p_it}\right)\right)dt.$

이는 다음과 같이 표현할 수도 있다.

:: $\operatorname{E}(T)=\sum_{q=0}^{m-1} (-1)^{m-1-q} \sum_{|J|=q} \frac{1}{1-P_J},$

여기서 m은 수집해야 하는 쿠폰의 수를 나타내고, P_J는 쿠폰 집합 J에서 어떤 쿠폰이라도 얻을 확률을 나타낸다.

2.1. 기댓값 계산

n종의 쿠폰을 모두 수집하는데 필요한 뽑기 횟수를 T라 하고, t_i를 i-1종의 쿠폰을 수집한 후 i번째 쿠폰을 얻기까지 걸리는 시간이라고 하자. 그러면 $T=t_1 + \cdots + t_n$ 이다. T와 t_i는 확률 변수로 생각할 수 있다. 이때, 새로운 쿠폰을 수집할 확률 p_i는 $p_i = \frac{n - (i - 1)}{n} = \frac{n - i + 1}{n}$ 이다. 따라서 t_i는 기댓값이 $\frac{1}{p_i} = \frac{n}{n - i + 1}$ 인 기하 분포를 따른다. 기댓값의 선형성에 의해 다음이 성립한다.

: $\begin{align}\operatorname{E}(T) & {}= \operatorname{E}(t_1 + t_2 + \cdots + t_n) \\& {}= \operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_n) \\& {}= \frac{1}{p_1} + \frac{1}{p_2} + \cdots + \frac{1}{p_n} \\& {}= \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} \\& {}= n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}\right) \\& {}= n \cdot H_n.\end{align}$

여기서 H_n는 n번째 조화수이다. 조화수의 점근선을 사용하면 다음과 같이 근사할 수 있다.

: $\operatorname{E}(T) = n \cdot H_n = n \log n + \gamma n + \frac{1}{2} + O(1/n),$

여기서 $\gamma \approx 0.5772156649$ 는 오일러-마스케로니 상수이다.

마르코프 부등식을 이용하면 확률의 상한을 구할 수 있다.

: $\operatorname{P}(T \geq cn H_n) \le \frac{1}{c}.$

2.2. 분산 계산

랜덤 변수 t_i의 독립성을 이용하면, 분산을 다음과 같이 계산할 수 있다.

: $\begin{align}\operatorname{Var}(T)& = \operatorname{Var}(t_1) + \operatorname{Var}(t_2) + \cdots + \operatorname{Var}(t_n) \\&= \frac{1-p_1}{p_1^2} + \frac{1-p_2}{p_2^2} + \cdots + \frac{1-p_n}{p_n^2} \\&< \left(\frac{n^2}{n^2} + \frac{n^2}{(n-1)^2} + \cdots + \frac{n^2}{1^2}\right) \\&= n^2 \cdot \left(\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} \right) \\&< \frac{\pi^2}{6} n^2\end{align}$

이는 $\frac{\pi^2}6=\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}+\cdots$ 이기 때문이다 (바젤 문제 참조).

체비쇼프 부등식을 사용하면, 원하는 확률을 결정할 수 있다.
: $\operatorname{P}\left(|T- n H_n| \geq cn\right) \le \frac{\pi^2}{6c^2}$

2.3. 꼬리 추정

$Z_i^r$ 을 처음 $r$ 번의 시도에서 $i$ 번째 쿠폰이 선택되지 않은 사건이라고 정의하면, 다음 식이 성립한다.

: $\begin{align}P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}.\end{align}$

$r = \beta n \log n$ 일 때, $P\left [ {Z}_i^r \right ] \le e^{(-\beta n \log n ) / n} = n^{-\beta}$ 가 된다. $n$ 개의 쿠폰에 대한 합집합 경계를 이용하면 다음을 얻을 수 있다.

: $\begin{align}P\left [ T > \beta n \log n \right ] = P \left [ \bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1^{\beta n \log n} ] \le n^{-\beta + 1}.\end{align}$

3. 일반화 및 확장

피에르시몽 라플라스, 폴 에르되시, 알프레드 레니는 T의 분포에 대한 극한 정리를 증명했다. 이 결과는 이전의 경계에 대한 추가적인 확장이다.

: $\operatorname{P}(T < n\log n + cn) \to e^{-e^{-c}}, \text{ as } n \to \infty.$

이는 귐벨 분포이다.

쿠폰 수집가 문제는 다양한 방식으로 일반화될 수 있다.

3.1. m개씩 수집

도널드 J. 뉴먼과 로렌스 솅은 각 쿠폰을 m개씩 수집해야 하는 경우로 쿠폰 수집 문제를 일반화했다. 각 쿠폰을 m개씩 처음 수집하는 시간을 T_m이라고 하면, 이 경우 기댓값은 다음과 같다.

: $\operatorname{E}(T_m) = n \log n + (m-1) n \log\log n + O(n), \text{ as } n \to \infty.$

여기서 m은 고정되어 있다. m = 1일 때, 위 식은 기댓값에 대한 이전 공식과 같아진다.

폴 에르되시와 알프레드 레니는 위와 같은 일반화 하에서 다음을 유도했다.

: $\operatorname{P}\bigl(T_m < n\log n + (m-1) n \log\log n + cn\bigr) \to e^{-e^{-c}/(m-1)!}, \text{ as } n\to\infty.$

3.2. 불균등 확률 분포

각 쿠폰이 뽑힐 확률이 서로 다른 경우에 대한 일반화도 가능하다. 각 쿠폰이 뽑힐 확률을 p_i라고 하면, 기댓값 E(T)는 다음과 같이 주어진다.

:: $\operatorname{E}(T)=\int_0^\infty \left(1 - \prod_{i=1}^m \left(1-e^{-p_it}\right)\right)dt.$

이것은 다음과 같이 표현할 수도 있다.

:: $\operatorname{E}(T)=\sum_{q=0}^{m-1} (-1)^{m-1-q} \sum_{|J|=q} \frac{1}{1-P_J},$

여기서 m은 수집해야 하는 쿠폰의 수를 나타내고, P_J는 쿠폰 집합 J에서 어떤 쿠폰이라도 얻을 확률을 나타낸다.

4. 극한 정리

에르되시 팔과 레니 알프레드는 T의 분포에 대한 극한 정리를 증명했다. 이 결과는 이전의 경계에 대한 추가적인 확장이다.

: $\operatorname{P}(T < n\log n + cn) \to e^{-e^{-c}}, \text{ as } n \to \infty.$

이는 귐벨 분포이다.

또한, 에르되시와 레니는 각 쿠폰을 m장씩 수집해야 하는 일반적인 경우에 대해서도 극한 정리를 유도했다.

: $\operatorname{P}\bigl(T_m < n\log n + (m-1) n \log\log n + cn\bigr) \to e^{-e^{-c}/(m-1)!}, \text{ as } n\to\infty$