확률 검색 결과

해당 글 2건

스포츠 경기 레이팅 (ELO) 시스템, 사람들의 실력을 어떻게 수학적으로 정의할 것인가?

회사에서 배드민턴 동아리 활동을 했다. 인기가 많은 동아리라 참여 인원이 많았고, 이에 자동 매칭 시스템을 만들어봐야겠다는 동기가 생겼다. 필연적으로 다음 과제를 해결해야한다: 사람들의 실력을 어떤 방식으로 정량화를 할 수 있을까? 그 고민의 결과가 나름 재미있어서 블로그에 옮겨보았다. 잘 정립된 기존 방식 중 하나는 FargoRate라는 것이 있다. 상대 전적에 따라 점수가 결정되며, 초보자는 100점, 월드 클래스 선수는 800점대로 분포가 된다. 가장 중요한 특징은 두 플레이어가 맞붙었을 때 승패 확률이 레이팅에 의해 결정된다는 점이다. 300점대의 두 플레이어가 붙었을 때 이길 확률은 서로 동일하며, 300점대 플레이어와 400점대 플레이어가 붙어서 나올 승패의 확률도 어느 정도 결정되어있다. 하..
Mathematics 2024. 12. 24. 12:24

생일 패러독스, 생일 공격

$n$명의 사람이 있다. 이 사람들의 생일이 모두 다를 확률은 얼마나 될까? $$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right) $$ 이다. 이 경우 $n = 23$만 되어도 이미 확률이 절반 이하가 된다. 생각보다 적은 수의 사람이 모여도 꽤 높은 확률로 생일이 같은 두 사람을 찾을 수 있다는 것이 생일 패러독스이다. 이를 이용하여 충돌쌍 하나를 효과적으로 구하는 암호론적 공격이 생일 공격이다. 해시함수의 충돌값을 찾거나, 블록암호를 공격할 때 사용된다. Factoring 문제를 효과적으로 푸는 Pollard's rho 랜덤 알고리즘도 똑같은 원리를 기반으로 한다. 특히 블록암호에서 어떤 함수 $G$에 대해 $G(x) = G(y)$인 서로 다른 문자열 $x,..
Mathematics 2020. 4. 3. 00:46