무작위성(Randomness)

동전 한 번의 앞뒤는 누구도 맞힐 수 없습니다. 그런데 공정한 동전을 만 번 던지면 앞면이 4,900번에서 5,100번 사이일 확률⁠(probability)⁠은 약 96%이고, 4,800번에서 5,200번 사이일 확률은 99.99%가 넘습니다. 하나하나는 모르는데 모두 모으면 압니다. 무작위성이라는 큰 생각⁠(big ideas)⁠은 이 역설에서 출발해 세 갈래로 뻗습니다. 모르는 것을 셈하는 언어가 되고(확률), 흉내 내어 계산하는 도구가 되고, 일부러 제비를 뽑아 존재를 증명하고 편향을 끊는 방법이 됩니다. 그리고 끝에 가서는 '무작위란 무엇인가'라는 질문 자체가 수학의 대상이 됩니다. 먼저, 같은 무작위가 분야마다 다른 이름으로 불리는 모습부터 봅시다.

아래 그림의 동전 던지기 300줄(줄마다 600번)은 한 번만 만들어 둔 것입니다. 렌즈만 바꿔 같은 자료를 세 가지로 읽어 봅니다. 렌즈: . 출발점 $k =$ , 벽 $N =$ , 확산 렌즈의 시간 $t =$ . 동전 새로 던지기

세 렌즈는 같은 수학의 세 얼굴입니다. 벽 없이 걸으면 평균⁠(mean)⁠ 위치는 0인데 퍼짐은 $\sqrt t$로 자라고, 분포는 종 모양이 됩니다(무작위 행보⁠(random walk)⁠, 중심극한정리⁠(central limit theorem)⁠). 벽을 세우고 k에서 출발시키면 같은 걸음이 도박꾼의 파산이 되어, N에 먼저 닿는 비율이 k/N에 모입니다. 출발점을 모두 바꿔 가며 그 비율을 재면 직선이 나오는데, 이것은 양 끝 온도를 0과 1로 고정한 막대가 열방정식⁠(heat equation)⁠에 따라 오래 지나 도달하는 온도 분포입니다. 뒤의 둘은 '각 값은 양옆 값의 평균'이라는 같은 방정식을 풀고 있기 때문입니다. 첫째 렌즈의 분포도 '다음 순간의 값은 지금 양옆 값의 평균'이라는, 같은 방정식의 시간이 흐르는 판(이산 열방정식)을 따릅니다. 그러니 무작위 걸음을 많이 흉내 내어 평균을 내는 것은 열방정식을 푸는 한 방법, 곧 몬테카를로 방법⁠(Monte Carlo method)⁠입니다.

