Infinite-mean Galton-Watson trees have zero random-interchange threshold

기술 요약: 무한 평균 갈톤-왓슨 트리의 무작위 교환 임계값은 0이다

문제 정의
본 논문은 국소 유한한 갈톤-왓슨 트리(Galton–Watson trees) 상에서의 무작위 교환 과정(random interchange process)의 상전이를 조사한다. 이 과정은 엣지를 따라 포아송 전치(Poisson transpositions)를 통해 공간적 무작위 순열을 생성한다. 핵심 질문은 무한 사이클(루프)의 존재 여부와 루프 임계 파라미터 $\beta_{\text{loop}}^c$와 링크 퍼콜레이션 임계 파라미터 $\beta_{\text{link}}^c$ 사이의 관계이다.

기존 연구는 유한한 자손 평균 $\mu \in (1, \infty)$를 갖는 갈톤-왓슨 트리에 대해, 생존을 조건으로 했을 때 루프와 링크 임계값이 엄격히 분리됨($\beta_{\text{loop}}^c > \beta_{\text{link}}^c$)을 확립했다. 본 연구는 자손 변수 $Z$가 거의 확실하게(almost surely) 유한하지만 자손 평균이 무한인($\mathbb{E}[Z] = \infty$) 보완적인 경우를 다룬다. 이 영역에서 링크 임계값은 0으로 알려져 있으며, 본 논문은 루프 임계값 또한 0인지 확인하여, 이 모델들의 거동에 기초한 평균의 유한성에 따른 이분법을 확립하는 것을 목표로 한다.

방법론
본 논문의 증명은 무한 트리 문제를 무작위 곡면의 필링 추정치(peeling estimates)로부터 유도된 유한 순열 추정치로 환원한다. 방법론은 다음과 같은 몇 가지 주요 단계로 진행된다:

1. 다중 링크 탐색 (Multi-link Exploration): 저자들은 $d$-진 트리(d-ary trees)에서 이전에 사용되었던 다중 링크 클러스터 탐색 기법을 비조건부 어닐드(unconditioned annealed) 갈톤-왓슨 설정에 맞게 조정한다. 이들은 "다중 링크" 성분을 적어도 두 개의 포아송 점(교차점)을 가진 엣지들의 연결된 부분 그래프로 정의한다. 루프는 이러한 성분 내에서 탐색되는 반면, 정확히 하나의 교차점을 가진 엣지("단일 링크")는 갱신 지점(renewal points) 역할을 한다.
2. 분기 기준 (Branching Criterion): 핵심 보조정리는 만약 "외부 단일 링크 출구"의 기대값이 1을 초과하면, 전체 루프가 양의 어닐드 확률로 무한한 정점 지지 집합을 갖는다는 것을 확립한다. 이는 루프 생존 문제를 분기 과정 분석으로 변환시킨다.
3. 태그된 깨끗한 이중 잎 (Tagged Clean Double Leaves): 출구의 기대값을 추정하기 위해, 저자들은 정확히 두 개의 교차점을 가진 엣지로 연결되어 있고 그 아래에 더 이상의 다중 링크 엣지가 없는 "태그된 깨끗한 이중 잎"에 집중한다. 이들은 다중 링크 루프가 기대적으로 이러한 잎들의 양의 비율을 방문함을 증명한다.
4. 유한 순열 추정치 (경계 쌍 형성, Boundary Pairing): 핵심적인 기술적 혁신은 무한 트리 루프 문제를 유한 순열 문제로 환원하는 것이다. 저자들은 정점에서의 루프 귀환을 두 가지 순열의 합성으로 모델링한다: 결정론적 순열 $\chi$ (트리 구조와 태그되지 않은 탈출로부터 유도됨)와 무작위 균등 고정점 없는 인볼루션(fixed-point-free involution) $\tau$ (태그된 끝점들의 무작위 쌍 형성으로부터 유도됨)의 합성이다.
   • 이들은 $\chi$의 짧은 사이클(길이 1 또는 2)에 속하는 점의 개수가 작으면, 높은 확률로 $\tau\chi$의 특정 점 $j$를 포함하는 사이클이 거시적(전체 점의 개수에 비례하는 크기)임을 보이는 "필링(peeling)" 알고리즘을 활용한다.
5. 어닐드에서 퀜치드(Quenched)로의 전이: 증명은 먼저 무한 루프에 대한 양의 어닐드 확률을 확립한다. 그 후 갈톤-왓슨 분기 성질과 (무한 평균으로 인한) 생성 함수의 엄격한 볼록성을 사용하여, 이를 퀜치드 결과로 격상시킨다: 즉, 생존을 조건으로 한 거의 모든 실현된 트리(realization of the tree)에 대해 루프 임계값은 0이다.

주요 기여 및 결과

• 주요 정리: $Z < \infty$를 만족하면서 $\mathbb{E}[Z] = \infty$인 자손 법칙 $Z$를 갖는 갈톤-왓슨 트리에 대해, 생존을 조건으로 할 때 무작위 교환 과정은 다음을 만족한다:
  $$\beta_{\text{loop}}^c(T) = \beta_{\text{link}}^c(T) = 0$$
  거의 확실하게(almost surely). 구체적으로, 임의의 고정된 $\beta > 0$ (충분히 작은 값)에 대하여 루트에서 시작하는 무한 루프의 확률은 양수이다.
• 이분법: 유한 평균에 대한 이전 결과들과 결합하여, 이는 $\mu \in (1, \infty]$인 국소 유한 갈톤-왓슨 트리에 대한 날카로운 이분법을 확립한다:
  • $\mu < \infty$이면, 루프와 링크 임계값은 엄격히 분리된다.
  • $\mu = \infty$이면, 두 임계값은 일치하며 모두 0이다.
• 기술적 환원: 본 논문은 무한 트리 루프 문제를 결정론적 사상과 무작위 인볼루션의 합성인 유한 순열 추정치로 환원하는 새로운 방식을 제공한다. 이 추정치는 무작위 평면 맵(random planar maps) 이론의 필링 기법을 사용하여 유도된다.

의의
본 논문은 표준적인 유한 평균 트리용 재귀적 추정치가 실패하는 무한 평균 영역에서의 무작위 교환 과정의 거동을 해결했다고 주장한다. 이 결과는 무한 사이클의 기하학적 구조가 자손 분포의 꼬리(tail) 거동에 따라 근본적으로 달라짐을 보여준다. 유한 평균 트리는 퍼콜레이션과 루프 형성 사이에 "간극"을 보이는 반면(즉, 루프 형성을 위해 더 높은 밀도의 링크가 필요함), 무한 평균 트리는 퍼콜레이션이 발생하는 즉시(즉, 임의의 양의 강도에서) 루프가 형성된다.

이 연구는 무작위 교환 과정을 무작위 곡면 이론과 연결하며, 트리의 무작위 순열의 조합적 구조가 무작위 평면 맵을 위한 도구들을 사용하여 분석될 수 있음을 보여준다. 저자들은 본 증명이 무한 트리 구조에 대한 더 복잡한 직접 분석을 피하고, 유한 순열 추정치로의 "깔끔한(clean)" 환원에 의존하고 있음을 언급한다.