푸아송 근사와 거대 컴포넌트 — 평균 차수 1이라는 임계점

1. 오늘의 질문: 1461명짜리 이항분포를 어떻게 다루나 (Why the Binomial Breaks Down)

4-1에서 얻은 차수 분포는 이것이었다.

$n=5$일 때는 다섯 항을 손으로 전부 썼다. 그런데 FMH는 $n=1461$이다.

수치적으로도 나쁘고, 무엇보다 매개변수가 둘($n$과 $p$)이라 감이 안 잡힌다. 그런데 위 표를 자세히 보면 규칙이 있다.

망이 커질수록 $n$은 커지고 $p$는 작아진다 — 그런데 둘의 곱 $(n-1)p$는 그대로 몇 명이다.

답은 푸아송 분포이고, 매개변수는 $\lambda$ 하나뿐이다. $n$과 $p$가 따로 사라지고 곱만 남는다는 것 — 이것이 4단계 내내 "평균 차수 $\lambda$"만으로 이야기할 수 있게 되는 근거다.

2. 정의 — 푸아송 분포 (The Poisson Distribution)

왜 $e^{-\lambda}$가 정규화 상수인가 — 지수함수의 급수를 그대로 쓰면 된다.

3. 손 계산 ① 이항이 푸아송으로 가는 길 — 네 조각 (The Poisson Limit in Four Pieces)

표기를 줄이자. $N=n-1$(한 학생이 관여하는 동전 수), $p=\lambda/N$. 이항 확률을 있는 그대로 쓴 뒤 곱셈 순서만 바꾼다. 근사는 아직 없다.

$\binom Nk=\dfrac{N(N-1)\cdots(N-k+1)}{k!}$를 펴고, $(1-\lambda/N)^{N-k}=(1-\lambda/N)^{N}(1-\lambda/N)^{-k}$로 쪼개면

네 조각의 정체를 하나씩 본다.

3-1. 네 조각을 실제 숫자로 — $\lambda=4/3$, $k=2$ (Four Pieces with Real Numbers)

추상적으로 "$\to 1$"이라고만 하면 감이 안 온다. FMH의 $\lambda=4/3$을 고정하고 $N$만 4, 50, 1460으로 키우며 네 조각을 각각 계산해 본다.

$N=4$의 네 조각을 분수로 전부 확인한다 ($p=\frac{4/3}{4}=\frac13$):

직접 계산과 대조: $\binom42\left(\frac13\right)^2\left(\frac23\right)^2 =6\cdot\frac19\cdot\frac49=\frac{24}{81}=\frac{8}{27}$ ✓ — 소수점이 아니라 분수까지 일치한다.

4. 손 계산 ② $\lambda=1$의 여섯 항 전부 (All Six Terms at $\lambda=1$)

$\lambda=1$은 오늘의 주인공 값이다(§11에서 임계점으로 다시 등장한다). $\lambda=1$이면 $\lambda^k=1$이므로 식이 아주 단순해진다.

즉 분자는 전부 1이고 분모만 $k!$로 커진다. $e^{-1}=0.3678794412$.

검산 — 분모를 $e$로 통일해 분자를 더한다:

$e=2.718282$와 비교하면 차이 $0.001615$ — 이것을 $e$로 나누면 $0.001615/2.718282=0.000594$로 위 표의 꼬리와 정확히 같다 ✓

5. 수렴을 눈으로 보기 (Watching the Convergence)

$\lambda=4/3$으로 고정하고 $N=n-1$만 키우며 이항의 앞 네 항을 나란히 놓는다.

6. 손 계산 ③ 고립자 기대 수 $n\,e^{-\lambda}$ (Expected Number of Isolates)

푸아송의 첫 항 $k=0$에는 특별한 이름이 있다 — 고립자(isolate). 교실에서는 아무도 친구로 지목하지 않고 자신도 아무도 지목하지 않은 학생이다.

6-1. 두 가지 식 — 정확식과 근사식 (Two Formulas: Exact and Approximate)

정확식: 한 학생이 관여하는 $n-1$개 동전이 전부 뒷면일 확률.

푸아송 근사: $k=0$을 대입하면 $\lambda^0=1$, $0!=1$이므로

기댓값은 독립이 아니어도 그냥 더해진다(4-1 §7에서 확인했다). 1461명 각각에 대해 더하면

6-2. FMH 숫자로 — 두 식이 얼마나 가까운가 (FMH Numbers: How Close Are They)

FMH: $n=1461$, $m=974$, $p=0.000913242$, $\lambda=2m/n=4/3$.

