ランダムウォークの混交時間の解析(スペクトルギャップと修正された対数ソボレフ不等式)

スペクトルギャップを用いたランダムウォークの混交時間の解析は前々から知ってたけど対数ソボレフ不等式を用いた解析は知りたいなぁと長年思っていてようやく理解できてきたのでまとめてみました.

連結かつ非二部なグラフ上の離散時間単純ランダムウォーク(隣接点に一様ランダムに遷移するランダムウォーク)の分布は必ず定常分布と呼ばれる分布に収束することが知られており, その収束のレートを測る指標として混交時間(mixing time)が知られています. 時刻$t$においてランダムウォークが頂点$v$にいる確率を$p_t(v)$と書き, $\pi\in[0,1]^V$を定常分布とします (基本的にベクトルは行ベクトルとして扱います). 通常のランダムウォーク(一様ランダムな隣接点に遷移するランダムウォーク)では$\pi(v) = \frac{\deg(v)}{2|E|}$となることが知られています.

より一般に, 頂点$u$から$v$への遷移確率$P(u,v)$を成分として持つ行列を遷移確率行列(transition matrix)と呼び, $\pi P = \pi$を満たす分布$\pi$を定常分布(stationary distribution)と呼び, 定常分布が存在するランダムウォークを可逆(reversible)であると言います. 時刻$t$におけるランダムウォークの分布ベクトル$p_t$は$p_t = p_{t-1}P$を満たすので, この等式の両辺を$t\to\infty$をとれば確かに$p_t$が収束するとしたらそれは定常分布になりそうな感じがします. 

可逆なランダムウォークは非常に重要なクラスであり, 定常分布が誘導するある計量を考えると遷移確率行列を対称行列として扱えるのが嬉しい性質で, 例えば$P$が実固有値を持つのでエクスパンダー性の議論などと相性が良いです (例えばこの記事参照). 基本的に無向グラフ上のランダムウォーク(辺重みがあっても良い)はこのクラスに属しますが, 有向グラフにすると可逆性が失われます. 本記事では主に可逆なランダムウォークを扱います.

$P(u,v)>0$のときに有向辺$(u,v)$を張って得られる有向グラフ$G$が強連結ならば$P$は既約(irreducible)であると言い, $G$の全ての有向閉路の長さのgcdが$1$であるならば非周期的(aperiodicity)であると言います (例えば二部グラフなら閉路長が偶数なので周期的). 既約ならば定常分布は一意に存在し, 非周期的ならばランダムウォークの分布は$\pi$に収束することが知られています (二部グラフ上のランダムウォークはステップ数の偶奇で分かれるので収束しない). ランダムウォークの文脈では確率$1/2$の自己ループによって長さ1の閉路を付与することで必ず非周期性を持たせられます. また, 連続時間ランダムウォークを考えると既約性だけで定常分布への収束性を保証できます. 自己ループ確率を$1/2$にすると遷移確率行列$P$が半正定値性を持ち, 例えば$\sqrt{P}$といった行列を考えることができるのが嬉しいポイントで, 例えば[Oliveira and Peres, 2019]ではこの分解を巧妙に使って到達時間(hitting time)のバウンドを証明しています.

混交時間の話に戻ります. 二つの分布$p_t,\pi\in[0,1]^V$の統計距離$d_{\mathrm{TV}}(p_t,\pi):=\frac{1}{2}\|p_t - \pi\|_1$を考え, 任意の初期分布$p_0$に対しこの値が$\epsilon$以下になるような最小の$t$を$\epsilon$-混交時間と呼び, $t_{\mathrm{mix}}(\epsilon)$で表します. すなわち
$$\begin{align*} t_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(p_t,\pi)\leq\epsilon\text{ for any }p_0\}. \end{align*}$$
なお, 初期分布$p_0$は各頂点上のDirac測度の凸結合で表せるので, 最悪の頂点からスタートした場合の混交スピードを測るという意味で最悪時の指標になっています. 例えば初期状態が定常分布だった場合は$0$ステップで混交しているので平均時みたいなものはあまり考えません.

ランダムウォークとはグラフ上を局所的に遷移する過程ですので一般に解析が難しそうに見えますが, 時刻$1$から$T$を長さ$t_{\mathrm{mix}}(\epsilon)$の区間で区切るとそれぞれで分布が$\pi$に収束するため, それぞれの区間の最後では$\pi$からランダムに頂点を選んだものとみなすことができます. 例えば正則グラフを考えると$\pi$は一様分布となるので, $100n\log n$個の区間を考えるとそれぞれで固定した頂点$v$に行き着く確率はおおよそ$\pi(v)=1/n$なので, ランダムウォークが一度も頂点$v$を訪れない確率は$(1-1/n)^{100\log n}\leq n^{-100}$となり, $v$に関するunion boundをとれば全ての頂点を訪問することがわかります. すなわち混交時間を抑えることによって, 全訪問時間(cover time)も抑えることができます. こちらの記事で, このトピックに関する簡単なサーベイをまとめています.

このように, 混交時間を抑えることによって到達時間や全訪問時間といった他のパラメータに対する上界も得ることができるため, 混交時間の解析はランダムウォークにおいては非常に重要な研究課題となっています. 現代はマルコフ連鎖モンテカルロ法(MCMC)の解析, 特にIsing modelやPotts modelに対するGlauber dynamicsなどの混交時間の解析が大きな注目を集めています. また, Langevin dynamicsによって最適化問題を表現し, その混交時間が抑えられればその最適化問題に対するアルゴリズムを与えることができます.

混交時間を抑えるためには$d_{\mathrm{TV}}(p_t,\pi)$を上から抑える必要があります. 本記事では, 

• Cauchy-Schwarzの不等式を使って$\chi^2$-ダイバージェンスで上から抑える (スペクトルギャップ)
• Pinskerの不等式を使ってKL-ダイバージェンスで上から抑える (修正された対数ソボレフ不等式)

という二つのよく知られる方法について, ダイバージェンスの観点から紹介します. スペクトルバウンドのみを理解したい場合はダイバージェンスを介さずとも良いのですが, 修正された対数ソボレフ不等式に基づく解析も理解するならば両方をダイバージェンスの縮小という観点で理解した方が見通しがよくなると思ったからです.

なお, オリジナルの対数ソボレフ不等式は元々は関数解析の分野の概念ですが, 本稿では関数解析には触れず, マルコル連鎖に焦点を絞って解説していきます.

スペクトルギャップに基づくバウンド

線形代数です. アイデアとしては, $\ell^1$ノルムを$\ell^2$ノルムで抑えて$\ell^2$ノルムをバウンドするためにスペクトルを使うというものです. $p_t-\pi = (p_{t-1} - \pi)P$であり, $p_{t-1}-\pi$は$P$の第一固有ベクトル$\mathbf{1}$と直交するので, $P$の第二固有値を見ることが肝要になります.

この議論をダイバージェンスの観点からと述べるために, $\chi^2$-ダイバージェンスと呼ばれる値を定義します. 確率変数$X$の台を$\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定めます.

定義1 ($\chi^2$-ダイバージェンス)

離散値をとり, $\mathsf{supp}(X) \subseteq \mathsf{supp}(Y)$を満たす二つの確率変数$X,Y$の$\chi^2$-ダイバージェンス$\chi^2(X||Y)$を以下で定義する:
$$\begin{align*} \chi^2(X||Y) &= \sum_{a\in \mathsf{supp}(Y)} \Pr[Y=a]\left(\frac{\Pr[X=a]}{\Pr[Y=a]}-1\right)^2 \\ &= \mathbb{E}_{a\sim Y}\left[ \left( \frac{\Pr[X=a]}{\Pr[Y=a]} - 1 \right)^2 \right]. \end{align*}$$
また, $\mathsf{supp}(X)\not\subseteq \mathsf{supp}(Y)$であった場合は$\chi^2(X||Y)=\infty$と定める.

この量は二つの分布の乖離度を測る指標として知られているのですが, 距離の公理は満たしません (そもそも$\chi^2(X||Y) = \chi^2(Y||X)$は一般に成り立たない). イメージとしては確率変数$X,Y$がどれくらい識別しにくいかを表す指標だと思ってもらえれば十分です.

今回の記事では特に扱いませんが, ダイバージェンス全般において特筆すべき性質としては

• 非負性: $\chi^2(X||Y)\geq 0$.
• データ処理不等式: 任意の決定的アルゴリズム(関数)$f$に対し, $\chi^2(f(X)||f(X))\leq \chi^2(X||Y)$.
• 凸性: 確率変数をその分布ベクトルとみなし, $\chi^2$を二つの分布から実数値を返す関数とみなしたときに$\chi^2$は凸関数.

がよく知られています. 特に凸性はJensenの不等式との相性が良いので非常によく使います. また, $\chi^2$ダイバージェンスと統計距離との間には以下の関係が成り立ちます.

補題2.

離散値をとる二つの確率変数$X,Y$に対して
$$\begin{align*} d_{\mathrm{TV}}(X,Y) \leq \frac{1}{2}\sqrt{\chi^2(X||Y)}. \end{align*}$$

証明.
$Y$の台を$\Omega$とし, $x(a)=\Pr[X=a],y(a)=\Pr[Y=a]$とします. $\mathsf{supp}(X)\not\subseteq\mathsf{supp}(X)$の場合は右辺が$\infty$となり自明なので, $\mathsf{supp}(X)\subseteq\mathsf{supp}(Y)$を仮定すると,
$$\begin{align*} d_{\mathrm{TV}}(X,Y) &= \frac{1}{2}\sum_{a\in \Omega}\left| x(a) - y(a) \right| \\ &= \frac{1}{2}\sum_{a\in\Omega} \sqrt{y(a)}\cdot \sqrt{y(a)} \left| \frac{x(a)}{y(a)} - 1 \right| \\ &\leq \frac{1}{2}\sqrt{\sum_{a\in\Omega}y(a)}\cdot \sqrt{\sum_{a\in\Omega}y(a)\left(\frac{x(a)}{y(a)} - 1 \right)^2} & & \text{the Cauchy--Schwarz inequality} \\ &= \frac{1}{2}\sqrt{\chi^2(X||Y)}. \end{align*}$$
より主張を得ます. (証明終)

ランダムウォークに話を戻すと, 補題2より$\chi^2(p_t||\pi)$の上界が得られれば混交時間のバウンドを得ることができます. 以下の補題で$\chi^2(p_t||\pi)$を$\ell^2$ノルムで抑えます.

補題3.

定常分布$\pi$を持つ可逆なランダムウォークに対して, $\pi_{\min}:=\min_{v\in V}\pi(v)$とすると,
$$\begin{align*} \chi^2(p_t||\pi) \leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2. \end{align*}$$

証明.

$$\begin{align*} \chi^2(p_t||\pi) &= \sum_{v\in V}\pi(v)\cdot \left(\frac{p_t(v)}{\pi(v)}-1\right)^2 \\ &= \sum_{v\in V}\pi(v)\cdot\left(\frac{p_t(v)^2}{\pi(v)^2} - \frac{2 p_t(v)}{\pi(v)} + 1\right) \\ &= \sum_{v\in V}\pi(v)\left(\frac{p_t(v)}{\pi(v)} - 1\right)^2 \\ &= \sum_{v\in V}\frac{1}{\pi(v)}\cdot \left( p_t(v) - \pi(v) \right)^2 \\ &\leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2. \end{align*}$$
よって主張を得る. (証明終)

最後に行列$P$のスペクトルを用いた混交時間の上界を導出します.

定理4.

遷移確率行列$P$に従い, 定常分布$\pi$を持つ可逆なランダムウォークを考える. $\lambda(P)=\max_{\|x\|_2=1,x\bot \mathbf{1}}\|Px\|$とする. $\lambda(P)<1$ならば,
$$\begin{align*} d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}}. \end{align*}$$

特に, スペクトルギャップ$\gamma:=1-\lambda(P)$に対し, $\tau_{\mathrm{mix}}(\epsilon) = O\left(\gamma^{-1}(\log(1/\epsilon) + \log(1/\pi_{\min}))\right)$.

