무작위 행보(Random walk)
매 걸음 동전을 던져 앞뒤로 한 칸씩 움직이는 운동. 평균적으로는 제자리지만, 퍼지는 폭은 걸음 수의 제곱근만큼 자란다.
한 걸음마다 동전을 던져 앞면이면 +1, 뒷면이면 −1만큼 움직입니다. 30명이
평균(mean) 위치는 0입니다. 앞뒤가 반반이니까요. 그런데 사람들은 점점 넓게 퍼집니다. 한 걸음의 분산(variance)이 1이고, 독립(independence)인 걸음을 더하면 분산이 더해지니 n걸음 뒤 분산은 n, 표준편차(standard deviation)는
1905년 아인슈타인은 물에 뜬 아주 작은 알갱이(꽃가루에서 나온 입자 같은)가 쉬지 않고 떨리는 브라운 운동(Brownian motion)을, 보이지 않는 물 분자들에게 사방에서 무작위로 떠밀리는 걸음으로 설명했습니다. 알갱이가 퍼지는 거리가 시간의 제곱근으로 자란다는 그의 예측은 몇 해 뒤 실험으로 확인되어, 분자가 실제로 있다는 결정적인 증거가 되었습니다. 같은 퍼짐은 인공지능(artificial intelligence)에서도 쓰입니다. 그림의 모든 화소에 작은 무작위 걸음을 거듭 더하면 그림은 잡음으로 퍼져 버리는데, 이 과정을 거꾸로 되돌리도록 신경망(neural network)을 학습시켜 잡음에서 그림을 만드는 것이 확산 모델(diffusion model)입니다.
n걸음 뒤 위치가
한 걸음당 평균 이동
양 끝에 벽이 있으면 어느 쪽 벽에 먼저 닿는지가 문제가 됩니다. 이것이 도박꾼의 파산(gambler's ruin)입니다. 0에서 출발해 한 번도 0 아래로 내려가지 않고 2n걸음 뒤 0으로 돌아오는 길의 수는 카탈랑 수(Catalan number)
직선 대신 그래프 위를 걸을 수도 있습니다. 점마다 거기서 나가는 선 가운데 하나를 무작위로 골라 옮겨 가는 것입니다. 어느 점에서든 선을 따라 다른 모든 점에 갈 수 있으면, 오래 걸은 뒤 각 점에 머무는 시간의 비율은 출발점과 상관없이 그래프의 모양이 정합니다. 많은 선이 모여드는 점, 그리고 그런 점에서 선을 받는 점일수록 비율이 높습니다. 웹 페이지를 점, 링크를 선으로 삼은 이 비율이 구글 검색의 순위 기준이었던 페이지랭크(PageRank)입니다. 웹에는 빠져나갈 링크가 없는 막다른 페이지도 있어서, 페이지랭크는 가끔 아무 페이지로나 건너뛰는 규칙을 더해 이 조건을 맞춥니다.
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 분산과 표준편차
… n배가 아니라 \sqrt{n} 배가 됩니다. 분산이 n배가 되고, 표준편차는 그 제곱근이기 때문입니다(무작위 행보). 분산은 정규분포의 폭을 정합니다. 회귀가 줄이려는 오차 제곱합도, 주성분 분석이 최대로 …
- 이항분포
… 발견된 경로(드무아브르, 1733)입니다. p = 1/2이면 공의 경로는 왼쪽·오른쪽 걸음을 반복하는무작위 행보와 같습니다. 이항계수 \binom{n}{k} = \frac{n!}{k!(n-k)!} 는 계승(1부터 …
- 정규분포
… 어느 하나가 합을 좌우하지 않는 한, 요인들의 분포와 상관없이 합이 이 모양에 가까워집니다. n걸음 뒤무작위 행보의 위치와 많은 측정 오차가 그렇고, 사람의 키도 성별을 나누어 보면 대략 그렇습니다. 그 폭은 분산이 …
- 중심극한정리
… 않습니다. 그 폭을 \sqrt n 배로 확대해 들여다보면 정규분포가 보인다는 것이 이 정리입니다.무작위 행보가 n걸음 뒤에 종 모양으로 퍼지는 것도 같은 이야기입니다. 왜 하필 정규분포일까요? 두 독립 변수의 …
- 마르코프 연쇄
… 연쇄는 주기가 2라서 확률이 끝없이 뒤바뀌며 한 값으로 모이지 않습니다. 상태가 무한히 많은 연쇄의 예가무작위 행보인데, 이 경우에는 확률이 끝없이 퍼지기만 해서 정상 분포가 없습니다. 웹 페이지를 무작위로 떠도는 사람의 …
- 파스칼의 삼각형
… 합니다( n 걸음 중 오른쪽 k 걸음을 고르는 셈). 갈림길마다 동전을 던져 방향을 정하면 이 길이무작위 행보가 되고, 도착한 칸의 분포가 이항분포 \binom nk / 2^n 입니다. 크기 k 인 부분집합의 …
- 이항계수
… / 2^n 입니다. 이 값들을 k마다 늘어놓은 것이 이항분포이고, →를 +1, ↑를 −1로 읽으면 길은무작위 행보의 자취가 됩니다. n이 크면 계승 계산이 버거운데, 스털링 공식이 \binom{2n}{n} …
- 도박꾼의 파산
… 잃습니다. 돈이 0이 되면 파산, N이 되면 목표를 이루고 그만둡니다. 돈의 변화는 양 끝에 벽이 있는무작위 행보입니다. 파스칼과 페르마 사이에서 다루어진 문제로 알려져 있고, 네덜란드의 하위헌스가 …
- 열방정식
… 뒤 e^{-t} 로 식어 갑니다. 지금 막대 한가운데 온도는 입니다. 이어지는 곳. 열은 수많은 입자의무작위 행보가 모인 결과로 볼 수도 있습니다. 끝없이 긴 막대의 한 점에 모인 열은 분산이 2t인 정규분포 …
- 로지스틱 사상
… 기록도 다시 공정한 동전 기록입니다. 왼쪽이면 한 걸음 뒤로, 오른쪽이면 한 걸음 앞으로 가며 누적하면무작위 행보가 됩니다. 우연이 전혀 없는 규칙이 확률처럼 보이는 가장 단순한 예입니다. 규칙으로 무작위처럼 보이는 …
- 로렌츠 끌개
… 기록처럼 불규칙해 보입니다. 날개를 바꿀 때마다 왼쪽이면 한 걸음 뒤로, 오른쪽이면 한 걸음 앞으로 옮기면무작위 행보같은 자취가 나옵니다. 멈출 곳이 하나도 없는데 흩어지지도 않는 이유는 부피가 줄기 때문입니다. 공간에 …
- 최단 경로
… 우편배달부 문제에서는 최단 경로가 오일러 경로를 만드는 부품으로 쓰입니다. 아무 길이나 골라 떠도는무작위 행보로 목표에 닿으려면 보통 최단 거리보다 훨씬 많은 걸음이 듭니다. 모든 점을 이어 주는 가장 짧은 도로망을 …
- 좁은 세상
… 구조임을 보였습니다. 웹 페이지의 링크망도 몇 번의 클릭으로 멀리 닿는 좁은 세상입니다. 그 링크를 따라무작위로 걷는사람이 각 페이지에 머무는 비율이 페이지랭크입니다.
- 페이지랭크
… 확률 d를 감쇠 계수라고 부릅니다. 다음 위치가 지금 위치에만 달려 있으니 이것은 링크 그래프 위의무작위 행보, 곧 마르코프 연쇄입니다. 오래 걸은 뒤 산책자가 각 페이지에 있을 확률이 그 페이지의 …
- 카탈랑 수
… 약 499로, 실제 값 429보다 16%쯤 큽니다). 이어지는 곳. 오르내리는 길은 동전 던지기로 움직이는무작위 행보입니다. 그런 길이 바닥과 꼭대기 가운데 어디에 먼저 닿는지를 묻는 것이 도박꾼의 파산이고, 바닥에 …
- 쿨백–라이블러 발산
… 큰 수의 법칙에 따라 증거는 한 번에 평균 D(p‖q)비트씩 곧게 쌓입니다. 증거의 합은 기울기가 있는무작위 행보인 셈입니다. 그래서 참이 p일 때 잘못 판단할 확률을 일정한 작은 수준 아래로 묶어 두면, 가장 좋은 …
- 맥스웰의 악마와 란다우어 원리
… 수의 법칙⟧), 분자가 10^{23} 개쯤 되면 온도계로는 볼 수 없을 만큼 작아집니다. 분자 하나하나는무작위 행보처럼 오가지만, 전체로는 엔트로피가 큰 쪽, 곧 고르게 섞인 쪽이 압도적으로 흔합니다(⟦최대 엔트로피 …
- 동역학계
… 고정점, 상태가 공간 전체에 퍼져 흐르는 열방정식과 파동방정식도 동역학계입니다. 우연이 섞이면무작위 행보와 도박꾼의 파산이 되고, 경사 하강법으로 신경망을 훈련하는 과정도 매개변수 공간 위의 이산 …
- 확률변수
… 중심극한정리의 일반적인 증명으로 이 길을 넓혔습니다. 이어지는 곳. 확률변수 여러 개를 더하면무작위 행보가 되고, 많이 더해 평균을 내면 큰 수의 법칙과 중심극한정리가 그 모양을 알려 줍니다. 확률변수 …
- 확산 모델
… 둔 작은 수로, 여기서는 0.0005에서 0.12까지 커지는 100개입니다. 점 하나는 원점으로 끌리는무작위 걸음을 하고, 다음 위치가 지금 위치에만 달려 있으니 마르코프 연쇄입니다. 당기는 비율 …
- 라플라시안과 그래프 라플라시안
… t 로 떠는데, 모드로 바꿔 보면 연산이 곱셈이 된다는 점에서 대각화의 가장 유명한 보기입니다.무작위 행보가 어느 경계에 먼저 닿을 확률은 라플라시안이 0인 함수여서 도박꾼의 파산과 전기 회로가 같은 문제가 …