Bayesian Modeling of Collatz Stopping Times: A Probabilistic Machine Learning Perspective

이 논문은 콜라츠 정리의 총 정지 시간을 예측하기 위해 단순한 공변량을 기반으로 한 베이지안 계층적 음이항 회귀 모델과 홀수 블록 분해에 기반한 생성적 근사 모델을 개발하고, 저차 모듈러 구조가 이산 시간의 이질성을 설명하는 핵심 요인임을 실증적으로 규명합니다.

핵심

콜라츠 추측의 비밀을 확률로 풀어낸 이야기: "숫자 놀이"를 예측하는 두 가지 방법

이 논문은 수학의 유명한 난제인 **'콜라츠 추측 (3x+1 문제)'**에 대해, 수학적 증명을 시도하는 대신 통계와 머신러닝의 눈으로 접근한 흥미로운 연구입니다.

쉽게 말해, "이 숫자 놀이 규칙이 왜 이렇게 복잡한 패턴을 만들까?"를 증명하려 하지 않고, **"이 규칙이 만들어내는 숫자들의 행동을 통계적으로 얼마나 잘 예측할 수 있을까?"**를 연구한 것입니다.

---

1. 콜라츠 게임이란 무엇인가요? (배경)

상상해 보세요. 어떤 숫자 (n) 를 선택합니다.

• 짝수면: 반으로 나눕니다 (n/2).
• 홀수면: 3 곱하고 1 을 더합니다 (3n+1).
  이 과정을 반복하면, 결국 모든 숫자가 1로 수렴한다는 것이 콜라츠 추측입니다.

이때, 1 에 도달하기까지 몇 번의 단계 (stopping time, τ) 가 걸리는지를 '정지 시간'이라고 부릅니다. 이 논문은 1 억 개 (10^7) 의 숫자를 모두 시뮬레이션해서, 이 '정지 시간'이 어떤 분포를 가지는지 분석했습니다.

2. 연구의 핵심 질문

숫자들이 1 로 가는 길은 매우 불규칙합니다. 어떤 숫자는 순식간에 1 로 가고, 어떤 숫자는 아주 먼 길을 돌아갑니다.

• 질문: "이 복잡한 숫자 놀이의 결과를, 간단한 규칙이나 확률 모델로 설명하고 예측할 수 있을까?"

저자들은 두 가지 서로 다른 접근법 (모델) 을 개발해서 비교했습니다.

---

3. 두 가지 예측 방법 (모델)

방법 A: "통계적 예언가" (베이지안 회귀 분석)

이 방법은 현실적인 데이터에 집중합니다.

• 비유: 마치 날씨 예보관처럼 행동합니다.
  • "오늘 기온이 20 도이고 (로그 n), 화요일이라면 (나머지 8), 비 올 확률이 얼마나 될까?"라고 묻는 것과 비슷합니다.
  • 그들은 숫자의 크기 (log n) 와 숫자를 8 로 나눴을 때의 나머지 (n mod 8) 만 보고, "이 숫자가 1 에 도달하는 데 걸리는 시간"을 예측합니다.
  • 특징: "정확한 이유"보다는 "데이터가 보여주는 패턴"을 믿습니다. 과거 데이터를 바탕으로 "대체로 이렇게 움직인다"는 통계적 법칙을 찾아냅니다.

방법 B: "메커니즘 시뮬레이터" (생성 모델)

이 방법은 게임의 내부 규칙을 흉내 냅니다.

• 비유: 마치 가상 현실 게임을 만드는 것과 같습니다.
  • 콜라츠 게임에서 홀수일 때 "3 곱하기 1"을 하면, 그다음에 몇 번이나 2 로 나눌 수 있는지가 중요합니다 (예: 3x+1=10 이면 2 로 한 번, 3x+1=32 면 2 로 다섯 번).
  • 연구자들은 이 '나눠지는 횟수'를 주사위로 대체했습니다. "홀수일 때 2 로 몇 번 나눌지"를 무작위 주사위로 결정해서 게임을 시뮬레이션합니다.
  • 특징: 게임의 내부 작동 원리를 이해하려고 합니다. 하지만 단순히 무작위 주사위만으로는 실제 데이터와 맞지 않아, "나머지 8"이라는 정보를 주사위에 추가했습니다.

---

4. 누가 이겼을까? (결과)

두 모델을 실제 데이터 (보지 못한 숫자들) 로 테스트했을 때 놀라운 결과가 나왔습니다.

1. 통계적 예언가 (방법 A) 의 승리:

   • 예측 정확도 (확률 점수) 에서 압도적으로 이겼습니다.
   • 이유: 복잡한 게임의 내부 규칙을 다 따져보기보다, "숫자가 클수록 시간이 더 걸리고, 특정 나머지 숫자는 특정 패턴을 따른다"는 간단한 통계적 사실을 잘 활용했기 때문입니다.
   • 마치 "날씨 예보가 복잡한 대기 물리 방정식보다 과거 10 년간의 기온 데이터 패턴을 보는 게 더 정확할 수 있다"는 것과 비슷합니다.

