무작위 알고리즘(Randomized algorithm)

무작위 알고리즘은 계산 도중에 동전을 던지는 알고리즘입니다. 같은 입력을 넣어도 실행할 때마다 다르게 움직이지만, 그 덕분에 평균적으로 빠르거나, 아주 작은 확률로만 틀리는 대신 훨씬 빠릅니다. 우연을 들이는 것은 확실함을 버리는 일처럼 보이지만, 실은 '늘 느린 나쁜 입력'이라는 것을 없애는 방법이기도 합니다.

퀵정렬을 보겠습니다. 늘 구간의 마지막 원소⁠(element)⁠를 피벗으로 쓰면 이미 정렬된 입력에서 $n(n-1)/2$번이나 비교합니다. 누군가 그런 입력만 골라 넣으면 끝입니다. 피벗을 무작위로 고르면, 서로 다른 n개로 된 어떤 입력에 대해서든 비교 횟수의 기댓값⁠(expected value)⁠이 위의 식이 됩니다. 여기서 기댓값은 입력이 아니라 알고리즘이 던지는 동전에 대한 평균입니다. 운이 나쁠 수는 있어도 입력이 나쁠 수는 없게 된 것입니다.

이미 정렬된 목록 를 무작위 피벗 퀵정렬로 정렬합니다. 100번 더 돌리기 처음부터

기댓값은 이렇게 셉니다. 크기로 i번째와 j번째인 두 원소는, 그 사이의 값들(둘을 포함해 $j - i + 1$개) 가운데 둘 중 하나가 가장 먼저 피벗으로 뽑힐 때, 그리고 그때에만 서로 비교됩니다. 사이의 값이 먼저 뽑히면 둘은 서로 다른 쪽으로 갈라져 다시 만나지 않습니다. 이 무리 안에서는 누가 먼저 뽑히든 확률이 같으니, 그 확률은 $2/(j-i+1)$입니다. 모든 쌍에 대해 더하면 조화급수⁠(harmonic series)⁠가 나와 위의 식이 되고, 첫째 항은 $2n \ln n \approx 1.39\,n\log_2 n$입니다. 둘째 항 $-2.85n$도 작지 않아서, n = 100이면 기댓값은 약 648번으로 $2n \ln n \approx 921$보다 꽤 작습니다. 더 반가운 것은 분포가 기댓값 근처에 몰려 있다는 점입니다. 기댓값의 1.5배를 넘는 실행은 거의 볼 수 없고, n이 커질수록 더 드물어집니다.

이처럼 답은 늘 맞고 걸리는 시간만 운에 달린 것을 라스베이거스 알고리즘⁠(Las Vegas algorithm)⁠, 시간은 정해져 있고 아주 작은 확률로 틀리는 것을 몬테카를로 알고리즘⁠(Monte Carlo algorithm)⁠이라 부릅니다. 후자의 대표가 밀러–라빈 소수 판정⁠(primality test)⁠입니다. 1976년 미국의 게리 밀러가 만든 판정법(일반화된 리만 가설⁠(Riemann hypothesis)⁠이 참이라면 늘 옳은 결정적 방법)을 1980년 마이클 라빈이 무작위 알고리즘으로 고친 것입니다. 수 n을 판정할 때 1과 n 사이의 수 a(밑)를 무작위로 골라, n이 두 조건을 만족하는지 확인합니다. 하나는 페르마의 소정리에서 나오는 거듭제곱 조건이고, 다른 하나는 소수⁠(prime number)⁠를 법으로 하면 1의 제곱근이 ±1뿐이라는 조건입니다. 첫째 조건만 보면 카마이클 수⁠(Carmichael number)⁠라는 합성수⁠(composite number)⁠가 (n과 서로소⁠(coprime)⁠인) 모든 밑을 통과해 버리기 때문에 둘째 조건이 필요합니다. 소수는 어떤 밑으로도 이 검사를 늘 통과합니다. 반면 홀수 합성수가 무작위로 고른 밑 하나의 검사를 통과할 확률은 1/4 이하입니다. 그러니 번 독립⁠(independence)⁠으로 검사하면 합성수를 소수라고 잘못 말할 확률은 이하입니다. RSA에 쓸 수백 자리 소수를 이렇게 찾습니다. '몬테카를로'라는 이름은 넓이⁠(area)⁠를 무작위 점으로 어림하는 몬테카를로 방법⁠(Monte Carlo method)⁠에서 빌려 왔습니다. 둘 다 운에 따라 답이 조금 어긋날 수 있다는 점이 같습니다.

이어지는 곳. 해시 테이블⁠(hash table)⁠은 해시 함수⁠(hash function)⁠를 무작위로 골라 일부러 만든 충돌 공격을 막고, 무작위 대조 시험⁠(randomized controlled trial)⁠은 처치를 무작위로 배정해 교란, 곧 처치 말고 결과에 영향을 주는 다른 원인이 한쪽 무리에 몰리는 일을 끊습니다. 둘 다 상대(입력을 고르는 사람, 숨은 변수)가 우리의 선택을 미리 알 수 없게 만드는 전략입니다. 무작위로 고른 대상이 원하는 성질을 가질 확률이 0보다 크면 그런 대상이 있다는 확률적 방법⁠(probabilistic method)⁠은 같은 생각을 증명에 쓴 것입니다. 무작위성이 계산을 본질적으로 빠르게 하는지는 아직 열린 문제로, 많은 이들은 그렇지 않다고, 곧 무작위 알고리즘이 빠르게 푸는 문제는 동전 없이도 빠르게 풀린다고 추측합니다(BPP = P 추측). 2002년 인도 공과대학 칸푸르의 아그라왈, 카얄, 삭세나가 소수 판정을 무작위 없이 다항 시간⁠(polynomial time)⁠, 곧 자릿수의 다항식⁠(polynomial)⁠만큼의 걸음에 하는 방법(AKS)을 찾아낸 것도 그 방향의 증거로 꼽힙니다. 이 물음은 P 대 NP 문제⁠(P versus NP problem)⁠와 나란히 계산 복잡도 이론⁠(computational complexity theory)⁠의 큰 물음입니다.