여섯 면이 모두 나올 때까지 공정한 주사위를 던지십시오. 던지기 횟수의 기댓값은 14.7입니다(첫 번째와 두 번째 링크, 같은 합을 인수분해한 형태와 펼친 형태). 논리는 한 줄입니다. 아직 k면이 남아 있는 동안 각 던지기는 k/6의 확률로 새 면이므로, 다음 새 면을 기다리는 일은 기댓값 6/k인 기하 시행이고, 합은 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6입니다. 세 번째 링크는 쿠폰 다섯 개로 같은 문제를 풀어 11.416666666667을 얻습니다. 네 번째 6⁶ = 46656은 여섯 번 던지는 가능한 수열의 수입니다. 이 질문에는 잘못된 도구이지만 이웃한 질문에는 맞는 분모입니다. 첫 여섯 번의 던지기에서 이미 여섯 면이 모두 나올 확률은 6!/46 656으로, 1.5퍼센트를 간신히 넘습니다.
답의 형태가 수 자체보다 중요합니다. n·H_n은 n ln n처럼 자라므로 비용은 거의 전부 마지막 몇 쿠폰에 있습니다. 백 개를 모으는 데는 100·H₁₀₀ = 518.7번의 시도가 들고, 그중 마지막 하나만으로 백 번을 차지합니다. 첫 번째는 던지기 한 번입니다. 이 비대칭이 무료 토큰 제도가 끝에서 멈춘 듯 느껴지게 하는 이유이고, 수집 카드 한 벌에서 마지막 피겨가 가장 비싼 이유이며, 모든 값을 봐야 하는 무작위 알고리즘이 같은 조화수 값을 치르는 이유입니다. 흩어짐도 같은 방향입니다. 척도를 바꾼 대기 시간의 분포는 굼벨 법칙에 접근하는데, 오른쪽 꼬리가 길어서 운 없는 수집가는 크고 예측 가능한 폭만큼 운이 나쁩니다.
답
14.7
읽는 방법
여섯째 조화수의 여섯 배입니다. 두 번째 링크는 같은 합을 항별로 펼친 것이고, 세 번째는 여섯 대신 다섯 쿠폰, 네 번째는 여섯 번 던지는 모든 수열입니다.
출처
the coupon collector's problem in Feller, 'An Introduction to Probability Theory and Its Applications', volume 1 (1950), where it is posed as the baseball-card question; the expectation n·H_n and the Gumbel limit of the rescaled waiting time are standard
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.