combinatorial designの構成

集合族$\mathcal{S}$であって任意の相異なる二つの元の共通部分が小さいものを平均計算量理論の文脈でcombinatorial designと呼ぶことがあり, 擬似乱数生成器の構成などにおいて非常に重要な役割を果たします. 具体的には, 台集合$E$上の集合族$\mathcal{S}$であって以下を満たすものを($E$上の)$(d,n)$-designと呼びます.

• 各$S\in\mathcal{S}$に対して$|S|=n$.
• 各$S\neq T\in \mathcal{S}$に対して$|S\cap T|\leq d$.

例1. グリッド

台集合$E=[m]^2$上の集合$S_i=\{(x,y)\in E\colon x=i\text{ or }y=i\}$を考えると $\mathcal{S}=\{S_i\}_{i\in[m]}$は$(2,2m-1)$-designになります.

本記事では$(d,n)$-designの応用先には特に触れず, [NW94]で与えられた以下の$(d,n)$-designを紹介します. Nisan--Wigderson Generatorを知っていても具体的なcombinatorial designを知らない人向けの備忘録です.

定理 (Lemma 2.4 of [NW94]).

各素べき$n$と$d\in\mathbb{N}$に対して, $|E|=n^2$かつ$|\mathcal{S}|=n^{d+1}$を満たす台集合$E$上の$(d,n)$-designが存在する.

証明.

有限体$\mathbb{F}_n$を考え, $E=\mathbb{F}_n^2$とします. $\mathcal{P}_{\leq d}$を$\mathbb{F}_n$上の次数高々$d$の多項式全体の集合とし, 各$p\in\mathcal{P}_{\leq d}$に対して$S_p=\{(x,p(x))\colon x\in \mathbb{F}_n\}$とし, $\mathcal{S}=\{S_p\}_{p\in\mathcal{P}_{\leq d}}$とします. 明らかに$|\mathcal{S}|=|\mathcal{P}_{\leq d}|=n^{d+1}$です.

上で与えた$\mathcal{S}$が確かに$(d,n)$-designになっていることを確認します. まず, 各$S\in\mathcal{S}$は$n$個の点の集合なので確かに$|S|=n$を満たします. 次に$|S_p\cap S_q|>d$を満たす相異なる二つの多項式$p,q\in\mathcal{P}_{\leq d}$が存在すると仮定します. このとき, $p(x)=q(x)$を満たす$x\in\mathbb{F}_n$が$d+1$個以上存在することになりますが, このとき多項式$p-q$は次数高々$d$で$d+1$個の点で$0$になるので, 恒等的に$0$となり, $p\neq q$と矛盾します.

(証明終)

参考文献

[NW94] N. Nisan and A. Wigderson, Hardness vs Randomness, JCCS, 1994.

ランダム行列の行列積 part 3

Part1, Part2に引き続き, 有限体$\mathbb{F}_q$上の二つの独立な一様ランダムな行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題は最悪計算量 (任意の与えられた$A,B$に対して$AB$を計算する時の計算量) とほぼ一致することを見ました. 具体的にはPart1,2で以下の二つの定理を証明しました.