Remark. $\lambda(P)$は$P$の非自明な第二固有値になります. すなわち, $P$の固有値を$1=\lambda_1 \geq \lambda_2\geq \dots \geq \lambda_{|V|}$としたときに$\lambda(P) = \max\{\lambda_2,|\lambda_{|V|}|\}$です. これはCourant-Fischerの定理(行列の固有値に関するmin-max定理)からわかります. エクスパンダーグラフの文脈では$\lambda(P)$が小さいグラフ (言い換えると$\gamma\approx 1$) を考えるのに対し, 例えば混交時間が多項式かどうかを気にするMCMCの文脈では$\gamma \geq 1/\mathrm{poly}(n)$かどうかを気にするので, $\gamma\to 0$の時の漸近挙動におけるオーダーを考えます.

証明. 分布$p_t$は等式$p_t = p_{t-1}P$を満たすので,
$$\begin{align*} \|p_t - \pi\|_2 = \|(p_{t-1} - \pi) P\|_2 \leq \|p_{t-1} - \pi\|_2\cdot \lambda(P) \end{align*}$$
を得る (最後の不等式ではベクトル$p_t-\pi$がall-one ベクトル$\mathbf{1}$に直交することを用いた).

補題2,3より,
$$\begin{align*} d_{\mathrm{TV}}(p_t,\pi) &\leq \frac{1}{2\sqrt{\pi_{\min}}}\cdot \|p_t - \pi\|_2 \\ &\leq \frac{1}{2\sqrt{\pi_{\min}}} \cdot \lambda(P)^t \|p_0 - \pi\|_2 \\ &\leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}} \end{align*}$$
特に, $\lambda(P)\leq 1-\gamma\leq\mathrm{e}^{-\gamma}$ならば$d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\exp(-\gamma t)}{\sqrt{2\pi_{\min}}}\leq \epsilon$とおくと混交時間のバウンドを得る. (証明終)

修正された対数ソボレフ不等式

スペクトルギャップの章は線形代数でしたが, こちらは情報理論です. Pinskerの不等式を使って統計距離をKLダイバージェンスで抑え, KLダイバージェンス$\mathrm{KL}(p_t||\pi)$がexponentialにdecayする議論を紹介します. この時の指数のrateが修正された対数ソボレフ不等式となります. このことを述べるためにまず, Dirichlet形式と連続時間マルコフ連鎖を導入します.

KLダイバージェンスについて. 二つの分布$\mu,\nu\in[0,1]^V$に対し, それらのKLダイバージェンスを, $\mathsf{supp}(\mu)\subseteq\mathsf{supp}(\nu)$のとき
$$\begin{align*} \mathrm{KL}(\mu||\nu) = \mathbb{E}_{v\sim\mu}\left[ \log \frac{\mu(v)}{\nu(v)}\right], \end{align*}$$
$\mathsf{supp}(\mu)\not\subseteq\mathsf{supp}(\nu)$のとき, $\mathrm{KL}(\mu||\nu)=\infty$と定義します. すると, Pinskerの不等式より, $d_{\mathrm{TV}}(\mu,\nu)\leq \frac{1}{2}\sqrt{\mathrm{KL}(\mu||\nu)}$が成り立ちます. 混交時間の文脈では$d_{\mathrm{TV}}(p_t,\pi)\leq \frac{1}{2}\sqrt{\mathrm{KL}(p_t || \pi)}$より, $p_t$と$\pi$のKLダイバージェンスを抑えれば混交時間も抑えることができます.

Dirichlet形式について. 行列$M\in\mathbb{R}^{V\times V}$を線形作用素$M\colon\mathbb{R}^V\to\mathbb{R}^V$ととらえます. 定常分布$\pi$を持つ遷移確率行列$P$を考えます. 空間$\mathbb{R}^V$に内積$\langle \cdot,\cdot\rangle$を
$$\begin{align*} \langle f,g\rangle = \sum_{v\in V}f(v)g(v)\pi(v) = \mathbb{E}_{v\sim\pi}[f(v)g(v)] \end{align*}$$
を定めます.

定義5.

定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$に対し, そのDirichlet形式$\mathcal{E}\colon \mathbb{R}^V\times\mathbb{R}^V\to\mathbb{R}$を
$$\begin{align*} \mathcal{E}(f,g) = \langle (I-P)f,g\rangle =\sum_{v\in V}\pi(v) (I-P)f(v) g(v) \end{align*}$$

で定める.

正規化されたラプラシアン$L=I-P$を用いると, $\mathcal{E}(f,g)=\langle Lf,g \rangle$と表すことができます. 特に$f=g$のとき,
$$\begin{align*} \mathcal{E}(f,f) &= \langle f,f\rangle - \langle Pf,f\rangle \\ &= \frac{1}{2}\mathbb{E}_{x\sim \pi,y\sim P(x,\cdot)}[f(x)^2 - 2f(x)f(y) + f(y)^2] \\ &= \frac{1}{2}\mathbb{E}_{x\sim\pi,y\sim P(x,\cdot)}[(f(x) - f(y))^2] \end{align*}$$
となり, ランダムな辺$xy$を選んだときの$f$の二乗差の平均となります. これを, $\mathcal{E}(f,f)$は関数$f$のエネルギーのようなものだと思ってください. 

連続時間マルコフ連鎖について. 可逆な遷移確率行列$P$に従う離散時間ランダムウォークを$(X_t)_{t=0,1,\dots}$とします. これを連続時間ランダムウォークに拡張します. 一般に状態空間が離散であるような連続時間のランダムウォークでは遷移時刻の間隔は平均$1$の指数分布$\mathrm{Exp}(1)$に従うものを考えます (指数分布とは$\Pr[\mathrm{Exp}(1)\geq t]=\mathrm{e}^{-t}$を満たす連続値をとる確率分布です). 以下でもう少しフォーマルに定義します. 確率変数$T_1,T_2,\dots$を$\mathrm{Exp}(1)$の独立なサンプルとし, $T_0=0$と定義します. 各$t$に対し$T_i \leq t < T_{i+1}$を満たす$i$を$i(t)$と書くことにします. 連続時間マルコフ連鎖とは, $Y_t=X_{i(t)}$で定義される連続時刻$t\in\mathbb{R}_{\geq 0}$で添字づけられた確率変数の族$(Y_t)_{t\in\mathbb{R}_{\geq 0}}$です. 連続時間ランダムウォークについても時刻$t$における分布$q_t\in[0,1]^V$を定義できます.

熱核について. $H_t = \mathrm{e}^{-t}\cdot \sum_{i=0}^\infty \frac{(tP)^i}{i!} = \mathrm{e}^{-t(I-P)}$とします. この行列はランダムウォークの分野では熱核(heat kernel)と呼ばれます (おそらく物理や微分方程式の文脈からきているのでしょうが私は専門外なので知りません). 証明は[Levin and Peres, 2017; Chapter 20]に譲りますが, $H_t(u,v)$は頂点$u$からスタートした連続時間ランダムウォークが時刻$t$において頂点$v$にいる確率を表します. 初期頂点の分布を$q_0$とすると, 時刻$t$におけるランダムウォークの分布は$q_t=q_0 H_t$と表すことができます. これを用いると連続時間ランダムウォークの$\epsilon$-混交時間$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon)$を, 離散時間の場合と同様に
$$\begin{align*} t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(q_t,\pi)\leq \epsilon \text{ for any $q_0$}\} \end{align*}$$
で定義できます.

連続時間と離散時間の比較. 連続時間と離散時間は期待値の意味では時刻$T\in\mathbb{N}$においてどちらも$T$回の遷移を行うため, その時点でのランダムウォークの分布$p_T,q_T$はほぼ同じ性質を有します. 従って混交時間についても離散時間と連続時間でほぼ同じになります. このことは遷移回数の集中性を使って簡単に説明できます. 離散時間ランダムウォークの$(\epsilon/2)$-混交時間を$t^*$とおき, $10t^*$回目の遷移が発生した瞬間の時刻$T^*:=T_{10t^*}$を考えます. 時刻$T^*$は$10t^*$個の独立な指数分布$\mathrm{Exp}(1)$の和となり, この値は期待値$10t^*$に集中するため, 確率$1-2^{-\Theta(t^*)}$で$T^*\geq t^*$が成り立ちます. 従って
$$\begin{align*} d_{\mathrm{TV}}(Y_{T^*},\pi) \leq d_{\mathrm{TV}}(X_{t^*},\pi) + \Pr[T^*<t^*] \leq \frac{\epsilon}{2} + 2^{-\Theta(t^*)}. \end{align*}$$
を得ます. 適当な定数$c>0$に対して$t^*\geq c\log(1/\epsilon)$であれば$d_{\mathrm{TV}}(Y_{T^*},\pi)\leq\epsilon$が成り立つので, $t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = O(t_{\mathrm{mix}}(\epsilon/2) + \log(1/\epsilon))$を得ます ($\log(1/\epsilon)$の項は$t^*\ll \log(1/\epsilon)$の場合をケア). 逆方向の不等式も同様に証明できます.

修正された対数ソボレフ定数について. 上記の議論から, 連続時間における$\mathrm{KL}(q_t||\pi)$を抑えることによって元の離散時間における混交時間をバウンドできます. $\mathrm{KL}(q_t||\pi)$の減少を知りたいので, KLダイバージェンスを$t$で微分してみます. 関数$\phi_t \colon v\mapsto  \frac{q_t(v)}{\pi(v)}$とすると,

$$\begin{align*} \frac{\mathrm{d}}{\mathrm{d}t} \mathrm{KL}(q_t||\pi) &= -\mathcal{E}(\phi_t,\log \phi_t) \end{align*}$$
を得ます. この式の右辺の減少スピードは, 以下で定義される修正された対数ソボレフ定数によって与えられます.

定義6.

定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考える. 関数$\phi\colon V\to\mathbb{R}_{>0}$に対し, $\mathrm{Ent}[\phi]$を
$$\begin{align*} \mathrm{Ent}[\phi] = \mathbb{E}_{v\sim\pi}\left[ \phi(v) \log\frac{\phi(v)}{\mathbb{E}_{\pi}[\phi]} \right] \end{align*}$$
とし, 修正された対数ソボレフ定数 (modified log-Sobolev constant) $\rho$を
$$\begin{align*} \rho = \inf\left\{ \frac{\mathcal{E}(\phi, \log \phi)}{\mathrm{Ent}(\phi)} \colon \phi\geq 0,\mathrm{Ent}[\phi]\neq 0 \right\} \end{align*}$$

で定める.

分布$q,\pi$のKLダイバージェンス$\mathrm{KL}(q||\pi)$は$\mathrm{KL}(q||\pi)=\mathrm{Ent}\left[\frac{q}{\pi}\right]$という関係が成り立ちます (このことからKLダイバージェンスを相対エントロピーと呼ぶのも納得ですね!). これを先ほどの微分の式に代入すると, $\rho$の定義より
$$\begin{align*} \frac{\mathrm{d}}{\mathrm{d}t} \mathrm{Ent}[\phi_t] = -\mathcal{E}(\phi_t,\log \phi_t) \leq -\rho\cdot \mathrm{Ent}[\phi_t] \end{align*}$$
を得ます. この微分方程式を解きます. $g(t) = \mathrm{Ent}[\phi_t]$とすると, 両辺を$g(t)$で割って
$$\frac{\mathrm{d}}{\mathrm{d}t}\log g(t) \leq -\rho.$$
積分定数$C_0$を使うと
$$\log g(t) \leq -\rho t + C_0.$$
従って$g(t) \leq \mathrm{e}^{-\rho t}\cdot g(0)$と表せます. 元々$g(t)=\mathrm{Ent}[\phi_t]=\mathrm{KL}(q_t||\pi)$だったので,
$$\mathrm{KL}(q_t||\pi) \leq \mathrm{e}^{-\rho t}\mathrm{KL}(q_0||\pi)$$
を得ます. 

定理7.

定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\rho$を修正された対数ソボレフ定数とする. このとき,
$$\begin{align*} t_{\mathrm{mix}}(\epsilon) = O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min}))). \end{align*}$$

で定める.

証明.
ここでは, 離散時間と連続時間のランダムウォークの比較で主張していた関係を認め, $t_{\mathrm{mix}}(\epsilon) = O(t^{\mathrm{cont}}_\mathrm{mix}(\epsilon/2))$を認めることとします. 以後では$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon/2)$を抑えるために, $q_t$を連続時間ランダムウォークの時刻$t$における分布とします. Pinskerの不等式および前段落の議論から
$$\begin{align*} d_{\mathrm{TV}}(q_t,\pi) &\leq \frac{1}{2}\sqrt{\mathrm{KL}(q_t||\pi)} \\  &\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\mathrm{KL}(q_0||\pi)} \\ &\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\log(1/\pi_{\min})}. \end{align*}$$
なお, 最後の式はKLダイバージェンスの定義から任意の分布$q$に対して$\mathrm{KL}(q||\pi)\leq \log(1/\pi_{\min})$が成り立つことを用いています. 従って, 適当な$t=O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min})))$に対して, この値は$\epsilon/2$以下になるので主張を得ます. (証明終)

