무작위성randomness은 어떻게 정의할 수 있을까?

uoctfjtzsimfvgpjbqvaxajlthvtzx
ababababababababababababababab

가능한 모든 길이 30짜리 문자열에서 같은 확률로 두 문자열을 선택하였다면 당연히 두 문자열은 같은 확률을 갖게 된다. 하지만 우리가 보기에 위의 문자열은 아래의 문자열보다 더 무작위적으로 보인다. 즉, 확률적인 논의만으로는 무작위성을 논하는 것이 어렵다. 복잡도/무작위성을 논하는 방법으로 콜모고로프 복잡도Kolmogorov complexity가 있다.

콜모고로프 복잡도는 어떤 대상의 복잡도를 대상을 기술하는 데 필요한 계산 능력으로 설명한다. 임의의 문자열을 기술하는 데 필요한 가장 짧은 프로그램의 길이를 복잡도로 삼는 것이다. 언어의 선택은 사실상 무관한데 임의의 프로그램을 임의의 언어로 기술하여도 서로 간에 번역하는 것이 상수배만큼의 추가적인 작업을 더 하는 것에 불과하기 때문이다.¹

위의 예에서 첫 번째 문자열은 압축해서 표현하기 쉽지 않지만 두 번째 문자열은 'ab' * 15 정도의 압축된 표현이 가능하다. 그런 의미로 두 번째 문자열의 복잡도가 더 낮다.

Occam's Razor에서 모델의 복잡도 이야기를 하였다. 이를 조금 더 엄밀하게 논하기 위해 콜모고로프 복잡도를 사용할 수 있다.

모델의 복잡도를 콜모고로프 복잡도로 대표하도록 하자. 모든 모델이 프로그램으로 기술 가능하다면 모든 모델의 집합은 가산 집합countable set이다. 각 모델에 참인 모델일 확률을 부여하면 당연히 그 합은 1이 되어야 한다. 그러므로 모델의 복잡도가 높아지면 높아질수록 모델이 참일 확률이 낮아져야 한다.²³

모델이 현상을 설명하는 정도를 가능도likelihood라 하면 비슷한 가능도를 가진 -- 같은 현상을 비슷한 정도로 설명할 수 있는 -- 다양한 모델이 있을 것이다. 이런 모델은 각각 대응되는 복잡도가 있는데 최종적으로 모델의 그럴싸함은 가능도와 복잡도로 유도된 확률의 곱으로 표현된다.

위의 논지 전개에서 복잡한 모델이 무조건 선택되지 않는 것은 아님을 주의해야 한다. 복잡한 모델이 참일 확률이 여전히 있고, 모델의 가능도가 크다면 복잡도로 인한 페널티를 덮어버릴 수도 있다. 하지만 모델이 복잡해질수록 복잡도 페널티는 기하급수적으로 증가하게 된다.

안타깝게도 콜모고로프 복잡도는 계산 가능하지 않다uncomputable.⁴ 하지만 우리가 사용하는 직관적인 복잡도의 개념으로 이를 근사할 수 있다.