확률적 방법(Probabilistic method)

어떤 성질을 가진 대상이 있다는 것을 보이는 가장 직접적인 방법은 그것을 만들어 보이는 것입니다. 확률적 방법은 반대로 갑니다. 대상을 무작위로 골랐을 때 원하는 성질을 가질 확률이 0보다 크다는 것만 보입니다. 그러면 그런 대상이 적어도 하나 있어야 합니다. 어느 것인지는 몰라도 됩니다.

가장 많이 쓰는 도구는 평균입니다. 무작위로 정해지는 수, 곧 확률변수⁠(random variable)⁠ X의 기댓값⁠(expected value)⁠이 E이면 X ≤ E인 경우와 X ≥ E인 경우가 반드시 둘 다 (0보다 큰 확률로) 있습니다. 모두가 평균⁠(mean)⁠보다 클 수는 없으니까요. 점 개를 모두 이은 그래프의 변마다 따로따로 동전을 던져 빨강이나 파랑으로 칠하면, 세 점이 이루는 삼각형 $\binom n3$개 각각이 한 색일 확률은 $2\cdot(1/2)^3 = 1/4$입니다. 그래서 한 색 삼각형 수의 기댓값은 $\binom n3/4$ = 입니다.

다시 칠하기 500번 칠하기 지금 한 색 삼각형은 개입니다.

그러니 한 색 삼각형이 $\binom n3/4$개 이하인 칠하기가 반드시 있습니다. 칠하기가 $2^{\binom n2}$가지나 되어도 하나하나 볼 필요가 없습니다.

에르되시의 램지 하한. 1947년 에르되시는 같은 계산으로 램지 수의 아래쪽 한계를 얻었습니다. $K_n$을 무작위로 칠할 때, 점 k개짜리 한 색 완전 그래프⁠(complete graph)⁠의 개수 X의 기댓값은

$$\mathbb E[X] = \binom nk\, 2^{\,1-\binom k2}$$

입니다. 이것이 1보다 작으면 X = 0인 칠하기, 곧 한 색 $K_k$가 전혀 없는 칠하기가 있으므로 $R(k,k) > n$입니다. 계산해 보면 $n = \lfloor 2^{k/2} \rfloor$에서 이미 기댓값이 1보다 작아서(k ≥ 3) $R(k,k) > 2^{k/2}$입니다. 핵심은 $\binom nk \lt n^k/k!$라는 어림으로, 이것을 넣으면 기댓값이 $2^{1+k/2}/k!$보다 작아집니다. k = 로 바꿔 보세요.

이상한 점은, k가 크면 무작위로 칠한 것이 거의 틀림없이 성공하는데도 그런 칠하기를 직접 만드는 방법은 이 한계에 크게 못 미친다는 것입니다. 위쪽 한계는 램지 이론⁠(Ramsey theory)⁠의 이항계수⁠(binomial coefficient)⁠ 한계로 $4^k$보다 조금 작은 정도입니다. 아래쪽 한계의 밑 $\sqrt2$는 1947년 이후 그대로이고, 위쪽은 2023년에야 캄푸스, 그리피스, 모리스, 사하스라부데 네 수학자가 $(4-\varepsilon)^k$(ε는 아주 작은 양수)로 밑을 처음 줄였습니다.

더 넓게. 변이 m개인 그래프의 점을 무작위로 두 편으로 나누면 변마다 확률 1/2로 두 편 사이를 가로지르므로, 가로지르는 변이 m/2개 이상인 나눔이 반드시 있습니다.

섀넌은 무작위로 고른 부호들의 평균 오류율을 계산해, 잡음이 있는 통로에서도 보내는 속도⁠(velocity)⁠가 통로 용량⁠(channel capacity)⁠보다 낮기만 하면 오류를 얼마든지 줄이는 오류 정정 부호⁠(error-correcting code)⁠가 존재함을 보였습니다(통로 부호화 정리⁠, noisy-channel coding theorem⁠). 이 증명도 '어느 부호인지'는 알려 주지 않았고, 실제로 그에 가까운 부호를 만들기까지 수십 년이 걸렸습니다.

비트열 하나를 출력하는 가장 짧은 프로그램의 길이를 그 비트열의 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠라 합니다. 길이 n인 비트열은 $2^n$개인데, 길이가 n보다 짧은 비트열(프로그램)은 모두 합쳐 $1 + 2 + \cdots + 2^{n-1} = 2^n - 1$개뿐입니다. 프로그램 하나는 비트열 하나만 출력하므로, 자기보다 짧은 프로그램으로는 만들 수 없는 비트열, 곧 더 짧게 줄일 수 없는 비트열이 반드시 있습니다. 이것은 확률 대신 개수로 한 같은 논법, 곧 비둘기집 원리⁠(pigeonhole principle)⁠입니다.

이어지는 곳. 존재 증명에 쓰던 무작위성을 계산에 쓰면 무작위 알고리즘⁠(randomized algorithm)⁠이 됩니다. 위에서 500번 칠해 평균을 낸 실험은 몬테카를로 방법⁠(Monte Carlo method)⁠이고, 칠한 횟수가 늘수록 그 평균이 기댓값에 모이는 것은 큰 수의 법칙⁠(law of large numbers)⁠입니다. 반 데르 바르던 수⁠(van der Waerden number)⁠의 아래쪽 한계도 같은 방법으로 얻습니다(반 데르 바르던 정리⁠(van der Waerden's theorem)⁠). 계산의 대부분은 이항계수를 어림하는 일이고, 여기에는 스털링 공식⁠(Stirling's formula)⁠이 쓰입니다.