쿠폰 수집기 문제

확률론에서 쿠폰수집자의 문제는 "모든 쿠폰을 모아서 이기는" 콘테스트를 기술한다.다음과 같은 질문을 던진다.시리얼 브랜드의 각 박스에 쿠폰이 들어 있고, 쿠폰 종류가 n개라면, 모든 쿠폰을 모으기 위해 t박스 이상을 사야 할 확률은 얼마인가?대안은 다음과 같다: 쿠폰이 n개인 경우, 각 쿠폰을 한 번 이상 추첨하기 전에 교체 쿠폰을 몇 개까지 추첨해야 할 것으로 예상하십니까?문제의 수학적 분석에 따르면 $\theta {\displaystyle \mathrm{}}$(${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle n}$ ${\displaystyle \Teta (n\log(n)}}$에 따라 필요한 시험의 예상 횟수가 증가한다는 것을 알 수 있다$.$^[a] 예를 들어, n = 50일 경우, 쿠폰 50장을 모두 회수하는 데 평균 약 225회의^[b] 시험이 소요된다.

해결책

기대치 계산

시간 T는 모든 n개의 쿠폰을 모으는 데 필요한 추첨 횟수로 하고, i - 1 쿠폰을 모은 후에는 i번째_i 쿠폰을 모으는 시간으로 한다.그러면 $T{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$+ ${\displaystyle \cdots }$+ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$ T와 t를_i 랜덤 변수로 생각한다.새 쿠폰을 수집할 확률은 ${\displaystyle p_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle n\frac{}{}}$- (${\displaystyle \frac{\mathrm{i}}{}}$- 1${\displaystyle \frac{}{}}$)${\displaystyle \frac{}{}}$= n${\displaystyle \frac{}{}}$- ${\displaystyle \frac{i}{}}$+ ${\displaystyle \frac{}{}}$ ${\$임을 확인하십시오$.$따라서 t ${\displaystyle i_{}}$ ${\$은(는) ${\displaystyle \frac{{기대치}_{}}{}}$ $1{\displaystyle \frac{\mathrm{}}{{}_{}}\frac{p}{}}$i =${\displaystyle \frac{n}{}}$ - ${\displaystyle \frac{\mathrm{i}}{}}$ + 1 ${\$ {$1}{p_{i}}}={\frac {n}{n-i+1}}}}}}}}$을(를) 가진 기하학적 분포가$$ 있다$.$ 기대치:

${\displaystyle{\begin{정렬}\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}}}+{\frac{1}{p_{n}}}\\& +\cdots,{}={\frac{n}{n}}+{\frac{n}{n-1}};{}=n\ +{\frac{n}{1}}\\& +\cdots.cdot \left({\frac{1}}{1}+{\frac {1}{2}}+\cdots +{\frac {1}{n}\오른쪽)\\&{}=n\cdot H_{n}.\end{정렬}}}$

여기서 H는_n n번째 고조파 수입니다.고조파 숫자의 점근법을 사용하여 다음을 얻는다.

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

여기서 $\gamma {\displaystyle \mathrm{}\approx }$ 0${\displaystyle .5772156649}$ ${\displaystyle \gamma$ \gamma \$약 0.5772156649}$은 오일러-마스체로니 상수이다.

마르코프 부등식을 사용하여 원하는 확률에 바인딩:

${\displaystyle \operatorname {P}(T\geq cnH_{n})\leq {\frac {1}{c}.}$

위 내용은 이미 쿠폰 일부를 회수했을 때 케이스 처리를 위해 약간 수정할 수 있다.k를 이미 수집된 쿠폰의 개수로 설정한 후:

${\displaystyle {\begin{aligned}\operatorname {E} (T_{k})&{}=\operatorname {E} (t_{k+1}+t_{k+2}+\cdots +t_{n})\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n-k}}\right)\\&{}=n\cdot H_{n-k}\end{arged}}}}$

$그리고{\displaystyle }$ k${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0}$이(가) 되면 원래의 결과가 나온다.

분산 계산

랜덤 변수 t의_i 독립성을 사용하여 다음을 얻는다.

