The Random Subsequence Model and Uniform Codes for the Deletion Channel

이 논문은 **랜덤 부분열 모델 (Random Subsequence Model)**을 소개하고, 이를 통해 **이진 삭제 채널 (Binary Deletion Channel)**에서 균일 무작위 코드 (Uniformly-random codes) 가 달성할 수 있는 최대 전송률 (Capacity) 에 대한 근본적인 문제를 해결합니다. 저자 Ryan Jeong 과 Francisco Pernice 는 통계물리학의 스핀 글래스 (Spin Glass) 이론을 정보이론 문제에 적용하여, 삭제 채널의 용량 하한과 상한에 대한 새로운 결과를 도출했습니다.

다음은 논문의 상세한 기술적 요약입니다.

1. 연구 배경 및 문제 정의

• 삭제 채널 (Deletion Channel): 입력 비트열의 각 비트가 확률 $p$로 독립적으로 삭제되어 출력되는 채널입니다. 입력과 출력 간의 동기화 (비트 위치 매칭) 가 손실되므로, 기존 메모리스 채널 (예: BSC) 보다 분석이 훨씬 어렵습니다.
• 균일 무작위 코드 (Uniform Random Codes): 모든 가능한 코드북을 균일하게 무작위로 선택하는 방식입니다. 많은 메모리스 채널에서 최적의 성능을 내지만, 삭제 채널에서는 $p$가 1 에 가까울 때 성능이 어떻게 변하는지, 특히 $p \ge 1/2$인 영역에서 양의 전송률을 달성할 수 있는지가 오랫동안 미해결 문제였습니다.
• 랜덤 부분열 모델 (Random Subsequence Model):
  • 두 개의 이진 문자열 $(X, Y)$가 주어졌을 때, $Y$가 $X$의 부분열 (subsequence) 로 매칭되는 경우의 수를 세는 분배함수 (Partition Function) $Z_{X,Y}$를 정의합니다.
  • Null 모델: $X$와 $Y$가 서로 독립적이고 균일하게 무작위로 생성됨.
  • Planted 모델: $X$가 균일 무작위이고, $Y$는 $X$에서 균일하게 선택된 길이 $M$의 부분열로 생성됨.
  • 이 모델의 분배함수는 삭제 채널의 상호정보량 (Mutual Information) 과 직접적으로 연결됩니다.

2. 주요 방법론

논문의 핵심은 통계물리학의 스핀 글래스 (Spin Glass) 이론과 방향성 고분자 (Directed Polymers) 모델을 정보이론 문제에 적용하는 것입니다.

• Free Energy (자유 에너지) 분석:
  • Annealed Free Energy: $\frac{1}{N} \log E[Z]$ (기댓값을 로그 안으로 취함).
  • Quenched Free Energy: $\frac{1}{N} E[\log Z]$ (로그를 취한 후 기댓값).
  • 두 값 사이의 간격 (Gap) 이 존재하는지, 즉 Jensen Gap이 0 이 아닌지 확인하는 것이 핵심입니다. 이 간격은 시스템이 스핀 글래스 상 (Spin Glass Phase) 에 있는지, 그리고 균일 코드가 최적의 성능을 낼 수 있는지를 결정합니다.
• 구조적 가설 검정 (Structural Hypothesis Testing):
  • Null 모델과 Planted 모델을 구별할 수 있는 "Good Set"을 정의합니다.
  • Planted 모델: 생성된 $Y$는 $X$의 구조와 높은 정렬 (Alignment) 을 보입니다.
  • Null 모델: $Y$는 $X$와 무관하므로, 임의의 $Y$가 $X$와 높은 정렬을 보일 확률은 지수적으로 작습니다.
  • 이를 위해 **블록 분할 (Block Partitioning)**과 국소 정렬 (Local Alignment) 개념을 도입하고, **표준화 알고리즘 (Standardization Algorithm)**을 사용하여 Null 모델에서의 편향된 정렬을 배제합니다.
• 변분법 (Variational Methods) 과 생성함수:
  • Planted 모델의 Annealed Free Energy 를 정확히 계산하기 위해, 분배함수의 모멘트 생성함수를 분석하고, 이를 **변분 문제 (Variational Problem)**로 변환하여 해석적으로 풀었습니다.

3. 주요 결과 및 기여

A. Quenched-Annealed Gap 의 엄격한 분리 (Theorem 1.1)

• 결과: 밀도 매개변수 $\alpha = M/N \in (0, 1)$의 모든 값에 대해, Null 모델과 Planted 모델의 Quenched Free Energy 와 Annealed Free Energy 사이에 엄격한 간격이 존재함을 증명했습니다.
  • $f_{pl}(\alpha) > f_{ann}^{null}(\alpha)$
  • Null 모델에서도 $\alpha < 1/2$일 때 $f_{null}(\alpha) < f_{ann}^{null}(\alpha)$가 성립합니다.
• 의미: 이 결과는 두 모델이 모두 영온도 (Zero Temperature) 에서 스핀 글래스 상에 있음을 시사하며, 균일 무작위 코드가 삭제 채널에서 최적의 성능을 내지 못하더라도 여전히 양의 전송률을 가질 수 있음을 의미합니다.

