PART IV — 확률
동전을 던지며 이리저리 걷는 사람을 상상해 보세요. 앞면이 나오면 한 칸 오른쪽, 뒷면이 나오면 한 칸 왼쪽. 단순해 보이지만 이 작은 그림은 자연 현상부터 금융 시장, 구글 검색 엔진의 심장부까지 두루 설명하는 강력한 도구예요. 이번 챕터에서는 1차원 임의 보행에서 출발해, 그래프 위 임의 보행, 그리고 PageRank의 직관까지 한 번에 따라가 봅니다.
장면을 하나 그려봅시다. 카지노에 들어선 도박꾼이 처음에 \( n \)달러를 가지고 있어요. 매 라운드마다 동전을 던져 앞면이면 1달러를 따고, 뒷면이면 1달러를 잃습니다. 도박꾼은 가진 돈이 \( T \)달러가 되면 의기양양하게 자리를 뜨겠다고 다짐했지만, 반대로 0달러가 되면 어쩔 수 없이 자리를 떠야 해요. 자, 그가 목표 \( T \)달러에 도달할 확률은 얼마일까요? 그리고 게임이 끝날 때까지 평균 몇 라운드를 버틸 수 있을까요?
이 문제를 도박꾼의 파산이라고 부르는데요, 18세기부터 사람들이 골머리를 앓아 온 고전 문제입니다. 표면적으로는 도박 이야기지만, 사실은 1차원 격자 위 임의 보행의 가장 깔끔한 형태예요. 정수 직선 위 \( n \)에서 출발해 매 단계마다 \( +1 \) 또는 \( -1 \)을 더하며 움직이고, 0이나 \( T \)에 닿으면 멈추는 거죠.
정의 21.1.1 (도박꾼의 파산 모형)
고정된 정수 \( 0 \le n \le T \)와 \( 0 < p < 1 \)에 대해, 다음과 같은 과정 \( X_0, X_1, X_2, \dots \)을 생각합니다. \( X_0 = n \)이고, \( X_t \in \{0, T\} \)이면 과정은 멈춥니다. 그렇지 않으면 독립적으로 확률 \( p \)로 \( X_{t+1} = X_t + 1 \), 확률 \( q = 1-p \)로 \( X_{t+1} = X_t - 1 \) 입니다. 우리가 알고 싶은 것은 두 가지: 멈출 때 \( X = T \)일 확률 \( w_n \)과 멈출 때까지의 기대 단계 수 \( e_n \)입니다.
직관적으로 \( p \)가 \( 1/2 \)에 가까우면 양쪽으로 비슷하게 흔들리니까 도박꾼이 살아날 가능성도 한가운데서 \( n/T \)쯤 될 것 같죠. 반대로 \( p < 1/2 \)인 약간 불공정한 게임이라면 카지노가 점점 도박꾼의 돈을 빨아들일 거고, \( p > 1/2 \)이면 도박꾼이 유리할 거예요. 이 직관을 정확한 식으로 만들어 봅시다.
핵심 아이디어는 한 걸음 조건부 분석(one-step conditioning)이에요. 도박꾼이 현재 \( n \)달러를 가지고 있을 때 목표를 달성할 확률을 \( w_n \)이라고 합시다. 첫 번째 동전을 던진 직후를 보면, 이전과 같은 모양의 게임이 약간 다른 자본금에서 시작됩니다. 그러니
\[ w_n = p \cdot w_{n+1} + q \cdot w_{n-1}, \qquad 1 \le n \le T-1 \]
이 됩니다. 경계조건은 \( w_0 = 0 \) (이미 파산), \( w_T = 1 \) (이미 우승)이고요. 이건 우리가 이전 챕터에서 봤던 선형 점화식이에요. 일반 해를 찾아봅시다.
정리 21.1.2 (도박꾼의 파산 확률)
\( p \ne 1/2 \)이고 \( r = q/p \)라고 두면, \[ w_n = \frac{1 - r^n}{1 - r^T}. \] \( p = 1/2 \)인 공정한 게임의 경우에는 \[ w_n = \frac{n}{T} \] 입니다.
증명 스케치
점화식 \( p \, w_{n+1} - w_n + q \, w_{n-1} = 0 \)의 특성방정식은 \( p x^2 - x + q = 0 \). 인수분해하면 \( (px - q)(x - 1) = 0 \)이라 근은 \( x = 1 \)과 \( x = q/p = r \).
\( r \ne 1 \) (즉 \( p \ne 1/2 \))일 때 일반해는 \( w_n = A + B r^n \). 경계조건 \( w_0 = 0 \)에서 \( A + B = 0 \), \( w_T = 1 \)에서 \( A + B r^T = 1 \). 두 식을 풀면 \( B = -A \)이고 \( A(1 - r^T) = -1 \)이므로 결국 \( w_n = (1 - r^n)/(1 - r^T) \).
\( p = 1/2 \)일 때는 두 근이 겹치므로 일반해의 형태가 \( w_n = A + B n \)이고, 같은 경계조건에서 \( w_n = n/T \)가 곧장 나옵니다.
∎
예제 21.1.3 (공정한 게임)
도박꾼이 100달러를 들고 들어가서 목표가 200달러, 동전이 공정하다(\( p = 1/2 \))고 합시다. 그러면 목표에 도달할 확률은 정확히 \( 100/200 = 1/2 \). 자, 그런데 만약 100달러로 백만 달러를 노린다면? \( w_{100} = 100/1{,}000{,}000 = 0.0001 \). 즉 0.01%예요. 공정한 게임이라도 자본 차이가 크면 작은 쪽이 거의 확실히 망합니다.
예제 21.1.4 (살짝 불리한 게임)
룰렛에서 빨강에 거는 시뮬레이션을 해 봅시다. 미국식 룰렛은 38칸 중 18칸이 빨강이라 \( p = 18/38 \approx 0.474 \), \( q = 20/38 \approx 0.526 \), \( r = q/p = 10/9 \). 도박꾼이 100달러로 200달러를 노리면 \[ w_{100} = \frac{1 - (10/9)^{100}}{1 - (10/9)^{200}} \approx \frac{-3 \times 10^4}{-9 \times 10^8} \approx 3 \times 10^{-5}. \] 고작 100달러를 두 배로 만들 확률이 0.003%! 작은 편향(\( p \)가 \( 1/2 \)에서 0.026 떨어짐)이 100라운드 동안 누적되면 거의 확정적인 패배가 됩니다. 카지노가 작은 마진만으로도 장기적으로 이기는 이유예요.
파산 확률을 알았으니 이제 게임의 길이도 따져봅시다. 시작 자본이 \( n \)일 때 게임이 끝날 때까지 걸리는 기대 라운드 수를 \( e_n \)이라고 둘게요. 같은 한 걸음 분석으로
\[ e_n = 1 + p \, e_{n+1} + q \, e_{n-1}, \qquad 1 \le n \le T-1, \]
\( e_0 = e_T = 0 \). 첫 번째 동전 한 번을 항상 더해주는 게 핵심이에요. 이 점화식의 동차부분은 위와 같고, 비동차항이 상수 \( -1 \)이라 특수해를 따로 잡아야 해요.
정리 21.1.5 (도박꾼의 파산 기대 시간)
\( p = 1/2 \)일 때 \( e_n = n(T-n) \). 즉 양 끝에서 멀수록 기대 시간이 커지고, 한가운데 \( n = T/2 \)에서 최대 \( T^2/4 \)가 됩니다.
\( p \ne 1/2 \)일 때는 \[ e_n = \frac{1}{q-p} \left( n - T \cdot \frac{1 - r^n}{1 - r^T} \right). \]
특히 공정한 게임에서 \( T = 100 \), \( n = 50 \)이면 평균 \( 50 \cdot 50 = 2500 \)라운드. \( T = 1000 \), \( n = 500 \)이면 평균 25만 라운드! 한가운데서 시작한 임의 보행이 한쪽 끝에 닿기까지 평균적으로 \( T^2 \) 정도 시간이 걸린다는 건, 임의 보행이 느리다는 의미예요. 거리에 비해 제곱만큼 시간이 든다는 \( \sqrt{t} \)–법칙은 확산(diffusion)의 본질이고, 브라운 운동이나 열 방정식과 같은 뿌리에서 자라난 결과입니다.
노트: 한국어 학생이 헷갈리기 쉬운 점
"공정한 게임에서 무한히 길게 두면 결국 본전을 찾지 않을까?"라는 질문을 자주 받아요. 무한 직선이라면 그렇지만(언젠가 0에 돌아오긴 합니다), 경계가 있는 도박꾼의 파산에서는 그 전에 0이나 \( T \)에 부딪혀 게임이 끝나요. 멈추는 시점이 유한하다는 게 결정적입니다. 그리고 무한 직선에서도 2차원까지는 원점에 다시 돌아올 확률이 1이지만, 3차원 이상에서는 영영 못 돌아올 수 있어요. 폴리아의 정리라고 부르는 신기한 사실이죠.
도박꾼의 파산은 단지 도박 이야기가 아니에요. 같은 점화식이 화학에서 분자가 막 사이를 통과할 확률, 신경과학에서 뉴런의 발화 임계값 도달 확률, 알고리즘에서 SAT 해법의 임의 재시작 분석에 등장합니다. "확률적인 한 걸음을 반복했을 때 어디서 멈추나"라는 질문은 정말 어디에나 있어요.
직선 위에서 좌우로만 움직이는 보행은 너무 평면적이에요. 실제로 우리가 흥미로운 구조 — 소셜 네트워크, 도시 도로망, 웹 페이지의 하이퍼링크 — 는 그래프 모양이거든요. 그래서 임의 보행을 그래프로 일반화해 봅시다.
정의 21.2.1 (그래프 위 단순 임의 보행)
유한 그래프 \( G = (V, E) \) (방향 또는 무방향)와 시작 정점 \( v_0 \in V \)이 주어졌을 때, \( t = 0, 1, 2, \dots \)에 대해 다음을 반복합니다. 현재 위치 \( v_t \)에서 이웃들의 집합 \( N(v_t) \) 중 하나를 균등하게 무작위로 골라 \( v_{t+1} \)로 옮겨갑니다. 이렇게 만들어진 정점 수열 \( v_0, v_1, v_2, \dots \)이 그래프 \( G \) 위 단순 임의 보행이에요.
이 과정은 사실 마르코프 연쇄(Markov chain)의 한 종류예요. 다음 위치 \( v_{t+1} \)이 과거 전체가 아니라 오직 현재 \( v_t \)에만 의존하니까요. 전이 확률 행렬 \( P \)는 \( P_{uv} = 1/\deg(u) \)이면 \( v \in N(u) \), 아니면 0입니다.
예제 21.2.2 (정사각형 위의 보행)
네 정점 \( a, b, c, d \)를 사이클로 연결한 \( C_4 \)를 생각해 봅시다 (\( a-b-c-d-a \)). 매 단계마다 양쪽 이웃 중 하나를 동전 던져 고르니, 사실은 4개 정점 위 1차원 임의 보행과 같죠. 시간이 흐르면 어느 정점에 머물 확률이 모두 \( 1/4 \)로 평형을 이룹니다. 대칭이라 결과가 깔끔해요.
예제 21.2.3 (별 그래프와 편향)
중심 정점 \( c \) 하나에 잎 정점 \( \ell_1, \ell_2, \dots, \ell_k \)가 매달린 별 그래프를 생각해 봅시다. 잎에서 출발하면 다음 단계엔 무조건 \( c \)로 옵니다 (이웃이 \( c \) 하나). 그런데 \( c \)에 오면 다음 단계엔 \( k \)개 잎 중 하나로 균등히 갈라지죠. 직관적으로 보행자는 \( c \)와 잎들 사이를 핑퐁처럼 오갈 거예요. 평형 분포에서 \( c \)에 머물 확률은 \( 1/2 \), 각 잎에 머물 확률은 \( 1/(2k) \). 차수가 큰 정점이 평형에서 더 무겁다는 법칙의 작은 예입니다.
충분히 오랫동안 임의 보행을 돌리면, 시작 위치는 잊혀지고 어떤 안정된 분포 \( \pi \)로 수렴해요. 무방향 연결 그래프에서 비주기적이면(예컨대 자기 자신으로 가는 변이 하나라도 있거나 홀수 사이클이 있으면) 이 평형 분포는 차수에 비례합니다.
정리 21.2.4 (무방향 그래프 평형 분포)
\( G = (V, E) \)이 연결된 비주기 무방향 그래프이면, 단순 임의 보행은 유일한 평형 분포 \( \pi \)로 수렴하고, 각 정점 \( v \)에 대해 \[ \pi(v) = \frac{\deg(v)}{2|E|} \] 입니다. (\( 2|E| = \sum_v \deg(v) \) 인 점에 유의.)
증명 스케치
평형 조건 \( \pi P = \pi \)를 검증하면 충분해요. 즉 \( \sum_u \pi(u) P_{uv} = \pi(v) \). 무방향 그래프의 인접관계는 대칭이라 \( P_{uv} = 1/\deg(u) \)는 \( u \sim v \)일 때만 \( 1/\deg(u) \). 따라서 \[ \sum_u \pi(u) P_{uv} = \sum_{u \sim v} \frac{\deg(u)}{2|E|} \cdot \frac{1}{\deg(u)} = \frac{\deg(v)}{2|E|} = \pi(v). \] 유일성과 수렴은 비주기성과 연결성에서 페론-프로베니우스 정리로 따라옵니다.
∎
이 결과가 의미하는 바는 단순해요. 이웃이 많은 정점일수록 보행자가 그곳에서 더 많은 시간을 보낸다. 차수가 평형 확률을 결정하고요. 그래프에서 "중요한 정점"을 이웃 수로 정의해도 된다는 첫 신호입니다. 하지만 웹 같은 방향 그래프에서는 이 깔끔한 차수 비례 공식이 그대로 통하지 않아요. 그래서 등장한 게 PageRank입니다.
1998년 스탠퍼드 박사과정생 두 명, 래리 페이지와 세르게이 브린이 풀고 싶었던 문제는 이거였어요. "웹 페이지가 수십억 개 있다. 검색어가 들어왔을 때 어떤 페이지를 가장 위에 띄울 것인가?" 단순히 "검색어가 등장한 횟수"로 정렬하면 키워드 스팸이 판칠 거고요. 그들의 통찰은 이거였죠. 웹은 거대한 방향 그래프다. 페이지가 페이지를 링크한다는 건 일종의 추천이다. 추천을 많이 받는 페이지가 중요하다. 그런데 추천하는 페이지 자체가 중요할 때 그 추천이 더 무겁다.
이 재귀적 정의를 어떻게 풀까요? 답은 우아하게도 임의 보행이에요. 어떤 가상의 서퍼가 임의의 페이지에서 출발해, 매 단계마다 현재 페이지의 외부 링크 중 하나를 균등하게 골라 클릭한다고 합시다. 이 서퍼가 충분히 오래 떠돌면 어떤 페이지에 머물 확률 분포가 평형을 이루는데, 그 평형 확률이 곧 그 페이지의 중요도입니다. 즉 임의 보행이 오래 머무는 페이지가 중요한 페이지예요.
정의 21.2.5 (PageRank, 단순 버전)
웹 그래프 \( G = (V, E) \)의 각 페이지 \( v \)의 PageRank \( \pi(v) \)는 다음 방정식을 만족하는 분포입니다. \[ \pi(v) = \sum_{u \to v} \frac{\pi(u)}{\deg^+(u)} \] 여기서 \( \deg^+(u) \)는 \( u \)에서 나가는 링크의 수, 합은 \( v \)로 들어오는 링크의 출발지 \( u \) 전체에 대한 것입니다.
식을 보면 핵심이 보여요. 페이지 \( v \)의 점수는 \( v \)로 링크를 거는 페이지들이 자기 점수를 자기의 외부 링크 수만큼 나눠서 \( v \)에 보태주는 합입니다. 큰 사이트가 적은 외부 링크로 \( v \)를 가리키면 점수가 크게 옮겨오고, 외부 링크가 산만하게 많은 페이지가 \( v \)를 가리키면 조금만 옮겨와요. 추천하는 사람이 신뢰할 만하고, 또 신중할수록 추천이 무겁다는 직관이 그대로 식이 된 것이죠.
노트: 막다른 골목과 텔레포트
실제 웹은 외부 링크가 하나도 없는 페이지(dangling nodes)도 있고, 작은 그룹끼리 서로 링크하며 외부와 단절된 함정도 있어요. 단순 임의 보행은 이런 곳에 빠지면 평형이 깨집니다. 구글의 해법은 우아해요. 매 단계 \( 1 - d \)의 확률(보통 \( d = 0.85 \))로 외부 링크를 따라가지만, 확률 \( d \)... 잠깐, 부호 헷갈리지 말고 다시 — 확률 \( d \approx 0.85 \)로 링크를 따라가고, \( 1-d \approx 0.15 \)의 확률로는 아무 페이지로나 텔레포트합니다. 이렇게 하면 그래프가 완전히 연결되고 비주기적이라 평형이 보장돼요.
정리 21.2.6 (PageRank, 텔레포트 포함)
감쇠 인자 \( d \in (0, 1) \)와 균등 분포 \( \mathbf{1}/|V| \)에 대해 \[ \pi(v) = \frac{1-d}{|V|} + d \sum_{u \to v} \frac{\pi(u)}{\deg^+(u)} \] 를 만족하는 유일한 확률 분포 \( \pi \)가 존재합니다. 이 \( \pi \)가 PageRank 점수예요.
어떻게 계산하느냐고요? 방법은 놀랍게도 단순합니다. 모든 \( \pi(v) \)를 \( 1/|V| \)로 초기화한 뒤, 위의 식을 우변에서 좌변으로 반복 대입합니다 — 이걸 거듭제곱 반복(power iteration)이라고 불러요. 수십 번 반복이면 수렴합니다. 1998년 당시 웹 페이지가 수억 개였는데도 이 방법이 통했다는 게 PageRank의 공학적 묘미예요.
예제 21.2.7 (작은 웹의 PageRank 한 바퀴)
세 페이지 \( A, B, C \)와 링크 \( A \to B, A \to C, B \to C, C \to A \)를 생각해 봅시다. 외부 링크 수는 \( \deg^+(A) = 2 \), \( \deg^+(B) = 1 \), \( \deg^+(C) = 1 \). 텔레포트를 잠깐 무시하면 평형 방정식은 \[ \pi(A) = \pi(C), \quad \pi(B) = \pi(A)/2, \quad \pi(C) = \pi(A)/2 + \pi(B). \] \( \pi(A) + \pi(B) + \pi(C) = 1 \)과 함께 풀면 \( \pi(A) = 2/5 \), \( \pi(B) = 1/5 \), \( \pi(C) = 2/5 \).
직관적으로 \( C \)는 들어오는 링크가 \( A \)와 \( B \) 둘 다라 무겁고, \( A \)는 \( C \)에서 받는 100% 추천 덕에 가장 중요한 페이지 중 하나가 됩니다. \( B \)는 \( A \)의 절반짜리 추천만 받기에 점수가 작죠. 식 한두 줄로 직관이 양적으로 바뀝니다.
PageRank의 진정한 천재성은 검색 결과를 전역적으로 정렬할 점수를 검색어와 무관하게 미리 계산해 둘 수 있다는 거예요. 사용자가 검색어를 입력하면 해당 검색어에 부합하는 페이지들 중 PageRank가 높은 순서로 보여주면 그만이거든요. "임의 보행의 평형 분포"라는 한 줄짜리 수학적 객체가 검색 엔진을 살리고 구글이라는 회사를 만들어낸 셈이에요.
노트: 임의 보행이 풀어주는 다른 문제들
PageRank 말고도 임의 보행은 의외로 많은 곳에 등장합니다. SAT 해법의 무작위 워크 알고리즘, 마르코프 연쇄 몬테카를로(MCMC)로 베이즈 추론하기, 그래프의 클러스터링(이웃에 머무는 시간이 길면 같은 클러스터), 추천 시스템의 사용자–아이템 이분그래프 위 보행으로 유사도 계산하기. 공통점은 하나예요. "멀리 있는 정보를 한 걸음씩 확률적으로 모아온다"는 발상. 이 한 가지 발상으로 우리는 도박장과 검색 엔진과 신경망 학습을 같은 언어로 말할 수 있게 되었어요. 단순한 동전 던지기에서 시작한 이야기치고는 꽤 멀리 왔습니다.