도박판에서 온 편지. 확률의 수학은 도박에서 시작했습니다. 16세기 밀라노의 카르다노는 주사위의 경우를 세는 글을 남겼지만 그 책은 그가 죽고 한 세기 가까이 지나서야 출판되었습니다. 전환점은 1654년 파스칼과 툴루즈의 페르마가 주고받은 편지입니다. 도중에 멈춘 내기의 판돈을 어떻게 나눌지 묻는 '분배 문제⁠(problem of points)⁠'에 두 사람은 앞으로 일어날 수 있는 모든 경우를 세어 답했고, 이것이 기댓값⁠(expected value)⁠의 출발이 되었습니다(파스칼의 삼각형⁠(Pascal's triangle)⁠, 이항계수⁠(binomial coefficient)⁠). 학술지가 없던 시절 학자들이 편지로 문제를 돌려 보던 편지 공화국의 전형적인 장면입니다. 이듬해 파리에서 이 이야기를 들은 네덜란드의 크리스티안 하위헌스가 1657년 첫 확률 책을 내며 마지막 문제로 도박꾼의 파산을 실었습니다. 이 모든 계산의 밑바닥에는 대칭이 있습니다. 주사위의 면이 서로 구별되지 않으니 각 면의 확률이 같다고 놓는 것입니다.

모르는 것이 모이면 법칙이 된다. 바젤의 야코프 베르누이는 20년 가까이 매달린 『추측술』(1713년 출판)에서 큰 수의 법칙⁠(law of large numbers)⁠을 처음 증명해, 확률을 오래 되풀이한 실험의 비율과 이었습니다. 1733년 런던의 위그노 망명자 드무아브르는 동전을 많이 던졌을 때 앞면 수의 분포가 종 모양 곡선에 다가가며 그 폭이 $\sqrt n$에 비례함을 보였고(이항분포⁠(binomial distribution)⁠, 정규분포), 라플라스는 이것을 동전에만 해당하는 사실이 아니라, 서로 독립⁠(independence)⁠인 작은 요인을 많이 더하면, 어느 하나가 전체를 좌우하지 않는 한 그 합이 근사적으로 종 모양 분포를 따른다는 정리로 넓혔습니다. 역설적이게도 라플라스는 우주의 모든 입자의 위치와 속도⁠(velocity)⁠를 아는 지성에게는 미래가 확실하다고 믿었습니다. 그에게 확률은 세계의 성질이 아니라 우리의 무지를 다루는 셈법이었습니다. 19세기 말 골턴은 못 박힌 판에 구슬을 떨어뜨리는 장치로 종 모양이 생겨나는 것을 보여 주었고, 부모와 자녀의 키에서 평균으로의 회귀⁠(regression to the mean)⁠를 찾아내 통계학⁠(statistics)⁠의 탄생으로 이어지는 길을 열었습니다.

걸음에서 확산으로. 1827년 식물학자 로버트 브라운은 물 위에 뜬 꽃가루에서 나온 작은 입자들이 쉬지 않고 떠는 것을 현미경으로 보았습니다. 1900년 파리의 수학자 루이 바슐리에는 주가의 오르내림을 같은 수학으로 다루는 학위 논문을 썼고, 1905년 아인슈타인은 그 떨림이 보이지 않는 분자들의 무수한 충돌이 만든 무작위 걸음이라고 설명하며 퍼짐이 시간의 제곱근으로 자란다는 예측을 내놓았습니다. 몇 해 뒤 물리학자 장 페랭의 실험이 이 예측을 확인하면서, 원자의 실재를 의심하던 과학자들도 대부분 이를 받아들였습니다. 그림의 확산 렌즈가 바로 그 현상이고, 푸리에가 1822년 열을 두고 세운 방정식이 무작위 걸음의 무리가 따르는 방정식이기도 했던 것입니다. 걸음이 지금 위치에만 달려 있다는 성질을 일반화한 것이 마르코프의 연쇄입니다. 그는 1913년 푸시킨의 『예브게니 오네긴』에서 모음과 자음이 이어지는 빈도를 세어 그 이론을 시험했고(마르코프 연쇄⁠, Markov chain⁠), 이 생각은 섀넌의 n-그램⁠(n-gram)⁠을 거쳐 링크를 무작위로 따라가는 사람이 머무는 비율인 페이지랭크⁠(PageRank)⁠까지 이어집니다. 이 모든 것을 한 언어로 묶은 것은 1933년 모스크바의 콜모고로프가 확률을 공리⁠(axiom)⁠ 위에 세운 일입니다. 그는 확률을 길이나 넓이⁠(area)⁠를 복잡한 집합⁠(set)⁠까지 넓힌 크기, 곧 측도⁠(measure)⁠의 한 종류로 보고 공리 셋만 두었습니다. 확률은 0 이상이고, 일어날 수 있는 모든 결과 전체의 확률은 1이며, 겹치지 않는 사건⁠(event)⁠들의 확률은 (첫째, 둘째, …로 셀 수 있게 무한히 많아도) 더해진다는 것입니다. 동전을 열 번 던져 나온 앞면 수처럼 우연에 따라 값이 정해지는 양을 확률변수⁠(random variable)⁠라 하는데, 이 틀에서는 그것이 결과 하나하나에 수를 하나씩 주는 함수⁠(function)⁠가 됩니다.

흉내 내어 계산하기. 1777년 프랑스의 박물학자 뷔퐁은 평행선 위에 바늘을 던져 선에 걸치는 비율로 π가 나온다는 것을 보였습니다(뷔퐁의 바늘⁠, Buffon's needle⁠). 바늘 길이가 선 간격과 같으면 걸칠 확률은 2/π입니다. 무작위로 계산한다는 생각이 도구가 된 것은 2차 세계대전 뒤 로스앨러모스에서였습니다. 폴란드 출신 수학자 스타니스와프 울람과 폰 노이만은 중성자가 물질 속을 떠도는 과정을 난수로 수없이 흉내 내 평균을 구하는 방법을 ENIAC에서 실행했고, 도박의 도시 이름을 따 몬테카를로 방법이라 불렀습니다(프린스턴과 로스앨러모스). 오늘날 무작위는 알고리즘⁠(algorithm)⁠ 곳곳에 섞여 있습니다. 호어의 퀵정렬⁠(quicksort)⁠은 피벗⁠(pivot)⁠, 곧 기준으로 삼아 나머지를 그보다 작은 쪽과 큰 쪽으로 나누는 원소⁠(element)⁠를 무작위로 고르면 어떤 입력에서도 평균적으로 빠르고(정렬 알고리즘⁠(sorting algorithm)⁠), 밀러–라빈 소수 판정⁠(primality test)⁠은 페르마의 소정리⁠(Fermat's little theorem)⁠를 다듬은 검사를 무작위로 고른 밑 a로 되풀이합니다. 합성수(1과 자신 말고도 약수⁠(divisor)⁠가 있는 수)라면 한 번의 검사에서 적어도 3/4의 확률로 들통나니, 합성수⁠(composite number)⁠가 검사 20번을 모두 통과할 확률은 $4^{-20}$ 이하, 곧 1조분의 1보다 작습니다. 그리고 RSA의 열쇠는 무작위로 고른 큰 소수⁠(prime number)⁠에서 만들어집니다. 무작위 알고리즘⁠(randomized algorithm)⁠을 쓸 때 조심할 곳도 확률이 알려 줍니다. 자료를 무작위처럼 흩어 칸에 넣는 해시 테이블⁠(hash table)⁠에서 두 자료가 같은 칸에 떨어지는 충돌은 생일 문제⁠(birthday problem)⁠처럼 생각보다 훨씬 일찍 일어납니다(무작위 알고리즘).

무작위로 존재를 증명하기. 1947년 에르되시는 세 쪽짜리 논문에서, 사람들 사이의 관계를 동전을 던져 정하면 서로 다 아는 k명도 서로 다 모르는 k명도 없을 확률이 0보다 크다는 것을 보였습니다. 확률이 0보다 크니 그런 관계망이 적어도 하나는 존재하고, 여기서 램지 수⁠(Ramsey number)⁠, 곧 서로 다 아는 k명이나 서로 다 모르는 k명이 반드시 생기게 하는 가장 작은 인원이 $2^{k/2}$보다 크다는 하한⁠(lower bound)⁠이 나옵니다(확률적 방법⁠(probabilistic method)⁠, 부다페스트의 수학자들). 한 해 뒤 벨 연구소의 섀넌은 통로 부호화 정리⁠(noisy-channel coding theorem)⁠를 같은 방식으로 증명했습니다. 무작위로 고른 긴 부호는 거의 언제나 좋으니 좋은 부호가 존재한다는 것입니다. 두 증명 모두 존재는 보여도 예를 보여 주지는 않습니다. 램지 문제에서 무작위만큼 좋은 관계망을 구체적으로 적어 내는 방법은 지금도 찾지 못했고, 섀넌의 한계에 다가가는 부호가 실제로 만들어지기까지는 40년 넘게 걸렸습니다.

무작위로 편향을 끊기. 1920년대 영국 로담스테드 농업 시험장의 로널드 피셔는 어느 밭에 어떤 비료를 줄지를 제비로 정하자고 했습니다. 연구자가 고르면 좋은 땅에 좋은 비료를 주는 식의 치우침이 몰래 끼어들지만, 제비는 알려진 요인과 알려지지 않은 요인을 모두 두 무리에 고르게 흩어 놓습니다(교란 변수⁠(confounding variable)⁠, 무작위 대조 시험⁠(randomized controlled trial)⁠). 1948년 오스틴 브래드퍼드 힐이 설계한 스트렙토마이신 결핵 시험이 이 원리를 의학으로 들여왔습니다. 인도의 마할라노비스는 같은 생각으로 나라 전체를 다 세는 대신 무작위로 뽑은 표본⁠(sample)⁠으로 재는 전국 조사를 세웠습니다. 제비를 뽑을 수 없을 때는 역사가 대신 뽑아 준 비교를 찾습니다. 1854년 런던의 존 스노는 같은 동네의 집들이 거의 우연히 서로 다른 물 회사의 물을 받는다는 점을 이용해 콜레라가 물로 옮는다는 증거를 쌓았습니다.

무작위란 무엇인가. 01을 스무 번 되풀이한 40자리 줄과 동전을 40번 던져 얻은 줄은 확률로는 똑같이 $2^{-40}$인데, 우리는 앞의 것이 무작위가 아니라고 느낍니다. 1960년대 콜모고로프 등은 이 느낌을 정의로 바꿨습니다. 무작위인 줄은 그 줄 자체보다 훨씬 짧은 프로그램으로 적을 수 없는 줄, 곧 압축되지 않는 줄이라는 것입니다(콜모고로프 복잡도⁠(Kolmogorov complexity)⁠, 원천 부호화 정리⁠(source coding theorem)⁠). 비둘기집 원리⁠(pigeonhole principle)⁠에 따르면 거의 모든 줄이 이런 뜻에서 무작위입니다. $n - c$비트보다 짧은 프로그램은 $2^{n-c}$개가 안 되니, 길이 n인 줄 가운데 c비트 넘게 압축되는 줄은 $2^{-c}$의 비율도 안 됩니다. 그런데 정작 주어진 줄 하나가 무작위임을 증명하는 일은 정지 문제⁠(halting problem)⁠ 때문에 일반적으로 불가능합니다. 컴퓨터가 쓰는 난수는 정해진 규칙으로 만든 의사 난수입니다. 폰 노이만과 울람은 로지스틱 사상⁠(logistic map)⁠을 되풀이해 난수를 만드는 방법도 내놓았는데, 완전히 결정된 규칙이 무작위처럼 보이는 혼돈⁠(chaos)⁠이 그 바탕입니다. 폰 노이만 자신은 산술로 난수를 만드는 사람은 죄를 짓는 상태에 있다는 농담 섞인 경고를 남겼습니다.

어긋남과 놀라움. '무작위로 고른다'는 말은 생각보다 모호합니다. 1889년 프랑스의 수학자 조제프 베르트랑은 원에 무작위로 현을 그을 때 그 현이 원에 내접하는 정삼각형의 변보다 길 확률을 물었는데, 현을 고르는 자연스러워 보이는 세 방법이 1/2, 1/3, 1/4이라는 서로 다른 답을 냅니다. 무작위에는 언제나 '무엇에 대해 고르게'가 따라붙어야 합니다. 무작위 걸음도 차원에 따라 성격이 바뀝니다. 1921년 부다페스트 출신의 수학자 조지 포여(폴리아 죄르지)는 직선과 평면 격자 위의 무작위 걸음은 확률 1로 언젠가 출발점으로 돌아오지만, 3차원 격자에서는 영영 돌아오지 못할 확률이 0보다 크다는 것을 증명했습니다. 사람의 직관은 무작위에 특히 약합니다. 생일이 365일에 고르게 퍼져 있다면 23명 가운데 생일이 같은 쌍이 있을 확률이 절반을 넘는다는 것도, 극단적인 성적 다음의 성적이 평범해지는 것이 벌이나 칭찬의 효과가 아니라 회귀라는 것도 처음에는 믿기 어렵습니다.

이어지는 곳. 주사위의 확률이 1/6인 근거는 대칭과 불변량⁠(invariant)⁠에 있습니다. 표본이 많을수록 평균이 $1/\sqrt n$의 속도로 정확해진다는 것은 근사와 오차의 그림에서 기울기⁠(slope)⁠ −1/2인 노란 선이고, 무작위로 고른 대상이 '평균적으로' 좋으면 가장 좋은 대상은 적어도 그만큼 좋다는 확률적 방법의 논리는 가장 좋은 것 고르기와 만납니다. 압축되지 않는 줄이 있다는 증명과 그것을 가려낼 수 없다는 증명은 모두 자기 참조⁠(self-reference)⁠와 대각선의 논법이고, 무한히 많은 동전 던지기를 다루는 측도의 언어는 무한을 다루는 법에서 이어집니다.