교란순열(Derangement)

모자 보관소 직원이 손님 n명의 모자를 뒤섞어 아무렇게나 돌려준다고 합시다. 아무도 자기 모자를 받지 못할 확률은 얼마일까요? 돌려주기 하나는 사람에서 모자로 가는 일대일대응, 곧 순열입니다. 순열에서 제자리에 그대로 있는 것을 고정점⁠(fixed point)⁠이라 하는데, 고정점이 하나도 없는 순열을 교란순열이라 하고 그 수를 $D_n$으로 씁니다. 1708년 프랑스의 수학자 피에르 레몽 드 몽모르가 확률 놀이에 관한 책에서 카드 맞추기 놀이 문제로 다룬 것이 이 문제의 이른 기록으로 꼽힙니다.

손님 명. 다시 돌려주기 1000번 돌려주기 지금은

왼쪽 그림에서 위는 사람, 아래는 모자이고, 선은 누가 어느 모자를 받았는지를 잇습니다. 빨간 세로선이 제 모자를 받은 사람입니다. 오른쪽 막대는 정확한 확률 $D_n/n!$이고, 점선은 $1/e \approx 0.3679$, 흰검은 점은 지금까지 돌려준 결과에서 아무도 제 모자를 못 받은 비율입니다.

포함배제로 세기. 사람 i가 제 모자를 받는 순열들의 집합⁠(set)⁠을 $A_i$라 하면, 교란순열은 어느 $A_i$에도 들지 않는 순열입니다. 정해진 k명이 제 모자를 받는 순열은 $(n-k)!$개이고 k명을 고르는 방법은 $\binom nk$가지이므로, 포함배제 원리⁠(inclusion–exclusion principle)⁠에 따라

$$D_n = \sum_{k=0}^{n} (-1)^k \binom nk (n-k)! = n!\left(1 - \frac1{1!} + \frac1{2!} - \cdots + \frac{(-1)^n}{n!}\right)$$

괄호 안은 $e^{-1}$의 테일러 급수⁠(Taylor series)⁠를 n번째 항에서 자른 것입니다. 그래서 확률 $D_n/n!$은 지수함수⁠(exponential function)⁠의 급수⁠(series)⁠를 따라 $1/e$로 아주 빨리 다가갑니다. 부호가 번갈아 바뀌며 크기가 줄어드는 급수를 중간에서 자르면 오차가 버린 첫 항보다 작으므로, 차이는 $1/(n+1)!$보다 작습니다. n = 6이면 이미 0.0002 안쪽입니다. 손님이 열 명이든 백만 명이든 아무도 제 모자를 못 받을 확률은 약 37%로 거의 같습니다. 실제로 $n \ge 1$이면 $D_n$은 $n!/e$에 가장 가까운 정수입니다. 지금 $D_n$ = , $D_n/n!$ = .

점화식⁠(recurrence relation)⁠. 1번 사람이 받은 모자의 주인을 j라 합시다(n−1가지). j가 1번의 모자를 받으면 나머지 n−2명의 교란순열이 남고, 받지 않으면 1번의 모자를 'j의 모자'로 여겨 n−1명의 교란순열을 세는 것과 같습니다. 그래서 $D_n = (n-1)(D_{n-1} + D_{n-2})$이고, $D_1 = 0,\ D_2 = 1$에서 0, 1, 2, 9, 44, 265, 1854, …가 나옵니다(점화식).

제 모자를 받는 사람 수의 기댓값⁠(expected value)⁠은 n에 상관없이 정확히 1입니다. 사람마다 확률 1/n로 제 모자를 받고, 사건⁠(event)⁠들이 서로 얽혀 있어도 합의 기댓값은 각 기댓값의 합이기 때문입니다(n × 1/n = 1). n이 크면 그 수는 평균⁠(mean)⁠이 1인 푸아송 분포⁠(Poisson distribution)⁠에 가까워집니다. 프랑스의 수학자 푸아송의 이름이 붙은 이 분포는 드물게 일어나는 일이 몇 번 일어나는지를 나타내며, 평균이 λ일 때 k번 일어날 확률은 $e^{-\lambda}\lambda^k/k!$입니다. λ = 1, k = 0을 넣으면 $e^{-1}$이니, n이 클 때 교란순열의 비율이 1/e에 다가간다는 사실과 맞아떨어집니다.

이어지는 곳. 제비뽑기로 선물을 줄 상대를 정하되 누군가 자기 이름을 뽑으면 모두 다시 뽑는 '비밀 산타'에서, 한 번에 성공할 확률이 바로 $D_n/n! \approx 1/e$입니다. 시뮬레이션으로 1/e를 어림하는 것은 몬테카를로 방법⁠(Monte Carlo method)⁠이고, 돌린 횟수가 늘수록 비율이 1/e에 모이는 것은 큰 수의 법칙⁠(law of large numbers)⁠입니다. 무작위 대응에서 직관과 다른 확률이 나오는 또 하나의 예는 생일 문제⁠(birthday problem)⁠입니다.