スペクトルギャップと修正された対数ソボレフ定数の関係については以下の結果が知られています

定理8 [Bobkov and Tetali, 2006].

定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\gamma$をスペクトルギャップ, $\rho$を修正された対数ソボレフ定数とする. このとき,
$$\begin{align*} \rho \leq 2\gamma \end{align*}$$

が成り立つ.

したがって修正された対数ソボレフ定数の下界を得るのはスペクトルギャップ以上に難しいことが分かります. しかしながら定理4と定理7を比較すると, $1/\pi_{\min}$に対する依存が大きく異なっていることが分かります. 例えば$n$頂点のグラフ上での解析を考えると$\log n$と$\log\log n$の差しかないのでそこまで大きくはなさそうなのですが, イジングモデルなど状態空間が指数的に膨大ならばその差は非常に大きくなってくるので, 修正された対数ソボレフ不等式のテクニックが有用になってきます.

参考文献

• Markov chain and mixing time, D. Levin and Y. Peres (2017): wikipediaに記事があるほど有名な本. タイトル通り, マルコフ連鎖の混交時間に関して網羅的にまとめられている.
• Lap Chi Lauによる講義ノート: 本稿はこの講義ノートの第23回を参考にしました.
• Mathematical Aspects of Mixing Times in Markov Chains, R. Montenegro (2006): 1,2章でコンパクトに色々とまとめられている (記述は数学の人向きな気がする).
• Logarithmic Sobolev inequalities for finite Markov chains, P. Diaconis, L. Saloff-Coste (1996): とても分かりやすい論文. 連続時間マルコフ連鎖も取り扱っている.
• Sinclairによる講義ノート: 連続時間マルコフ連鎖に対するVarianceやEntropyのdecayについて, 計算途中も含めて書いてありよく解説されています.

Pinskerの不等式の簡単な証明

 Pinskerの不等式とは, KLダイバージェンスと統計距離(total variation distance)の関係を表す不等式です. 本記事ではこれを紹介し, こちらの論文やYihong Wuの講義資料のTheorem 4.5に載っている非常にトリッキーな証明を紹介します.

有限集合$\Omega$を値域とする二つの確率変数$X,Y$に対して

• 統計距離: $d_{\mathrm{TV}}(X,Y) = \frac{1}{2}\sum_{x\in \Omega}|\Pr[X=x] - \Pr[Y=y]| = \sup_{A\subseteq \Omega}|\Pr[X\in A] - \Pr[Y \in A]|$.
• KLダイバージェンス: $\mathrm{KL}(X||Y)=\sum_{a\in\mathsf{supp}(Y)}\Pr[X=a]\ln\frac{\Pr[X=a]}{\Pr[Y=a]}$.

定理 (Pinskerの不等式)

$$d_{\mathrm{TV}}(X,Y) \leq \sqrt{\frac{1}{2}\mathrm{KL}(X||Y)}.$$

証明では, KLダイバージェンスに関する以下のデータ処理不等式(data processing inequality)を認めることにします.

補題 (データ処理不等式)

$\Omega,\Omega'$を有限集合とする. 任意の関数$f\colon \Omega\to\Omega'$と$\Omega$上に値をとる任意の確率変数$X,Y$に対し
$$\mathrm{KL}(f(X),f(Y)) \leq \mathrm{KL}(X,Y).$$

KLダイバージェンス$\mathrm{KL}(X||Y)$は直感的には二つの確率変数$X,Y$の識別しにくさを表す指標であり, データ処理不等式とは二つのデータ$X,Y$をアルゴリズム$f$で処理して得られるデータ$f(X),f(Y)$を考えたとき, データ処理不等式とはデータを処理しても識別しにくさは上がらないことを意味します.

一般にデータ処理不等式は決定的アルゴリズム$f$を乱択アルゴリズムに置き換えても成り立ちます. こちらの講義資料が参考になると思います.

Pinskerの不等式の証明.

大まかな流れとしてはデータ処理不等式を用いて$01$値確率変数の場合に帰着して, あとは積分を計算します.

統計距離の定義および$\Omega$が有限であることから, ある集合$E\subseteq \Omega$が存在して$d_{\mathrm{TV}}(X,Y)=\Pr[X\in A] - \Pr[Y \in A]$が成りたちます. この集合$A$の指示関数を$f$とします. すなわち$f\colon\Omega\to\{0,1\}$は$x\in A$ならば$f(x)=1$, そうでなければ$f(x)=0$です.

データ処理不等式から$\mathrm{KL}(f(X),f(Y))\leq \mathrm{KL}(X,Y)$なので, ベルヌーイ試行$f(X),f(Y)$に対してPinskerの不等式が証明できれば証明が完了します.

では, $X,Y$がそれぞれベルヌーイ試行で$X\sim\mathrm{Ber}(p),Y\sim\mathrm{Ber}(q)$とします (すなわち$\Pr[X=1]=p,\Pr[Y=1]=q$). このとき

• $d_{\mathrm{TV}}(X,Y)=|p-q|$,
• $\mathrm{KL}(X||Y)=p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}$

です. 従って, 任意の$p,q\in[0,1]$に対して不等式
$$\begin{align} 2(p-q)^2 \leq p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} \end{align}$$
を示せば良いです. $p,q\in\{0,1\}$の場合は4通り試せば明らかに成り立つことが確認できます.

$p,q\in(0,1)$とし, $f(x) = p\log x + (1-p)\log(1-x)$とします. すると
$$\begin{align*} (\mathrm{RHS}) &= f(p) - f(q) \\ &= \int_q^p f'(x)\mathrm{d}x \\ &= \int_q^p \frac{p-x}{x(1-x)}\mathrm{d}x \\ &\geq 4\int_q^p (p-x)\mathrm{d}x \\ &= 2(p-q)^2 = (\mathrm{LHS}) \end{align*}$$
より証明を得ます. (証明終)

確率論的手法の計算論的な複雑性 (大雑把なサーベイ)

組合せ論や計算量理論ではしばし, 良い性質を持った離散構造の存在性が議論されます. 例えば

• 疎な正則エクスパンダーグラフ
• girthと彩色数が無限に大きくなるグラフ
• ランダム抽出器 (randomness extractor)
• 困難な真理値表 (hard truthtable)
• rigid matrix
• universal transversal sequence
• 大きい素数
• discrepancyの小さな部分彩色
• quasi-random graph
• Lovász local lemma
• 多変数多項式の根

といった離散構造はそれ自体が興味の対象となるだけではなく非常に幅広い応用をもち, 擬似ランダム生成器, 良い性質を持つ誤り訂正符号, 計算量下界の証明, 脱乱択の証明, 近似アルゴリズムの構成, アルゴリズムの近似率の限界(PCP定理)などに用いられます.

しかしながらこれらの存在性の証明の多くはしばし確率論的手法や鳩の巣原理などに基づいた非構成的な手法もしくは非効率的な構成に基づく証明になっています. 実際の応用では(特に擬似ランダムネスの文脈では)しばし効率的(計算量が小さい)かつ決定的(ランダムネスを使わない)な構成が求められます. これを確率論的手法の脱乱択化と呼ぶことにします. 

確率論的手法の脱乱択化は組合せ論と計算量理論が密接に関連しているとても面白いトピックですので, ここでは非常に大雑把にいくつかのトピックを紹介していきます. なお, この辺りの擬似ランダムネスに関するトピックはVadhanの本に詳しいです.

疎なエクスパンダーグラフ (ラマヌジャングラフ)

頂点数$n$の$d$-正則グラフ$G$を考えます (ただし$n\geq 2, d\geq 3$). 隣接行列$A$の固有値を大きい順に並べて$d=\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$とします. すると, 

$$\lambda_2 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1}-1}{\lfloor \mathrm{diam}(G)/2\rfloor}$$

が成り立つことが知られています(Alon-Boppanaの定理). ここで$\mathrm{diam}(G)$はグラフ$G$の直径で, Moore bound (または幅優先探索に基づく議論)により, $\mathrm{diam}(G)=\Omega(\log_{d-1} n)$が成り立ちます. 従って上記のバウンドにより, $d\geq 3$を固定し$n\to\infty$の漸近を考えると$\lambda_2 \geq 2\sqrt{d-1} - O(1/\log n)$となります.

では, このバウンドは(漸近的に)タイトなのでしょうか? 実はこの問いはランダム正則グラフを考えることで簡単に肯定的に解けます. $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだグラフを$G_{n,d}$と書くと, Friedman(2003)によると, $n\to\infty$の漸近的を考えると, 確率$1-n^{-0.1}$で$G_{n,d}$は

$$\lambda_2 \leq 2\sqrt{d-1} + O\left(\left(\frac{\log\log n}{\log n}\right)^2\right)$$

を満たすことが知られています. なので, 無限に多くの$n$について上記を満たす$n$頂点$d$正則グラフがとれるため, $n\to \infty$の漸近においてAlon-Boppanaの定理のバウンドはほぼタイトであることがわかります. ちなみにFriedman(2003)の定理の別証明を与えたという論文も知られています.

しかしながらこの証明は非構成的であるという点で応用向きではありません. スペクトルグラフ理論では, $\lambda_2 \leq 2\sqrt{d-1}$を満たすグラフをラマヌジャングラフと呼びます. ある$d\geq 3$に対して$d$-正則ラマヌジャングラフの列$(G_i)_{i=1,2,\dots}$であって, $G_i$の頂点数が$i\to\infty$で発散するようなものが陽に構成できるか, という問題を考えます. この問題はLubotzky, Phillips, Sarnak (1988)によって解決され, その後も様々な進展を見ています.

• Lubotzky, Phillips, Sarnak (1988)は$p\equiv 1 \bmod 4$を満たす全ての素数$p$に対して$(p+1)$-正則ラマヌジャングラフの列を代数的に構成する方法を与えました. この構成はいわゆるLPSラマヌジャンなどと呼ばれています.
• Morgenstern (1994)はLPSラマヌジャンを$p$がprime powerの場合に拡張しました.
• 全ての$d\geq 3$に対して$d$正則ラマヌジャングラフは存在するのでしょうか?Friedmanの定理によるとランダム正則グラフは$\lambda_2 \leq 2\sqrt{d-1}+o(1)$を満たすことが知られていますが, 厳密にはラマヌジャングラフであるということを意味しません. このように, $\lambda_2\leq 2\sqrt{d-1}+o(1)$を満たすグラフをnear-Ramanujan graphといいます.
• Marcus, Spielman, Srivastava (2015)は上の問いを解決し, 任意の$d\geq 3$に対して$d$正則二部ラマヌジャン(multi)グラフの無限列の存在性を証明しました. 彼らの証明はinterlacing polynomial methodと呼ばれる手法に基づいており, LPSラマヌジャンなどの代数的なアプローチとは根本的に異なっています.
• すぐ後にCohen(2016)はMarcus, Spielman, Srivastavaの証明を構成的に修正し, $n$頂点ラマヌジャングラフを$\mathrm{poly}(n)$時間で構成するアルゴリズムを与えました.

ランダムネス抽出器

平たく言うとランダムネス抽出器(または単に抽出器)とは, ランダムっぽい文字列を受け取ってランダムな文字列を出力する乱択アルゴリズムです. 入力で与えられる文字列の「ランダムっぽさ」はmin-entropy(以下で定義している)によって測り, 出力文字列のランダムネスは一様ランダムな文字列との統計距離(total variation distance)によって測ります. 一般にdata processing inequalityより, どのような決定的なアルゴリズムを考えても分布のエントロピーを増大させることはできないため, ランダム抽出器は乱択アルゴリズムとしています.

定義1 (min-entropy).

確率変数$X$のmin-entropy $H_\infty(X)$を以下で定める:
$$\begin{align*} H_\infty (X) = \min_{x\in\mathsf{supp}(X)}\log_2\frac{1}{\Pr[X=x]}. \end{align*}$$

