Records, drift, and the longest increasing subsequence of biased Gaussian… — 쉬운 설명

마주친 술취한 사람이 길고 곧은 거리를 걸어가는 모습을 상상해 보세요. 이것이 바로 랜덤 워크입니다. 그들이 취하는 한 걸음 한 걸음은 조금씩 무작위적입니다: 때로는 앞으로, 때로는 뒤로 걸어가죠.

수십 년간 과학자들은 이 사람이 앞으로 걸을 확률과 뒤로 걸을 확률이 동일할 때 (즉, 대칭적인 워크일 때) 어떤 일이 일어나는지 연구해 왔습니다. 그들은 그 사람이 오직 오름길만 걷고 (절대 내려가지 않고) 취한 가장 긴 발걸음의 열은 총 걸음 수의 제곱근처럼 천천히 증가한다는 사실을 발견했습니다.

하지만 만약 그 사람이 약간 앞으로 기울어지는 경향이 있다면 어떨까요? 만약 그들이 약간 오름길을 걷도록 편향되어 있다면 어떨까요? 이 논문은 바로 그 시나리오를 탐구합니다.

다음은 발견된 내용들을 간단한 개념으로 분해한 이야기입니다:

1. 설정: 편향된 술취한 사람

연구자들은 '가우스'(종형 곡선) 분포에 기반하여 걸음을 취하는 보행자를 시뮬레이션했는데, 여기에 한 가지 변형이 있었습니다: 보행자에게는 양의 편향이 존재한다는 점입니다.

대칭적 경우 (50/50): 보행자가 완벽하게 균형을 이룬다면, 가장 긴 오름길은 천천히 증가합니다.
편향된 경우 (조금만이라도): 보행자가 뒤로 걸을 때보다 조금만이라도 앞으로 걸을 확률이 더 높다면, 규칙은 완전히 바뀝니다.

2. 주요 발견: '선형적' 폭발

가장 놀라운 발견은 가장 긴 오름길이 얼마나 빠르게 증가하는지에 관한 것입니다.

균형 잡힌 세계에서는: 경로는 천천히 증가합니다 ( $\sqrt{n}$ 처럼).
편향된 세계에서는: 앞쪽 방향으로 아무런 편향이라도 존재하는 순간, 가장 긴 오름길은 갑자기 선형적으로 증가하기 시작합니다.

유추: 보행자가 산을 오르고 있다고 상상해 보세요.

바람이 잔잔할 경우 (대칭적), 그들은 위아래로 헤매다가, 걷는 총 시간에 비해 상대적으로 짧은 연속된 등반을 성취할 수 있습니다.
그들이 앞으로 밀어주는 아주 gentle한 바람 (편향) 이라도 있다면, 그들은 목적 없이 헤매는 것을 멈춥니다. 그들은 꾸준히 오르기 시작합니다. 그들의 연속된 등반 길이는 걷는 시간에 비례하게 됩니다. 그들이 두 배 더 오래 걷는다면, 두 배 더 높이 오르는 것입니다.

이 논문은 영이 아닌 모든 편향에 대해 이 선형적 성장이 즉시 발생함을 발견했습니다. '지수'(증가를 설명하는 거듭제곱) 는 약 0.5 에서 정확히 1로 점프합니다.

3. 워크의 '골격': 기록들

왜 이런 일이 일어나는지 이해하기 위해, 저자들은 **기록 (Records)**을 살펴보았습니다.

기록이란 보행자가 과거에 도달했던 어떤 지점보다 더 높은 새로운 최고점에 도달하는 순간을 말합니다.
균형 잡힌 워크에서는 기록이 드뭅니다.
편향된 워크에서는 기록이 끊임없이 발생하여 워크의 '골격'이나 등뼈를 형성합니다.

연구자들은 최장 증가 부분 수열 (LIS)—즉, 가장 긴 오름길—이 본질적으로 이 '기록 골격'을 따름을 발견했습니다.