2. 메커니즘 시뮬레이터 (방법 B) 의 교훈:

   • 처음엔 예측이 엉망이었습니다. 하지만 "나머지 8" 정보를 주사위에 추가하자 성능이 크게 좋아졌습니다.
   • 의미: 이는 콜라츠 게임이 단순히 무작위가 아니라, 숫자의 마지막 몇 자리 (2 의 거듭제곱 구조) 에 숨겨진 규칙이 있다는 것을 증명했습니다.

---

5. 결론: 왜 이 연구가 중요한가요?

이 논문은 콜라츠 추측을 "증명"하지는 못했지만, 통계와 머신러닝의 관점에서 중요한 통찰을 주었습니다.

• 통계적 접근의 힘: 복잡한 수학적 현상도, 적절한 변수 (숫자 크기, 나머지) 를 선택하면 간단한 통계 모델로 매우 정확하게 예측할 수 있습니다.
• 규칙의 숨은 단서: "나머지 8"이라는 작은 정보가 게임의 행동을 결정하는 핵심 열쇠였습니다. 이는 수학자들이 추측해 온 '2 진법 구조'의 중요성을 데이터로 확인해 준 것입니다.

한 줄 요약:

"콜라츠 게임은 복잡한 미스터리 같지만, 사실은 통계적 패턴과 숫자의 마지막 자리라는 두 가지 열쇠로 그 행동을 꽤 잘 예측할 수 있었습니다. 수학적 증명은 아직이지만, 확률론적 눈으로 보면 이 게임은 꽤 '예측 가능한' 놀이였습니다."

이 연구는 수학의 난제를 풀기 위해 데이터 과학의 도구를 어떻게 활용할 수 있는지 보여주는 훌륭한 사례입니다.

기술 요약

논문 요약: 콜라츠 정지 시간의 베이지안 모델링

이 논문은 콜라츠 추측 (Collatz Conjecture) 의 증명 시도가 아닌, 확률적 머신러닝 관점에서 **콜라츠 총 정지 시간 (Total Stopping Time, $\tau(n)$)**의 통계적 특성을 분석하고 예측하는 데 초점을 맞추고 있습니다. 저자들은 $N=10^7$까지의 정수들에 대한 $\tau(n)$ 데이터를 기반으로, 이산형 과분산 (overdispersed) 데이터를 설명하기 위한 두 가지 상보적인 모델을 개발하고 비교 평가했습니다.

1. 연구 문제 및 배경

• 문제 정의: 콜라츠 맵 $T(n)$ (짝수면 $n/2$, 홀수면 $3n+1$) 에 대해$T^t(n)=1$이 되는 최소 시간$t$를$\tau(n)$이라 정의합니다. 이 논문은$\tau(n)$이 결정론적 함수임에도 불구하고,$n$을 무작위로 샘플링했을 때 발생하는$\tau(n)$의 경험적 분포와 산술적 이질성 (arithmetic heterogeneity) 을 확률적 모델로 어떻게 설명하고 예측할 수 있는지 연구합니다.
• 데이터 특성: $1 \le n \le 10^7$에 대한 데이터를 분석한 결과,$\tau(n)$은 다음과 같은 특징을 가집니다:
  • 심한 왜도 (Skewness) 과 과분산: 분산이 평균보다 훨씬 큽니다 (분산/평균 비율 $\approx 24.56$). 이는 포아송 분포를 배제하고 음이항 분포 (Negative Binomial) 를 필요로 합니다.
  • 산술적 이질성: $n$에 따른 $\tau(n)$의 분포는 단순한 스케일 효과뿐만 아니라, $n \pmod 8$과 같은 모듈러 구조에 의해 형성된 밴딩 (banding) 현상을 보입니다.

2. 제안된 방법론

저자들은 예측 성능과 기계적 해석 가능성 (mechanistic faithfulness) 을 모두 고려하여 두 가지 모델을 제안합니다.

A. 베이지안 계층적 음이항 회귀 (Bayesian Hierarchical Negative Binomial Regression, NB2-GLM)

• 모델 구조: $\tau(n)$을 과분산 카운트 데이터로 간주하고, 조건부 평균 $\mu_n$이 $\log n$과 $n \pmod 8$에 의존한다고 가정합니다.
  • 링크 함수: $\log \mu_n = \beta_0 + \beta_{\log} \log n + u_{n \pmod 8}$
  • 계층적 구조: $n \pmod 8$의 8 가지 잔류류 (residue class) 별 편차 $u_r$을 정규 분포에서 추출하는 랜덤 효과 (random effect) 로 처리하여 부분 풀링 (partial pooling) 을 수행합니다. 이는 과적합을 방지하고 클래스별 추정을 안정화합니다.