$e^{-4/3}$을 손으로: $e^{-4/3}=e^{-1}\cdot e^{-1/3} =0.3678794\times 0.7165313=0.2635971$. 대략 네 명 중 한 명이다.

7. FMH 대조 ① 고립 학생 524명 (FMH: 524 Isolated Students)

모형은 385명을 예측했다. 실제는?

7-1. 어디가 남고 어디가 모자라는가 — 아홉 항 전부 (Where It Overshoots and Undershoots)

고립자만 볼 것이 아니라 차수 분포 전체를 푸아송 기대와 나란히 놓는다. 기대 인원은 $1461\times e^{-4/3}(4/3)^k/k!$이다.

8. 정말 어긋나는가 — 카이제곱과 무작위화 (Chi-Square and Randomization)

"139명 초과"가 우연일 수 있을까? 두 가지 방식으로 확인한다.

8-1. 카이제곱 적합도 검정 (Chi-Square Goodness-of-Fit Test)

$k=0,1,2,3,4$와 $k\ge5$를 묶어 여섯 칸으로 만들고 $\chi^2=\sum(\text{관측}-\text{기대})^2/\text{기대}$를 각 항 전부 계산한다.

8-2. 무작위화 — 같은 $n,m$으로 200번 (Randomization: 200 Draws at the Same n and m)

set.seed(12)
sim <- replicate(200, { g <- sample_gnm(1461, 974)
                        c(sum(igraph::degree(g)==0), max(components(g)$csize),
                          components(g)$no) })

참고로 실제 FMH의 컴포넌트 크기 상위 열 개는 439, 23, 19, 12, 11, 9, 8, 8, 8, 8이다. 1등과 2등의 격차가 19배다 — 이런 모양을 두고 "거대 컴포넌트가 있다"고 한다. 다음 절에서 그 "거대함"을 계산으로 다룬다.

9. 거대 컴포넌트 — 분지 과정으로 세는 법 (The Branching Process)

이제 오늘의 두 번째 이야기다. 질문은 이것이다.

$\lambda$를 0.1부터 조금씩 올리면, 망 전체를 관통하는 덩어리는 언제 생기는가?

9-1. 그림으로 먼저 (Starting with a Picture)

학생 한 명을 아무나 붙잡고 친구를 따라 퍼져 나간다고 하자.

여기서 1이라는 숫자가 자동으로 특별해진다.

9-2. 식으로 — 소멸 확률 $u$ (In Formulas: The Extinction Probability)

$u$를 "한 사람에게서 시작한 퍼짐이 결국 말라 죽을 확률"이라 하자. 그 사람에게 친구가 $k$명이라면, 퍼짐이 죽으려면 $k$개의 가지가 전부 각각 죽어야 한다 — 확률 $u^k$. 그러니 $k$에 대해 평균을 낸다.

여기에 푸아송 $P(k)=e^{-\lambda}\lambda^k/k!$를 넣으면 급수가 그대로 접힌다.

세 번째 등호가 §2에서 확인한 지수 급수다 — $\sum x^k/k!=e^x$에 $x=\lambda u$를 넣었을 뿐이다. 그리고 거대 컴포넌트가 차지하는 비율은

10. 손 계산 ④ $u=e^{-\lambda(1-u)}$ 반복 대입 열두 번 (Twelve Iterations by Hand)

$u=e^{-\lambda(1-u)}$는 $u$가 양변에 있어 손으로 풀리지 않는다. 대신 아무 값이나 넣고 계속 다시 넣는다(반복 대입, fixed-point iteration). FMH의 $\lambda=4/3$, 출발점 $u_0=0.5$로 열두 번 전부 적는다.

첫 줄만 손으로 확인해 보자: $1-0.5=0.5$, $-\frac43\times0.5=-\frac23=-0.666667$, $e^{-0.666667}=0.513417$ ✓

11. 임계점 $\lambda=1$ — 왜 하필 1인가 (The Critical Point)

$f(u)=e^{-\lambda(1-u)}$라 두면 우리가 찾는 것은 $f(u)=u$인 점이다.

먼저 확인할 것: $u=1$은 $\lambda$가 무엇이든 항상 해다.

즉 "퍼짐이 반드시 죽는다"는 언제나 하나의 답이다. 문제는 $u<1$인 두 번째 해가 있느냐다. 그 판정은 $u=1$에서의 기울기가 한다.

11-1. $\lambda$를 올려 가며 — 열 줄 전부 (Raising λ Step by Step)

11-2. 시뮬레이션과 이론 — 여덟 줄 (Simulation vs Theory)

12. FMH 대조 ② 거대 컴포넌트 439명 (FMH: A Giant That Is Too Small)