通常のShannon entropyは情報量の期待値によって定義されますが, min-entropyでは情報量の最小値を考えます. すなわちmin-entropyの方がworst-caseの情報量を考えていることになります. 二つの確率変数$X,Y$の統計距離を$d_\mathrm{TV}(X,Y)$で表します.

定義2 (ランダムネス抽出器)

以下を満たす関数$\mathrm{Ext}\colon \{0,1\}^m\times\{0,1\}^d\to\{0,1\}^n$を$(k,\epsilon)$-抽出器と呼ぶ: 任意の$H_{\infty}(X)\geq k$を満たす$\{0,1\}^m$上の分布$X$と$\{0,1\}^d$上の一様分布$U_d$に対し, $d_{\mathrm{TV}}\left( \mathrm{Ext}(X,U_d) , U_n \right) \leq \epsilon$.

すなわち, 抽出器とは, $m$ビットのランダムっぽい文字列$X$と$d$ビットの一様ランダムな文字列$U_d$を受け取り, $n$ビットのランダムな文字列を返す関数のことです. 一般に$m,d$は小さい方がよく, $n$は大きい方が良いです. 入力$X$をしばし弱ランダムソースと呼びます.

ランダムな関数を考えると高確率でランダムネス抽出器になっていることが簡単に示せます. すなわち, 各$\mathrm{Ext}(x,r)$の値を$\{0,1\}^n$上の一様ランダムにとってきたとき, $\mathrm{Ext}(\cdot,\cdot)$が抽出器になっている確率は適切なパラメータの下で$1-o(1)$になることが示せます.

ランダムネス抽出器は以下のように二部グラフによって表現することによって組合せ論的な解釈を与えることができ, そこに組合せ論のテクニックが介入する余地があります.

左側の各頂点は弱ランダムソース$X$の入力に対応しており, 右側の各頂点は$\{0,1\}^n$の元に対応します. 頂点$X$からは$2^d$本の辺が出ており, 各辺には$\{0,1\}^d$の元でラベル付けされています. 頂点$X$からラベル$u\in\{0,1\}^d$の辺を辿った先にある右側の頂点が$\mathrm{Ext}(X,u)$になるようにグラフを構成します.

このように二部グラフを構成すると, 抽出器とは以下の性質を持つ二部グラフ$G=(L,R,E)$であると解釈できます:

左側の頂点集合$L$上のmin-entropy$\ge k$であるような任意の分布に従って頂点$X$を選び, そこから$1$ステップだけランダムウォークを行って得られる右側の頂点を$Y\in R$とする. このとき, $Y$は$R$上一様分布に(統計距離の意味で)近い.

特に, エクスパンダーグラフを考えるとある条件下では抽出器になることが知られています. 抽出器についてのサーベイは, 古い論文ですがNisan(1996)に詳しいです.

エクスパンダーグラフなどの組合わせ論的な道具を使った構成のほかにも, 平均時計算量の道具を使って抽出器を構成するという手法も知られています. Trevisan (2001)は非常に賢いアイデアによって, 多くの擬似ランダム生成器の構成が実は抽出器の構成とみなせるということが示しました. 擬似ランダム生成器(pseudorandom generator; PRG)とは短いランダム文字列を受け取って長いランダム文字列を出力するアルゴリズムです. ただし一般に任意のアルゴリズムはエントロピーを増大しないので, PRGの出力は擬似ランダムであるということが求められます. 詳細は以前の記事をご覧ください. 

例えばNisan-Wigderson generator $G^f_{\mathrm{NW}}\colon \{0,1\}^d\to\{0,1\}^n$は, 計算が非常に困難なBoolean関数$f\colon\{0,1\}^\ell\to\{0,1\}$を使って$d$ビットのランダム文字列$U$(いわゆる乱数シード)を$n$ビットのランダム文字列に変換しています. Trevisan (2001)の抽出器では, 弱ランダムシード$x\in\{0,1\}^m$をまず誤り訂正符号で$2^\ell$ビットの文字列に復号化し, この文字列を真理値表として持つ関数をNisan-Wigderson generatorの構成に用いることによって, 抽出器を構成しています.

解析の大雑把な概要:

もしもTrevisan's extractorの出力値が一様ランダム文字列$U_n$から統計的に離れているならば, Nisan-Wigderson generatorのreconstructionの議論により関数$\mathrm{ECC}(x)\colon\{0,1\}^\ell\to\{0,1\}$からハミング距離$1/2-\epsilon$以下の文字列は短い記述を持つ. さらに$\mathrm{ECC}(x)$に対するリスト復号のアルゴリズムを用いれば, 最終的に弱ランダムシード$x$は短い記述を持つ. これはmin-entropyの仮定に反する.

Rigid Matrix

グラフの剛性とは違う文脈で行列のrigidityと呼ばれる概念があります. 直感的には, $M$がrigidであるというのは, $M$の成分をたくさん書き換えなければ低ランクにできない, ということを意味します. 有限体上の行列$M \in \mathbb{F}_q^{n\times n}$のランクを$\mathrm{rank}(M)$と書き, 二つの行列のハミング距離(異なる成分の個数)を$d_{\mathrm{ham}}(\cdot,\cdot)$で定義します. 

定義3 (matrix rigidity)

行列$M\in\mathbb{F}_q^{n\times n}$と自然数$r\leq n$に対し, $R_M(r)$を
$$\begin{align*} R_M(r) := \min\{|S|\colon \mathrm{rank}(A+S)\leq r\} \end{align*}$$
で定める. ここで, $|S|$は行列$S\in\mathbb{F}_q^{n\times n}$の非ゼロ成分の個数である.

$(n-r)\times (n-r)$首小行列を考えれば任意の行列$M$に対し$R_M(r)\leq (n-r)^2$が簡単に分かります.

各成分を$\mathbb{F}_q$から一様ランダムに選んで得られるランダム行列$M$に対し高確率で$R_M(r)\leq (n-r)^2/\log n$であることが示せます. 実際, ランク$r$以下の行列の個数とハミング距離$\leq s$のボールのサイズを考える数え上げによる議論で示せます.

Rigid matrixの概念はValiant(1977)によって, 線形変換を計算する算術回路のサイズ下界を得るという文脈で導入されました. 大雑把にいうと, Valiant(1977)はrigidな行列に基づく線形変換は超線形サイズの算術回路を要することを証明しており, ランダム行列は高確率でrigidであることを踏まえると, ランダムな線形変換の算術回路複雑性は超線形であることを意味します. この辺りのサーベイについてはLokam(2009)をご覧ください.

線形変換の回路下界自体も重要なトピックで, 例えば高速フーリエ変換は実用的にも重要な線形変換の一つなのでその計算の下界がわかればアルゴリズムの最適性も議論できることになります.

行列のrigidityに関しては次の重要な予想が重要な未解決問題として知られています.

予想 (Valiant, 1977)

ある体$\mathbb{F}_q$, 定数$\delta,\epsilon>0$およびサイズが発散していく陽に構成できる行列の列$(M_n)_{n=1,2,\dots}$が存在して, 十分大きな任意$n\in\mathbb{N}$に対して$R_{M_n}(\epsilon n) \geq n^{1+\delta}$を満たすようにできるか?

現在は$R_M(r)=\Omega\left(\frac{n^2}{r}\log\frac{n}{r}\right)$という下界が知られています(Friedman(1993), Shokrollahi, Spielman, Stemann (1997)).

近年はrigid matrixを計算量の道具を使って(NPオラクルを使って)構成するという手法が開発されました. Alman and Chen (2019)はNPオラクルを用いてrigid matrixを決定的に構成する手法を与えました. この解析は後にrectanglar PCPというアイデアを用いてsimplifyされました (Bhangale, Harsha, Paradise, Tal (2020)). 以下ではrectanglar PCPについてものすごくざっくり説明します.

非決定性機械に対する時間階層定理より, $\mathsf{NTIME}(2^n)\setminus \mathsf{NTIME}(2^n/n)$に属する判定問題$L$が存在します. さらに$\mathsf{NTIME}(2^n)$に対してPCP定理から PCP $\pi$とPCP検証者$V^{\pi}(\cdot)$が得られます. rencangular PCPとはその名の通り, 行列として表現できるPCP $\pi$のことです. ただしPCP検証者はランダムネスを使って行$i$と列$j$を選び, $\pi[i][j]$を見ます. これを定数回繰り返し, 見た証明ビットの内容においじて受理/拒否を決定します. Bhangaleら(2020)はNTIMEで解ける問題に対してある種の性質を満たすrectangular PCPが存在するということを示しています.

PCP定理から, 入力$x$上で元の問題$L$を得くためにはPCP検証者$V^{\pi}(x)$の受理確率を十分な精度で近似できれば良いです. もしrectanglular PCP $\pi$がrigidでないならば, ある低いランク行列$L$にハミング距離の意味で非常に近いはずです. そこで, nondeterministicに$L$の分解$L=R^\top R$をguessします. 実はこの情報を使ってPCP検証者の受理確率を決定的に十分な精度で近似することができます(!!). 実際には受理確率をある行列内に含まれる$1$の個数で表現し, $\pi$の低ランク分解を用いるとその行列もまた低ランク分解できることを示し, 最後に低ランク行列内に含まれる1の個数は高速に数え上げられるという結果(Chan and Williams, 2016)を使い, 最終的に$L$を$\mathsf{NTIME}(2^n/n)$で解けることを主張します. ところがこれは時間階層定理に矛盾するので, rectangular PCP $\pi$はrigidであることが結論づけられます.

その他の話題 (クラスPPAD)

確率論的手法以外にも非構成的な存在性の証明手法はあります. 例えばゲーム理論ではナッシュ均衡の存在性はブラウアーの不動点定理でその存在性が保証されるものの実際にそれを構成しているわけではありません. このような問題を扱うため, 計算量理論ではPPADと呼ばれる計算量クラスが考えられています. ナッシュ均衡の計算やブラウアーの不動点定理における不動点の計算はPPAD完全である, というある種の困難性の結果が知られています (Daskalakis, Goldberg, Papadimitriou, 2009).

まとめ

確率論的手法は興味深い離散構造の存在性を証明できる非常に強力なツールである一方, その離散構造をどのように得るかについては明示的な情報を与えてくれません. それではそれをどのように構成するかに関しては組合せ論や計算量理論で広く研究されており, 驚くほど広い(理論的な)応用を持っています.

discrepancy: ハムサンドイッチ定理の離散化 (確率論的手法)

本記事ではdiscrepancyと呼ばれる組合せ論(特に確率論的手法の文脈)でよく知られる概念について紹介します. この概念はハムサンドイッチ定理と呼ばれる定理を離散化したような概念とみなすことができます. discrepancyはその定義自体はとても簡単である一方で奥深い結果が多く知られており, 理論計算機科学においてはビンパッキング問題に対する近似アルゴリズムの設計にも応用されています. 後の章になっていくほどテクニカルになっていきます.

1. ハムサンドイッチ定理

ハムサンドイッチ定理とは, 直感的に説明すると「3次元空間内に配置された三つの物体は、ある平面でうまくスラッシュすることによって全ての物体の体積を半分にできる」ということ主張する定理です. 私は詳しくないのですが, wikipediaによると, より一般に$d$次元空間にある$d$個の「物体」（有限測度を仮定するが必ずしも連結である必要はない）はある$d-1$次元超平面によってそれぞれの測度を半分ずつにできる、という主張をハムサンドイッチの定理と呼ぶらしいです.

名前の由来はハムとそれを挟む2枚のパンからなる三つの物体は, 一回のナイフカットによって平等に二分割できるということから来るようです. 特に二次元($d=2$)の場合はパンケーキの定理とも呼ばれるようで, 限りなく薄い2枚のパンケーキを等分割するようにカットできるということを意味します (下図)

要するにハムサンドイッチ定理とは二つの物体を組み合わせたものはうまくナイフを入れることで等分できる, ということを主張しています. この定理を数学的に厳密に述べるのは難しいのですが, ここではそれを離散化した設定を考えます.

2. discrepancy

ハイパーグラフ$H=(V,E)$を考える (各$e\in E$は$e\subseteq V$を満たす). 関数$\chi\colon V\to\{-1,1\}$と集合$S\subseteq V$に対して$\chi(S)=\sum_{i\in V}\chi(i)$とし, $\chi$のdiscrepancyを
$$\begin{align*} \mathrm{disc}_{\chi}(H) = \max_{e\in E}|\chi(e)| \end{align*}$$
で定義します. 直感的には$\chi$は頂点集合$V$を二つに分けるナイフカットを意味しており, そのdiscrepancyは$\chi$がどれだけ二等分に近いかを表す指標とみなすことができます. この設定下ではdiscrepancyが最小となる$\chi$が最も公平な分割と思うことができます. すなわち, 以下で定義される最小discrepancyを考えてみましょう:
$$\mathrm{disc}(H):=\min_{\chi\colon V\to\{-1,1\}}\mathrm{disc}_{\chi}(H).$$