• 추론: 약한 정보적 사전분포 (weakly-informative priors) 를 사용하며, PyMC 프레임워크의 NUTS (No-U-Turn Sampler) 를 통해 MCMC 추론을 수행했습니다.

B. 기계적 생성 모델 (Mechanistic Generative Odd-Block Model)

• 기본 아이디어: 콜라츠 동역학을 '홀수에서 홀수로'의 점프로 축약합니다. 홀수 $m$에 대해 $3m+1 = 2^{K(m)} m'$($m'$은 홀수) 로 표현할 때,$K(m) = v_2(3m+1)$을 '블록 길이'로 간주합니다.
• 확률적 근사: 결정론적인 $K(m)$을 확률 변수 $K$로 대체하여 생성 모델을 만듭니다.
  • 전통적 휴리스틱: $K$가 기하분포 $P(K=k) \approx 2^{-k}$를 따른다는 가정을 기반으로 합니다.
  • 보정 (Calibration): 관찰된 데이터에서 블록 길이 분포 $p_k$를 디리클레 - 다항식 (Dirichlet-multinomial) 업데이트를 통해 추정합니다.
  • 조건부 모델 ($G_3$): 블록 길이 분포를 $m \pmod 8$에 따라 조건부 (conditional) 로 설정하여 산술적 구조를 명시적으로 반영합니다.

3. 주요 결과 및 평가

두 모델은 $N_{test}=50,000$개의 홀드아웃 (held-out) 데이터 세트를 사용하여 **로그 예측 점수 (Log Predictive Score)**와 **1-워asserstein 거리 (W1 distance)**로 평가되었습니다.

모델	설명	로그 예측 점수 (높을수록 좋음)	W1 거리 (낮을수록 좋음)
NB2-GLM (M3)	베이지안 회귀 모델	-272,911	3.20
Odd-block G2	전역적 블록 길이 분포 (기하분포 기반)	-1,165,983	17.59
Odd-block G3	$m \pmod 8$ 조건부 블록 길이 분포	-1,079,086	5.43

• 예측 성능: **NB2-GLM (M3)**이 압도적으로 높은 예측 가능도 (predictive likelihood) 를 보였습니다. 이는 단순한 통계적 모델이 복잡한 산술적 구조를 가진 데이터를 예측하는 데 매우 효과적임을 시사합니다.
• 생성 모델의 개선: 전역적 생성 모델 (G2) 은 성능이 낮았으나, $m \pmod 8$에 대한 조건부 정보를 도입한 G3 모델은 분포 적합도가 크게 개선되었습니다. 이는 저차원 모듈러 구조가 $\tau(n)$의 이질성을 설명하는 핵심 요인임을 입증합니다.
• 분포적 적합도: NB2-GLM 은 전체 분포와 꼬리 부분 (tail) 을 잘 포착했으나, 생성 모델은 조건부 정보를 통해 평균 편향을 줄이고 본질적인 구조를 더 잘 설명합니다.

4. 기여 및 의의

1. 확률적 머신러닝 관점의 도입: 콜라츠 문제와 같은 결정론적 동역학 시스템에 대해 "작동 가능 우도 (working likelihood)"를 도입하여, 물리적 노이즈가 없더라도 $n$의 무작위성에 기반한 불확실성 정량화와 예측을 가능하게 했습니다.
2. 산술적 구조의 정량화: $n \pmod 8$과 같은 간단한 모듈러 조건이 콜라츠 정지 시간의 분산과 분포 형태를 결정하는 데 얼마나 중요한 역할을 하는지를 통계적으로 증명했습니다.
3. 상보적 모델링 접근:
   • NB2-GLM: 높은 예측 정확도와 불확실성 정량화를 제공하는 실용적 도구.
   • Odd-block Generator: 콜라츠 동역학의 기계적 메커니즘 (블록 길이) 을 해석 가능한 형태로 제공하는 이론적 도구.
4. 향후 연구 방향: 더 높은 2 의 거듭제곱 ($2^k$) 에 대한 조건부 구조 확장, 상태 의존적 (state-dependent) 블록 길이 모델링, 그리고 생성 모델의 기계적 해석성과 점수 기반 성능을 일치시키기 위한 가능성 제시.

5. 결론

이 논문은 콜라츠 정지 시간의 복잡한 분포를 설명하기 위해 간결한 계층적 회귀 모델과 기계적 생성 모델을 결합한 접근법을 제시했습니다. 통계적 모델이 예측 면에서 우월함을 보인 반면, 생성 모델은 데이터의 산술적 이질성을 설명하는 메커니즘을 제공하며, 특히 모듈러 조건 ($n \pmod 8$) 을 고려할 때 두 모델 간의 격차가 줄어듦을 확인했습니다. 이는 콜라츠 문제와 같은 수학적 난제에 대해 확률적 머신러닝 기법이 새로운 통찰을 제공할 수 있음을 보여주는 사례입니다.