높은 편향에서: 보행자는 올라가는 데 매우 집착하여 거의 모든 걸음이 기록이 됩니다. 가장 긴 오름길은 거의 그들의 모든 개인 최고 기록 목록과 동일합니다.
낮은 편향에서: 보행자는 여전히 대부분 기록을 따르지만, 때로는 두 기록 사이에 추가적인 걸음을 끼워 넣기 위해 작은 '우회' (변동) 를 취합니다.

4. 기록과 경로 사이의 '간격'

이 논문은 기록의 수와 최장 경로의 길이 사이의 차이를 측정합니다.

간격: 이는 보행자가 취하는 '추가' 걸음을 나타내는데, 이는 개인 최고 기록은 아니지만 여전히 오름길 사슬에 포함됩니다.
간격의 모양: 이 간격은 편향이 아주 작을 때는 (워크가 여전히 혼란스러우므로) 작고, 편향이 매우 클 때는 (보행자가 너무 집착하여 모든 걸음이 기록이 되므로) 작습니다.
피크: 간격은 '중간' 편향 (앞으로 걸을 확률이 약 60% 정도) 에서 가장 큽니다. 여기서는 보행자가 꾸준히 오를 만큼 집착하지만, 주요 이정표 사이에 추가적인 '숨겨진' 걸음을 찾아낼 만큼 여전히 흔들립니다.

5. '전환점' (특이한 한계)

연구의 가장 미묘한 부분은 편향이 거의 0 인 가장자리, 즉 50.1% 대 49.9% 인 지점에서 어떤 일이 일어나는지입니다.

이 논문은 '느린 성장'에서 '선형적 성장'으로의 전환이 특이적임을 보여줍니다. 그것은 부드러운 미끄러짐이 아니라 절벽입니다.
편향이 점점 작아질수록 경로의 길이는 단순히 선형적으로 줄어들지 않습니다. 선형보다 더 느리게 줄어듭니다. 마치 편향이 절대 영도에 도달할 때까지 경로가 완전히 사라지기를 거부하는 것처럼 보입니다.
저자들은 이 아주 작은 영역에서 경로가 어떻게 줄어드는지에 대한 간단한 수학적 공식을 찾지는 못했지만, 그것이 누구도 예상하지 못했던 방식으로 행동함을 증명했습니다.

6. 데이터의 모양: '기이함'에서 '정상'으로

마지막으로, 이 논문은 이러한 경로들의 분포를 살펴봤습니다 (시뮬레이션을 10,000 번 실행했을 때 결과가 어떻게 보이는지).

균형 잡힌 워크 (50/50): 결과는 '왜도'가 있고 '두꺼운 꼬리'를 가집니다. 로그 정규 분포와 같습니다. 대부분의 경로는 짧지만, 가끔은 놀랍게도 긴 경로가 나옵니다. 예측 불가능하고 '기이합니다'.
편향된 워크 (조금만이라도): 결과는 **가우스 (종형 곡선)**로 딱 맞춰집니다. 경로들은 매우 예측 가능하고 '정상'이 됩니다. 워크를 편향시킬수록 결과는 표준 종형 곡선과 더 비슷해집니다.

요약

이 논문은 랜덤 워크의 세계에서 방향에 대한 아주 작은 변화조차 모든 것을 바꾼다고 알려줍니다.

이전: 균형 잡힌 보행자는 헤매며, 그들의 최고의 등반은 짧고 예측 불가능합니다.
이후: 편향된 보행자는 앞으로 행진합니다. 그들의 최고의 등반은 시간과 함께 꾸준히 그리고 선형적으로 증가하며, 개인 최고 기록들의 예측 가능한 '골격'을 따릅니다.
전환: 편향을 도입하는 순간, 게임의 규칙은 즉시 바뀌어 혼란스럽고 느린 성장의 세계에서 안정적이고 선형적인 성장의 세계로 이동합니다.

기술적 요약: 편향된 가우시안 랜덤 워크의 기록, 드리프트 및 최장 증가 부분 수열

