Sₙ상에서의 무작위 행보

초록

"이거 모르면 오함마로 손목 찍힙니다."

n장의 카드 중 두 장을 무작위로 선택하여 서로 교환하는 시행을 반복한다고 하자. 이 과정은 symmetric group Sₙ에서 무작위로 선택된 transposition을 왼쪽에 곱하는 Sₙ 위의 random walk로 볼 수 있다.

본 세미나의 목표는 이러한 확률 과정을 통해 카드의 순서에 대한 확률 분포가 얼마나 빠르게 균등 분포에 가까워지는지 살펴보는 것이다. 특히 확률분포의 convolution을 finite group에서의 Fourier transform을 이용하여 분석할 수 있음을 설명하고, 이 과정에서 group representation이 어떻게 사용되는지 소개한다.

Abstract

"If you don’t know this, your wrist gets smashed with a sledgehammer"

Consider a process where two cards are randomly selected and swapped among n cards. This process can be viewed as a random walk on the symmetric group Sₙ, generated by multiplying a randomly chosen transposition on the left.

The objective of this seminar is to examine how quickly the probability distribution of the card order converges to a uniform distribution through this stochastic process. In particular, we will explain how the convolution of probability distributions can be analyzed using the Fourier transform on finite groups, and introduce how group representation theory is applied in this context.