定理1(BLR93).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理2(folklore; explicitly in [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たし, かつ$q>\lceil6/\alpha\rceil$ならば, ある$O(T(n)/\alpha^2)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

これら二つの定理はそれぞれ

• 定理1では$\mathcal{A}$の成功確率は$0.75$以上でなければ意味をなさない.
• 定理2では$\mathbb{F}_q$のサイズが大きくなければならない.

という課題を抱えていました. この二つの課題は[Asadi, Golonev, Gur, Shinkar, STOC22]によって次のように解決されました:

定理3([Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たすならば, ある$q^{O(\log^4(1/\alpha)}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理3の帰着$\mathcal{A}'$の計算時間は$q$に依存しますが, $q$が大きい場合は定理2を使えば良いです.

本記事では定理3の計算時間を少し遅くした以下の定理を証明します.

定理4(weark ver of [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たすならば, ある$q^{O(\alpha^{-2})}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理4の証明のために二つの道具を用意します. 一つは前回の記事で証明した確率的Bogolyubov--Ruzsaの補題です.

補題1 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

もう一つの道具はランダム低ランク行列です. パラメータ$k$を受け取り以下のアルゴリズムによって生成された行列を$R_k$とします.

• $v_1,\dots,v_k\sim\mathbb{F}_q^n$を一様ランダムに生成する.
• $v_{k+1},\dots,v_n$をそれぞれ$v_1,\dots,v_k$のランダムな線形結合とする (結合の各係数が$\mathbb{F}_q$上一様ランダム).
• $v_1,\dots,v_n$を並べた行列を$R_k$として出力する.

この時, 以下が成り立ちます (証明は省略).

補題2.

$\dim(V)\geq N-k$を満たす任意の線形部分空間$V$と任意の行列$C\in\mathbb{F}_q^N$に対し, $\Pr[C+R_k\in V]\geq \frac{1}{2q^k}$.

定理4の証明.

$N=n^2$とし, 行列全体の集合$\mathbb{F}_q^{n\times n}=\mathbb{F}_q^N$を線形空間とみなします. $S=\{(A,B)\colon \mathcal{A}(A,B)=AB\}$を$\mathcal{A}$が成功する入力の集合とします. 行列$A\in\mathbb{F}_q^N$を固定し,

$$D_A = \{B\in\mathbb{F}_q^N\colon (A,B)\in S\}$$

とします. $A\sim\mathbb{F}_q^N$が一様ランダムに与えられたときの$|D_A|$の期待値は　$\geq\alpha|\mathbb{F}_q^N|$です.

最後に, $D=\{A\in\mathbb{F}_q^N\colon |D_A|\geq (\alpha/2)|\mathbb{F}_q^N|\}$とします. 直感的には, $A\in D$は$\mathcal{A}$にとって(平均的に)解きやすいインスタンスであるといえます. $A\sim\mathbb{F}_q^N$の時の確率変数$|D_A|/|\mathbb{F}_q^N|$に対して逆マルコフの不等式(Part2, 補題2参照)を適用すると$\Pr_{A\sim\mathbb{F}_q^N}[|D_A|\geq (\alpha/2)|\mathbb{F}_q^N|]\geq \alpha/2$が成り立ちます. すなわち$|D|\geq (\alpha/2)|\mathbb{F}_q^N|$となります.

ここまでで二つの集合$D,D_A$を定義しました. ここからは二段階に分けた帰着を考えます.

1. $A\in D$を満たす任意の入力$(A,B)$に対して$AB$を計算するアルゴリズム$\mathcal{A}_1$を構成する.
2. $\mathcal{A}_1$をサブルーチンとして呼び出すことで$A\not D$に対しても$AB$を計算できるアルゴリズム$\mathcal{A}_2$を構成する.

ケース1: $A\in D$.

この時は$|D_A|\geq \alpha/2$となります. $D_A$に対して補題1を適用すると, $\dim(V)\geq N-4\alpha^{-2}$を満たすある線形部分空間$V$が存在して

$$\forall x\in V,\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D_A]\geq \alpha^5/32$$

です (ここでは$a+b-c-d=x \iff d=a+b-c-x$に注意). $a,b,c,d\in D_A$ならば$\mathcal{A}$は行列積$Aa,Ab,Ac,Ad$を正しく計算できることになるので, $Ad=Aa+Ab-Ac-Ax$に注意すると$Ax$を計算することができます.

さらに, 与えられた$B$に対して補題2より

$$\Pr[B+R_k\in V]\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=B+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}_1$は$B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S_1,S_2,S_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(B+R_k)$とする.
• $AR_k$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}(A,S_1)+\mathcal{A}(A,S_2)-\mathcal{A}(A,S_3)-\mathcal{A}(A,S_4)-AR_k$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

各繰り返しは$O(T(n))$時間で計算可能です. 最初のステップで$B+R_k\in V$かつ$S_1,S_2,S_3,S_4\in D_A$を満たせば最後のステップで$C=AB$となります. これが起こる確率は上記の解析より$q^{-O(\alpha^{-2})}$です. 従って全体の繰り返し回数を$q^{O(\alpha^{-2})}$でとれば成功確率を$0.99$にでき, この時の$\mathcal{A}_1$の計算時間は$q^{O(\alpha^{-2})}T(n)$です.

ケース2: $A\not\in D$.

ケース2もケース1とほぼ同じです. ここでは$\mathcal{A}_1$をサブルーチンとして使います. $|D|\geq \alpha/2$より, $D$に対して補題1を適用すると, $\dim(V')\geq N-4\alpha^{-2}$を満たすある線形部分空間$V'$が存在して

$$\forall x\in V',\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D]\geq \alpha^5/32$$

です. $a,b,c,d\in D$ならば$\mathcal{A}_1$は任意の$B$に対して行列積$aB,bB,cB,dB$を正しく計算できることになるので, $dB=aB+bB-cB-xB$に注意すると$xB$を計算することができます.

さらに, 与えられた$A$に対して補題2より

$$\Pr[A+R_k\in V']\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=A+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}$は$A,B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S'_1,S'_2,S'_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(A+R_k)$とする.
• $R_kB$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}_1(S_1,B)+\mathcal{A}_1(S_2,B)-\mathcal{A}_1(S_3,B)-\mathcal{A}(S_4,B)-R_kB$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

ケース1と同じ解析により, アルゴリズム$\mathcal{A}$の計算時間は$q^{O(\alpha^{-2})}\cdot T(n)$になります. (証明終).

Bogolyubov-Ruzsaの補題 (加法的組合せ論)

加法的組合せ論(additive combinatorics)で知られるBogolyubov--Ruzsaの補題と呼ばれる結果を紹介します. この補題は様々なバリエーションが知られていますが, ここでは以下のタイプの結果を証明します. 

加法的組合せ論は極値グラフ理論(ラムゼー理論)と密接に関連しており, 密な部分集合が持つ構造的特徴を解析します. 例えばRothの定理は$\mathbb{N}$上の任意の密な部分集合$S\subseteq\mathbb{N}$は長さ3の非自明な等差数列 (つまり交差が非ゼロ) を含むことを主張します. ここでは$S$が「密な部分集合」, 「長さ3の等差数列を含む」が「構造的特徴」に対応します. なお, Rothの定理よりも強い主張として, 任意の密な自然数の部分集合は無限に長い等差数列を含むという事実が知られています (Szemerédiの定理).

$\mathbb{F}_q$を素体として$n\in\mathbb{N}$に対して線形空間$\mathbb{F}_q^n$を考えます. $D\subseteq\mathbb{F}_q^n$が密である時にそれはどのような性質を持つかを考えます. 幾つか記号を導入します.

• $D+D = \{a+a'\colon a,a'\in D\}$.
• $-D = \{-a\colon a\in D\}$.
• $k\in\mathbb{N}$に対して$kD=\{a_1+\dots+a_k\colon a_1,\dots,a_k\in D\}$.
• $D-D = D+(-D) = \{a-a'\colon a,a'\in D\}$.

例えば$D$が部分空間ならば$D+D,D-D$などは全て$D$と一致します. イメージとしては$D$と$D-D$などの"ギャップ"を考えることによって$D$の"部分空間っぽさ"を捉えることができます. Bogolyubov--Ruzsaの補題は, $D$が密ならば$2D-2D$は大きな線形部分空間を含むことを主張します.

定理1 (Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって

任意の$x\in V$に対してある$a,b,c,d\in D$が存在して$x=a+b-c-d$

を満たすものが存在する (即ち$V\subseteq 2D-2D$).

本記事ではより強いことを主張する以下の結果を証明します.

定理2 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

証明.

フーリエ解析の記法を用いる (定義の記事参照). $D\subseteq \mathbb{F}_q^n$に対し, $\mathbb{1}_D$を指示関数 ($x\in D$なら$\mathbb{1}_D(x)=1$, そうでなければ$\mathbb{1}_D(x)=0$) とする. この関数のフーリエ変換$\widehat{\mathbb{1}}_D$を考え, パラメータ$\epsilon>0$に対して

$$R_\epsilon = \{v\in\mathbb{F}_q^n\colon |\widehat{\mathbb{1}}_D(v)|\geq\epsilon\}$$

とする. Parsevalの等式より

$$\delta = \|\mathbb{1}_D\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^2 \geq \epsilon^2|R_\epsilon|$$

なので$|R_\epsilon|\leq\delta\epsilon^{-2}$である. $V$を$R$の張る部分空間の直交補空間, すなわち

$$V=\{v\in \mathbb{F}_q^n\colon \forall r\in R_{\epsilon},\langle v,r\rangle=0\}$$

とする. 明らかに$\dim V \geq n-|R_\epsilon|\geq n-\delta\epsilon^{-2}$である.

よって, $\epsilon=\delta^{1.5}$のときに上で定義された$V$が所望の性質を満たすことを言えば良い. 関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$を

$$f=\mathbb{1}_D\ast \mathbb{1}_D \ast \mathbb{1}_{-D}\ast \mathbb{1}_{-D}$$

とする. 畳み込みの定義より

$$f(x) = \Pr_{a,b,c,d\sim\mathbb{F}_q^n}[a,b\in D,c,d\in -D|a+b+c+d=x]$$

であるので, 任意の$x\in V$に対して$|f(x)|\geq \delta^5$を示せばよい.

$f(x)$をフーリエ級数展開する. 畳み込みの性質から$\widehat{f}(v)=\widehat{\mathbb{1}}_D(v)^2\widehat{\mathbb{1}}_{-D}(v)^2$だが,

$$\widehat{\mathbb{1}}_{-D}(v) = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{-D}(x) \overline{\omega^{\langle v,x\rangle}}\right] = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{D}(x) \omega^{-\langle v,-x\rangle}\right] = \overline{\widehat{\mathbb{1}}_{D}(v)}$$

より, $\widehat{f}(v)=|\widehat{\mathbb{1}}_D|^4$となるので$f(x)=\sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^4\chi_v(x)$である. この和を

1. $v=0$
2. $v\in R_\epsilon$
3. それ以外 ($v\not\in R_\epsilon\cup\{0\}$)

に分けて考える.

• $v=0$の時は$\chi_0\equiv 1$より$\widehat{\mathbb{1}}_D(0)\chi_0(x)=\langle \mathbb{1}_D,1\rangle = \delta$である.
• $v\in R_\epsilon$の時は, $V$の定義より$\langle x,v\rangle = 0$なので$\widehat{\mathbb{1}}_D(v)\chi_v(x)=\widehat{\mathbb{1}}_D(v)$である.

それ以外の場合は, $v\not\in R_\epsilon$より$|\widehat{\mathbb{1}}_D|\leq \epsilon$より

$$\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^4 \leq \epsilon^2\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^2 \leq \epsilon^2\left(\delta -  |\widehat{\mathbb{1}}_D(0)|^2\right)=\epsilon^2(\delta-\delta^2).$$

以上の三つのケース組み合わせると, $\epsilon=\delta^{1.5}$のとき,

$$|f(x)|\geq \delta + \sum_{v\in R_\epsilon}|\widehat{\mathbb{1}}_D(v)|^4 - \epsilon^2(\delta-\delta^2) \geq \delta^5$$

となり主張を得る. (証明終).

ランダム行列の行列積 part 2

前回の記事に引き続き, 独立一様ランダムな二つの行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題を考えます.

前回は[Blum, Luby, Rubinfeld, 1993]による以下の定理を証明しました. ここで有限集合$S$に対して$x\sim S$と書いた時は$x$は$S$上一様ランダムに選ばれた元と解釈してください.

定理1(BLR93).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

この定理は$\mathcal{A}$の成功確率が$0.75$より小さい (即ち$\epsilon\geq 1/4$) と$\mathcal{A}'$の成功確率が$0$になってしまうため, $\mathcal{A}$は75%より多くのインスタンスに対して正解しなければなりませんでした. 本記事では$\mathbb{F}_q$が大きいという仮定の下でこの課題を乗り越え, 「$\mathcal{A}$の成功確率が1%でも$\mathcal{A}'$は高確率で成功する」ような$\mathcal{A}'$を構成していきます.

定理2(folklore; explicitly in [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たし, かつ$q>\lceil6/\alpha\rceil$ならば, ある$O(T(n)/\alpha^2)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理2の証明は[Asadi, Golonev, Gur, Shinkar, STOC22]によって明示的に与えられていますが, その証明はパーマネントのランダム自己帰着の文脈などでよく知られる手法に基づいています (なおAGGSの本質的な貢献は$\mathbb{F}_q$が小さい場合に帰着を与えたという点にあります). AGGSが与えた帰着では$\mathcal{A}'$の計算時間は$O(T(n)/\alpha^4)$になっていますがここで紹介する帰着はそれより少しだけ高速で$O(T(n)/\alpha^2)$になっています.

1. 準備

定理2の証明のために幾つかの準備をします.

補題1 (Freivald's algorithm).

$A,B,C\in\mathbb{F}_q^{n\times n}$が与えられたとき, $AB=C$かどうかを判定する問題を考える. この問題を成功確率$1-\epsilon$で解く$O(n^2\log(1/\epsilon))$時間アルゴリズムが存在する.

証明.

$v\sim\mathbb{F}_q^n$を一様ランダムなベクトルとして, $ABv=Cv$かどうかをチェックします. 行列とベクトルの積なのでこれは$O(n^2)$時間でチェックできます. もし$ABv\neq Cv$ならば明らかに$AB\neq C$なのでNOと出力し, そうでなければ改めて$v\sim\mathbb{F}_q^{n\times n}$をサンプルしなおして同じことを繰り返し, 一度もNOにならなかったらYESを出力します.

このアルゴリズムは$AB=C$ならば必ずYESを出力する一方で, $AB\neq C$ならば

$$\Pr[ABv= Cv]=\Pr[(AB-C)v= 0]=\Pr[v\in \mathrm{ker}(AB-C)] \leq 1/q$$

なので各試行では確率$1-1/q\geq 1/2$でNOを出力します. 最後の不等式は$AB-C\neq 0$より$\mathrm{ker}(AB-C)$の次元は$n-1$以下であり, $|\mathrm{ker}(AB-C)|\leq |\mathbb{F}_q^n|/q$であることを使いました. (証明終).

補題2 (逆マルコフの不等式).

$X$を$[0,1]$上に値をとる確率変数とし, $\mu=\mathrm{E}[X]\in(0,1)$とすると,

$\Pr[X\geq \mu/2] \geq \mu/2.$

証明.

非負の確率変数$1-X$にマルコフの不等式を適用すると, 任意の$c\in(0,1)$に対して

$$\Pr[X\leq c] = \Pr[1-X\geq 1-c] \leq \frac{1-\mu}{1-c} = 1-\frac{\mu-c}{1-c} \leq 1-(\mu-c).$$

これに$c=\mu/2$を代入すればよい. (証明終)

系3.

$X_1,\dots,X_m$を$\{0,1\}$上に値をとる(独立とは限らない)確率変数で全ての$i\in[m]$に対し$\mathbb{E}[X_i]=\alpha$を満たすとし, $X=\sum_{i=1}^m X_i$とすると, $\Pr[X\geq m\mu/2]\geq \mu/2$.

2. 定理2の証明

与えられた行列を$A,B$とします. $R,S\sim\mathbb{F}_q^{n\times n}$を二つの独立な一様ランダムな行列とし, $f,g\colon\mathbb{F}_q\to\mathbb{F}_q^{n\times n}$を $f(t)=A+tR, g(t)=B+tS$とします. $f(t)$と$g(t)$は各成分が$\mathbb{F}_q[t]$に属する一次多項式行列とみなすことができます. このとき積$f(t)g(t)$の各成分は二次多項式になっているので, 相異なる三つの点$1\leq t_1<t_2<t_3\leq q-1$に対して$f(t_i)g(t_i)$ ($i=1,2,3$)が計算できれば多項式補間によって$f(t)g(t)$の各成分を得ることができます. そうすれば定数項$f(0)g(0)=AB$が計算できます.

各$t=1,\dots,m$ ($m\leq q-1$は後で決めるパラメータ) に対して確率変数$X_t$を, $\mathcal{A}(f(t),g(t))=f(t)g(t)$ならば$X_t=1$, そうでなければ$X_t=0$とします. 固定した$t\neq 0$に対して$f(t)$と$g(t)$はそれぞれ$\mathbb{F}_q^{n\times n}$上一様ランダムな行列なので, $\mathbf{E}[X_t]=\Pr_{R,S}[\mathcal{A}(f(t),g(t))=f(t)g(t)]=\alpha$です. よって系3より

$$\Pr[X\geq m\alpha/2]\geq \alpha/2$$

を得ます. ここで$m=\lceil6/\alpha\rceil$とすれば (ここで$q-1\geq 6/\alpha$の仮定を利用する), 確率$\alpha/2$で$X\geq 3$となり前の段落で述べた$1\leq t_1<t_2<t_3\leq m$が存在します. しかも補題1より$f(t)g(t)=\mathcal{A}(f(t),g(t))$かどうかは効率的に検証できるので$t_1,t_2,t_3$を求めることができます. 最後に求めた$t_1,t_2,t_3$及び$f(t_1)g(t_1),f(t_2)g(t_2),f(t_3)g(t_3)$を使って多項式補間すれば$f(0)g(0)$を計算できます.

まとめると次のアルゴリズムを得ました:

1. $R,S\sim\mathbb{F}_q^{n\times n}$を一様ランダムな行列とする.
2. $f(t)=A+tR,g(t)=B+tS$とし, $m=\lceil 6/\alpha \rceil$とする.
3. 各$t=1,\dots,m$に対して$C_t=\mathcal{A}(f(t),g(t))$を計算し, 補題1のアルゴリズムを使って$f(t)g(t)=C_t$かどうかをチェックし, $f(t)g(t)=C_t$となるような最初の三つの$t$を$t_1,t_2,t_3$とする. そのような$t_i$が三つとれなければステップ1に戻る.
4. $f(t_1)g(t_1), f(t_2)g(t_2), f(t_3)g(t_3)$を使って$f(t)g(t)$の各成分を多項式補間し, $f(0)g(0)$を出力する.

ステップ4に進む確率は$\alpha/2$なので, ステップ1から3を$O(\alpha^{-1})$回繰り返せば高確率で一度はステップ4に進むため, アルゴリズムは成功します. 各繰り返しではステップ3で$m$回$\mathcal{A}$を呼び出しているので, $\mathcal{A}'$の全体の計算時間は$O(T(n)/\alpha^2)$となります. (証明終).

次回のpartでは体$\mathbb{F}_q$が小さい場合に[Asadi, Golonev, Gur, Shinkar, STOC22]によって与えられた帰着を紹介します.

理論計算機科学におけるフーリエ解析 (定義)

フーリエ変換とは関数の良い基底を使って線形和で表すことを指します. 競技プログラミングの文脈などでは畳み込みのフーリエ変換と積の関係が非常に有名だと思いますが, それ以外にも様々な応用があります. 基本的にフーリエ変換と聞くと$\sin$や$\cos$が混じった積分がでてくるというイメージだと思いますが, 理論計算機科学では離散的なものを扱う都合上そういったものは(文脈によるが)登場せず, 全てが初等的に定義されるのでより親しみやすいと個人的に思います. 

本記事では定義と基本的な事実だけ紹介します. 将来的にフーリエ変換を使った証明等を書く時にこの記事を参照していきます.

$n\in\mathbb{N}$に対し$[n]=\{1,\dots,n\}$と略記します. 有限集合$S$上で一様ランダムに$x$が選ばれることを$x\sim S$で表します.

$\mathbb{F}_q$を素体とし, $\omega=\mathrm{e}^{\frac{2\pi i}{q}}$とします. 二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その内積を

$$\langle f,g\rangle := \mathbb{E}_{x\sim\mathbb{F}_q^n}[f(x)\overline{g(x)}] = \frac{1}{|\mathbb{F}_q^n|}\sum_{x\in\mathbb{F}_q^n}f(x)\overline{g(x)}$$

とします. この内積が誘導するノルム$\|f\|=\sqrt{\langle f,f\rangle}$を考えます.

$v\in\mathbb{F}_q^n$に対し$\chi_v\colon\mathbb{F}_q^n\to\mathbb{C}$を $$\chi_v(x)=\omega^{\sum_{i=1}^n v_ix_i}$$ とし, 

$$\widehat{f}(v)=\langle f,\chi_v\rangle$$

で定義される関数$\widehat{f}$を$f$のフーリエ変換といいます.

関数族$(\chi_v)_{v\in\mathbb{F}_q^n}$は基底をなしていることが知られており, 任意の関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$は一意に $f=\sum_{v\in \mathbb{F}_q^n}\widehat{f}(v) \chi_v$ と表せることが知られています. このような$f$の表現を$f$のフーリエ逆変換といいます.

また, $\|f\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{f}(v)|^2$が成り立ちます (Parsevalの等式). これはフーリエ変換がノルムを保つ変換(ユニタリ変換)であると解釈できます.

二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その畳み込み$f\ast g$を

$$(f\ast g)(x) = \mathbf{E}_{a\sim\mathbb{F}_q^n}[f(a)g(x-a)]$$

とします. よく知られる事実として, $\widehat{f\ast g}(v) = \widehat{f}(v) \widehat{g}(v)$が成り立ちます.

最後に, $f\colon\mathbb{F}_q^n\to\mathbb{C}$と$1\leq p\leq\infty$に対して$f$の$\ell_p$ノルムを $$\|f\|_p=\left(\mathbb{E}_{x\sim\mathbb{F}_q^n}[|f(x)|^p]\right)^{1/p}$$ で定めます.

本記事では$\mathbb{F}_q^n$上の関数を対象にしていましたが, より一般にアーベル群上の関数に対して群の表現を考えることで似たような枠組みを考えることができます.

ランダム行列の行列積 part 1

 二つの行列$A,B\in\mathbb{F}_q^{n\times n}$が与えられたときにその積$AB$を計算せよという問題はこれまで多くのアルゴリズムが提案されており, 2022年4月現在では[Alman, Williams, SODA2021]による$O(n^{2.37286})$時間が(漸近的な意味で)最速のアルゴリズムとされています. 行列積は$n^2$個の値を計算する問題なので明らかに$\Omega(n^2)$時間かかるので, $2$と$2.37286$の間に限界があるというわけです.

本記事では「$A,B$が$\mathbb{F}_q^{n\times n}$上一様ランダムに与えられた時に$AB$を計算せよ」というランダム行列に対する行列積を計算する問題を考えます.

幾つかの問題ではランダムなインスタンスに対して比較的効率的に問題が解けるということが知られています. 例えばランダムグラフの文脈ではErdős–Rényiグラフ$G(n,p)$上では$O(n^{4+o(1)})$時間でハミルトン閉路を検出し見つけることができます [Bollobás, Fenner, Frieze, Combinatorica, 1987].

果たして行列積は簡単になるでしょうか？

実は答えは(ある意味で)否です. というのも, ランダムな行列の行列積を高速に計算するアルゴリズムがあればそれとほぼ同等の時間で全ての行列に対して行列を計算する乱択アルゴリズムが存在します.

本記事では以下を証明していきます.

定理1 [Blum, Luby, Rubinfeld, 1993]

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

証明.

以下で与えられるアルゴリズム$\mathcal{A}'$を考えます. 入力を$A,B$とします.

1. 一様ランダムな行列$R_1,S_1\sim \mathbb{F}_q^{n\times n}$をサンプリングし, $R_2=A-R_1,S_2=B-S_1$とする.
2. $\sum_{i,j\in\{1,2\}}\mathcal{A}(R_i,S_j)$を出力する.

このアルゴリズムは4回$\mathcal{A}$を呼び出しているので計算時間は$O(T(n))$です. さらに, $\Pr_{R_1,S_1}[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たします.

実際, $R_2,S_2$の(周辺)分布はそれぞれ$\mathbb{F}_q^{n\times n}$上一様なので, 各$i,j\in\{1,2\}$に対して$\Pr[\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-\epsilon$です. よってunion boundより$\Pr[\forall i,j\in\{1,2\},\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-4\epsilon$を得るので, この確率で出力値は

$$\sum_{i,j\in\{1,2\}}R_iS_j=(R_1+R_2)(S_1+S_2)=AB$$

を得ます. (証明終)

BLR93の定理において$\epsilon=1/4-\delta$であれば$\mathcal{A}'$の正答確率が$4\delta$になるので, $100\delta^{-1}$回繰り返せば高確率でそれらの出力の中に一つ以上の正解が含まれています. ところが行列積は乱択を使えば簡単に検証 ($A,B,C$に対して$AB=C$かどうかは$O(n^2)$時間で判定. Freivald's algorithmと呼ばれる.) できるので, 出力された$100\epsilon^{-1}$個の行列の中にある正解がどれかは分かります.

しかしながら証明の解析でunion boundをとっている都合上どうしても$\epsilon\geq 1/4$にはできません.

次回以降のpartではこの$\epsilon\geq 1/4$のケースに対しても上記の定理のような「最悪時から平均時への帰着」が存在することを示した[Asadi, Golovnev, Gur, Shinkar, STOC2022]を紹介したいと思います.

Goldreich-Levinの定理 (アルゴリズム的側面の紹介)

Goldreich-Levinの定理はGoldreich and Levin (1989)によって証明された非常に有名な定理で, 自分のお気に入りの定理の一つです. 元々は平均計算量理論の文脈でone-way functionのhardcore predicateを与えたりYaoのXOR補題の証明に使われたりしている定理ですが, その後Hadamard codeのlocal list decoding, large Fourier coefficientの計算など様々な解釈が与えられ多くの研究に影響を及ぼす重要な定理です. しかしこの定理の主張の説明の多くは理解するためにいろんな前提知識を要するため, 多くの情報系の方にとって敷居の高いものになっているような気がします.

そこで, 本記事では定理の重要性などの背景は省き, その内容と証明のアルゴリズム的な側面を本質だけ抽出して紹介します. 前提知識は特に必要ありません.

1. 線形関数の復元

$\mathbb{F}_2^n$上の線形関数$g(x)=\langle a,x\rangle=\sum_{i=1}^n a_ix_i$がオラクルで与えられるとき, 

$a_1,\dots,a_n\in\mathbb{F}_2$を復元せよ

という問題を考えます. つまり, 任意の$x\in\mathbb{F}_2^n$をクエリしたときに$g(x)$が得られるという仮定の下で係数を復元するという問題です. このような問題設定は学習理論の文脈と少し近い雰囲気を持っています. 学習理論の文脈では「$(a,h(a))$の組が複数与えられたとき, 関数$h$ (ただし$h$は何らかの関数族$\mathcal{F}$に属する)を計算せよ」というような問題設定を考えることがあります. 上記の問題はこの設定よりも簡単で, 好きな入力に対して$h(a)$を得ることが出来るという設定になっています.

この問題は簡単で, $n$個の単位ベクトル$e_1,\dots,e_n$をクエリすれば$a_i=g(e_i)$なので$n$個の係数を復元することができます.

では, 「オラクルが1%の入力に対し間違っている」という設定で同じ問題が解けるでしょうか？与えられるオラクルを$\mathcal{O}$とします. 入力全体$\mathbb{F}_2^n$のうち, ある$|L|\leq 0.01|\mathbb{F}_2^n|$を満たす$L\subseteq \mathbb{F}_2^n$が存在して$x\in L$に対しては$\mathcal{O}(x)\neq g(x)$です. オラクル$\mathcal{O}$のみが与えられたとき (つまり, $L$は分からない), 全ての係数は復元できるでしょうか? この問題設定は学習理論の文脈ではLWE (learning with errors) に対応します.

オラクルが間違わない設定だと, 単位ベクトル$e_i$に対して$\mathcal{O}(e_i)=a_i$が成り立つので簡単に復元できましたが, この設定だと入力$e_i$においてオラクルが間違えている(つまり$e_i\in L$)の可能性があり, しかも間違えているかどうかが分からないので上手くいきません.

ですが実はこの問題設定においても乱択を許せば効率的なアルゴリズムが存在します. 第$i$番目の係数$a_i$を復元する以下の乱択アルゴリズムを考えます: 

$r\in\mathbb{F}_2^n$を一様ランダムにサンプリングし, $\mathcal{O}(e_i+r)-\mathcal{O}(r)$を出力する.

このアルゴリズムは98%の確率で$a_i$を正しく出力します. なぜならば, $r\in\mathbb{F}_2^n$が一様ランダムなので99%の確率で$O(r)=\langle a,r\rangle$であり, しかも$e_i+r$も(周辺分布を見ると)一様ランダムなので, 同様に99%の確率で$\mathcal{O}(e_i+r)=\langle a,r+e_i\rangle$です. なのでunion boundより98%の確率で両方の値は正確で, 最後に線形性より$a_i=\langle a,e_i\rangle = \langle a,r+e_i\rangle - \langle a,r\rangle$により正しく復元できています. 

この議論はオラクルが正直である確率が$0.75+\epsilon$であれば成功確率は$0.5+2\epsilon$となるので, $\lceil\frac{\log (n/\delta)}{8\epsilon^2}\rceil$回繰り返して多数決をとることによって成功確率を$1-\delta/n$までamplifyすることができます. 実際, $i$番目の繰り返しにおいて, 上記のアルゴリズムが正しく$a_i$を計算できていれば$X_i=1$, そうでなければ$X_i=0$として確率変数$X_i$を定義(ランダムネスはベクトル$r$の選択)して$S=X_1+\dots+X_T$とおくと ($T$は繰り返しの回数), $\mathrm{E}[S]\geq (0.5+2\epsilon)T$なので, Hoeffdingの不等式より

$$\Pr[S\leq T/2]\leq \Pr[S\leq \mathrm{E}[S]-2\epsilon T] \leq \exp(-8\epsilon^2 T)$$

を得ます. $T=\lceil\frac{\log(n/\delta)}{8\epsilon^2}\rceil$とすれば, この確率は高々$\delta/n$になります.

再び$i=1,\dots,n$でunion boundをとれば, 全ての成分$a_1,\dots,a_n$を確率$1-\delta$で復元することができます.

上記のアルゴリズムはオラクルが高々$0.25-\epsilon$の割合の$x$に対して誤った値を返すという仮定が大前提でした. この割合がもっと大きくても (例えばオラクルが40%の確率で間違うという設定で)$a$を復元できるでしょうか？

定式化するために, 「オラクルが間違う入力の割合」を関数の距離として捉えます. 二つの関数$f,g\colon\mathbb{F}_2^n\to\mathbb{F}_2$に対して$d(f,g):=\Pr_x[f(x)\neq g(x)]$と定義します. これは$f$と$g$を長さ$2^n$のbinary文字列とみなしたときの(正規化した)ハミング距離と見なすことができます.

$\mathbb{F}_2^n$上の二つの相異なる線形関数$g(x)=\langle a,x\rangle$, $g'(x)=\langle a',x\rangle$に対して, $x\in\mathbb{F}_2^n$を一様ランダムにとってくると

$$\Pr[g(x)=g'(x)] = \Pr[\langle a-a',x\rangle=0] = \frac{1}{2}$$

となります. 最後の等式は$a\neq a'$であることを利用しています. 対偶をとって$\Pr[g(x)=g'(x)]<1/2$ならば$g=g'$という命題を得ます. このことから, $\mathbb{F}_2^n$を係数に持つ線形関数の世界では二つの相異なる線形関数はハミング距離の意味でかなり離れているという面白い性質を持つことがわかります.

図1. Boolean関数全体の空間において二つの異なる線形関数は離れている (0.5以上とありますが実際はぴったり0.5です).

ここで冒頭の「$0.25-\epsilon$の割合の入力に対しオラクルは間違える」という問題設定に戻りましょう. 与えられるオラクル$\mathcal{O}$は, ある線形関数$g$に対して$d(\mathcal{O},g)\leq 0.25-\epsilon$という条件を満たしています. つまりオラクル$\mathcal{O}$は$g$を中心とした半径$0.25-\epsilon$の円に属しているため, 一意に復元可能です.

ところが, 「$0.25+\epsilon$の割合の入力に対しオラクルは間違える」という問題設定だと, 図2のように二つの円が被ってしまう可能性があります.

図2. 半径が大きすぎると円が被りその共通部分にオラクルがあると一意じゃない可能性がある.

ここまでの状況を整理しましょう. 「オラクルが間違える」という表現を距離$d$の言葉で置き換えて以下のように問題を再定義します:

関数$\mathcal{O}$がある線形関数$g$に対して$d(\mathcal{O},g)\leq 0.25-\epsilon$であるとする. 

関数$\mathcal{O}$のオラクルが与えられたとき, $g$ (の係数を全て) を求めよ.

この問題は先ほどのアルゴリズムで解くことができます. 定理の形で述べておくと

定理1. 上記の問題に対し確率$1-\delta$で正しい係数を全て出力する$O(n\epsilon^{-2}\log(n/\delta))$時間乱択アルゴリズムが存在する.

一方で, 

関数$\mathcal{O}$がある線形関数$g$に対して$d(\mathcal{O},g)=0.25+\epsilon$であるとする. 

関数$\mathcal{O}$のオラクルが与えられたとき, $g$ (の係数を全て) を求めよ.

という問題を考えると, 候補となる$g$が複数存在しうることを図で紹介しました. 

2. Goldreich-Levinの定理

次の列挙問題を考えてます:

関数$\mathcal{O}$のオラクルが与えられたとき, $d(\mathcal{O},h)\leq 0.5-\epsilon$を満たす線形関数$h$を列挙せよ.

そのような$h$が存在しない場合は「なし」と出力せよ.

定理1では距離の条件が$0.25-\epsilon$で考えていましたが, ここでは大きく攻めて$0.5-\epsilon$に緩和します. なお, 任意の相異なる線形関数は距離0.5だけ離れているので, "$0.5-\epsilon$"を"$0.5$"に置き換えた場合, $O=g$だとすると全ての線形関数を列挙しなければならないので列挙候補の個数は$2^n$になってしまいます. ですが$0.5-\epsilon$にすると多項式時間で列挙できるということがGoldreich and Levin (1989)によって(本質的に)示されました.

定理2.

上記の列挙問題の全ての解$h$を含むリスト$L$を確率$1-\delta$で出力する$O\left(\frac{n^3}{\delta^2\epsilon^8}\log\left(\frac{n}{\delta\epsilon^4}\right)\right)$時間アルゴリズム$A$が存在する. 

注釈: 冒頭にも述べた通り, Goldreich-Levinの定理自体は様々な解釈ができ, Goldreich and Levin (1989) の平均計算量の文脈の結果のアルゴリズム的に本質的な部分を抽出したものが定理2なので, 定理2そのものをGoldreich-Levinの定理と呼ぶべきかどうかは微妙かもしれませんので, 注意してください.

定理2を証明していきます. まず, 以下の定理を既知として認めます.

定理3. 上記の列挙問題の解は高々$1/\epsilon^2$個しか存在しない.

定理3は関数$\mathcal{O}$のフーリエ級数解析で簡単に示せますが, 後日行います.

定理2の証明). 以下が主張にあるアルゴリズム$A$になります.

1:  $t\leftarrow \lceil \log_2\left(1+\frac{n}{4\delta\epsilon^4}\right)\rceil$;

2:  $r_1,\dots,r_t\in\{0,1\}^n$を独立一様ランダムに生成;

3:  $L\leftarrow \emptyset$;

4:  for each $b=(b_1,\dots,b_t)\in\{0,1\}^t$ do:

5:     for each $i\in\{1,\dots,n\}$ do:

6:        for each $S\subseteq \{1,\dots,t\}$ of $S\neq\emptyset$ do:

7:            $b_S\leftarrow \sum_{i\in S}b_i$;

8:            $r_S\leftarrow \sum_{i\in S}r_i$;

9:            $c_S \leftarrow \mathcal{O}(r_S+e_i)-b_S$;

10:       $a_i \leftarrow \mathsf{maj}((c_S)_{S\neq\emptyset})$;

11:   $L \leftarrow L\cup \{(a_1,\dots,a_n)\}$;

12: return $L$;

ただし, $\mathsf{maj}$は多数決をとる関数 (受け取ったビット列の中で多く登場したビットを返す関数) です.

以下ではアルゴリズム$A$の解析を行います. $d(\mathcal{O},g)\leq 0.5-\epsilon$を満たす関数を一つとってきて$g$とします. アルゴリズム$A$の重要なポイントは

• 2行目で生成したランダムベクトルに対し, $g(r_1),\dots,g(r_t)$の値はオラクルに聞いていないので分からないが, 4行目で$\{0,1\}^t$を列挙しているためどれか一つの$b$に対しては$b_i=g(r_i)$ ($\forall i$) が成り立ちます. 以後この条件を満たす$b$に対して話を進めます.
• 7行目で与えた$b_S$は$g$の線形性より$b_S=g\left(\sum_{i\in S}r_i\right)=g(r_S)$が成り立ちます. ここまでの議論は任意の線形関数$g$で成り立ちます.
• 9行目では, ベクトル$r_1,\dots,r_t$の一様ランダム性により$r_S+e_i$の分布も一様ランダムです. なのでオラクル$\mathcal{O}$の性質により, $\Pr[c_S=g(e_i)]\geq 0.5+\epsilon$です ($b_S=g(r_S)$の仮定の下で).

ここまでをまとめると, 

ある$b\in\{0,1\}^t$が存在して$\forall S\neq\emptyset$, $\Pr[c_S=g(e_i)]\geq 1/2+\epsilon$

が成り立ちます. 10行目では多数決をとってこの確率をamplifyしています. この部分を解析します. 確率変数$X_S$を, $c_S=g(e_i)$ならば$X_S=1$, そうでなければ$X_S=0$と定義して$X=\sum_{S\neq\emptyset} X_S$とします. $r_1,\dots,r_t$は全て独立ですが, $(r_S)_{S\neq\emptyset}$はそうではないので, Hoeffdingの不等式を適用して$X$の集中性を示すことはできません. 代わりにChebyshevの不等式 (以前の記事参照) を利用して$X$の集中性を示します. Chebyshevの不等式は分散が小さければ集中することを主張する不等式なので, $X=\sum X_S$の分散を抑えれば良いことになります. これは$(r_S)$のpairwise independentという性質を用いると可能です.

定義. 確率変数の族$(R_i)$が任意の$i\neq j$に対し

$$\Pr[R_i=a\land R_j=b] = \Pr[R_i=a]\Pr[R_j=b]$$

を満たすとき, $(R_i)$はpairwise independentであるという.

例えば$(R_i)$が全て独立ならば自動的にpairwise independentになります. ところでアルゴリズム$A$で考えた確率変数の族$(r_S)$も実はpairwise independentです (簡単な計算で確認できます). 従って$X_S$もpairwise independentです. 次に分散$\mathrm{Var}[X]=\mathrm{E}[X^2]-\mathrm{E}[X]^2$を計算しましょう.

$$\mathrm{E}[X^2]=\mathrm{E}\left[\sum_{S,S'\neq\emptyset}X_S X_{S'}\right] =\left(\sum_{S}\mathrm{E}[X_S]\right)^2 + \sum_{S}\mathrm{E}[X_S](1-\mathrm{E}[X_S]^2) \leq \mathrm{E}[X]^2 + \frac{2^t-1}{4}$$

より$\mathrm{Var}[X]\leq (2^t-1)/4$です. ここの式変形ではpairwise independentであることから$\mathrm{E}[X_SX_{S'}]=\mathrm{E}[X_S]\mathrm{E}[X_{S'}]$が成り立つことを利用しています (2番目の等式). 最後の不等式では任意の$x\in[0,1]$に対して$x(1-x)\leq 1/4$であることを用いました.

よってChebyshevの不等式および$t$の条件より

$$\Pr[X\leq (2^t-1)/2] \leq \Pr[X\leq\mathrm{E}[X]-(2^t-1)\epsilon] \leq \frac{\mathrm{Var}[X]}{(2^t-1)^2\epsilon^2} \leq \frac{1}{4(2^t-1)\epsilon^2}\leq \frac{\delta\epsilon^2}{n}.$$

を得ます. つまり確率$1-\epsilon^2\delta/n$で$a_i=g(e_i)$が成り立つので, $i=1,\dots,n$と条件を満たす線形関数$g$ (定理3より高々$\epsilon^{-2}$個) に関するunion boundにより, アルゴリズム$A$の出力リストの中に$g$の第$i$番目の係数が入っていない確率は高々$\delta$となる, すなわち$A$は確率$1-\delta$で答えが含まれるリストを出力することができました.

なお, $A$の計算時間は$O(nt 2^{2t})=O\left(\frac{n^3}{\delta^2\epsilon^8}\log\left(\frac{n}{\delta\epsilon^4}\right)\right)$です.

(証明終)

なお, アルゴリズム$A$の出力されたリスト$L$の中から$d(h,\mathcal{O})\leq 0.5-\epsilon$を満たす関数$h$を抽出するのは(乱択を許せば)ある程度までは簡単で, 「ランダムな入力$x\in\{0,1\}^n$に対して$\mathcal{O}(x)=h(x)$かどうかをチェックする」という操作を何度も行って正答数が$0.5+\epsilon$くらいになるような$h$のみを抽出すればOKです (ただし, $d(h,\mathcal{O})\leq 0.5-(1-o(1))\epsilon$を満たす$h$も抽出される可能性もあるので完璧ではありません).

Markovの不等式とChebyshevの不等式

今後の記事で参照できるようにするために, 確率に関する非常に基礎的な不等式であるMarkovの不等式とChebyshevの不等式を紹介します. Markovの不等式さえ覚えていればChebyshevの不等式は非常に簡単に導出できます.

定理 (Markovの不等式). $X$を平均が有限であるような非負の確率変数$X$とする. 任意の$a>0$に対し$\Pr[X\geq a]\leq \mathrm{E}[X]/a$.

証明(概要). 簡単のため$X$を離散値をとる確率変数とする. 任意の$a>0$に対し,

$$\mathrm{E}[X] \geq \sum_{i\geq a} i\Pr[X=i] \geq a\sum_{i\geq a} \Pr[X=i]=a\Pr[X\geq a].$$

$X$が連続値をとる場合でも同様に証明できる.

(証明終)

定理 (Chebyshevの不等式). $X$を平均と分散が有限な実数値確率変数とする. 任意の$a>0$に対し, $\Pr[|X-\mathrm{E}|\geq a] \leq \frac{\mathrm{Var}[X]}{a^2}$.

証明. 確率変数$(X-\mathrm{E}[X])^2$は非負なので, Markovの不等式より

$$\Pr[|X-\mathrm{E}[X]|>\lambda] = \Pr[(X-\mathrm{E}[X])^2>\lambda^2] \leq \frac{\mathrm{Var}[X]}{\lambda^2}.$$

(証明終)

McDiarmidの不等式(小記事)

確率集中不等式の文脈でよく知られているMcDiarmidの不等式について解説します. 

準備: 集中不等式でよくある設定

$S$を集合として$X_1,\dots,X_n\in S$を$S$に値をとる独立な確率変数とします (同一分布に従うとは限らない). 関数 $f\colon S^n\to\mathbb{R}$に対し, 確率変数$Y=f(X_1,\dots,X_n)$を考えます. 例として$S=[0,1]$, $f(x_1,\dots,x_n)=x_1+\dots+x_n$とすると, Hoeffdingの不等式より$Y$はその期待値に集中します. つまり, 任意の$t>0$に対して

$$\Pr[|Y-\mathrm{E}[Y]|>t] \leq 2\exp\left(-\frac{2t^2}{n}\right)$$

が成り立ちます.

これを一般化して次のresearch questionを考えます:

関数$f$がどのような性質を持てば$Y$は集中性が成り立つのか?

結論から言うと, 次の法則が知られています.

$f$が"滑らか"ならば$Y$は集中する.

"滑らか"とはどういうことか, については色んな定義が考えられますが, ひとまずこの法則の根拠となる不等式の一つとしてMcDiarmidの不等式という便利な不等式があります.

McDiarmidの不等式

この不等式では関数の滑らかさをハミング距離に関するリプシッツ性と捉えます. $x,y\in S^n$に対してそのハミング距離$d_{\mathrm{ham}}(x,y)$を異なる要素の個数, すなわち$d_{\mathrm{ham}}(x,y)=|\{i\in[n]\colon x_i\neq y_i\}|$と定義します. 

定理 (McDiarmidの不等式)

関数$f\colon S^n\to \mathbb{R}$が, $d_{\mathrm{ham}}(x,y)=1$を満たす任意の$x,y\in S^n$に対し$|f(x)-f(y)|\leq L$を満たすとする. $X_1,\dots,X_n\in S$を独立な確率変数とし, $Y=f(X_1,\dots,X_n)$とする. このとき,

$$\Pr[|Y-\mathrm{E}[Y]|>t] \leq 2\exp\left( -\frac{2t^2}{nL^2} \right).$$

つまり, $f(x_1,\dots,x_n)$に対して一つの要素$x_i$を別の値に置き換えてもその時の$f$の値がほとんど変わらない(i.e., $L$が小さい)ならば$Y$はその期待値に集中するということを主張する定理です. 例えば冒頭で見た例 $S=[0,1]$, $f(x_1,\dots,x_n)=x_1+\dots+x_n$ ならば, 一つの要素$x_i\in [0,1]$を別の要素 $x'_i\in [0,1]$に置き換えたとしても関数値は高々$1$しか変化しないので, $L=1$としてMcDiarmidの不等式を適用するとHoeffdingの不等式が得られます (より一般に$S=[a,b]$という設定でも得られます).

McDiarmidの不等式の証明は関数$f(x_1,\dots,x_n)$に対するDoobのマルチンゲールを考え, それにAzuma--Hoeffdingの不等式を適用させるだけで得られるので, それほど難しくはありません.

von Neumannのmin-max定理に基づくhardcore lemmaの証明

 Impagliazzoのhardcore lemmaに関する以前の記事ではboosting algorithmとして解釈できる証明を与えました. 本記事ではvon Neumannのmin-max定理に基づく証明を与えます. この証明はImpagliazzo(95)に書いてありますが, アイデア自体はNisanによって与えられたものらしいです. Impagliazzoの元論文やArora--Barakの本にも同様の議論が紹介されていますが, これらを自分なりにかなり噛み砕いて説明していきます.

1. hardcore lemmaの復習

• 関数$f\colon\{0,1\}^n\to\{0,1\}$と入力分布$D$を考える. 任意のサイズ$s$以下の回路$C$に対し $\Pr_{x\sim D}[C(x)=f(x)]\leq 1-\delta$が成り立つとき, $f$は$D$上でサイズ$s$に対して$\delta$-hardであるという.
• 関数$M\colon\{0,1\}^n\to[0,1]$をmeasureと呼ぶ. $|M|:=\sum_{x\in\{0,1\}^n}M(x)\geq \delta 2^n$を満たすとき$M$は$\delta$-denseであるという.
• measure $M$ が誘導する以下の$\{0,1\}^n$上の確率分布を考える: 各$x\in\{0,1\}^n$が選ばれる確率は$M(x)/|M|$. これを$x\sim M$と表す.
• $\{0,1\}^n$上の一様分布を$U_n$で表す.

定理1(hardcore lemma; Impagliazzo 95)

$f\colon\{0,1\}^n\to\{0,1\}$を$U_n$上でサイズ$s$に対し$\delta$-hardな関数とする. あるサイズ$\delta2^n$以上の集合$H\subseteq\{0,1\}^n$が存在して, $f$は$H$上一様分布上でサイズ$O(s\delta^2\epsilon^2)$に対して$(1/2-\epsilon)$-hardである.

定理1は直感的には「$f$が入力全体上でちょっとhardならば多くの難入力からなる集合$H$がとれてその上ではすごくhardである」ということを意味します(この集合$H$をhardcore setといいます). 証明するには最終的に「難入力からなる集合$H$がとれる」ことを言わなければなりませんが, まず集合を01のindicatorとみなしこれの連続緩和であるmeasureに対して, hardcore measureの存在性を証明し, それをrandomized roundingしてhardcore set の存在性を証明します. 前半のステップには大きく分けて二つの証明手法があり, 一つが前回の記事で紹介したboosting algorithmに基づくものです. もう一つが本記事で紹介するvon Neumannのmin-max定理に基づくものです. 具体的には以下の定理を証明します.

定理2(hardcore measure)

$f\colon\{0,1\}^n\to\{0,1\}$を$U_n$上でサイズ$s$に対し$\delta$-hardな関数とする. ある$\delta$-denseなmeasure $M$ が存在して, $f$は$M$上でサイズ$s'=O(s\epsilon^2/\log(\delta^{-1}\epsilon^{-1}))$に対して$(1/2-\epsilon)$-hardである.

定理2の証明の準備としてvon Neumannのmin-max定理の特殊ケースとして得られる以下の補題を述べておきます.

補題3(min-max定理の特殊ケース)

$A,B$を有限集合とし, $x\in[0,1]^A,\,y\in[0,1]^B$をそれぞれ$A$上と$B$上の確率分布とする. $R\colon A\times B\to\mathbb{R}$を関数とし, $c(x,y):=\mathrm{E}_{a\sim x,b\sim y}[R(a,b)]$とする. このとき, $\max_x\min_y c(x,y)=\min_y\max_x c(x,y)$が成り立つ.

上記の補題はしばし二人ゼロ和ゲームの文脈で解釈されます. すなわち二人のプレーヤー1,2がいて, プレーヤー1は戦略として$a\in A$をとることができ, プレーヤー2は戦略として$b\in B$をとることができます. このときにプレーヤー1の報酬を$R(a,b)$とします(同時にプレーヤー2が得る報酬は$-R(a,b)$としてゼロ和ゲームとします). すると$x,y$はそれぞれプレーヤー1,2の混合戦略(戦略集合上の確率分布)とみなすことができ, $c(x,y)$はそれぞれの混合戦略をとった時の期待報酬になります.

定理2の証明

以下の二人ゼロ和ゲームを考えます: プレーヤー1はサイズ$s'$の回路$C$を選び, プレーヤー2は$\delta$-denseな集合$H$を選びます. プレーヤー1が得る報酬は$R(H,C)=\Pr_{x\sim H}[C(x)=f(x)]$とします. つまり, プレーヤー1の目的はできるだけ良い回路を選び$R(H,C)$をできるだけ大きくし, プレーヤー2の目的はできるだけ難しい入力集合$H$を選び$R(H,C)$をできるだけ小さくすることです.

両プレーヤーの混合戦略$\mathcal{C},\mathcal{H}$の期待報酬$c(\mathcal{C},\mathcal{H})$を考えます. 補題3より以下の二つのうちどちらか一方が成り立ちます.

• ケース1: $\min_{\mathcal{H}}\max_{\mathcal{C}} c(\mathcal{H},\mathcal{C})<1/2+\epsilon$.
• ケース2: $\max_{\mathcal{C}}\min_{\mathcal{H}} c(\mathcal{H},\mathcal{C})\geq 1/2+\epsilon$.

ケース1: $\max_\mathcal{C}$の混合戦略の部分を純粋戦略に置き換えても期待報酬は上がらないので, $\min_{\mathcal{H}}\max_{C} c(\mathcal{H},C)<1/2+\epsilon$です (ここで$C$はサイズ$s'$以下の回路全体を動きます). また, $\mathcal{H}$は$\{0,1\}^n$の分布$D$を以下のように誘導します: まず$H$を$\mathcal{H}$に従って選択し, $H$上の一様分布を出力する.

このように定義された$D$に対して$D(x)$を$x$が出力される確率と定義すると, 関数$M(x)=\delta 2^n D(x)$は$[0,1]$上の値をとるためmeasureになっており, しかも$\sum_{x\in\{0,1\}^n}M(x)=\delta 2^n$なので$\delta$-denseです. さらに$x\sim M$と$x\sim D$は同じ分布です. 任意に固定された小さい回路$C$に対し $$c(\mathcal{H},C)=\mathrm{E}_{H\sim\mathcal{H}}[\Pr_{x\sim H}[C(x)=f(x)]]=\Pr_{x\sim M}[C(x)=f(x)]<1/2+\epsilon$$ なので, $M$はhardcore measureになっているため定理2の主張が成り立ちます.

ケース2: 回路の良い混合戦略$\mathcal{C}$が存在することになります. 集合$H$の選び方を混合戦略から純粋戦略に置き換えるとプレーヤー2のとれる選択肢の幅が狭まります. つまりある$\mathcal{C}$が存在して任意のサイズ$\geq \delta 2^n$の集合$H$に対し$\mathrm{E}_{C\sim\mathcal{C}}[R(C,H)]=\Pr_{C\sim\mathcal{C},x\sim H}[C(x)=f(x)]\geq 1/2+\epsilon$が成り立ちます.

ここで, 固定した入力$x\in\{0,1\}^n$に対して$\Pr_{C\sim\mathcal{C}}[C(x)=f(x)]\leq 1/2+\epsilon/2$が成り立つときに入力$x$はgoodであるということにします. 直感的にはgoodとはプレーヤー2にとって($\mathcal{C}$の正答率を下げられるという意味で)都合の良い入力です. $S\subseteq \{0,1\}^n$をgoodな入力の全体としましょう. 直感的には$S$が多いと$\mathcal{C}$にとって困難な入力集合を構成できてしまうので$|S|$は小さいはずです. 実際にこの直感は成り立ちます.

主張: $|S|\leq \delta(1-\epsilon)2^n$.

主張の証明. $S$に要素を任意に追加していきサイズ$\delta 2^n$にしたものを$H^*$とします. $H^*$から一様ランダムに入力を選ぶと確率$|S|/\delta 2^n$で$S$上の一様分布, 残りの確率で$H^*\setminus S$上の一様分布で選ばれます. 前者の入力に対する$\mathcal{C}$の正答率は高々$1/2+\epsilon/2$で後者は高々$1$です. よって

$$\frac{1}{2}+\epsilon \leq \mathrm{E}_{C\sim \mathcal{C}}[\Pr_{x\sim H^*}[C(x)=f(x)]] \leq \frac{|S|}{\delta 2^n}\left(\frac{1}{2}+\frac{\epsilon}{2}\right)+\left(1-\frac{|S|}{\delta 2^n}\right)$$

を得ます. これを$|S|$について解くと$|S|\leq \delta 2^n\cdot \frac{1-2\epsilon}{1-\epsilon}\leq \delta (1-\epsilon)2^n$です.

最後に, $\mathcal{C}$から独立に$t$個の回路$C_1,\dots,C_t$をサンプリングしてそれらをmajorityで結合したものを$C'$とします. 任意の$x\not\in S$に対して$t$個のindicator $\mathbf{1}[C_1(x)=f(x)],\dots,\mathbf{1}[C_t(x)=f(x)]$はiidな確率変数であり, これらの期待値は$x\not\in S$より$1/2+\epsilon/2$以上です. 従ってHoeffdingの不等式より

$$\Pr_{C_1,\dots,C_t}[C'(x)\neq f(x)]=\Pr\left[\sum_{i=1}^t\mathbf{1}[C_i(x)=f(x)]\leq t/2\right] \leq \exp(-\epsilon^2t/2).$$

この確率は適当な$t=O(\epsilon^{-2}\log(\epsilon^{-1}\delta^{-1}))$に対して$\leq \delta\epsilon$となります. この$t$に対して$C'$を考えるとそのサイズは$O(ts')<s$となります. また, 固定した$C'$に対して

$$\Pr_{x\sim U_n}[C'(x)\neq f(x)]\leq \Pr_{x\sim U_n}[x\in S]+\Pr_{x\sim \{0,1\}^n\setminus S}[C'(x)\neq f(x)]$$

および$|S|$の上界より,

$$\mathrm{E}_{C'}[\Pr_{x\sim U_n}[C'(x)\neq f(x)]] \leq \delta(1-\epsilon)+\delta\epsilon =\delta.$$

よって$C'$は期待値的には一様分布上で$f$を確率$1-\delta$で計算することになるので, averaging principleにより正の確率でこの性質を満たします. probabilistic methodにより仮定($f$の$\delta$-hardness)に矛盾する回路$C'$の存在性が言えました. (証明終)

証明におけるケース2の$C'$の構成はboostingの時に考えた構成と同様にmajorityをとっていますがここではi.i.d.に$C_1,\dots,C_t$を$\mathcal{C}$からサンプリングしています. ただ, この回路$C'$はランダムに構成された回路であってあくまでもその存在性はprobabilistic argumentに基づいています.

単純ランダムウォークの到達時間と全訪問時間のまとめ

概要

連結無向グラフ上の単純ランダムウォークの到達時間(hitting time)と全訪問時間(cover time)に関する様々な結果を紹介します. 前半で諸定義を書き後半は軽いサーベイになっています.

1. 用語と定義

この章は基本的な用語の定義だけなのでよく分からなければ読み飛ばしても大丈夫です. 本記事では有限集合$V$上の離散時間マルコフ連鎖$(X_t)_{t\geq 0}$をランダムウォークと呼ぶことにします. 便宜上, 集合$V$を頂点集合と呼びその要素$v\in V$を頂点と呼ぶことにします. 遷移確率が時刻に依存せず一定であれば, $(X_t)$は斉時的である (time-homogeneous) といいます. 以下では断りなく$(X_t)$はtime-homogeneousなランダムウォークを表すこととし, その遷移確率行列を$P$と表記します. 即ち, $P\in[0,1]^{V\times V}$であって$(X_t)$は

$$\Pr[X_{t+1}=v\mid X_t=u] = P(u,v)$$

の遷移規則を満たす確率変数列です. 数直線上のランダムウォークなどを考えると$V=\mathbb{Z}$は無限集合になることもあり, この時は$P$は行列ではなく線形作用素と見なすことになりますが, ここではそのようなケースは考慮しません.

$P$と初期点$X_0$を与えると$(X_t)$の軌道の分布が定まります. $X_t$の分布を$x_t\in[0,1]^V$とすると, $x_{t}=x_{t-1} P = \dots = x_0 P^t$を満たします. 大袈裟に言ってしまえば, $(X_t)$の分布を調べることは$P^t$の性質を調べることと同義なので, 線形代数が重要になってくることは想像に難くないと思います. 特に, $P$がその定常分布から誘導される計量(内積空間)において自己随伴的であることを仮定することが多く (これを可逆性; reversibility), この場合は特に実固有値を持ち, 特にCourant–Fischerの定理を使うことによって混交時間 (mixing time)などを抑えることができます. これらの基礎をちゃんと学びたい人は Reversible Markov Chains and Random Walks on Graphs や Markov Chains and Mixing Times などの教科書がオススメです.

例(単純ランダムウォーク)

無向グラフ$G=(V,E)$の頂点$u\in V$の次数を$\deg(u)$とします. 

$$\begin{align*} P(u,v) = \begin{cases} \frac{1}{\deg(u)} & \text{if }uv\in E,\\ 0 & \text{otherwise}\end{cases}\end{align*}$$

によって定義される$P$によって定まる$(X_t)$を単純ランダムウォーク(simple random walk; SRW) といいます. 言い換えると, 隣接頂点から一様ランダムに頂点を選びそこに遷移する過程で, 最も有名なランダムウォークだと思います. $X_t$の分布のベクトル$x_t\in[0,1]^V$に対し, $\lim_{t\to\infty}x_t$は収束するでしょうか?

結論から言うとNOとなる例が存在します. 無向二部グラフ上の単純ランダムウォークを考えてみましょう. すると左右の頂点集合に交互に移動することになるので, $x_t$は収束しないことがすぐわかります.

このようなランダムウォークの周期性 (periodicity) を除去するために, 確率$1/2$で今の位置にとどまるような以下の$P$で定まるランダムウォークを考えてみましょう:

$$\begin{align*} P(u,v) = \begin{cases} \frac{1}{2} & \text{if }u=v,\\ \frac{1}{2\deg(u)} & \text{if }uv\in E,\\ 0 & \text{otherwise}.\end{cases}\end{align*}$$

自己ループをくっつけたので, 先ほどの二部グラフのような周期性は除外され, 実は$x_t$の集束することが証明できます ($G$の無向性は必要). このようなランダムウォークは遅延単純ランダムウォーク (lazy simple random walk; LSRW) と呼びます (lazyの和訳でよく使われるものを知らないのでとりあえずここでは遅延と呼ぶことにします).

1.1. 到達時間, 全訪問時間, 混交時間

$V$上のランダムウォーク$(X_t)_{t\geq 0}$を考えます. 二つの頂点$u,v$に対し確率変数 $$\tau_{\mathrm{hit}}(u,v)=\min\{t\geq 0\colon X_t=v,X_0=u\}$$

を考えます. これは頂点$u$からスタートして頂点$v$に初めて到達するまでに要する時間を意味します. 定義より明らかに$\tau_{\mathrm{hit}}(u,u)=0$です.

$$t_{\mathrm{hit}}=\max_{u,v\in V}\mathrm{E}[\tau_{\mathrm{hit}}(u,v)]$$

を到達時間(hitting time)と呼びます. 以降, ``$\tau$"が付くものは確率変数で``$t$"がつくものはそれの期待値だと思ってください.

次に, 全訪問時間(cover time)を定義します. 頂点$u$に対し確率変数

$$\tau_{\mathrm{cov}}(u)=\min\{t\geq 0\colon \{X_0,\dots,X_t\}=V,X_0=u\}$$

を定義します. これは$u$を始点としたランダムウォークが全ての頂点に少なくとも1回ずつ到達するのに要した時間を表す確率変数です.

$$t_{\mathrm{cov}}=\max_{u\in V}\mathrm{E}[\tau_{\mathrm{cov}}(u)]$$

を$(X_t)$の 全訪問時間(cover time) と呼びます.

1.2. SRWに対する有名なバウンド

この節では連結無向グラフ$G$上のSRWの到達時間と全訪問時間のバウンドに関する既存結果だけを簡単に紹介します. LSRWを考えても期待値的に値は2倍しか変わりません. $G$の頂点数を$n$, 辺数を$m$とします.

自己ループ付きの完全グラフ上のSRWの全訪問時間はクーポンコレクター問題になり, 古くから研究されており, $t_{\mathrm{cov}}=(1+o(1))n\log n$です.

$n$頂点のパスグラフは最悪な始点として端の頂点を考えればよく, この場合はもう一方の端の頂点に到達するまでに要する時間を考えれば$t_{\mathrm{hit}}=t_{\mathrm{cov}}=\Theta(n^2)$が示せます. $\Theta(n^2)$の直感としては, 無限の数直線$\mathbb{Z}$上の$T$ステップの単純ランダムウォークは$T$個の独立なRademacher確率変数 (一様に$\pm 1$のいずれかを出力する確率変数)の和として表すことができ, 中心極限定理より$T$ステップ後の座標は絶対値が大体$\Theta(\sqrt{T})$くらいになります. $n$だけずれるのに要する時間は$\Theta(\sqrt{T})=n$を$T$について解いて$T=\Theta(n^2)$を得ます.

明らかに到達時間は全訪問時間の下界になるため$t_{\mathrm{hit}}\leq t_{\mathrm{cov}}$なのですが, 実は$t_{\mathrm{cov}}=O(\log n\cdot t_{\mathrm{hit}})$が任意のグラフで成り立ちます. これはランダムウォークの文脈ではMatthew's bound [Matthew, Ann. Probab. 88]などと呼ばれる非常に有名なテクニックです.

Aleliunasら [Aleliunas, Karp, Lipton, Lovász, and Rackoff, FOCS1979]は任意の連結グラフに対し$t_{\mathrm{cov}}\leq 2m(n-1)$を証明しました. この証明は全域木に沿った軌道を考えそれぞれの辺に対するedge commute timeの総和を考えることで得られており, 1ページほどにまとめられていて面白いです.

Kahnら [Kahn, Linial, Nisan, Saks, J. Theor. Probab., 1989]は$\frac{m}{2d_{\min}}\leq t_{\mathrm{hit}} \leq t_\mathrm{cov}\leq 16mn/d_{\min}$ ($d_{\min}$は最小次数) を示しました. ここから系として, 正則グラフに対する$t_{\mathrm{cov}}=O(n^2)$というバウンドが得られます. この定理の証明はAleliunasらの証明における全域木を巧妙に構成することによって得られています. この上界は定数倍を除いてタイトで, t_{\mathrm{hit}}=\Omega(n^2)$を満たす3正則グラフが構成されています (cf. Aldous--Fill本).

Aleliunasらの上界がタイトになる例も知られており[Brightwell, Winkler, RSA1990]はロリポップグラフと呼ばれるグラフが$t_{\mathrm{hit}}=(4/27+o(1))n^3$になることを証明し, Feige [Feige, RSA1995]は任意の連結グラフで$t_{\mathrm{cov}}=(4/27)n^3+O(n^{2.5})$となることを証明しました.

hardcore lemmaとその証明

1. 導入

Impagliazzoのhardcore lemmaと呼ばれる非常に面白いメッセージ性を持つ平均計算量理論において有名な結果[Impagliazzo, FOCS95]を紹介し, その証明をします. 直感的に言えばこの結果は「任意の"まぁまぁ困難な"計算問題に対して"めちゃくちゃ難しい"インスタンスの集合$H$であって密なものが存在する」ということを主張します.

平均計算量理論については以前の記事で触りだけ紹介しています. 本記事では問題として判定問題$f\colon \{0,1\}^n\to\{0,1\}$を考え, 入力分布としてある有限集合$H$ (例えば$H=\{0,1\}^n$) 上の一様分布を考えます. また, 計算モデルとしては回路を考え, その効率性を回路サイズ (=ゲートの個数) で測ります. これを回路計算量と呼びます. アルゴリズムの時間計算量と回路計算量の関係性は非自明で以前の記事で触れていますが, 任意のアルゴリズムはその動作を回路で（少しのオーバーヘッドがあるものの）シミュレーションできるため, 「時間計算量が小さいならば回路計算量が小さい」は成り立ちます (逆は必ずしも成り立たちません).

2. Hardcore lemmaの主張

定義1 (関数のhardness).

関数$f\colon\{0,1\}^n\to\{0,1\}$は, 任意のサイズ$s$以下の回路$C$に対し$\Pr_{x\sim H}[C(x)=f(x)]\leq 1-\delta$を満たすとき, サイズ$s$に対し$H$上で$\delta$-hardであるという. ここで, $\Pr_{x\sim H}[...]$は$x\in\{0,1\}^n$が$H$上一様ランダムにサンプリングされた時の確率をとることを意味する.

$\delta$の値が大きいほど$f$は難しいと解釈できますが, 常に0を出力する回路と常に1を出力する回路を考えればどちらか一方は半分以上の入力$x$に対し$f(x)$を正しく計算できるので, $\delta>1/2$にはなりえません. 

定理1 (Impagliazzo's hardcore lemma)

任意の$\delta,\epsilon>0$に対し以下が成り立つ: $f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対し$\{0,1\}^n$上で$\delta$-hardであるならば、サイズ$\delta 2^n$以上のある集合$H$が存在して$f$はサイズ$O(\delta^2\epsilon^2 s)$に対し$H$上で$(1/2-\epsilon)$-hardである.

冒頭でも述べた通り, $f$が$\{0,1\}^n$上でまぁまぁ難しい (i.e., $0.01$-hard) ならば, $f$がめちゃくちゃ難しい(i.e., $0.499$-hard)ようなサイズ$0.01\times 2^n$以上のインスタンスの集合$H$が存在することになります.

3. 証明

主に二通りの証明方法 (ブースティングアルゴリズムに基づくものとNewman's min-max theoremに基づくもの) が知られています. 後者の証明はArora-Barakの本などにも紹介されているので, 本記事では前者の証明を紹介します.

3.1. Hardcore measure

まず, setの連続緩和としてmeasureという概念を定義し, hardcore setの存在性の代わりにhardcore measureの存在性を証明します. 

定義2 (measure)

関数$M\colon\{0,1\}^n\to\{0,1\}$をmeasureと呼ぶ (測度論における測度とは区別するのを注意してください). $M$のサイズを$|M|=\sum_{x\in\{0,1\}^n}M(x)$とし, 相対サイズを$\mu(M)=|M|/2^n$とする. $\mu(M)\geq \delta$であるとき, $M$は$\delta$-denseであるという.

定義3 (measureにおけるhardness)

$M$をmeasureとする. 関数$f\colon \{0,1\}^n\to\{0,1\}$は以下を満たすとき, サイズ$s$に対し$M$上で$\delta$-hardであるという: 任意のサイズ$s$以下の回路$C$に対し$\Pr_{x\sim M}[C(x)=f(x)]\leq 1-\delta$.

ここで, $\Pr_{x\sim M}[...]$は$M(x)$に比例する確率で$x$をサンプリングした時の確率を考える.

注釈: measureは集合$H\subseteq \{0,1\}^n$を"連続化したもの"と解釈できます. 例えば$M$として$H$の指示関数 ($M(x)=1$ if $x\in H$, $M(x)=0$ if $x\not\in H$) をとれば, $M$が$\delta$-dense $\iff$ $|H|\geq \delta 2^n$ となります.

まず, 定理1の代わりにそれのmeasure版となる以下の結果を証明します:

定理2 (hardcore measure)

任意の$\delta,\epsilon>0$に対し以下が成り立つ: $f$が$\{0,1\}^n$上でサイズ$s$に対し$\delta$-hardならば, ある$\delta$-denseな measure $M$が存在し, $f$は$M$上でサイズ$O(\delta^2\epsilon^2s)$に対し$(1/2-\epsilon)$-hardである.

(証明)

待遇 (i.e., 任意の$M$上でhardでないならば$\{0,1\}^n$上でhardでない) を示します. 具体的には, 任意の$\delta$-denseなmeasure $M$に対し, $f$は$M$上でサイズ$s'$に対し$(1/2-\epsilon)$-hardでないと仮定します. すなわち, 任意の$\delta$-denseな$M$に対しあるサイズ$s'$の回路$C_M$が存在して$\Pr_{x\sim M}[C(x)=f(x)]>1/2+\epsilon$とします. これらの回路$C_M$を組み合わせることによって, $\Pr_{x\sim \{0,1\}^n}[C'(x)=f(x)]>1/2+\delta$となるようなサイズ$O(\epsilon^{-2}\delta^{-2}s')$の回路$C'$を構成します.

最終的に得られる回路$C'$は$C'=\mathsf{maj}(C_1,\dots,C_t)$の形になります ($\mathsf{maj}(x_1,\dots,x_t)$は$\sum x_i\geq t/2$以上ならば$1$, そうでなければ$0$を返す関数で, この関数はサイズ$O(t)$の回路で計算できることが知られています.) 以下では$C_1,\dots,C_t$を定義します.

$\gamma:=\delta\epsilon$とします. まず, 定数measure $M_1\equiv 1$ から始めます. measure $M_i$に対し$C_i=C_{M_i}$とします (待遇の仮定からこのような回路が存在). 事象$Z$の符号付き指示関数を$[Z]$と定義し (i.e., $Z$が真なら$[Z]=1$, そうでないなら$[Z]=-1$), $R_i(x)=\sum_{j=1}^i [C_i(x)=f(x)]$とします. 次のステップにおけるmeasure $M_{i+1}$を,

$$M_{i+1}(x) = \begin{cases} 1 & \text{if }R_i(x)\leq 0,\\1-\gamma R_i(x) & \text{if }0<R_i(x)<1/\gamma,\\0 & \text{if }R_i(x)>1/\gamma\end{cases}$$

で定義します. イメージとしては, これまで得られた回路の過半数が間違えるような入力に対しては最大の重み$M_{i+1}(x)=1$を与え, これまでの回路のうち多くが正解するような入力に対しては重みを与えない ($M_{i+1}(x)=0$) ようなものです. これを$\mu(M_{i+1})\leq \delta$になるまで繰り返し, 得られた回路を$C_1,\dots,C_t$とします.

最終的な回路$C'$の性能を評価します. 入力$x$に対して$C'(x)\neq f(x)$ならば, $C_1,\dots,C_t$のうち過半数が違う値を計算してるので, $C_1(x)+\dots+C_t(x)<t/2$となり, $R_t(x)<0$となります. このとき上記の構成より$M_{t+1}(x)=1$です. したがって

$$\Pr_{x\sim \{0,1\}^n}[C'(x)\neq f(x)] \leq \Pr_{x\sim \{0,1\}^n}[M_{t+1}(x)=1] \leq \frac{1}{2^n}\sum_{x\in\{0,1\}^n}M_{t+1}(x)\leq \delta$$

となるので, $C'$は$\{0,1\}^n$上で$f$を$1-\delta$以上の確率で計算していることになります. また, 各$C_i$のサイズ$\leq s'$であることから$C'$のサイズは$O(ts')$です.

最後に$t=O(\epsilon^{-2}\delta^{-2})$を示せば証明が完了します. ポテンシャルとして

$$A_t:=\sum_{1\leq i\leq t}\sum_{x\in\{0,1\}^n}M_i(x)[C_i(x)=f(x)]$$

を考え, その上下界を求めます:

(1): $A_t\geq t2^{n+1}\gamma$.

回路$C_i$の$M_i$上の正答率の仮定から $$\sum_{x\in\{0,1\}^n}\frac{M_i(x)}{|M_i|}[C_i(x)=f(X)]=2\Pr_{x\sim M_i}[C_i(x)=f(x)]-1\geq 2\epsilon$$ なので,

$$A_t=\sum_{1\leq i\leq t}|M_i|(2\Pr_{x\sim M_i}[C_i(x)=f(x)]-1)\geq t\delta 2^{n+1}\epsilon=t2^{n+1}\gamma.$$

(2): $A_t\leq 2^n(\gamma t/2+1/\gamma)$.

$x\in\{0,1\}^n$を固定し, $S:=\sum_{i=1}^tM_i(x)[C_i(x)=f(x)]$を上から抑えます. $a\in\mathbb{Z}$に対して

$$m(a) = \begin{cases} 1 & \text{if }a\leq 0,\\1-\gamma a & \text{if }0<a<1/\gamma,\\0 & \text{if }a>1/\gamma\end{cases}$$

と定めると, $M_i(x)=m(R_{i-1}(x))$と書けます. ここで, 次で定義される辺重み付き有向グラフ$G=(V,A)$を考えます: $V=\{R_i(x)\colon i=0,\dots,t\}$, $A=\{(R_i(x),R_{i+1}(x))\colon i=0,\dots,t-1\}$, 辺$(R_i(x),R_{i+1}(x))$の重みは$M_i(x)(R_i(x)-R_{i-1}(x))=m(R_{i-1}(x))(R_i(x)-R_{i-1}(x))$.

有向グラフ$G$

ここで, 辺のペア$(a,a+1)$と$(a+1,a)$を考えます. これらの辺は逆向きなので重みの符号は異なり, その大きさは$|M(a)-M(a+1)|\leq \gamma$を満たします. このような辺のペアは高々$t/2$本あり, 総和に対して高々$\gamma t/2$だけ寄与します. 次に, この辺のペアを$G$から除去すると残るグラフは右に行き続けるパスまたは左に行き続けるパスになります.

ペアを全て除去して残ったグラフ

上図のように左に行き続けるパス (つまり, 頂点$a\to a-1\to\dots \to a-\ell$を辿るパス) の辺重みは全て負なので, パス重みの総和には寄与しません. また, 右に行き続けるパス (頂点$a\to a+1\to \dots \to a+\ell$を辿るパス) の寄与は$m(a)+m(a+1)+\dots+m(a+\ell-1)$ですが, $b>1/\gamma$なる任意の$b$に対して$m(b)=0$なのでこの寄与は高々$1/\gamma$となります. 従って, パス重みの総和は高々$\gamma t/2 + 1/\gamma$です. 考えるべきパスは$2^n$個あるから, $A_t\leq 2^n(\gamma t/2+1/\gamma)$を得ます.

(1),(2)のバウンドより, 

$$t2^{n+1}\gamma \leq A_t \leq 2^n(\gamma t/2+1/\gamma)$$

となるので, $t\leq 2/(3\gamma^2) \leq (\delta\epsilon)^{-2}$を得ます.

3.2. Hardcore measure $\Rightarrow$ Hardcore set

3.1の議論により, hardcore measure $M$の存在性が言えました. randomized roundingとprobabilistic methodを組み合わせてhardcore set $H$の存在性を証明します. 整理すると, $M$は$\delta$-denseであり, かつ任意の小さい回路$C$に対して

$$\Pr_{x\sim M}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon$$

を満たします.　この節では$|H|\geq \delta/2\cdot 2^n$であり, かつ任意の小さい回路$C$に対して

$$\Pr_{x\sim H}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon$$

を満たす集合$H\subseteq\{0,1\}^n$の存在性を証明します.

Hardcore measure $M$ を考えます. 各$x\in\{0,1\}^n$に対して, 独立に確率$M(x)/|M|$で$x$を含むようなランダム集合を$H$とします. まず, $|H|$の期待値は$|M|$なので, Hoeffding boundより確率$1-2^{-\Omega(2^{n})}$で$|H|\geq 0.9|M|$を満たします (つまり$H$は高確率で密な集合). 次に$\Pr_{x\sim H}[C(x)=f(x)]=\frac{|\{x\in H\colon C(x)=f(x)\}|}{|H|}$を考えます ($H$がランダム集合なので, この値は$H$のランダムネスに起因する確率変数となる). 先ほど分母の下界を求めたので, 次は分子の上界を求めます. まず, 回路$C$を固定して$A_C=\{x\colon C(x)=f(x)\}$を回路$C$が正解する入力の集合とします. すると分子は$|H\cap A_C|=\sum_{x\in A_C}\mathbf{1}_{x\in H}$となり, これは($H$の構成法により)独立な確率変数の和となります. さらにその期待値は$\mathrm{E}[|H\cap A_C|]=|M|\sum_{x\in A_C}\frac{M(x)}{|M|}=|M|\Pr_{x\sim M}[C(x)=f(x)]\leq (1/2+\epsilon)|M|$となるので, 非常に高い確率 (確率$1-2^{-\Omega(2^n)}$) で$|H\cap A_C|\leq 1.001(1/2+\epsilon)|M|\leq (1/2+\epsilon')|M|$となります. 従って, 回路$C$に関するunion bound ($C$が小さいサイズ, 例えば多項式サイズならば, $C$の総数は$2^{\mathrm{poly}(n)}$以下になる) により, 

$$\Pr_H[\forall C,\Pr_{x\sim H}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon'] \geq 1-2^{-\Omega(2^n)}\cdot 2^{\mathrm{poly(n)}}>0.$$

よって正の確率で$H$はhardcore setの条件を満たすので, 所望の$H$の存在性が証明できました (証明終).

4. 教師有り学習のブースティングとの関係

教師有り学習の文脈では, $f\colon\{0,1\}^n\to\{0,1\}$を二値分類タスクとみなし, $C_M$を$M$上で動作する弱い分類器とみなすことにより, $C'$の構成をブースティングの一種と解釈することができます (ただし上記の証明ではあくまでも$C'$の存在性にすぎず, その構成アルゴリズムを与えたものではないため, ブースティングアルゴリズムそのものは与えていません). 上記の証明は$M$を上手く更新しながら対応する分類器をとってきてそれらのmajorityをとるものになっており, 今回の証明以外にも$M$の更新方法は様々知られており, 例えばAdaBoostのようなmultiplicative updateに基づくもの (+Bregman projection)も知られており, $t=O(\epsilon^{-2}\log\delta^{-1})$まで改善されています (Barak et al. SODA09).