카드 셔플이 잘 되는 시간 - 임성혁 (KAIST 수학과)
[seminar] 2 min read
2019-02-27 16:00, KAIST 오픈동방. 발표자: 임성혁 (KAIST 수학분과장) 참고 논문: Shuffling Cards and Stopping Times (‘86) — David Aldous, Persi Diaconis
트럼프 카드를 몇 번 섞어야 잘 섞인 것인가
발표자는 수학과장. Persi Diaconis 교수는 강의하기 전 마술사였음.
핵심 질문: 트럼프 카드를 몇 번 섞어야 잘 섞였다고 말할 수 있는가?
정의: Markov Chain
\((X_n)_{n=0}^{\infty}\)를 Markov chain이라 할 때:
- 초기: \(N!\) 크기의 확률 vector (모든 배열 동일 확률)
- 섞기: 다른 상태로 보내주는 함수 \(f\)
- \(Q^{*k}\): \(k\)번 섞은 후 카드 상태의 분포
- \(U(\pi) = 1/n!\): 균일 분포
거리 측정
$$\|Q^{*k} - U\| = \frac{1}{2} \sum_{x \in S_n} |Q^{*k}(x) - U(x)| = \max_{A \subseteq S_n} |Q^{*k}(A) - U(A)|$$- 0이면 잘 섞임, 1이면 전혀 안 섞임
Top-in-at-random Shuffle (toy model)
맨 위 카드를 빼서 랜덤한 위치에 꽂기.
Strong Uniform Time
Random variable \(T\)가 Strong Uniform Time이면: \(T\) 이후에는 무조건 잘 섞임.
Lemma: \(P(T > k) \geq \|Q^{*k} - U\|\)
주요 결과
상수 \(c > 0\)에 대해 \(n\log n + cn\) 번 섞으면 잘 섞임.
$$P(V > k) \leq \sum P(\text{i번째 공 안 뽑힘}) = n\left(1 - \frac{1}{n}\right)^k$$\(\left(1 - \frac{1}{n}\right)^n \to e^{-1}\) (단조증가). \(k = n\log n + cn\) 대입하면 수렴값 존재 (Coupon-collector’s problem).
Theorem
$$\|Q^{*k} - U\| \to 1 \text{ as } n \to \infty$$Markov & Chebyshev inequality 활용.
힌두 셔플 vs. 리플 셔플
- 힌두 셔플: 연구결과 없음 (open problem)
- 리플 셔플: \(m\)개와 \(n-m\)개로 분할, 확률 \(\binom{n}{m}/2^n\)
- 더 높은 쪽 카드를 떨어뜨림
- Reeds의 inversion lemma로 정리됨
결론: 대충 14번 섞으면 잘 섞임.
논문이 5페이지 반인데 40분이 금방 잡아먹힘. 크누스가 여기서도 나옴.
분류:KAIST 세미나