namuid(r9 판)

유니코드 기준 현대 한글의 모든 완성형 글자는 총 $19 \times 21 \times 28 = 11,172$자이며, $6$개의 문자가 연달아 사용되므로 표본 공간의 크기는

입니다. 편의상 이를 $N$이라고 하겠습니다.

하나의 작업에서 $x$개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 $p$로 둡시다. 예를 들어 $p = 30\%$라면 대략 $30\%$의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다.

이어서 이 확률식을 역으로 계산하여 '식별자 충돌이 발생할 확률이 $p$ 이상이기 위해서는 적어도 $x$개의 식별자를 생성해야 하는지'를 보이려고 합니다. namuid의 식별자 충돌이 거의 불가능함을 보이고 싶으므로 $p = 0.1\%$로 두고 테일러 전개로 필요한 표본의 수 $x$의 하한을 근사해 봅시다. 일단 자명하게

이므로 어떤 함수 $f(x)$에 대해 $f(x) \leq 1 - p$ 를 성립시키는 가장 큰 $x$를 근사하면 됩니다. 우선 위에 쓴 $p$를 구하는 수식을 곱의 형태로 정리해 봅시다.

이어서 $e^{-\frac kN}$을 테일러 전개하고 선형 근사를 구하면

이 근사를 적용해서 '어떤 함수' $f(x)$가 $1 - p$를 근사하도록 조립해 봅시다.