以後, 関数$\chi\colon V\to\{-1,1\}$を彩色と呼びます.

例えば$G=(V,E)$が通常の意味でのグラフだとすると, $\mathrm{disc}(G)=0$であることと$G$が二部グラフが同値になります.

図: グラフ$G=(V,E)$が二部グラフならば, それぞれの部集合を$\chi^{-1}(1),\chi^{-1}(-1)$とすれば, discrepancyを$0$にできる.

3. 行列を用いたdiscrepancyの表現

ハイパーグラフ$H=(V,E)$の接続行列$A_H\in\{0,1\}^{E\times V}$を,
$$A_H(e,v) = \begin{cases} 1 & \text{ if }v\in e,\\ 0 & \text{otherwise} \end{cases}$$
で定義します. 関数$\chi\colon V\to\{-1,1\}$をベクトル$\chi\in\{-1,1\}^V$と同一視すると, 行列$A\chi \in \mathbb{Z}^{E}$は, その第$e$成分が$\sum_{v\in V}\chi(v)$になるので,
$$\mathrm{disc}(H) = \min_{\chi\in\{-1,1\}^V}\left\| A_H\chi \right\|_{\infty}$$
と表せます. ここで$\|\cdot\|_{\infty}$は$\ell^{\infty}$-ノルムで, 各成分の最大絶対値を表します.　いくつかの論文ではこの形でdiscrepancyを議論していくこともあります. 

より一般に$A\in\{0,1\}^{m\times n}$に対して$\mathrm{disc}(A)$を
$$\mathrm{disc}(A) = \min_{\chi\in\{-1,1\}^V}\left\| A\chi \right\|_{\infty}$$
と定義することができ, さらにこの定義は一般の実行列$A\in\mathbb{R}^{m\times n}$に対して考えるもできます. これを行列$A$のdiscrepancyと呼びます.

蛇足になりますが, 関連する概念としてlinear discrepancyと呼ばれるものが知られています. この値は$m\times n$実行列$A$に対して定義でき,
$$\mathrm{lindisc}(H) = \max_{w\in[-1,1]^n}\min_{x\in \{-1,1\}^n} \left\| A(x-w) \right\|_{\infty}$$
で定義されます. この概念は元々は連続変数$w\in[-1,1]^n$を持つ線形計画問題を整数変数$x\in\{1,1\}^n$に丸めた際のギャップを考えるという文脈で定義されています.

4. discrepancyの計算量

考えるハイパーグラフ$H=(V,E)$の頂点数を$n$, ハイパー辺の個数を$m$で表します.

[Charikar, Newman, Nikolov, SODA11]によって, $m=O(n)$を満たすとき, 以下の二つの入力を区別することがNP困難であることが示されています:

• $\mathrm{disc}(H)=0$
• $\mathrm{disc}(H)=\Omega(\sqrt{n})$

