Day 071-Q3 | ランダムウォーク混合時間（Mixing Time・スペクトルギャップ・TV距離）

問題

$N$ 頂点の無向連結グラフ $G$ 上のランダムウォークを考える。各ステップで現在の頂点 $v$ から、$v$ の全隣接頂点から一様ランダムに次の頂点を選ぶ。

以下を計算せよ:

定常分布: 各頂点 $v$ の定常確率 $\pi(v)$
スペクトルギャップ: $\gamma = 1 - \lambda_2$（$\lambda_2$ は推移行列の2番目に大きい固有値）
混合時間の上界: TV 距離が $\varepsilon = 0.01$ 以下になるステップ数の上界

制約

パラメータ	範囲
$N$	$2 \le N \le 8$
$M$	$N-1 \le M \le N(N-1)/2$
グラフ	連結かつ非二部グラフ

入出力例

入力例 1（4-サイクル）

出力例 1

定常分布: 0.250000 0.250000 0.250000 0.250000
スペクトルギャップ: 0.500000
混合時間上界: 37

入力例 2（完全グラフ K₃）

出力例 2

定常分布: 0.333333 0.333333 0.333333
スペクトルギャップ: 1.000000
混合時間上界: 8

完全グラフ $K_3$ のスペクトルギャップは 1.0（1ステップで混合）。4-サイクルは二部グラフに近く混合が遅い。

概念図: スペクトルギャップと混合時間

ヒント（段階的開示）

ヒント1: 方向性

無向グラフ上のランダムウォークの推移行列 $P$ は $P[u][v] = 1/\deg(u)$ if $(u,v) \in E$。定常分布は $\pi(v) = \deg(v) / (2M)$。固有値の計算が核心で、$N \le 8$ なので numpy で直接固有値分解できる。

ヒント2: アプローチ

推移行列 $P$ を構成: $P[v][u] = 1/\deg(v)$ if $(v,u) \in E$
対称化行列 $S = D^{1/2} P D^{-1/2}$ を構成（$D$ は次数対角行列 $\pi(v)$ でスケール）
numpy.linalg.eigvalsh(S) で固有値を取得（昇順）
2番目に大きい固有値 $\lambda_2 = \text{eigenvalues}[-2]$
混合時間上界: $\lceil \frac{1}{\gamma} \ln \frac{1}{\pi_{\min} \varepsilon} \rceil$

ヒント3: コード骨格

import numpy as np, math

# 推移行列
P = np.zeros((N, N))
for v in range(N):
    for u in adj[v]:
        P[v][u] = 1.0 / deg[v]

# 定常分布
pi = np.array([deg[v] / (2 * M) for v in range(N)])

# 対称化
D_half = np.diag(np.sqrt(pi))
D_inv_half = np.diag(1.0 / np.sqrt(pi))
S = D_half @ P @ D_inv_half

# 固有値（昇順 → 降順に並べ直す）
eigs = np.sort(np.linalg.eigvalsh(S))[::-1]
spectral_gap = 1.0 - eigs[1]

# 混合時間上界
pi_min = np.min(pi)
t_upper = math.ceil((1/spectral_gap) * math.log(1/(pi_min * 0.01)))

模範解答 (Python)

import sys
import numpy as np
import math

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    adj = [[] for _ in range(N)]
    deg = [0] * N

    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        adj[u].append(v)
        adj[v].append(u)
        deg[u] += 1
        deg[v] += 1

    # 推移行列 P
    P = np.zeros((N, N))
    for v in range(N):
        for u in adj[v]:
            P[v][u] = 1.0 / deg[v]

    # 定常分布
    pi = np.array([deg[v] / (2 * M) for v in range(N)])

    # 対称化行列 S = D^{1/2} P D^{-1/2}
    D_half = np.diag(np.sqrt(pi))
    D_inv_half = np.diag(1.0 / np.sqrt(pi))
    S = D_half @ P @ D_inv_half

    # 固有値計算（降順）
    eigenvalues = np.sort(np.linalg.eigvalsh(S))[::-1]
    lambda2 = eigenvalues[1]
    spectral_gap = 1.0 - lambda2

    # 混合時間上界
    epsilon = 0.01
    pi_min = np.min(pi)
    t_upper = math.ceil((1.0 / spectral_gap) * math.log(1.0 / (pi_min * epsilon)))

    pi_str = " ".join(f"{p:.6f}" for p in pi)
    print(f"定常分布: {pi_str}")
    print(f"スペクトルギャップ: {spectral_gap:.6f}")
    print(f"混合時間上界: {t_upper}")

solve()

Step-by-Step 解説

Step 1: 定常分布の計算

無向グラフのランダムウォークでは詳細均衡条件が成立: $\pi(u) P[u][v] = \pi(v) P[v][u]$

これを解くと $\pi(v) = \deg(v) / (2M)$（次数比例分布）。

Step 2: スペクトル理論

推移行列 $P$ の固有値 $1 = \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_N \ge -1$。

スペクトルギャップ $\gamma = 1 - \lambda_2$ は混合の速さを支配する。$\gamma$ が大きいほど速く混合する。

Step 3: TV 距離の収束

$$\|P^t(u, \cdot) - \pi\|_{\text{TV}} \le \sqrt{\frac{1}{\pi_{\min}}} \cdot (1-\gamma)^t$$

これが $\varepsilon$ 以下になる $t$ の上界: $t \le \frac{1}{\gamma} \ln \frac{1}{\pi_{\min} \varepsilon}$

Step 4: 対称化による固有値計算

$P$ は一般には非対称。$\pi$ による重み付き内積空間で対称なため、$S = D^{1/2} P D^{-1/2}$（$D = \text{diag}(\pi)$）を実対称行列として固有値分解する。

Step 5: 計算量

処理	計算量
推移行列構成	$O(N + M)$
固有値計算（numpy）	$O(N^3)$
混合時間計算	$O(1)$

よくあるミス

ミス	原因	正しい書き方
固有値の順序	numpy は昇順で返す	`[::-1]` で降順に並べ直す
λ₂ の選び方	λ₁=1 が最大固有値	降順ソート後 `eigenvalues[1]`
二部グラフで λ_N = -1	絶対スペクトルギャップが必要	`γ* = 1 - max(λ₂, -λ_N)`
ln の底の誤解	自然対数を使う	`math.log(x)` = $\ln x$

次のステップ

発展問題: 二部グラフのランダムウォーク（絶対スペクトルギャップ・遅延ウォーク）
Metropolis-Hastings アルゴリズムと MCMC への応用
Expander グラフの構成（ラマヌジャングラフ）
Conductance による混合時間下界（Cheeger の不等式）

Day 071-Q3 — ランダムウォーク混合時間（Mixing Time・スペクトルギャップ・TV距離）

問題

制約