문제 제기
전통적으로 무작위 순열과 평균이 0 인 대칭 랜덤 워크에 대해 연구되어 온 최장 증가 부분 수열 (LIS) 문제는 유한 분산의 경우 $\sqrt{n \log n}$ 로, 혹은 heavy-tailed 증가분의 경우 $n^\theta$ 로 성장하는 기대 LIS 길이에 대한 엄밀한 스케일링 법칙을 확립해 왔습니다. 그러나 양의 드리프트를 갖는 편향된 랜덤 워크의 LIS 거동은 아직 탐구되지 않았습니다. 편향된 워크는 방향성 추세를 가진 시계열을 모델링하며, 여기서 LIS 는 상관관계가 있고 비정상적인 시퀀스 내의 단조 구조를 탐구합니다. 본 논문은 단위 분산과 양의 평균 드리프트 $\mu_p$ 를 갖는 가우시안 랜덤 워크의 LIS 를 조사하며, 여기서 $p = P(\xi > 0) \ge 1/2$ 로 매개변수화됩니다. 핵심 질문은 대칭적인 경우와 비교하여 작은 비대칭성조차 도입하는 것이 LIS 의 점근적 스케일링과 분포적 성질을 어떻게 변화시키는지입니다.

방법론
본 연구는 편향된 가우시안 랜덤 워크에 대한 LIS 길이 ( $L_n$ ) 를 계산하기 위해 인내심 정렬 (patience sorting) 알고리즘을 사용한 수치적 접근법을 채택합니다.

모델: 워크는 $X_k = \mu_p k + W_k$ 로 정의되며, 여기서 $W_k$ 는 단위 분산을 갖는 중심화된 가우시안 랜덤 워크이고, $\mu_p = \Phi^{-1}(p)$ 는 편향 매개변수 $p$ 에 의해 결정된 드리프트입니다.
관측 가능량: 각 실현에 대해 저자들은 다음을 측정합니다:
1. LIS 길이 $L_n(p)$ .
2. 기록 횟수 $R_n(p)$ (워크가 새로운 최댓값을 설정하는 횟수).
3. 중첩 $R^{LIS}_n(p)$ (회복된 LIS 에 포함된 기록 시점의 수).
시뮬레이션 프로토콜: 저자들은 $n$ 이 $10^4$ 에서 $10^7$ 까지이고 편향 매개변수 $p \in [0.5, 0.999]$ 인 워크 길이에 대해 10,000 개의 독립적인 실현을 생성했습니다. 특히 대칭점 $p=1/2$ 근처와 결정론적 한계 $p \to 1$ 근처 영역에 특별한 주의를 기울였습니다.
분석: 본 연구는 유효 지수, 선형 계수, 진단 비율 (예: $R^{LIS}_n/L_n$ ), 그리고 양 - 양 (quantile-quantile) 플롯 및 통계적 검정 (콜모고로프 - 스미르노프, 왜도, 첨도) 을 통한 $L_n$ 의 분포적 형태를 분석합니다.

주요 기여 및 결과