例えば$m=n$を満たす任意のハイパーグラフ$H$に対して$\mathrm{disc}(H)\leq 6\sqrt{n}$であることが知られている (後述するがこの結果はSpencer's six standard deviations theoremと呼ばれる重要な結果) ので, 上記の困難性は定数倍を除いてタイトです.

5. ランダム彩色による上界

彩色$\chi\colon V \to \{-1,1\}$を一様ランダムにとってきたときのdiscrepancyを考えてみましょう. すなわち, 各$v\in V$に対して$\chi(v)$を$\pm 1$から一様ランダムに選びます. このとき, Hoeffding boundとunion boundを組み合わせることによって簡単に以下を示すことができます.

命題1 (ランダム彩色のdiscrepancy)

ハイパーグラフ$H=(V,E)$に対し, $n=|V|,m=|E|$とする. 一様ランダムに選ばれた彩色$\chi\colon V \to \{-1,1\}$を考えると, 以下が成り立つ:
$$\begin{align*} \Pr\left[\mathrm{disc}_\chi(H) \leq \sqrt{2n\log(3m)} \right] \geq \frac{1}{3}. \end{align*}$$

特に, $\mathrm{disc}(H)\leq \sqrt{2n\log(3m)}$である.

命題1の証明のために以下のHoeffding boundを用います:

補題1 (Hoeffding bound)

$X_1,\dots,X_\ell$を$\pm 1$に値をとる独立一様ランダムな確率変数とし, $X=\sum_{i\in[\ell]} X_i$とする. このとき, 任意の$t\geq 0$に対して

$$\begin{align*} \Pr\left[ |X| \geq t \right] \leq 2\exp\left(-\frac{t^2}{2\ell}\right). \end{align*}$$

[命題1の証明].

固定した辺$e\in E$に対して, 補題1より
$$\begin{align*} \Pr\left[\chi(e) > \sqrt{2n\log(3m)} \right] \leq \Pr\left[\chi(e) > \sqrt{2|e|\log(3m)}\right] \leq \frac{2}{3m}. \end{align*}$$
従って, $e\in E$に関するunion boundにより
$$\begin{align*} \Pr\left[\mathrm{disc}_{\chi}(H) > \sqrt{2n\log(3m)}\right] \leq \Pr\left[\exists e\in E,\,\chi(e)>\sqrt{2n\log(3m)}\right] \leq \frac{2}{3}. \end{align*}$$

すなわち, ランダムに選ばれた$\chi$のdiscrepancyは確率$1/3$で$\mathrm{disc}_\chi(H)\leq \sqrt{2n\log(3m)}$を満たす. (証明終)

証明から分かるように, $\log(3m)$の定数$3$は任意の定数$c>1$に対し$\log(cm)$に置き換えることが可能です.

6. Spencer's six standard deviation theorem

$m=O(n)$のとき, 5章では確率論的手法を使って$\mathrm{disc}(H)=O(\sqrt{n\log n})$が得られますが, 実はさらに改善して$\mathrm{disc}(H)=O(\sqrt{n})$を示すことができます[Spencer, 1985].

定理1 [Spencer's six standard deviation theorem]

$|V|=|E|$を満たす任意のハイパーグラフ$H=(V,E)$は$\mathrm{disc}(H)\leq 6\sqrt{|V|}$を満たす.

この結果は, その係数からSpencer's six standard deviation theoremと呼ばれます. 実はこの証明は$\chi$の存在性を鳩の巣原理から導出しており構成的ではないのですが, 後に構成論的な証明が与えられ[Bansal, 2010], 現在ではより簡単な証明も知られています[Lovett, Meka, 2015]. ここではhidden constantについてはoptimizeせず, 単に存在性($\mathrm{disc}(H)=O(\sqrt{n})$)を証明します.

証明では部分彩色 (partial coloring) という概念が鍵になります. 部分彩色とは関数$\chi\colon V\to\{-1,0,1\}$です. 部分彩色に対しても$\chi(e) = \sum_{v\in e} \chi(v)$とし, $\chi$のdiscrepancyを
$$\mathrm{disc}_{\chi}(H) = \max_{e\in E}\left| \chi(e) \right|$$
で定義することができます.

明らかに, 全ての頂点に$0$を割り当てる部分彩色を考えるとdiscrepancyが$0$となり最小値をとります. 従って, 部分彩色$\chi$であって

• 多くの頂点(少なくとも$0.01|V|$個以上の頂点) に$\pm 1$の値を割り当てる, かつ
• $\mathrm{disc}_{\chi}(H)$が小さい

ような部分彩色が望ましい部分彩色であるといえます. 以下の補題はそのような部分彩色の存在性を保証します.

補題2 (部分彩色補題)

ある定数$C_0$が存在して, $m\leq \frac{n}{10}$を満たす任意のハイパーグラフ$H=(V,E)$に対し, 以下の二つを同時に満たすある部分彩色$\chi\colon V\to \{-1,0,1\}$が存在する:

• $\chi(v)\in \{-1,1\}$を満たす頂点$v$が少なくとも$\frac{n}{10}$個ある.
• $\mathrm{disc}_\chi(H)\leq C_0\sqrt{n}$

補題2の証明が最もテクニカルなパートになるので次の章で紹介するとして, ここでは補題2$\Rightarrow$定理1を示します.

まずは証明のアウトラインを述べます. 元々は$m=n$という仮定でしたが, ダミー頂点を追加すれば相対的に$|E|\leq \frac{|V|}{10}$になるようにできるので, 与えられたハイパーグラフは$m=\frac{n}{10}$を満たすと仮定して良いです (ダミー頂点追加後の彩色に対するdiscrepancyは$O(\sqrt{O(n)})=O(\sqrt{n})$になるのでdiscrepancyのバウンドも大丈夫). これに対して補題2を適用して得られる部分彩色に対し, $0$が割り当てられた頂点部分集合からなる誘導部分ハイパーグラフに対して再帰に彩色を得て先ほどの部分彩色とマージするという方針になります. 一回の反復で塗られていない頂点の個数は$0.9$倍になるので, 全体のdiscrepancyは高々$\sum_{t=0}^\infty C_0 \sqrt{0.9^t n}=O(\sqrt{n})$になるという議論です.

[補題2$\Rightarrow$定理1]. 

以下の手順に従ってハイパーグラフの列$(H_t)_{t=0,1,\dots}$と各$H_t$上の部分彩色$\chi_t$を定義します:

1. $H_0 = (V_0,E_0) = H$とする.
2. For $t=1,2,\dots,$ do:
1. 部分彩色$\chi_t$を, $H_{t-1}$に対する補題2で存在性が保証される部分彩色とする.
2. $V_t=\{v\in V_{t-1}\colon \chi_t(v)= 0\}$, $E_t = \{e\cap V_t\colon e\in E_{t-1}$とし, $H_t=(V_t,E_t)$で定める.
3. $E_t=\emptyset$になったら終了する.

補題2の条件より, $|V_t| \leq 0.9|V_{t-1}|$ なので, 十分大きな$T=O(\log n)$に対して$E_T=\emptyset$となるため, 上の手順は有限ステップで終了します. このとき, $\chi_1,\dots,\chi_T$に対して彩色$\chi$を, $\chi(v) = \chi_i(v)$で定めます. ここで$i\in[T]$は$\chi_i(v)\neq 0$を満たす唯一の$i$とします. 

上で定義した$\chi$のdiscrepancyを評価します. 各辺$e\in E$に対して
$$\begin{align*} |\chi(e)| \leq \left|\sum_{v\in e}\chi(v)\right| \leq \sum_{t=1}^T \left| \sum_{e\in E_{t-1}\setminus E_t } \chi(e) \right| \leq \sum_{t=1}^T C_0\sqrt{0.9^t n} = O(\sqrt{n}) \end{align*}$$

を得ます.

7. 部分彩色補題の証明(スケッチ)

6章で紹介した補題2(部分彩色補題)を証明します. この証明はその鳩の巣原理からその存在性が保証されるため構成的ではありません. 部分彩色補題 (ひいては定理1) を満たす彩色$\chi$の構成については長年未解決だったのですが, Bansal (2010) によるブレイクスルーにより解決され, 現在ではLovett and Meka (2015) による(ランダムネスを用いる)簡単な構成法も知られています. 厳密な証明をしようとすると瑣末な部分のケアで煩雑になってしまい大変なので, できる限り本質を捉えつつ厳密性を捨てて, 分かった気になれる証明のスケッチを紹介します.

定義1 (エントロピー)

離散集合上に値をとる確率変数$X$に対し, そのエントロピー$\mathrm{H}(X)$を
$$\begin{align*} \mathrm{H}(X) = \mathbb{E}_{x\sim X}\left[\log\frac{1}{\Pr[X=x]}\right] = \sum_{x\in \mathsf{supp}(X)} \Pr[X=x]\log\frac{1}{\Pr[X=x]} \end{align*}$$
で定義します. ここで対数の底はlogとし, $\mathsf{supp}(X)$は$X$の台(support)と呼ばれる集合で, $\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定義されます.

なお, 連続値をとり密度関数が存在するような確率変数に対しても$\Pr[X=x]$を密度関数$f(x)$に置き換えて微分エントロピーという値が定義されます. すなわち, 密度関数$f$を持つ実数値をとる確率変数$X$の微分エントロピー$\mathrm{H}(X)$は

$$\begin{align*} \mathrm{H}(X)=\int_\mathcal{\mathsf{supp}(X)} f(x) \log\frac{1}{f(x)}\mathrm{d}x \end{align*}$$
で定義されます. エントロピーに関しては上記の定義と以下の性質のみを使います.

補題3 (エントロピーの劣加法性).

ランダムなベクトル$X=(X_1,\dots,X_n)$に対し, そのエントロピー$\mathrm{H}(X)$は
$$\mathrm{H}(X) \leq \sum_{i\in[n]}\mathrm{H}(X_i)$$ を満たす.

さて, 部分彩色補題の証明に戻ります. ランダムな彩色$\chi\colon V \to \{-1,1\}$を考え, パラメータ$w>0$と頂点部分集合$S$に対し, 確率変数
$$Z_S = \left\lfloor \frac{\chi(S)}{w\sqrt{|S|}}\right\rfloor$$
のエントロピー$\mathrm{H}(Z_S)$を考えます. 実際にはもう少し複雑な式を使って評価するのですが, ここでは以下の主張を認めて証明を進めていきます.

主張1.

パラメータ$w$を適切にとり, 部分集合$S$の要素数が十分大きいとき, $\mathrm{H}(Z_S)\leq 0.9$とできる.

なお, この主張は本当に成り立つかは分かりません(えっ...). 実際の証明ではもう少し複雑な式を使ってエントロピーを評価します. ここではその証明のアイデアを簡潔に説明するためにあえて「成り立つか分からない主張」を仮定します. ただ, この主張には一応の理由づけはできるので, 以下ではその妥当性を説明します (実際の研究の場面ではこのようなことは私はよくやります).

[主張1の妥当性の説明]

• 定義よりエントロピーはスケーリングで不変なので, $\mathrm{H}(Z_S)=\mathrm{H}(w\cdot Z_S) \approx \mathrm{H}(\chi(S)/\sqrt{|S|})$ (本当は切り下げの有無でのエントロピーの誤差の評価が必要).
  
• $\chi(S)$は平均$0$, 分散$1$の独立な確率変数$(\chi(v))_{v\in S}$の和なので, $|S|$が十分大きければ中心極限定理より$\chi(S)/\sqrt{|S|}$は漸近的に標準正規分布$\mathcal{N}(0,1)$で近似できる.
• 従って, $\mathrm{H}(\chi(S)/\sqrt{|S|}) \approx \mathrm{H}(\mathcal{N}(0,1)) = (1+\log(2\pi))/2 \approx 1.419$. なお, 正規分布の微分エントロピーについての事実を使っている(例えばこの記事参照).  本当はBerry--Esseenの不等式などを使ってエントロピーの誤差評価が必要.
• これらをまとめると, $\mathrm{H}(Z_S)\approx 1.419$なので, パラメータ$w$を適切にとり, 集合サイズ$|S|$が十分大きいならば, 近似精度を$0.001$未満にできて$\mathrm{H}(Z_S)\leq 1.42$にできる.

ハイパーグラフ$H$に対し, ランダムベクトル$Z=Z(\chi)=(Z_e)_{e\in E}$を考えます. ここで, 全ての辺$e$の要素数は十分大きいと仮定します (そうでない場合はサイズが小さいのでdiscrepancyに寄与しないため無視できる). するとエントロピーの劣加法性(補題3)と主張1より
$$\begin{align*} \mathrm{H}(Z) \leq \sum_{e\in E}\mathrm{H}(Z_e) \leq 1.42m \leq 0.2n \end{align*}$$
を得ます. エントロピーの定義より, averaging argumentにより, あるベクトル$z^*\in\mathbb{Z}^E$が存在して
$$\begin{align*} \log\frac{1}{\Pr[Z=z^*]} \leq 0.2n \end{align*}$$
となります. これを整理すると$\Pr[Z=z^*] \geq \mathrm{e}^{0.2n} > 2^{0.2n}$を得ます. ここでの確率は一様ランダムな彩色を考えていたので, 少なくとも$2^{0.8n}$個の$\chi\in \{-1,1\}^V$が存在して$Z(\chi)=z^*$を満たすことになります. そのような$\chi$の集合を$B\subseteq\{-1,1\}^V$とします. ここで, $|B|\geq 2^{0.8n}$より, ある二つのベクトル$\chi_1,\chi_2\in B$が存在して, $\|\chi_1-\chi_2\|_1 \geq 0.1n$となります (後述). そのような$\chi_1,\chi_2$に対して$\chi = \frac{1}{2}(\chi_1 - \chi_2)$と定義します. するとこの$\chi$は部分彩色補題の要件を満たしています:

• $\chi_1,\chi_2$の選び方より, $\chi(v)=0\iff \chi_1(v)=\chi_2(v)$となる$v\in V$は高々$0.9n$個あります.
• $\chi_1,\chi_2\in B$より, $Z(\chi_1)=Z(\chi_2)$です. すなわち, 任意の$e\in E$に対して
  $$\left\lfloor\frac{\chi_1(e)}{w\sqrt{|e|}} \right\rfloor = \left\lfloor \frac{\chi_2(e)}{w\sqrt{|e|}} \right\rfloor$$
  が成り立つので, $|\chi(e)| = |\chi_1(e) - \chi_2(e)| \leq w\sqrt{|e|} \leq w\sqrt{n}$です. これは$\mathrm{disc}_\chi(H)\leq w\sqrt{n}$を意味します.

以上より, 部分彩色補題(補題3)の証明が完了し, 同時に定理1の証明も完了しました. (証明終)

以上の証明では次の事実を用いています:

主張2.

集合$B\subseteq \{-1,1\}^n$が$|B|\geq 2^{0.8n}$を満たすならば, ある二つのベクトル$x,y\in B$が存在して$\|x - y \|_1\geq 0.1n$となる.

証明(概要). 一般に, 任意のベクトル$x\in \{-1,1\}^n$に対し$x$からハミング距離$\alpha n$以内にある点の個数は高々$\sum_{i=0}^{\alpha n} \binom{n}{i} \leq 2^{\mathrm{H}(\alpha)n}$を満たします (ここで$\mathrm{H}(\alpha):=\alpha\log_2\frac{1}{\alpha} + (1-\alpha)\log_2\frac{1}{1-\alpha}$はbinary entropy function). $\alpha=0.1$を代入すると, この個数は$2^{\mathrm{H}(0.1)n}< 2^{0.469n}<|B|$なので, 主張を満たす2点をとることができます. (証明終)

Further Reading

• 驚くべきことにスタンフォード大学では過去にdiscrepancyについての講義(おそらく集中講義?)があり, いくつかの講義ノートが公開されています.
• The Probabilistic Method (Alon and Spencer)の12章ではランダムな$\chi$の解析とsix-deviation theoremとBeck-Fiala theoremとHadamard行列に基づく下界の紹介がされています.
• ビンパッキング問題の近似アルゴリズムに対する応用については "A Logarithmic Additive Integrality Gap for Bin Packing" (Hoberg and Rothvoss, SODA2017) 参照. なお, 箇条書き一つ目のリンクにあるLecture 10のノートには少し弱い近似精度を持つビンパッキングの近似アルゴリズムについての解説があります.

hardcore補題を使ったXOR補題の証明

 平均時計算量においてはXOR補題と呼ばれる定理がよく知られています. この分野では脱乱択化や暗号プリミティブの構成への応用を念頭に, 非常に難しい関数をどのように構成するかが研究されています.

関数$f\colon\{0,1\}^n\to\{0,1\}$に対する回路$C$の成功確率$p_{C,f}$を

$$\begin{align*} p_{C,f}:= \Pr_{x\sim\{0,1\}^n}[C(x)=f(x)] \end{align*}$$

と定めます. ここで, 有限集合$S$に対して$x\sim S$で$x$は$S$上一様分布に選ばれたことを意味します. 任意のサイズ$s$の回路$C\colon\{0,1\}^n\to\{0,1\}$に対してその成功確率が高々$1-\delta$であるとき, 関数$f$はサイズ$s$に対して$\delta$-困難であるといいます. 定数回路(常に$0$を出力, または常に$1$を出力する回路)を使えば成功確率$\geq1/2$を達成するので, 基本的に$\delta\leq1/2$の範囲で考えます. 特に, 小さい$\epsilon>0$に対して$(1/2-\epsilon)$-困難な関数は正解できる入力の個数が下界に近いので非常に困難な関数であるとみなすことができます. XOR補題とは, XORをとることによって関数の困難性を増幅できることを主張する定理です.

定理1 (XOR補題)

関数$f$, パラメータ$k\in\mathbb{N}$に対して関数$f^{\oplus k}\colon \{0,1\}^{nk}\to\{0,1\}$を

$$\begin{align*} f^{\oplus k}(x_1,\dots,x_k)=f(x_1)\oplus \dots \oplus f(x_k) \end{align*}$$
で定める. $f$がサイズ$O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$に対して$\delta$-困難かつ$k\geq \frac{C\log(1/\epsilon)}{\delta^2}$ならば,$f^{\oplus k}$はサイズ$s$に対して$(1/2-\epsilon)$-困難である. ここで$C$は十分大きな定数である.

一般に, 「関数$f$がサイズ$s$に対して$\delta$-困難ならば関数$g$はサイズ$s'$に対して$(1/2-\epsilon)$-困難である」という形の定理を困難性の増幅(hardness amplification)といい, XOR補題はその最も基本的な定理の一つです. 原則として$s'\approx s$であることが望まれます.

本記事ではこの定理を証明します. そのためにhardcore lemmaを使います. 回路$C$の問題$f$に対する入力集合$H\subseteq\{0,1\}^n$上での成功確率を$p_{C,f,H}:=\Pr_{x\sim H}[C(x)=f(x)]$と定義します. ここでは[Impagliazzo (1995)]のパラメータを改善した[Barak, Hardt, Kale (2009)]による以下のhardcore lemmaを用いることにします:

補題1. (hardcore lemma)

サイズ$s$に対して$\delta$-困難な関数を任意にとってきて$f$とすると, ある$|H|\geq\delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$であって, 任意のサイズ$O\left(\frac{\epsilon^2}{\log(1/\delta)}s\right)$の回路$C$に対して$p_{C,f,H}\leq 1/2-\epsilon$を満たすものが存在する.

補題1によって存在性が保証されている集合$H$を$f$のハードコア集合と呼びます. hardcore lemmaの対偶をとると以下の主張を得ます:

補題1'. (hardcore lemma)

任意の$|H|\geq \delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$に対してあるサイズ$s$の回路$C_H$が存在して$\Pr_{x\sim H}[C_H(x) = f(x)]\geq 1/2+\epsilon$を満たすならば, あるサイズ$O\left(\frac{\log(1/\delta)}{\epsilon^2} \cdot s\right)$の回路$C'$が存在して, $\Pr_{x\sim\{0,1\}^n}[C'(x)=f(x)]\geq 1-\delta$.

関数$f\colon \{0,1\}^n\to\{0,1\}$が$\delta$-困難であるならば, 一様ランダムな$x\sim \{0,1\}^n$に対して確率変数$f(s)$は1ビットのベルヌーイ試行$\mathrm{Ber}(\delta)$と区別がつかないということを意味します. ここでベルヌーイ試行$\mathrm{Ber}(\theta)$とは確率$\theta$で$1$, 確率$1-\theta$で$0$を出力する確率変数です. 従って, ハードコア補題は, 直感的には,

$f$が$\delta$-困難ならば, サイズ$|H|\geq \delta$を満たすある入力集合$H\subseteq \{0,1\}^n$が存在して, 一様ランダムな$x\sim H$に対して$f(x)$は1ビットの一様分布$\mathrm{Ber}(1/2)$と(計算論的に)区別がつかない

ということを主張しています. では, 定理1を証明しましょう. まずはアウトラインを述べます. 独立に$x_1,\dots,x_k\sim\{0,1\}^n$をランダムにとって$f^{\oplus k}(x_1,\dots,x_k)$を考えてみましょう. まず, $x_1,\dots,x_k$のうち少なくとも一つが$H$に入っている確率は下から$1-(1-\delta)^k\approx 1-\mathrm{e}^{-\delta k}\approx 1-\epsilon$で抑えられます. 非常に高確率で発生するこの事象で条件つけ, 例えば$x_i\in H$であるとします. このとき, $x_i$の分布は$H$上で一様ランダムです. したがって$f(x_i)$は$\mathrm{Ber}(1/2)$と区別がつきません. ここで確率変数$f(x_1),\dots,f(x_k)$は$x_1,\dots,x_k$が独立なのでこれらもまた独立であり, $f(x_i)$が$\mathrm{Ber}(1/2)$と区別できないので, XORをとった$f^{\oplus k}(x_1,\dots,x_k)$もまた$\mathrm{Ber}(1/2)$と区別できないです (一様ランダムなビットと他のビットのXORをとったらそれもまた一様ランダムなビットになる). すなわち, $f^{\oplus k}(x_1,\dots,x_k)$が$\mathrm{Ber}(1/2)$と区別できず, これは$f^{\oplus k}(x_1,\dots,x_k)$が$(1/2-\epsilon)$-困難であることを意味します (事象の発生確率が$1-\epsilon$なので$\epsilon$程度のロスが発生している).

以上の流れを対偶を使って証明します. 以下, 二つの確率変数$X,Y$に対し, $X\not\approx_c Y$で$X$と$Y$をcomputationalに識別できる (i.e., ある小さい回路$C$が存在して$|\Pr[C(X)=1]-\Pr[C(Y)=1]|$がnon-negligibleに大きい) ことを表すとします. また, $X\approx_s Y$によって, $X$と$Y$はstatisticalの意味で近い (つまりtotal variation distanceが小さい)ことを表すとします. 最後に, $U_k$によって一様ランダムな$k$ビットの文字列を表すとします. 例えば$(U_{nk},f^{\oplus k}(U_{nk}))$と書いた場合は, $x\sim U_{nk}$を一様ランダムにサンプリングして$x=(x_1,\dots,x_k)$に$k$分割して$(x,f^{\oplus k}(x_1,\dots,x_k))$の分布のことを表すものとします (なので分布のランダムネスは$x$の選び方のみです).

1. $f^{\oplus k}(x_1,\dots,x_k)$を成功確率$(1/2+\epsilon)$で計算するサイズ$s$の回路が存在するので, $(U_{nk},f^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},U_1)$.
2. ランダム関数$f_H(x)$を, $x\in H$ならば$f_H(x)=U_1$, $x\not\in H$ならば$f_H(x)=f(x)$と定義する. 情報論的なバウンドによって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s (U_{nk},U_1)$.
3. 1と2の議論によって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s U_{nk+1}\not \approx_c (U_{nk},f^{\oplus k}(U_{nk}))$が得られる. 特に, $(U_{nk},f_H^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},f^{\oplus k}(U_{nk}))$.
4. $(U_{nk},f^k(U_{nk})) \not\approx_c (U_{nk},f^k_H(U_{nk}))$を得る (k-wise XORを識別できるので). ここで, $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$と定義していて, $(U_{nk},f^k(U_{nk}))$とは$(x_1,\dots,x_k)\sim U_{nk}$に対して$(x_1,\dots,x_k,f(x_1),\dots,f(x_k))$によって与えられるものです.
5. ハイブリッド議論(hybrid argument)によって$(x,f(x))\not\approx_c (x,f_H(x))$となる (ただし分布のランダムネスは$x\sim U_n$).
6. $H$が密(i.e., $|H|\geq \delta 2^n$)であることを使うと, $H$上一様ランダムな$x\sim H$に対して$(x,f(x))\not\approx_c (x,f_H(x))=(x,U_1)$が示せる.
7. Yao's next-bit predictorより, $x\sim H$に対して$f(x)$を成功確率$1/2+\epsilon$で計算できる.
8. ハードコア補題より$\{0,1\}^n$上で$f$を成功確率$1-\delta$で計算できる. これは元の$f$の条件に矛盾する.