이론은 $S=0.4544$, 즉 $1461\times0.4544=664$명을 예측한다. 실제는?

13. R 검증 (R Verification)

13-1. 푸아송 근사 (The Poisson Approximation)

dpois(0:5, 1)          # 0.367879 0.367879 0.183940 0.061313 0.015328 0.003066
sum(dpois(0:5, 1))     # 0.9994058

lam <- 4/3
for (N in c(4, 10, 50, 200, 1460))
  cat(N, max(abs(dbinom(0:20, N, lam/N) - dpois(0:20, lam))), "\n")
# 4 0.066066 / 10 0.024529 / 50 0.004728 / 200 0.001174 / 1460 0.000161

13-2. 고립자 (Isolates)

data(faux.magnolia.high); G <- asIgraph(faux.magnolia.high)
n <- vcount(G); m <- ecount(G); p <- m/choose(n,2); lam <- 2*m/n
c(정확 = (1-p)^(n-1), 푸아송 = exp(-lam))    # 0.2634366  0.2635971
c(기대 = n*exp(-lam), 실제 = sum(igraph::degree(G)==0))
#     기대      실제
#  385.1154   524

13-3. 거대 컴포넌트 — 반복 대입 한 줄 (The Giant Component in One Line)

solve_u <- function(lam) { u <- 0.5; for (i in 1:2000) u <- exp(-lam*(1-u)); u }
1 - solve_u(4/3)                              # 0.4543950  (§10 손 계산과 일치)
n * (1 - solve_u(4/3))                        # 663.8710  -> 664명
max(components(G)$csize)                      # 439
components(G)$no                              # 661

13-4. 상전이 시뮬레이션 (Simulating the Phase Transition)

set.seed(11)
for (L in c(0.5, 0.8, 1.0, 1.2, 4/3, 1.5, 2.0, 3.0)) {
  s <- replicate(20, max(components(sample_gnp(1461, L/1460))$csize))
  cat(sprintf("%6.3f  %8.1f  %.4f  (이론 %.4f)\n", L, mean(s), mean(s)/1461, 1-solve_u(L)))
}

14. 교실 적용 (Classroom Application)

15. 연습문제 (Exercises)

16. 해설과 답 (Solutions)

연습문제 1 해설 (Solution to Exercise 1)

(1) 무엇을 나누는가 — 밀도는 실제 간선 수 ÷ 가능한 짝의 수, $\lambda$는 악수 정리.

(2) 무엇을 곱하는가 — $P(k)=e^{-2}\cdot 2^k/k!$. $2^k$와 $k!$를 따로 적고 마지막에 $e^{-2}=0.1353352832$를 곱한다. 여섯 항 전부:

비 검산 — 푸아송은 이웃 항끼리 $\dfrac{P(k)}{P(k-1)}=\dfrac{\lambda}{k}$다. $\lambda=2$이므로 $2/1=2$, $2/2=1$, $2/3$, $2/4$, $2/5$ — 위 표의 "왜 그 값인가" 열이 정확히 이 수열이다 ✓

(3) 두 방식으로 고립자 세기

(4) 거대 컴포넌트 — $\lambda=2$의 소멸 확률은 $u^{*}=0.203188$.

검산 — $u^{*}$가 정말 해인지 식에 도로 넣는다: $e^{-2(1-0.203188)}=e^{-1.593624}=0.203188$ ✓

(5) 7명은 유의한가

배수만 보면 커 보인다. 그런데 흔들림을 봐야 한다. 고립자 수는 대략 $X\sim B(30,\,e^{-2})=B(30,\,0.135335)$이므로

연습문제 2 해설 (Solution to Exercise 2)

(1) 무엇을 반복하는가 — 두 경우 모두 $u_{i+1}=e^{-\lambda(1-u_i)}$, $u_0=0.5$. 여덟 번 전부 나란히 놓는다.

(2) 수렴값과 $S$

검산 — B학년의 $u^{*}$를 식에 도로 넣는다: $e^{-1.25(1-0.628630)}=e^{-1.25\times0.371370}=e^{-0.464213}=0.628630$ ✓

(3) 왜 A가 느린가 — 반복 대입의 속도는 도착점에서의 기울기가 정한다.

표의 "증가폭" 열로 직접 확인하자. A: $0.084080/0.137628=0.611$, $0.056732/0.084080=0.675$, … $0.015289/0.018874=0.810$ — 회를 거듭할수록 0.9로 올라간다(도착점에 가까워지므로).
B: $0.024121/0.035261=0.684$, … $0.004049/0.005288=0.766$ — 0.786으로 수렴한다.

(4) 이론 0인데 왜 53명인가

(5) 두 담임에게