${\displaystyle{\begin{정렬}\operatorname{바르}(T)&,{}=\operatorname{바르}(t_{1}+\cdots{n+t_})\\&,{}=\operatorname{바르}(t_{1})+\operatorname{바르}(t_{2})+\cdots+\operatorname{바르}(t_{n})\\&,{}={\frac{1-p_{1}}{p_{1}^{2}}}+{\frac{1-p_{2}}{p_{2}^{2}}};{}<, \left({\frac{{2n^}}{n^{2}}}++{\frac{1-p_{n}}{p_{n}^{2}}}\\& +\cdots.{\frac{{2n^}}{(n-1)^{2}}:}+\cdots +{\frac{n^{2}}:{1^{2}}\오른쪽)\\&{}=n^{2}\cdot \left\frac {1}{1^{2}}:}+{1}{1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}\오른쪽)\\\&{}<{\frac {\pi^{2}}:{6}n^{2}\end{aigned}}}}}$

since ${\displaystyle {\frac {\pi ^{2}}{6}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots }$ (see Basel problem).

체비셰프 부등식을 사용하여 원하는 확률 제한:

${\displaystyle \operatorname {P} \left(T-nH_{n}\geq cn\right)\leq {\frac {\pi^{2}}{6c^{2}}.}$

꼬리 추정치

상부 꼬리에 대한 더 강력한 꼬리 추정치는 다음과 같이 구한다.$Z{\displaystyle }$ i ${\displaystyle {}_{}^{}}$ ${\$은(는) 첫 $번째$ r ${\displaystyle i}$ -th$$ 쿠폰이 선택되지 않은 이벤트를 나타낸다$$.그러면

${\displaystyle {\reasoned}P\왼쪽[{Z}_{i}^{r}\오른쪽]=\왼쪽(1-{\frac {1}{n}\오른쪽)^{r}\leq e^{-r/n}\end{정렬}}}$

Thus, for ${\displaystyle r=\beta n\log n}$, we have ${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$. Via a union bound over the ${\displaystyle n}$ coupons, we obtain

${\displaystyle {\reasoned}P\좌[T]\베타 n\log n\우]=P\\왼쪽[\bigcup _{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n}}}\leq n^{-\beta +1}.\end{정렬}}}$

확장 및 일반화

• 피에르 시몬 라플레이스는 물론 폴 에르드스와 알프레드 레니도 T의 분배를 위한 한계 정리를 증명했다.이 결과는 이전 한도의 추가 연장이다.

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

• 도날드 J. 뉴먼과 로렌스 셰프는 각 쿠폰의 m 카피를 수집해야 할 때 쿠폰 수집기의 문제를 일반화했다.각 쿠폰의 m 복사본이 수집되는 것은 T가_m 처음이다.그들은 이 경우에 대한 기대가 다음을 충족한다는 것을 보여주었다.

${\displaystyle \operatorname {E}(T_{m})=n\log n+(m-1)n\log \log n+O(n),{\text{{}를 }n\n\to \inflt.}로 표시$

여기 m은 고정되어 있다.m = 1일 때 우리는 기대치에 대한 더 이른 공식을 얻는다.

• Erdős 및 Rényi에 의한 일반적인 일반화:

${\displaystyle \operatorname {P} \left(T_{m}) \log n+(m-1)n\log n+cn\right)\to e^{-e^{-c}/(m-1)!},{\text{}n\n\to \fto.}}$

• 필립 플라졸레에 따르면 균일하지 않은 확률 분포의 일반적인 경우,^[1]

${\displaystyle \operatorname {E}(T_{m})=\int _{0}^{\infit }\좌측(1-\prod _{i=1}^{m}\좌측(1-e^{p_{i}t}\오른쪽)dt.}$

이것은 와 같다.

${\displaystyle \operatorname {E}(T_{m})=\sum _{q=0}^{m-1-q}\sum _{J =q}{\frac {1}{1-P_{J}}}}}}}}}}}}}}}}}$

여기서 m은 수집할 쿠폰의 수를 나타내며, P는_J 쿠폰 J 세트의 쿠폰을 받을 확률을 나타낸다.

참고 항목

• 와터슨 추정기
• 생일 문제

메모들

참조

외부 링크

• 울프램 시연 프로젝트인 에드 페그 주니어의 "쿠폰 수집기 문제".매스매티카 패키지.
• 도론 질베르거의 짧은 노트인 '쿠폰 수집기'는 얼마나 많은 싱글, 더블, 트리플 등, 몇 개의 싱글을 예상해야 하는가?