それでは, 定理1の証明をします. 以下の議論では上記のステップ1〜8を補足しつつフォーマルに確認していくだけなので, 上記のアイデアで満足な人は読まなくても構いません.

関数$f$をサイズ$s$に対して$\delta$-困難な関数とし, $H\subseteq\{0,1\}^n$をハードコア集合とします. 回路$D$のサイズを$\mathrm{size}(D)$と表すことにします.

ステップ1. $f^{\oplus k}(U_{nk})$を成功確率$1/2+\epsilon$で計算する回路を$C$とします. 与えられた$(x,b)\in \{0,1\}^{nk+1}$に対して$C(x)\oplus b \oplus 1$を出力する回路を$C_1$とすると,

$$\begin{align*} &\Pr_{x\sim U_{nk}}[C_1(x,f^{\oplus k}(x))=1] = \Pr_x[C(x)=f^{\oplus k}(x)] \geq \frac{1}{2}+\epsilon \\ &\Pr_{x\sim U_{nk},b\sim U_1}[C_1(x,b)=1] = \frac{1}{2} \end{align*}$$

より, 二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$を$\epsilon$のアドバンテージで識別できます. $C_1$のサイズは, $\mathrm{size}(C_1) = \mathrm{size}(C)+O(1)$を満たします.

ステップ2. 関数$f_H\colon\{0,1\}^n\to\{0,1\}$を

$$\begin{align*}f_H(x) = \begin{cases}U_1 & \text{ if }x\in H,\\f(x) & \text{otherwise}\end{cases}\end{align*}$$

とします. ここで$U_1$は各$x\in H$ごとにランダムに生成されるランダムビットです. 厳密には$\mathcal{F}_H$を, 任意の$x\not\in H$に対して$g(x)=f(x)$を満たす関数$g$の集合, すなわち

$$\begin{align*} \mathcal{F}_H = \{g\colon \forall x\not\in H, g(x)=f(x)\} \end{align*}$$

と定義したときに$f_H$は$\mathcal{F}_H$から一様ランダムに選ばれたランダム関数として定義されます. 独立に$k$個の入力$x_1,\dots,x_k\sim U_n$と$k$個のランダム関数$f_H$をサンプリングして, $f_H(x_i)$のXORをとったときの値$f_H^{\oplus k}(x_1,\dots,x_k)$の分布を考えましょう (ランダムネスは$x_i$と$f_H$の選び方についてとる). どれか一つの$i$でも$f_H(x_i)=U_1$であったならば, そのXORの値もまた$U_1$となります. 従って, 統計距離は$\prod_{i=1}^k \Pr[x_i\not\in H] \leq (1-\delta)^k$となり (ここで$|H|\geq\delta\cdot 2^n$を使っている), 適当な$k=O(\log(1/\epsilon)/\delta)$に対して統計距離は高々$0.1\epsilon$となります.

ステップ3. 統計距離の性質から, ステップ1で構成された回路$C_1$は二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$をアドバンテージ$0.9\epsilon$で識別します.

ステップ4. 二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$を識別する回路$C_2$を以下のように構成します: 入力$(x_1,\dots,x_k,b_1,\dots,b_k)$に対し, $C_1(x_1,\dots,x_k,b_1\oplus\dots\oplus b_k)$を出力する. この回路$C_2$は, $C_1$の識別性により確かに二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$をアドバンテージ$0.9\epsilon$で識別します. 回路$C_2$のサイズは高々$\mathrm{size}(C_1)+O(k)$です.

ステップ5. ステップ4で構成された回路$C_2$は二つの分布
$$\begin{align*} &D_0 := (x_1,\dots,x_k,f(x_1),\dots,f(x_k)),\\ &D_k := (x_1,\dots,x_k,f_H(x_1),\dots,f_H(x_k)) \end{align*}$$
をアドバンテージ$0.9\epsilon$で識別します. これら二つの分布を滑らかに補間するような分布列$D_1,\dots,D_{k-1}$を
$$\begin{align*} D_i := (x_1,\dots,x_k,f(x_1),\dots,f(x_{i-1}),f_H(x_i),\dots,f_H(x_k)) \end{align*}$$
とします(これをハイブリッド分布とよぶ). $i=0,k$の場合でもそれぞれ$D_0,D_k$になっていることが分かります. $p_i = \Pr[C_2(D_i)=1]$とすると, $p_0 - p_k = \sum_{i\in[k]}(p_{i-1} - p_{i}) \geq 0.9\epsilon$なので, ある$i\in[k]$が存在して$p_{i-1} - p_i \geq 0.9\epsilon/k$を満たします. 

さらに, ある$z_1,\dots,z_{i-1},z_{i+1},\dots,z_k \in \{0,1\}^{n}$および$c_1,\dots,c_{i-1},c_{i+1},\dots,c_k\in \{0,1\}$が存在して,

$$\begin{align*} \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f(x))=1] - \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f_H(x))]\geq \frac{0.9\epsilon}{k} \end{align*}$$
が成り立ちます. ここで, $\mathbf{v}(i,x,b)$は
$$\begin{align*} \mathbf{v}(i,x,b) = (z_1,\dots,z_{i-1},x,z_{i+1},\dots,z_k,c_1,\dots,c_{i-1},b,c_{i+1},\dots,c_k) \end{align*}$$
で定義される文字列である (インデックス$i$と各$z_j$と$c_j$は入力$x$に依存しない値なので, これらの情報を回路にあらかじめ組み込むことによって, 与えられた$x,b$に対し$\mathbf{v}(i,x,b)$はサイズ$O(kn)$の回路で計算できる). 従って, 関数$(x,b)\mapsto C'(\mathbf{v}(i,x,b))$はサイズ$s+O(nk)$程度で計算でき, さらに上記の式より二つの分布$(x,f(x))$と$(x,f_H(x))$をアドバンテージ$0.9\epsilon/k$で識別する. この回路を$C_3$とします.

ステップ6. 全ての$x\not\in H$に対して定義より$f(x) = f_H(x)$となるので, $(U_n,f(U_n))$と$(U_n,f_H(U_n))$が区別できるということは, ステップ5の回路$C_3$を使って$x\sim H$に対して$(x,f(x))$と$(x,f_H(x))$が区別できるということになります. 実際,
$$\begin{align*} \frac{0.9\epsilon}{k} &\leq \Pr[C_3(U_n,f(U_n))=1] - \Pr[C_3(U_n,f_H(U_n))=1] \\ &= 2^{-n}\sum_{x\in\{0,1\}^n} (C_3(x,f(x)) - \mathbb{E}_{f_H}[C_3(x,f_H(x))]) \\ &= 2^{-n}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &\leq \frac{1}{|H|}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &= \Pr_{x\sim H}[C_3(x,f(x))=1] - \Pr_{x\sim H,U_1}[C_3(x,U_1)=1] \end{align*}$$

なので$C_3$は, $x\sim H$に対して$(x,f(x))$と$(x,U_1)$を識別します.

ステップ7. 以前の記事で紹介した計算量的な識別不可能性の概念を思い起こします. この概念は関数の困難性と等価であることがYao's next-bit predictorからわかります.

定義1.

$\{0,1\}^n$上の二つの確率変数$X,Y$は, あるサイズ$s$の回路$C$が存在して
$$\begin{align*} \Pr[C(X)=1]-\Pr[C(Y)=1]\geq \epsilon \end{align*}$$

を満たすとき, サイズ$s$で$\epsilon$-識別可能であるといい, $C$を識別回路という. 逆に, そのような回路$C$が存在しない場合はサイズ$s$で$\epsilon$-識別不可能であるという.