B. 균일 코드의 양의 전송률 증명 (Corollary 1.2)

• 주요 성과: 삭제 확률 $p \in [0, 1)$인 모든 영역에서 균일 무작위 코드가 **양의 전송률 (Positive Rate)**을 달성함을 증명했습니다.
• 의미:
  • 이전 연구들은 주로 $p < 1/2$ 영역에서만 양의 전송률을 보였습니다.
  • 이 논문은 **$p \ge 1/2$ (각 비트가 보존될 확률보다 삭제될 확률이 더 높은 영역)**에서도 양의 전송률이 가능함을 최초로 증명하여, [PIW24] 의 여러 추측을 해결했습니다.
  • $p \to 1$일 때, 전송률이 $(1-p)^k$ ($k$는 상수) 꼴로 감소함을 보였습니다.

C. Planted 모델의 Annealed Free Energy 에 대한 정확한 해석식 (Theorem 1.3)

• 결과: Planted 모델의 Annealed Free Energy $f_{ann}^{pl}(\alpha)$에 대한 정확한 해석적 공식을 도출했습니다.
  • 이 공식은 $x_\alpha, y_\alpha$와 같은 대수적 변수를 통해 표현되며, 변분 문제의 최적해를 통해 얻어졌습니다.
• 의미:
  • 이 값은 균일 코드가 달성할 수 있는 전송률에 대한 **상한 (Upper Bound)**을 제공합니다.
  • 기존 삭제 채널 용량의 상한/하한과 비교했을 때, 균일 코드에 대한 이 상한/하한은 훨씬 더 가깝게 수렴하여, 균일 코드가 실제 채널 용량을 이해하는 중요한 단서임을 보여줍니다.

4. 기술적 세부 사항 및 증명 전략

1. 약한 수렴 (Weak Limits):
   • Null 모델과 Planted 모델 모두에서 $\frac{1}{N} \log Z$가 확률적으로 수렴하는 상수 (Free Energy) 를 가짐을 증명했습니다. Null 모델의 경우 $\alpha > 1/2$에서는 $Z=0$일 확률이 높아 수렴하지 않지만, $\alpha < 1/2$에서는 양의 값을 가집니다.
2. 정렬 (Alignment) 과 표준화 (Standardization):
   • Null 모델에서 $Y$가 $X$와 우연히 높은 정렬을 보일 가능성을 배제하기 위해, $Y$를 블록으로 나누고 각 블록의 합 (Majority bit) 과 랜덤 워크 변위 (Displacement) 를 분석했습니다.
   • 표준화 알고리즘을 통해 임의의 분할을 "표준화된" 분할로 매핑하고, 이 과정에서 정렬 점수가 크게 증가하지 않음을 보여, Null 모델에서의 정렬이 Planted 모델보다 훨씬 낮음을 증명했습니다.
3. 변분 문제의 해:
   • Planted 모델의 Annealed Free Energy 계산을 위해, 분배함수의 합을 **경로 (Path)**의 관점에서 재해석하고, 이를 지수족 (Exponential Family) 분포를 가진 확률 측도 $\nu$에 대한 최적화 문제로 변환했습니다.
   • 라그랑주 승수법을 사용하여 최적 해를 구하고, 생성함수 (Generating Function) 를 Vandermonde 항등식을 통해 닫힌 형태 (Closed-form) 로 계산했습니다.

5. 의의 및 향후 과제

• 정보이론적 의의: 삭제 채널의 용량 문제는 수십 년간 해결되지 않은 난제였습니다. 이 논문은 균일 코드가 $p \ge 1/2$에서도 작동함을 증명함으로써, 삭제 채널의 용량 하한에 대한 이해를 획기적으로 넓혔습니다.
• 통계물리학적 의의: 스핀 글래스 모델과 정보이론의 연결을 강화했습니다. 특히, "Rank-one" 랜덤 환경에서의 방향성 고분자 모델을 분석하여, 기존에 알려진 솔버블 (Solvable) 모델들 (예: Strict-Weak Polymer) 과의 관계를 규명했습니다.
• 남은 과제 (Open Problems):
  • Planted 모델의 Quenched Free Energy ($f_{pl}$) 계산: 현재는 Annealed Free Energy ($f_{ann}^{pl}$) 만 정확히 구했습니다. 실제 전송률을 결정하는 Quenched Free Energy 의 정확한 값은 여전히 미해결이며, Replica Method 나 Cavity Method 를 통한 추정이 필요합니다.
  • Likely Deletion Regime ($\alpha \to 0$): $p \to 1$일 때 전송률의 점근적 행동에 대한 더 정밀한 분석이 필요합니다.

결론

이 논문은 랜덤 부분열 모델이라는 새로운 프레임워크를 도입하여, 삭제 채널에서 균일 무작위 코드가 모든 삭제 확률 $p < 1$에서 양의 전송률을 가진다는 것을 rigorously 증명했습니다. 또한, Planted 모델의 Annealed Free Energy 에 대한 정확한 해석식을 도출하여 전송률의 상한을 제시함으로써, 삭제 채널 용량 연구에 있어 중요한 이정표를 세웠습니다.