선형 스케일링으로의 전환:
$E[L_n] \sim \sqrt{n \log n}$ 인 대칭적인 경우 ( $p=1/2$ ) 와는 대조적으로, 저자들은 임의의 고정된 $p > 1/2$ 에 대해 평균 LIS 길이가 $n$ 에 선형적으로 성장함을 발견합니다:
$\langle L_n(p) \rangle \sim a(p)n$
유효 지수 $\theta(p)$ 는 모든 $p > 1/2$ 에 대해 1 로 빠르게 수렴합니다. 연구의 관련 대상은 지수에서 계수 $a(p)$ 로 이동하며, 이는 $p=1/2$ 에서 0 에서 시작하여 $p \to 1$ 로 갈 때 1 로 매끄럽게 증가합니다.
기록 통계 및 "기록 골격":
본 논문은 편향된 영역에서 LIS 가 점점 더 "기록 골격"(기록 시점의 시퀀스) 과 정렬됨을 확립합니다.
- 평균 기록 횟수 또한 선형적으로 성장합니다: $\langle R_n(p) \rangle \sim \lambda(p)n$ .
- 계수 $\lambda(p)$ 는 편향된 워크에 대한 알려진 결과인 Spitzer 의 평균 상승 사다리 시점 공식 (식 24) 에 의해 정량적으로 설명됩니다.
- $p \to 1$ 로 갈 때, LIS 요소 중 기록인 것들의 비율 ( $R^{LIS}_n/L_n$ ) 과 LIS 에 사용된 기록들의 비율 ( $R^{LIS}_n/R_n$ ) 모두 1 에 접근하여, LIS 가 점근적으로 기록 골격과 동일함을 나타냅니다.
변동 초과 ( $a(p) - \lambda(p)$ ):
주요 발견 중 하나는 LIS 계수 $a(p)$ 와 기록 계수 $\lambda(p)$ 사이의 0 이 아닌 간격입니다. 이 차이, $a(p) - \lambda(p)$ 는 기록 사이의 중심화된 워크 $W_k$ 의 국소적 이동 (local excursions) 이 LIS 에 기여하는 바를 나타냅니다.
- 이 간격은 단조롭지 않으며, $p=1/2$ 와 $p \to 1$ 에서 소멸하고 $p \approx 0.6$ ( $\mu_p \approx 0.25$ ) 근처에서 약 0.1 의 최대값에 도달합니다.
- 이는 선형 영역에서도 LIS 가 순수한 기록 과정이 아님을 의미하며, 특히 중간 정도의 드리프트에서 상당한 비율의 비기록 단계를 포함합니다.
분포적 전환:
LIS 길이의 경험적 분포는 특이점 $p=1/2$ 에서 급격한 전환을 겪습니다:
- $p=1/2$ 에서: 분포는 대칭적 워크에서 관찰된 것처럼 로그정규 근사와 일치하는 오른쪽으로 치우치고 두꺼운 꼬리를 가집니다.
- $p > 1/2$ 에서: 표준화된 $L_n$ 의 분포는 가우시안 변동과 일치하며, 선형 영역에서 LIS 의 광범위한 합과 유사한 구조에 대한 중심극한 그림을 지지합니다.
$p=1/2$ 에서의 특이한 한계:
대칭점은 선형 영역의 특이한 한계입니다.
- 기록 밀도는 작은 드리프트에 대해 $\lambda(\mu_p) \sim 1.39 \mu_p$ 로 스케일링됩니다.
- LIS 계수 $a(\mu_p)$ 는 선형보다 더 느리게 소멸합니다. 비율 $a(\mu_p)/\mu_p$ 는 $\mu_p \to 0$ 으로 갈 때 증가합니다.
- 변동 초과 $a(\mu_p) - \lambda(\mu_p)$ 는 샘플링된 범위에서 단일 멱법칙을 따르지 않으며, 국소 로그 - 로그 기울기가 드리프트하여 단순한 기록 간 이동 추정치로는 포착되지 않는 복잡한 경계층 거동을 시사합니다.

의의 및 범위
본 논문은 편향된 랜덤 워크에 대한 LIS 의 첫 번째 수치적 특성을 제공하며, 양의 드리프트가 스케일링을 아선형 ( $\sqrt{n \log n}$ ) 에서 선형 ( $n$ ) 으로 근본적으로 변화시킨다는 것을 보여줍니다. 연구는 편향된 영역에서 지배적인 구조로 기록 골격을 식별하지만, 비기록 변동의 지속적인 기여를 정량화합니다.

저자들은 명시적으로 Spitzer 의 항등식을 통해 기록 계수 $\lambda(p)$ 가 분석적으로 알려져 있지만, 현재 LIS 계수 $a(p)$ 에 대한 폐쇄형 표현식은 이용 가능하지 않다고 명시합니다. 확인된 주요 미해결 문제는 기록 골격의 갱신 구조와 기록 간 보간을 지배하는 전역적 단조성 제약을 조화시키는 $a(p)$ 의 유도입니다. 논문은 소박한 기록 간 이동 추정치로는 포착되지 않는 작은 드리프트 거동의 정확한 점근적 형태가 여전히 해결되지 않았으며, 결과가 유한 분산 가우시안 증가분에 구체적임을 겸손하게 지적하며, 무한 분산 경우 (편향된 코시 워크 등) 는 향후 조사에 남겨둡니다.

Records, drift, and the longest increasing subsequence of biased Gaussian random walks