補題2 (Yao's next-bit predictor; 以前の記事の定理の対偶の言い換え).

関数$f\colon \{0,1\}^n\to\{0,1\}$に対し, 二つの分布$(U_n,f(U_n))$と$(U_n,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して

$$\begin{align*} \Pr_{x\sim U_n}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon. \end{align*}$$

上記の補題において, $U_n$を$H$上の一様分布に置き換えることによって以下の補題を得ます.

補題3.

関数$f\colon \{0,1\}^n\to\{0,1\}$と任意の集合$H\subseteq\{0,1\}^n$を考える. $x\sim H$に対して二つの分布$(x,f(x))$と$(x,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して
$$\begin{align*} \Pr_{x\sim H}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon. \end{align*}$$

補題3の証明は省略しますが, $\ell = \lceil \log_2 |H|\rceil$に対して, $H$上の一様分布を$U_\ell$とみなすことができることから分かると思います.

ステップ6までの議論より補題3の仮定を満たす回路が存在するので, あるサイズ$\mathrm{size}(C_3)+O(1) = s+O(nk)$の回路$C_4$が存在して
$$\begin{align*} \Pr_{x\sim H}[C_4(x) = f(x)] \geq \frac{1}{2} + \frac{0.9\epsilon}{k} \end{align*}$$
が成り立ちます.

ステップ8. ハードコア補題(補題1)の対偶を適用する. 任意の$|H|\geq \delta 2^n$を満たす$H$に対してある回路$C_4$が存在して$p_{C_4,f,H}\geq \frac{1}{2} + \frac{0.9\epsilon}{k}$となるので, 補題1'より, $f$を成功確率$1-\delta$で計算する回路$C_5$であって, サイズ
$$\mathrm{size}(C_5) = O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$$
となるものが存在する. これは定理1の$f$の困難性の仮定に矛盾します.

緩和の順番を工夫してBellman-Ford法は改善できる

久々にブログのタイトル通りにアルゴリズム(Bellman-Ford法)に関する記事を書きます. それなりに丁寧に書いたつもりなので, Bellman-Ford法を知らない人でも楽しめると思います. プログラムの実行時間はアルゴリズムに加えて実装や実行環境に依存するため, アルゴリズムの計算量では原則として定数倍を無視して議論するわけですが, この記事で紹介する手法はそのような実行環境に依存せず, 本質的に演算回数を定数倍減らしているので競プロ的な(ナイーブな手法を改善していくという)面白さがあると思います.

概要. Bellman-Ford法は$O(mn)$時間で単一始点最短経路問題を解きます. このアルゴリズムは「各辺に対して緩和と呼ばれる操作を行う」ことを$n-1$回繰り返すというアルゴリズムです. 実は緩和を行う辺の順番を工夫することによって反復回数を$n-1$から$n/2$に改善することが可能です [Yen, 1970]. 本稿ではこの単純かつ素晴らしいアイデアを紹介します.

1. Bellman-Ford法とその正当性の証明

フォーマルに書くとBellman-Ford法は以下で定まるアルゴリズムです. まず距離を格納するリスト$\mathrm{dist}[u]$を,

$$\begin{align*} \mathrm{dist}[u] = \begin{cases} 0 & \text{if $s=u$},\\ \infty & \text{otherwise}. \end{cases} \end{align*}$$
で初期化し, その後, 「各辺$e\in E$に対して $\mathrm{relax}(e)$ を行う」を$n-1$回繰り返します. ここで$\mathrm{relax}(e)$とは, 有向辺$e=(u,v)$に対し, その重みを$w_e$とすると,
$$\mathrm{dist}[v] \leftarrow \min\{\mathrm{dist}[v], \mathrm{dist}[u]+w_e\}$$
で更新する操作である.

Bellman-Ford法では見る辺の順番に関しては特に言及されておらず, どのような順番で辺を見たとしても高々$n-1$回の反復で(負閉路がない場合の)単一始点最短経路が正しく解けることが保証されます. その正当性として以下の「よくある」証明が知られています.

「よくある」Bellman-Ford法の証明.

各$i=0,\dots,n-1$に対して, $i$回目の反復が終了した時点での配列$\mathrm{dist}$を$\mathrm{dist}_i$と書くことにします. ただし$\mathrm{dist}_0$は初期化によって得られる$\mathrm{dist}$で, $\mathrm{dist}_{n-1}$はBellman-Ford法の出力です. 次の主張を$i$に関する帰納法で示します: 各$u\in V$に対して$\mathrm{dist}_i[u] = su$-経路のうち辺数が高々$i$であるもののうち最短の長さである. 実際, $i=0$の場合はこの主張は正しいです. また, $i\leq j$まで主張が正しいと仮定すると, $j+1$回目の反復について考えると, 漸化式
$$\begin{align*} \mathrm{dist}_{j+1}[u] = \min_{v \in N^-(u) \cup \{u\}}\{ \mathrm{dist}_j[v] + w_{vu} \} \end{align*}$$
を得ます (ただし$N^-(u)=\{v\in V\colon (v,u)\in E\}$は頂点$u$に入っていく辺のもう一方の端点からなる集合で, $w_{uu}=0$と定義している). 帰納法の仮定より各$\mathrm{dist}_j[v]$は辺数$j$本以下の中での最短$sv$経路の長さなので, $\mathrm{dist}_{j+1}[u]$は所望のものになっており, 主張が証明されました. さて, 元のグラフに負閉路がない場合は$s$から辿り着ける全ての頂点$u$に対して最短$su$経路は辺数が高々$n-1$なので, アルゴリズムの出力$\mathrm{dist}_{n-1}[u]$は確かに頂点$s$を始点とした最短経路長を格納した配列になっています. (証明終)

上記の帰納法に基づく証明により, Bellman-Ford法は始点$s$から近い順に最短経路長を決めていることがわかります. イメージとしては, $s$を根とした最短経路木(最短経路に属する辺からなる木. 最短経路が複数あるときは任意に一つだけ選んでその辺を木に追加していって構成できる) に対して, 根から順番に(幅優先探索の要領で)最短経路長が決定していくことがわかります. 特に, 各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていきます. 木の辺数は$n-1$であることからもBellman-Ford法の反復回数が高々$n-1$であることが納得できると思います.

2. Yen(1970)の方法

Bellman-Ford法の解析では 「各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていく」ことを示したわけですが, それでは「各反復では最短経路木に含まれる辺のうち, 少なくとも2本が最短経路として同定されていく」ならば, 反復回数は高々$\lceil n/2\rceil$となります. Yen(1970)による定数倍改善はこの観察に基づきます. Yen(1970)は, 以下のアルゴリズムによって定まる反復に基づくBellman-Ford法の反復回数は高々$\lceil n/2 \rceil$回であることを主張します:

1. 頂点に適当に番号づけて, $V=\{v_1,\dots,v_n\}$, 始点を$s=v_1$とする. 各辺$e=(v_i,v_j)$に対し, $i<j$ならば$e$を上昇辺, $i>j$ならば$e$を下降辺と呼ぶ.

2. 頂点を$v_1,\dots,v_n$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての上昇辺に対して緩和を実行する.

3. 頂点を$v_n,\dots,v_1$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての下降辺に対して緩和を実行する.

以下にこのアルゴリズムの正当性の証明を載せます.

Yen(1970)の手法の正当性の証明

頂点$u\in V\setminus \{s\}$を固定し, $su$-最短経路を任意に一つ選び, その経路を頂点列とみなし$P=(w_0,w_1,\dots,w_\ell)$とします (ただし$s=w_0,u=w_\ell$). このパス$P$は上昇辺からなる「増加部分」と下降辺からなる「減少部分」の交互列に分解できます. 例えば$P$が

$v_1 \to v_3 \to v_5 \to v_4 \to v_2 \to v_7 \to v_6$

という頂点列の場合, 

• $v_1 \to v_3 \to v_5$
• $v_5 \to v_4 \to v_2$
• $v_2 \to v_7$
• $v_7 \to v_6$
  

のように, 番号に関する極大な増加列と極大な減少列が交互に現れるように分解できます (始点を$s=v_1$にしているので最初は必ず増加列です). この分解を$P=(U_1,D_1,U_2,D_2)$と表すことにします. ここで$U_1=(v_1,v_3,v_5), U_2 = (v_2,v_7)$は増加列, $D_1=(v_5,v_4,v_2), D_2 = (v_7,v_6)$は減少列です. 一般に増加部分を$U_1,\dots,U_p$, 減少部分を$D_1,\dots,D_q$とし, 連続する上昇列と下降列を繋げて得られる$(U_i,D_i)$という$P$の部分列を山折りと呼ぶことにします. 各山降りは少なくとも2本の辺を含むため, 最短経路$P$が含む山折りの個数は高々$\lceil n/2\rceil$です. Yen(1970)のステップ2では小さい頂点から順番に上昇列を緩和していっているため, $P$の上昇列を順番に同定していきます. 同様にステップ3では$P$の下降列を順番に同定していきます. ステップ2-3を交互に繰り返すため, 一回の反復では一つの山折りに対応する部分列$(U_i,D_i)$の最短経路が順番で同定されていきます. 従って, 山折りの個数, すなわち高々$\lceil n/2\rceil$回の反復で最短経路が求まります. (証明終)

3. その後の進展

[Bannister and Eppstein, 2012]によって, 乱択を用いた反復回数のさらなる定数倍改善$n/3$が得られています (著者のブログ記事). このアルゴリズムも非常に単純なテクニックに基づいたものになっています. 具体的には, Yen(1970)では任意に選ばれた頂点順番に基づいて上昇辺と下降辺が定義されていましたが, これをランダムな順番にすると期待値の意味で反復回数が$n/3$になる, ということを示しています. ここではラフな証明を載せておきます. Yen(1970)の上記の解析により, 任意の最短経路$P$を同定するのに必要な反復回数はそれに含まれる山折りの個数で抑えることができます. 従って, 頂点番号がランダムに振られたときの$P$に含まれる山折りの個数の期待値について考察します. 最短経路の頂点列を$(v_0,\dots,v_\ell)$とし, 各$v_i$はランダムに振られた番号を表すとすると, 山折りの個数の期待値はおおよそ$\ell \cdot \sum_{i=1}^n (1/n) \cdot (i/n)^2 \approx \ell \cdot \int_0^1 x^2 \mathrm{d}x \leq n/3$となります (この式における$(1/n)\cdot (i/n)^2$というのは, パス中の頂点を一つ固定したときにその頂点の番号が$i$になり, かつ両隣の頂点の番号がどちらも$i$以下となる確率を意味します). ざっと論文を目を通したくらいなので詳しいことはわかりませんが, おそらく山折りの個数の集中性を示して(集中不等式の文脈ですでに知られている結果がほぼブラックボックスに使えるっぽい), 終着頂点に関するunion boundをとることによって証明がなされています.

なお, 執筆時(2023年12月時点)では負辺ありの単一始点最短経路問題に対するアルゴリズムのオーダーの改善も知られており, 特にFOCSのbest paperをとったブレイクスルーの結果[Bernstein, Nanongkai, Wulff-Nilsen, 2022]によって, 負辺を含むグラフの単一始点最短経路問題が$O(m\log^8(n)\log W)$時間で解けることが示されました. ここで$W>0$は, $w_e\geq -x$を満たす最小の$x$に対して$W=\max\{2,x\}$で定義される値です. ($2$とのmaxをとっているのはlogをとったときに$0$にならないようにするため.) さらに翌年, [Bringman, Cassis, Fischer, 2023]によって$O(m\log^2(n)\log(nW)\log\log n)$時間アルゴリズムが発表されました.

少し余談になりますが, 同じ会議(FOCS2023)では最短経路に関する別の論文[Duan, Mao, Shu, Yin, FOCS23]もあって, この論文ではcomparison-addition modelと呼ばれるモデルにおいて負辺なしの最短経路問題をダイクストラ法より高速に$O(m\cdot \sqrt{\log n\cdot \log\log n})$時間で解く乱択アルゴリズムを提案しています. comparison-addition modelとは, Bellman-Ford法の緩和操作のように, 数値の加算と比較のみが定数時間で行えるような環境を考えるモデルです. 彼らのアルゴリズムのアイデアは根幹の部分ではダイクストラ法と似たようなことをやっています. 通常のダイクストラ法では全ての頂点をヒープに入れて近い順に頂点を取り出してその周りの辺を緩和するというものでしたが, Duanらのアルゴリズムではパラメータ$k=\sqrt{\log n / \log\log n}$に対して, $n/k$個の頂点をランダムに選び, それらをまずFibnacci heapに入れ, 順番に頂点$u$を取り出して, $u$に"近い"頂点を緩和していくようなことをしています (arXiv版のSection 3参照).

4. 感想

講義のために最小費用流や最短経路問題の色々なアルゴリズムを勉強してみたのですが, マトロイドや離散凸といった一般的な枠組みを追求していく面白さとは違った面白さがあり, シンプルで賢いアルゴリズムは勉強していてとても楽しいですね.

5. 参考文献

• "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Jin Y. Yen, Quarterly of Applied Mathematics, 27(4), pp.526--530, 1970.
• "Randomized Speedup of the Bellman–Ford Algorithm", Michael J. Bannister and David Eppstein, Proceedings of ANALCO, 2012.
• "Negative-Weight Single-Source Shortest Paths in Near-linear Time", Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen, Proceedings of FOCS, 2022.
• "Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!", Karl Bringmann, Alejandro Cassis, Nick Fischer, Proceedings of FOCS, 2023.