목록 90개에서 매번 무작위로 하나를 뽑아 보여준다고 하자 (작업 중에 문구를 바꿔 띄우는 스피너 같은 것). 90개를 다 보려면 90번쯤이면 될까.

아니다. 평균 457번이다. 5배다. 1초에 하나씩이면 7분 반.

목록을 한 번 섞어서 처음부터 끝까지 도는 게 아니라 매번 90개 전체에서 다시 뽑기 때문이다. 그러면 이미 본 것이 계속 다시 나온다. 섞어 돌았다면 90번에 정확히 끝났을 일이다.

꼬리가 어디서 생기는지가 핵심이다. 89개를 모았을 때, 남은 마지막 하나가 뽑힐 확률은 90분의 1이다. 그 한 개를 만나는 데만 평균 90번 — 섞어서 돌았다면 90개 전부를 봤을 횟수다.¹

이게 쿠폰 수집가 문제(coupon collector)다. 전부 모으는 데 걸리는 평균 횟수는

n × (1 + 1/2 + 1/3 + … + 1/n)

Footnotes

1. 전부 모으는 기대 횟수는 n·H_n(H_n은 조화수). 그리고 i번째 새 쿠폰까지의 기대 대기는 n/(n-i+1) 이므로 마지막 한 장은 n/1 = n — 단계 중 가장 오래 걸린다. (Coupon collector’s problem — Wikipedia) ↩