グラフの Spanner と Erdős Girth Conjecture

1. Introduction

離散アルゴリズム・理論計算機科学の界隈で数年前からホットな話題がいくつかありますが, 今回はそのうちの一つであるSpannerを取り上げたいと思います. Spannerと聞くとなんとなく「spanning tree」などを思い浮かべるかもしれませんが, 雰囲気は似ています. 本記事ではあくまでも初歩的な内容までを取り扱います.

グラフ $G=(V,E)$ の全域部分グラフ $H=(V,F)$ (ただし $F\subseteq E$) が $G$の $(\alpha, \beta)$-spannerであるとは, 任意の頂点ペア $u,v\in V$ に対して $d_H(u,v)\leq \alpha\cdot d_G(u,v)+\beta$ が成り立つことです. ここでグラフ$X$に対して$d_X(u,v)$ は頂点 $u,v$ 間の $X$上における最短経路長(距離)とおいています. 気持ちとしては, 辺をたくさん持つようなグラフから辺を取り除いてスパースにしたい. でも元のグラフの構造(最短経路長)をあまり損ないたくない という動機から産み出された概念であって, 例えば大規模グラフに対してその構造上の特性を失わずに前処理で辺を削ってから何か(例えば直径とか)を計算する, みたいな状況を想定しています. 上述の定義における$\alpha$ をstretch, $\beta$ を additive error などと言ったりします. 今回は stretch に着目します.

最近(2011年〜)の理論計算幾科学系の名だたるトップカンファレンス(SODA, STOC, FOCS)において, $(1,\beta)$-spanner と $(\alpha, 0)$-spanner のそれぞれに関する論文が散見されます. 実際に

• An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter , Shay Solomon, Ben-Gurion, (SODA11, best student paper)

• New Additive Spanners , Shiri Chechik (SODA13, best student paper)

• Near-Optimal Light Spanners , Shiri Chechik, Christian Wulff-Nilsen (SODA16, best paper)

• The 4/3 Additive Spanner Exponent is Tight , Amir Abboud, Greg Bodwin (STOC16, best student paper)

はそれぞれ上記のカンファレンス(FOCSでの受賞は未だありません)において受賞しています. これを見るといかにSpannerが注目されているトピックであることが分かると思います. さて, Spanner系の研究で実際になされていることは

• Spannerの辺数と $\alpha, \beta$とのトレードオフの境界
• 実際にSpannerを構成するアルゴリズム

がメインのトピックになります. 前者のトピックに関しては, 実際にSpannerを構成するアルゴリズムを提案すれば「ここまで辺を削減できる」という上界を得ることができます. では, 「どのアルゴリズムを用いてもこれ以上辺を削減できない」ことを言うためにはどうすれば良いでしょうか？そこで登場するのがタイトルにある Erdős Girth Conjecture です.

2. Erdős Girth Conjecture

グラフの girth (内周) とは, 最小閉路長のことです. 例えば, 図を見ると分かるように, girth$\geq 4$であることと三角形を持たないことは同値です. Spannerとgirthの関係はどこにあるのでしょうか.

上図では, 内周6のグラフから辺 $uw$ を除去しています. 消去後のグラフでは, $uv$間の距離は1から5に変化します. 内周が6なので, $uv$ としてどの辺を選んでもこうなります. すなわち, 内周 $k$ のグラフを持っているとき, そのグラフに対して $(k-2,0)$-spanner となるような真部分グラフを構成することは不可能です.

一方で, こちらの記事で紹介したように, girth $\geq 5$のグラフは辺数が高々 $O(n^{1.5})$ となります. 実は, 一般に girth $\geq 2k+1$ のグラフは辺数が高々 $O(n^{1+1/k})$ となることが知られています (完全二部グラフを見てわかるように, 二部グラフは$n^2/4$くらいの辺を持ちうるので偶数長の閉路は問題にはなりません. 実際, 任意のグラフに対して最大カットのサイズは|E|/2以上なので, 辺数を半分くらいにすれば二部化することができます).  Erdős Girth Conjecture はこの上界が定数倍をのぞいてタイトであることを述べています.

Conj. Erdős Girth Conjecture     

次の2条件を満たすグラフ $G=(V,E)$ が存在する.

1. $|E|=\Omega(n^{1+1/k})$ を満たす.
2. $G$の内周が$2k+1$以上である.

 Erdős Girth Conjecture を仮定するとどうなるでしょうか. この予想を満たすグラフ$G$に対し, その$(2k-1,0)$-Spanner を構成しようとするとすでに$G$の内周が$2k+1$以上なので, 所望のSpanner は $G$ 自身でなければなりません ($G$のどの辺 $uv$ を削除しても上述のように距離が $2k$倍になってしまうからです).

一方で, 実は任意に入力で与えられたグラフ $G$ に対して $(2k-1, 0)$-Spanner でかつ辺数が $O(n^{1+1/k})$ なるものを多項式時間で求めるアルゴリズムが知られています[1]. 辺数をこのアルゴリズムより削減できるようなアルゴリズムが存在したとすると,  Erdős Girth Conjecture のグラフを入力として与えたときに上の議論と矛盾してしまいます. つまりこの知られているアルゴリズムが最適である, と結論づけることができます.

3. 余談

実は辺重み有りグラフでも, 辺数が $O(n^{1+1/k})$ なる $(2k-1, 0)$-Spanner を多項式時間で求めるアルゴリズムが知られています[1].

なお,  Erdős Girth Conjecture は $k=1,2,3,5$ の場合は解決されているようです [2].

今回は additive の方には触れませんでしたが, 興味のある方はぜひ調べてみてください.

[1]: I. Althöfer, G. Das, D. Dobkin, D. Joseph, J. Soares. On sparse spanners of weighted graphs. Networks, 9(1): 81–100, 1993

[2]: R. Wenger. Extremal graphs with no C4’s, C6’s, or C10’s. Journal of Combinatorial Theory, 113–116, 1991.

単著論文がSODAに通りました

The Diameter of Dense Random Regular Graphs
という単著の論文がSODA18に採択されました.

SODAは Symposium on Discrete Algorithms という理論的な国際会議で, コンピュータ科学において「トップカンファレンス」と呼ばれるもので, なかなか通すのが難しいと言われています. 今年のSODA17には通した日本人が1,2人しかいなかったと記憶しています. 今年はバルセロナでの開催でしたが, 来年のSODAはニューオリンズです. 他にもFOCS, STOCなどが有名です.

通した論文の内容はランダム正則グラフの直径についてのものです. ランダム正則グラフは次数が定数の場合は直径が漸近的(頂点数→無限)に"最適" (i.e. Moore Boundから得られる直径の理論下界との比が1に収束)で, HPCのネットワークトポロジーとしても有用であることが知られています. しかし次数が頂点数とともに増加する場合はその直径がどうなるかはexplicitには知られていませんでした. (実際にはMoore Bound と最近発表された定理を拾ってくるとだいたいのケースでは上界と下界が得られます). 今回の論文はそのようなランダム正則グラフの直径について, 次数dが $d=\beta \cdot n^{\alpha}$ ($n$は頂点数) の場合だとその直径が $\lfloor \alpha^{-1} \rfloor + 1$ となることを証明しました (研究の本質的な点は, 上記の次数を持つランダム正則グラフに対してMoore Boundから得られる下界と上述の定理から得られる上界の間のギャップに関する問題を解決したという点にあります)

三角形・四角形を含まないグラフ(極値グラフ理論)

0. 概要

グラフ理論の中に「極値グラフ理論 (extremal graph theory)」と呼ばれる分野があります. 極値グラフ理論では, 「与えられた性質$\mathcal{P}$を満たすグラフのうち, 最大辺数を求める」ことを考えます. 極値グラフ理論で最も有名な結果はおそらくTuranの定理でしょう. これは, 性質$\mathcal{P}$を「サイズ$r$の完全グラフ$K_r$を含まない」としたとき, 辺数が最大のグラフは$r-1$部完全グラフであるという結果です.

気持ちとしては, 「どれほどの辺数を持てばグラフが性質$\mathcal{P}$を満たすことを保証できるか」という問題について考えるのが極値グラフ理論です.

1. Triangle-free グラフ

「三角形($=K_3$)を含まない」という性質を満たすグラフのうち最大辺数を持つグラフを考えます. (このようなグラフをtriangle-freeグラフといいます). こちらのページで紹介されているように(またはTuranの定理の帰結として), 完全二部グラフを考えると, 三角形を含まないような頂点数$n$のグラフが持ちうる辺数はおおよそ, 高々$\frac{n^2}{4}=O(n^2)$となります.

2. Triangle & Square-free グラフ

では, 「三角形・四角形を含まない」という性質を満たすグラフの最大辺数について考えます. 結論から言うとこのような性質を持つ頂点数$n$のグラフの辺数は高々$O(n^{1.5})$となることが示せます. 「奇数長の閉路を含まない」という制約を考えても完全二部グラフがとれるので, 辺数が$O(n^2)$になります. しかし四角形の制約を付け加えるだけでオーダーが劇的に下がる, という点が面白い点です. この結果はとても簡単に証明できるので, 紹介します.

定理. 三角形及び四角形を含まない$n$頂点のグラフ$G$の辺数は高々 $\frac{n\sqrt{n-1}}{2}$ である.

証明.
$G=(V,E)$を三角形・四角形を含まない$n$頂点のグラフとします. このグラフが含む長さ2のパスの本数を二通りの方法で数えます:

図のように, 頂点$v$を一つ選んだときに$v$を真ん中の頂点として持つような長さ2のパスを考えます. そのようなパスの個数は$v$に対して$i,j$の選び方の総数に等しいので, $\binom{d_v}{2}=\frac{d_v(d_v-1)}{2}$となります. ここで$d_v$は頂点$v$の次数です.
従って, 長さ2のパスの総数は



となります.


一方, $G$が四角形を含まないため, 隣接していない二頂点$i,j$を選択したときに, $i,j$を端点として持つような長さ2のパスは高々1本となります (下図). 従って, 長さ2のパスの本数は非隣接的な二頂点の選び方の総数, 即ち$\binom{n}{2}-|E|$で上から抑えることが出来ます.

非隣接頂点対$i,j$に対して, $i$と$j$の両方と隣接している頂点は高々一つである.

従って



よって,

                    ...(1)

となります.


次にコーシーシュワルツの不等式を用います. コーシーシュワルツの不等式は

$\left(\sum_v x_v y_v\right)^2 \leq \left(\sum_v x_v^2\right)\left(\sum_v y_v^2\right)$

ですが, これに$x_v=d_v$, $y_v=1$を代入すると

$4|E|^2 = \left(\sum_v d_v\right)^2 \leq n\sum_v d_v^2$                    ...(2)


(1)(2)より,

$\frac{4|E|^2}{n}\leq \sum_v d_v^2 \leq n(n-1)$

従って,

$|E| \leq \frac{\sqrt{n^3-n}}{2} = \frac{n\sqrt{n-1}}{2}$. (証明終)

3. 不等式はタイトなのか？

結論から言うとタイトです. こちらの記事で紹介したMoore graphを考えます. Moore graph は頂点数$k^2+1$の$k$-正則グラフで, かつ三角形・四角形を含まない($\iff$ 直径$=2$)ものです. Moore graph は $k=2,3,7$に対しては存在しますが, これら三つのグラフは辺数が$\frac{kn}{2}=\frac{k^3+k}{2}$となりますが, この値は辺数の上界$\frac{n\sqrt{n-1}}{2}=\frac{(k^2+1)k}{2}$となり, 辺数と等しくなっています.

強正則グラフのスペクトル解析と未解決問題への応用

0. 背景

グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」特徴付けや性質(例えばHallの結婚定理, グラフマトロイドの基, 交互増加道, 残余ネットワークに関するものなど)を与えるという, アルゴリズム上のモチベーションが最も大きいんじゃないかと思います.

しかしそれとは別に純粋数学寄りな一面もあります. グラフ理論の一分野に「Algebraic graph theory」というのがあります. 直訳すると「代数的グラフ理論」で, この分野はグラフの特徴を代数的に解析するもしくは代数的に「綺麗な」グラフを構成したり, Tutte多項式といった興味深い不変量について解析しています. ここで言う「代数」とは線形代数(スペクトラムグラフ理論)や群(Cayley graph)などです. 面白いことに正則グラフ(全ての頂点の次数がある定数に等しいグラフ)に対するゼータ関数としてIhara zeta function というものが知られていて, Ihara zeta function を用いてラマヌジャングラフと呼ばれるスペクトラムグラフ理論において非常に重要なグラフの特徴づけを与えられています.

グラフの持つ美しい性質の解析の一方で, こちらの記事で紹介したような「小直径グラフを構成する」や「彩色数と内周(girth)が共に大きいグラフ」といった, 普通のグラフでは満たされないような性質を満たすグラフをalgebraic graph theoryの道具を用いて巧妙に構成するという研究も有ります.

今回の記事では 強正則グラフ (strongly regular graph) と呼ばれるグラフについて, スペクトラムグラフ理論においてしばしば用いられるテクニック(=線形代数)を用いて解析していきます. 更にその応用として, グラフ理論における二つの未解決問題(Moore graph と Conway 99 problem)について考察してみます. あらかじめ記しておきますが, 本記事は予想以上に線形代数成分が強いです (というかグラフ理論成分は少なめです).

1. 強正則グラフ

グラフ$G$に対し, その頂点$v$に隣接する頂点の全体を$N(v)$で表します.
$n$頂点の$k$-正則グラフ$G$ (全ての頂点の次数が$k$に等しいグラフ) が以下の全ての性質を満たすとき, $G$はパラメータ$(n,k,\lambda,\mu)$を持つ強正則グラフであると言います.

1. 任意の隣接する二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\lambda$に等しい.
2. 任意の隣接しない二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\mu$に等しい.

イメージとしてはこんな感じです:

特に, $\mu>0$の場合はグラフの直径は$2$以下となります. $\mu=0$の場合はグラフは非連結で, 各連結成分はサイズ$\lambda+2$の完全グラフになっていて次数は$k=\lambda-1$となります.

例:

・長さ5の閉路 : $(n,k,\lambda,\mu)=(5,2,0,1)$.

・Petersen graph : $(n,k,\lambda,\mu)=(10,3,0,1)$.

Petersen graph

・$n$頂点の完全グラフ : $(n,k,\lambda,\mu)=(n,n-1,n-2,0)$.

・長さ$3$の閉路 : $(n,k,\lambda,\mu)=(3,2,1,0)$.

$\lambda$は三角形の個数, $\mu$は四角形の個数を規定している感じになっています.

2. 強正則グラフのスペクトル

$G$を$(n,k,\lambda,\mu)$をパラメータに持つ強正則グラフとします. 更に$\mu\neq 0$を仮定します. $G$の隣接行列を$A$とします. すなわち

と定めます. 今回の目的は$A$の全ての固有値を特定することです. 固有値を求めてそこから得られる様々な条件を考えることによって, 与えられたパラメータ$(n,k,\lambda,\mu)$に対応する強正則グラフの存在性について議論することが出来ます (後述).

$i\neq j$に対し, $(A^2)_{ij}$は頂点$i$から頂点$j$への長さ2のパスの本数に等しいはずです. $ij$が隣接しているときはこの値は$\lambda$と等しく, そうでないときは$\mu$に等しくなります (上図参照). $i=j$に対しては$A^2_{ij}$は次数に等しいので$k$となります. 以上より

なので, 

$A^2+(\mu-\lambda)A=(k-\mu)I+\mu J$                    ...(1)

となります. ここで $I$ は$n\times n$の単位行列, $J$は全ての要素が1に等しい$n\times n$行列です. 即ち強正則グラフの隣接行列は行列の二次方程式が成り立ちます.

$A$は$k$-正則グラフなので, 各行に含まれる$1$の個数(=次数)は全て$k$に等しいはずです. すなわち $A\mathbb{j}=k\mathbb{j}$ が成り立ちます. ここで$\mathbb{j}\in\mathbb{R}^n$は全要素が$1$の列ベクトルです. 更に$A$対称行列なので全ての固有値は実数であり, しかも最大固有値は$k$に等しく, ($\mu>0$よりグラフは連結なので, $A$は行列として既約であるため, ペロン=フロベニウスの定理より)最大固有値の多重度は$1$となります. したがって$A$の他の固有値$\theta$に対応する固有ベクトル$x$は必ず$\mathbb{j}$と直交します. このベクトル$x$を二次方程式の両辺に掛けると, ($Jx=\mathbb{j}\mathbb{j}^{T}=0$に留意して)

$(A^2+(\mu-\lambda)A)x = (\theta^2+(\mu-\lambda)\theta)x = (k-\mu)x$

となります. したがって$\theta$は以下の二次方程式:

$\theta^2+(\mu-\lambda)\theta-(k-\mu)=0$

の解になっているので, 

以上より, $A$の固有値は三種類しかなく, それらは

となることが分かりました. 更に, $A$に関する二次方程式の両辺に$\mathbb{j}$を掛けると

$k^2+(\mu-\lambda)k=k-\mu+\mu n$                    ...(2)

即ち, $k(k-\lambda-1)=(n-k-1)\mu$ が成り立ちます.

最後に, それぞれの多重度を求めてみましょう. 

とおいてそれぞれの多重度を$s,t$とおきます. すると$A$のトレース(=対角成分の和=固有値の和)は$0$に等しく, 固有値$k$の多重度は$1$であることも合わせると

$fs+gt+k=0$, $s+t=n-1$

となり, これを連立させると

                    ...(3)

が成り立ちます. 即ち $(n,k,\lambda,\mu)$をパラメータとして持つような強正則グラフが存在するためには, これら四つの値が (2)を満たしかつ(3)で与えられる$s,t$が整数とならなければいけません. これらの条件を使うことによって与えられたパラメータに対応する強連結グラフの存在性について議論することが出来ます.

先ほどみたように, 連結な強正則グラフの固有値は3種類しかありません. 面白いことに逆も成り立つことが知られています:

定理1:

$G$を連結な$k$-正則グラフで完全グラフでないものとする. $G$の隣接行列が三つの相異なる固有値$k>s>t$を持つとする. このとき, $G$は強正則グラフである.

また一般に, 固有値の種類数はグラフ(強正則でなくても良い)の直径を上から抑えるということが知られています:

定理2:

連結な$G$に対してその隣接行列が持つ相異なる固有値の個数を$m$とする. $G$の直径は$m-1$以下である.

強正則グラフは固有値は3種類しかないので直径2となっていますが, このことは定理2と整合性がとれています (余談ですが, 定理2の証明は2016年に東京大学情報理工学系研究科の数理情報学専攻の修士課程の大学院入学試験で出題されました).

応用1: Moore graph の存在性

Moore graph とは簡単に言うと「直径$D$の$d$-正則グラフの中で最も頂点を多く含んでいるグラフ」のことです. 詳しくはこちらの記事に書いてあります. Moore graphは

1. 直径$>2$の場合は存在しない
2. 直径$=2$かつ$d\not \in \{2,3,7,57\}$ の場合は存在しない.

ことが示されています. 今回は二つ目の事実をこれまでの議論を使って示していきます. こちらの記事より, 直径2のグラフ$G$が Moore graph であることの必要十分条件は, $G$が三角形と四角形を含まないことです. 更に, 明らかに$n=k^2+1$となります). 従って, $G$はパラメータ$(n,k,\lambda,\mu)=(k^2+1,k,0,1)$を持つ強正則グラフとなっていることに注意します($n=k^2+1$は今回導出した(2)の条件に$\lambda=0,\mu=1$を代入することで導出できます).

(3)の整数性条件を考えます. パラメータを代入して計算すると

即ち, $k^2-2k=0$ もしくは $4k-3=p^2$ ($p\in\mathbb{N}$) が必要条件となります. $k^2-2k=0$, 即ち$k=2$に対しては長さ$5$の閉路が対応しています. ２番目の条件より, $k=(p^2+3)/4$ を $s$ に代入すると,

$s=\frac{p^4+6p^2+9}{32}+\frac{p^4-2p^2-15}{32p} = \frac{p^5+p^4+6p^3-2p^2+9p-15}{32p}$

整理すると

$p^5+p^4+6p^3-2p^2+(9-32s)p=15$

従って$p$は$15$を割り切るので, $p\in \{1,3,5,15\}$となり, それぞれの$p$を$4k-3=p^2$に代入ことにより, $k=1,3,7,57$ が得られます. $k=1$の時は$n=k^2+1=2$より, グラフは$K_2$となります (直径2ではないのでこれは除外します).

従って, 直径2のMoore graphが存在するならば, $k\in \{2,3,7,57\}$ が成り立ちます.

応用2: Conway 99 graph problem

元ネタ : https://oeis.org/A248380/a248380.pdf
関連文献 : https://arxiv.org/abs/1707.08047

こちらの問題はグラフ理論というよりは, Conwayが出した未解決な問題であり, 解けたら1000ドルもらえるというプチミレニアム未解決問題です. 具体的には次のような問題です:

問題: 以下の二つの性質を満たす$99$頂点のグラフは存在するか否か.

1. 任意の隣接している二頂点$u,v$に対して, $u,v$を含む三角形が唯一存在する.
2. 任意の隣接していない二頂点$u,v$に対して, $u,v$を対角線上に含むような四角形が唯一存在する.

イメージとしては次のような感じです:

三角形は被ってはいけない. 四角形は二辺を共有してはいけない.

本記事では条件1を三角形条件, 条件2を四角形条件と呼ぶことにします (番号が乱立して可読性が下がるため)

問題を見た感じだと正則グラフには見えないのですが, もし所望のグラフ$G$が存在するとして, それが$k$-正則であったならば, $G$はパラメータ$(99,k,1,1)$を持つ強正則グラフであることが分かります. すると(2)の条件より, $k=14$が出てきます. そもそもなぜ頂点数が99なのでしょうか？この記事ではより一般に, パラメータ$(n,k,1,1)$を持つ強正則グラフについて考え, どのような$n$と$k$に対してそのグラフが存在するのかについて考えていきます.  まず明らかですが, $n=3,k=2$に対しては$K_3$が所望の性質を満たすことが確認できます(非隣接点が存在しないため). これ以外に所望のグラフはあるのでしょうか？

実は, 所望のグラフが存在するとしたら, そのグラフは必ず正則であることが次のようにして証明できます:

$G=(V,E)$の頂点数を$n$とします. $G$において隣接している二頂点$u,v$を任意にとってきます. するとある頂点$w\in V\backslash \{u,v\}$が一意に存在して$uvw$が三角形となります. 更に$n\geq 4$のとき, $G$の直径は$2$であり, $k\geq 3$となる ($k=2$ならば$n=3$となってしまうから). 従って$u$に隣接する頂点$z\in V\backslash \{v,w\}$が存在し, この$z$はどれも$v$には隣接していない (そうでないならば, $uvz$が三角形条件に反する. 下図1参照).

図1 : $z$と$v$は隣接してはいけない.

　そこで$z, v$に対して四角形条件を適用すると, $zv$を対角線として持つような四角形$uvz'z$が存在することになります. 特にこの四角形は一意なので, $z$に対して$z'$は唯一定まります (図2). 特に$z'\in N(v)$に注意します.

図2. $vz$を対角線に持つような四角形がとれる. 一方で$z$に対して複数の$z'$をとることは出来ない.

そこで写像$z\mapsto z'\in N(v)$を考えると, これは単射になっています. $z_1\neq z_2 \in N(u)$に対して$z_1\mapsto z'$, $z_2\mapsto z'$となると四角形条件に反するからです.

図3: $z_1,z_2 \mapsto z'$となると$uz'$を対角線に持つ四角形が二つできてしまう.

従って, 単射$N(u)\to N(v)$が構成できた(実際は全単射になっている)ので, $|N(u)|\leq |N(v)|$. 同様にして逆も言えるので, $|N(u)|=|N(v)|$. $G$は連結なので, どの頂点の次数もある定数に等しい. よって$G$は正則である.

以上より, 議論すべきグラフは正則なので, パラメータ$(n,k,1,1)$を持つ強正則グラフです. 更に(2)の条件より, $n=\frac{k^2}{2}+1$となります. $n$の整数性から$k$が偶数であることも直ちに従います. さらに, 固有値の多重度の整数性条件から





すなわち$k^2-4k=0$, $4k-7=p^2$となります.

$k^2-4k=k(k-4)=0$の場合は$k=4$となり, 対応する$n$は$n=\frac{k^2}{2}+1=9$.

$4k-7=p^2$の場合は$k=(p^2+7)/4$を$s$に代入することにより





従って, $p^5+p^4+14p^3-2p^2+(49-64s)p=63$ となるので, $p$は$63$を割り切ります. 即ち$p\in \{1,3,7,9,21,63\}$. 対応する次数$k$は$k\in\{2,4,14,22,112,994\}$.

まとめると, $(n,k,1,1)$をパラメータとして持つ強正則グラフが存在するための十分条件は(計算ミスがなければ)





実際, $(n,k)=(3,2)$に対しては$C_3$が対応しています. しかし$(n,k)=(9,4)$に対しては存在しないことが示せます(三角形条件と四角形条件を使って局所的な構造を絞ることによって示せますがあまり証明としては綺麗ではありません). こちらにあるように, $(n,k)=(9,4)$は具体的にグラフが構成でき, 隣の研究室の後輩に教えられたのですが, $K_{3,3}$の線グラフ(辺と頂点を交換したグラフ)が条件を満たしています. (2018年7月24日追記) $(n,k)=(99,4)$はConwayの99問題に対応しています. 他にも三つほどヤバそうな$(n,k)$がありますが, とりあえず有限個であることは以上の議論より示すことが出来ました.

要するに「99」という数字の本質は線形代数的な議論によって導かれます. また, Moore graphにおいても「次数57」の条件は同様な議論から導出できます. 即ち「良い性質を持った」グラフの存在性については未だに線形代数的な議論によってしか条件を絞り込むことが出来ていないというのが現状です. 従って今回提示した二つの未解決問題を解くためには, 線形代数から少し離れたアプローチ, もしくはよりグラフ理論っぽいアプローチから新たな必要条件を導出するしかないんじゃないかなぁとなんとなく思っています.

3. まとめ

今回の記事では「スペクトラムグラフ理論」と言いながらほとんど「スペクトラムグラフ」感が感じられないものだったので, あまりその凄さが通じなかったのかもしれません. しかし実はスペクトラムグラフ理論の技法はグラフの構造上の特徴の情報を得ることが出来ます. 例えば, $(n,k,1,1)=(99,14,1,1)$をパラメータに持つ強正則グラフ(Conwayの問題におけるグラフ)が存在するならば, その最大独立点集合のサイズが高々22であり, 彩色数は5以上である, ということを証明することが出来ます (驚くべき証明があるのですが余白がないので省略します).

そして実際に今回示した手法によってMoore graph や Conway problem に対してある程度までの必要条件を導出することが出来ました. なお今回のConway problemに関する結果については僕は論文でも見たことはなく, (載っている論文がぱっと見見つからないという意味で)新しいものなのかもしれませんが, 教科書に載っている程度の初等的な議論によって得られる結果なので「プロ」の研究者にとっては既知の情報かとは思います. また, 今回の議論は次を参考文献として提示します.

• "Elementary Number Theory, Group Theory and Ramanujan Graphs", Giuliana Davidoff, Mount Holyoke College, Massachusetts Peter Sarnak, (2003)

こちらの本はグラフスペクトル理論の初歩的な部分について解説していて, Ramanujan graph についての話題が書いてあります. 前提知識もあまり必要でなく, 非常に読みやすかったです.

• "Topics in Graph Automorphisms and Reconstruction", Josef Lauri, University of Malta Raffaele Scapellato, Politecnico di Milano, (2016)

こちらの本は algebraic graph theory に関わる話題として automorphism (vertex-transitivityなど)や, グラフ理論における非常に有名な未解決問題: reconstruction conjecture について紹介しています. strongly regular graph, Moore graphについて節が割かれています.

高速な全点対最短経路アルゴリズム

1. 全点対最短経路問題の計算量の外観

　グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります.

　実は辺重み付きグラフのAPSPの計算量には多くの歴史があり、ワーシャルフロイド法以降様々なアルゴリズムが提案されてきました.

APSPのアルゴリズムの歴史

　しかし、任意の $\epsilon>0$ に対して $O(n^{3-\epsilon})$ 時間でAPSPを解くアルゴリズムはこれまで知られていません. なので現在ではそのようなアルゴリズムは存在しないのではないかと予想されています. ちなみにSETHの仮定の下で計算量の下界が示されている問題が多くありますが, APSPのこの下界をSETHの仮定の下で示すのは難しいだろう, という根拠が2016年にCarmosino, Gao, Impagliazzoらによって示されました.

2. 重み無しグラフの全点対最短経路

　以上のことから, 辺重み付きグラフのAPSPを$O(n^{2.99})$で解くのは絶望的であると言えます. では, 辺重み無しグラフのAPSPについてはどうなのでしょうか？以降は「グラフ」は辺重み無しグラフを指すこととします.

　頂点数$n$, 辺数$m$のグラフのAPSPは各頂点から幅優先探索を行うことによって $O(nm)$ 時間で解くことができます. したがってグラフが密で, $m=\Omega(n^2)$ であるならば計算時間は $O(n^3)$ だけかかってしまいます. 

　結論から言うと辺重み無しグラフのAPSPは$m$に依存せず $O(n^{\omega}\log n)$ 時間で解くアルゴリズムが存在します. そのアルゴリズムは[Seidel, 1992]で初めて与えられました. 非常にシンプルなので, 本記事ではこのアルゴリズムについて解説します.

3. Seidel のアルゴリズム

　前提として入力として与えられるグラフ$G$は連結であるとします. したがってその直径は高々$n$です. 更に, 入力において$G$は隣接行列として与えられるとします. そしてアルゴリズムの出力は距離行列$D$とします. ただし$D_{ij}=ij$間の最短経路長と定義します.

　グラフ $G$ に対し, 任意の辺$uv,vw \in E(G)$ に対して 新たな辺$uw$を$G$に追加して得られるグラフを$\tilde{G}$ と定めます. 気持ちとしては$\tilde{G}$ は「全ての長さ2のパスに対してその端点を結ぶ」ことを出来るだけ行って得られるグラフです.

追加した辺を赤く塗っています. 三角形がめちゃくちゃ増えます.

$A$を$G$の隣接行列とします. すると$\tilde{G}$の隣接行列$\tilde{A}$は

になります ($i\neq j$に対し$A^2$の$ij$成分は$ij$間の長さ2のパスの本数を表すからです). したがって, $A^2$を$O(n^{\omega})$時間で計算することで$\tilde{A}$が計算できるので, $\tilde{G}$を得ることが出来ます. 

　この$\tilde{G}$に対して再帰によってAPSPの距離行列$\tilde{D}$を得ます. $\tilde{G}$の直径は$G$の直径の半分くらいになっているので, 再帰を繰り返した結果, 最終的には$G$の直径が$1$(=完全グラフ)となり, この時は(再帰のベーシックケースとして)出力$D$は非対角成分が全て1の行列となります. 更に, 再帰の深さは$\log n$くらいです. というのも$G$の直径が高々$n$で, 一回の再帰で直径が半分くらいになるからです.

　さて, 再帰の出力$\tilde{D}$を使って$G$の距離行列$D$を得ましょう. 下図のように, $\tilde{G}$の$ij$間の最短経路を考えます. 明らかに, 元のグラフ$G$における$ij$間の最短経路長$d_{ij}$が奇数であれば, $\tilde{G}$における$ij$間の最短経路長$\tilde{d}_{ij}$に対して $d_{ij} = 2\tilde{d}_{ij}-1$ が成り立ちます (下図(a)参照. $\tilde{G}$では長さ2のパスを1ホップで通過出来るので, 出来るだけ新しい辺を利用した方が経路長が短くなる). 一方で$\tilde{d}_{ij}$が偶数であれば, $d_{ij}=2\tilde{d}_{ij}$が成り立ちます (下図(b)). 以上より, $d_{ij}$のパリティが分かれば$\tilde{d}_{ij}$を用いて$d_{ij}$を復元できます.

元の最短経路長のパリティが分かれば復元できる.

　ここで, $\tilde{G}$上で ① $ij$間に(a)の図のような最短経路が存在する場合, $d_{ij}=2\tilde{d}_{ij}-1$となります. 一方で ② そのような最短経路が存在しない場合(つまり任意の$ij$間の最短経路が(b)のように赤い辺のみで構成されている場合), $d_{ij}=2\tilde{d}_{ij}$となることに注意します. つまり$d_{ij}$を復元するためには①と②の場合を判別する必要があります.

　そのために行列$X:=\tilde{D}A$を考えます. これは行列積なので$O(n^{\omega})$時間で計算できます. 行列積の定義より$X_{ij}$は

$X_{ij}=\sum_{k=1}^n \tilde{d}_{ik}\cdot A_{kj} = \sum_{k \in N(j)} \tilde{d}_{ik}$

となります. ここで$N(k)$は$G$における$k$の隣接点の集合, $\tilde{d}_{ik}$は$\tilde{G}$における$ik$間の最短経路長です. 

　②を仮定します. すると任意の$k\in N(j)$に対し, $\tilde{d}_{ik} \geq \tilde{d}_{ij}$ が成り立ちます (そうでないとすると, $\tilde{G}$上の$ik$間の最短経路に辺$kj$を足したものが$ij$間の最短経路になりますが, それは②に反するからです. 下図参照).

②で考えるケース. どの$k\in N(j)$も$\tilde{G}$上の$ij$間の最短経路上に含まれていない.

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

となります. ここで$\mathrm{deg}(j)=|N(j)|$は頂点$j$の$G$における次数です.

　次に①について考えます. この時はある$k\in N(j)$に対して$k$を含むような$\tilde{G}$上の$ij$間最短経路が存在します (下図).

　この$k$に対して $\tilde{d}_{ik} = \tilde{d}_{ij}-1$ が成り立ちます. 更に他の$k'\in N(j)$ に対しても $\tilde{d}_{ik'} \leq \tilde{d}_{ik}+1 = \tilde{d}_{ij}$が成り立ちます ($k$と$k'$間は$\tilde{G}$の辺で繋がっています. 下図参照).

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立ちます.

以上より, 

① $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

② $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立つので, 

として$d_{ij}$を求めることが出来ます. これでめでたく出力すべき$D=(d_{ij})$を構成することが出来ました.

　アルゴリズム全体の流れとしては

1. $G$の直径が$1$ならば自明な解を出力.
2. そうでないときは, $A^2$を計算することで$\tilde{A}$を計算し, 再帰に投げることで$\tilde{D}$を得る.
3. $X=\tilde{D}A$を計算し, $X$と$\tilde{D}$を用いて各$ij$に対して$d_{ij}$を計算する.
4. $D=(d_{ij})$を出力.

という感じになります. まず再帰の深さは$O(\log n)$で, ステップ2, 3においては行列積を計算しているので計算時間は$O(n^{\omega})$となり, ステップ4では$O(n^2)$かかるので, 全体の計算時間は$O(n^{\omega}\log n)$となります.

4. まとめ

　辺に重みがある場合と無い場合でAPSPの計算量には大きなギャップがあります. 辺重み付きグラフでは$O(n^{2.99})$では解けなさそうである一方, そうでないグラフに対しては$O(n^{\omega}\log n)=O(n^{2.38})$時間で解くアルゴリズムが知られています. もちろん辺重みが無いスパースなグラフに対しては依然として幅優先探索を用いた$O(nm)$の方が高速ですが, 密な場合はSeidel のアルゴリズムの方が高速であると言えます.
　では, 重み付きグラフに対して$O(n^{2.99})$時間でAPSPを計算するアルゴリズムは存在するのでしょうか？これは$P\neq NP$ほどではないですが, 計算量理論においてかなりホットな話題なので, みなさんもぜひ挑戦してみてください.

問題を解きやすいグラフクラスとその拡張

NP-困難な問題はP≠NPの仮定のもとでは多項式時間で解けません. しかしNP-困難な問題を解きたいという場面が少なからずあります. そのようなときには近似を考えたり入力インスタンスのクラスを制限する、ということを考えることが多々あります.

今回のトピックはグラフに対するNP-困難問題に対し, 「グラフクラスを制限することによって多項式時間で解く」アプローチについて広く浅く列挙します.

- 樹状幅を制限したグラフクラス (bounded tree-width)

　樹状幅とはもともと, Robertson・Seymour によるグラフマイナー定理の証明に用いられた重要な概念であり, グラフの「木っぽさ」を表す指標になっています. グラフクラス(有限グラフの無限個の集合)として樹状幅がある定数で抑えられるようなクラスのことをbounded tree-widthと呼びますが, このクラスに対してはクラスカルの定理を用いることでマイナー順序がwell-quasi-orderであることを示し, そうでないクラスについては「樹状幅がboundできない」という情報からグラフの構造上の特徴を示し, 曲面に「だいたい」埋め込んだ後に色々して証明している(らしい)です.
　一方でNP-困難な問題は木に対しては効率よく解けるということがよくあり, 例えば最大独立点集合問題は良い例です. したがって「木っぽい」グラフクラスであるbounded tree-widthに対しても最大独立点集合問題を効率よく解けるんじゃないか、という観点から研究が流行りました.
　樹状幅が高々kであるようなグラフに対しては $O(2^k n)$ 時間で幅が小さい樹状分解を求めることができるので、$k$を定数とみなすとこれは線形時間になっています. これを用いて樹状分解上での動的計画法や分割統治法を用いて様々な問題を解きます. このような(樹状幅などのパラメータを定数とみなしたときに多項式時間で解けるかどうかを議論する)枠組みのことを FPT (Fixed-Parameter Tractability) といいます.
　また, NP-困難な問題以外でも「グラフの直径の計算」「グラフの平均距離の計算」といったクラスPの問題(この２つの問題は $O(n^3)$ で解けるが $O(n^{2.999})$ 時間で解けるアルゴリズムが知られていない) に対しても同様のアプローチを考えることができて, 平均距離の計算を $O(2^{k \log (k)}\cdot n^{1+o(1)})$ 時間で行うアルゴリズムが2009年に提案されています. また, 2016年のSODAで FPT in P の概念が提唱され, (僕の中で)話題になりました.

- 平面的グラフ

　グラフクラスを平面的グラフに限ると高速になるという話がたくさんあります. 例えばグラフの最大カット問題は一般にはNP-困難ですが, 平面グラフに対しては多項式時間で解くことができます.
　一方でグラフクラスを平面的グラフに限ってもハミルトン閉路問題や最大独立点集合問題はなおNP-困難です. 平面的グラフ全体のクラスはbounded tree-width ではないので, 樹状幅によるFPTが通用しません. 実際, $k\times k$の格子グラフの樹状幅は$k$であることを示すことが出来ます.
　平面的グラフの辺数は最大で$3n - 6$なので, スパースです. 辺数$m$のグラフの直径を$o(m^2)$ 時間で計算するアルゴリズムがSETHの仮定のもとで存在しないことが知られています. つまり, スパース(i.e. $m=O(n)$)なグラフの直径には(SETHのもとで)$\Omega(n^2)$時間が必要であることになります. しかし, 平面的グラフの直径・平均距離を $O(n^{11/7} \cdot \mathrm{poly}\log n)$ 時間で行うアルゴリズムが2017年に提案されています(この論文はSODA2017でBest Paper Awardを受賞).

- bounded local tree-width

　bounded local tree-width というグラフクラスに触れます. このクラスに属すグラフ$G$ は次の条件を満たしています:

ある関数 $f(r)$ が存在して, 任意の頂点 $v$ に対して, $v$ から半径 $r$以内にある頂点から誘導される $G$の部分グラフの樹状幅 が $f(r)$ で上から抑えられている.

bounded local tree-width のイメージ.

　局所的な部分の樹状幅が functionally bounded であるということです. 実は平面的グラフは bounded local tree-width です. 実際, $f(r) = 3r-1$ が成り立ちます (この事実は全然自明じゃないです). また, bounded local tree-width なグラフ$G$に対しては $\mathrm{tw}(G) \leq f(\mathrm{diam})$ が成り立ちます. (ここで$\mathrm{diam})$は $G$ の直径です).

したがって,  bounded local tree-width というグラフクラスは bounded tree-width を拡張して平面的グラフを含むようにしたというようなグラフクラスになっています. このクラスに対するFPTのような枠組みは僕はあまり見かけたことはありませんが, 面白い研究題材になるんじゃないかと思っています.

余談 : bounded tree-width と bounded local tree-width のマイナーによる特徴づけ.

グラフマイナー理論において, bounded tree-width をマイナーの言葉で特徴づけしている次の定理が知られています:

グラフクラス $\mathcal{C}$ が bounded tree-width でないことの必要十分条件は, 任意の平面的グラフ $H$ に対して$H$をマイナーとして含むグラフ $G\in \mathcal{C}$ が存在することである.

　この定理は片方の向き (右から左) は自明です. 左の主張を仮定します. $H$ を $n\times n$ の格子グラフであるとすると, $H$をマイナーとして含む $G\in \mathcal{C}$ が存在しますが, $H$の樹状幅は$n$なので, $\mathrm{tw}(G)\leq n$ となります. $n$は任意にとれるので, $\mathcal{C}$は bounded tree-width ではありません.
　この定理の凄いところは左から右です. 実は, 「任意の$n$に対してある$k$が存在して, 樹状幅$k$以上の任意のグラフは$n\times n$の格子グラフをマイナーとして含む」という定理が知られていて, 更に「任意の平面的グラフ$H$に対して$H$をマイナーとして含むような格子グラフ$H'$が存在する」ということが簡単に言えます. この２つの事実を組み合わせることによって左から右の主張を証明することができます. 左の主張を仮定します. 任意の平面的グラフ$H$に対してある$n$が存在して, $n\times n$ 格子グラフ$H'$は$H$をマイナーとして含みます. この $n$に対してある$k$が存在して, 樹状幅$\geq k$の任意のグラフは$H'$, すなわち$H$をマイナーとして含みます. 左の主張の仮定より, $\mathcal{C}$は樹状幅$\geq k$のグラフ$G$を必ず持つので, 右の主張における所望のグラフをこの$G$が得られます.

　では, bounded local tree-width をマイナーの言葉で特徴づけすることはできるのでしょうか？ 実は, 次の定理が知られています[Eppstein, 2000]:

minor-closed なグラフクラス $\mathcal{C}$ が bounded local tree-width でないことの必要十分条件は, 任意のApex graph $H$ に対して$H$をマイナーとして含むグラフ $G \in \mathcal{C}$ が存在することである.

Apex graph とは, 「頂点を一つ取り除くことによって平面的になるようなグラフ」のことです. Apex graph の全体は平面的グラフを含みます. 例えば $n\times n$格子グラフに新たな頂点を一つ追加し, 新たな頂点を格子グラフの$n^2$個の頂点に接続して得られるグラフ$H$を考えましょう. このグラフは直径が2ですが, 樹状幅$=n$なので, bounded local tree-width ではありません. このことから定理の片方の向き (右から左) が言えます.

グラフが平面的であることの必要十分条件一覧

グラフ$G$を考える.
単射 $\phi:\,V\to\mathbb{R}^2$ 及びジョルダン曲線の族 $(J_e)_{e\in E}$ が存在し, 次の性質を満たすとき, $G$ は平面的であると定義します. 特に$G$が平面的グラフであるとき, 組 $(\phi,(J_e)_{e\in E})$を$G$の埋め込みと呼びます.

性質:
$G$ の各辺 $e=\{u,v\}\in E$に対し,

• $J_e$ は 点 $\phi(u)$ と点 $\phi(v)$ を結ぶ.
• $J_e\backslash \{\phi(u),\,\phi(v)\} \cap \left(\bigcup_{v\in V} \{\phi(v)\} \cup \bigcup_{f \in E\backslash \{e\}} J_f\right)=\emptyset$

$J\subseteq \mathbb{R}^2$ がジョルダン曲線であるとは, 適当な連続な単射 $f:[0,1]\to\mathbb{R}^2$の像として$J$が表せることを指します.

ちなみに, いわゆる「平面グラフ」という言葉は「平面に埋め込まれた」グラフを指すのであって「平面に埋め込める」グラフは指しません.

以下は全て同値です:

• グラフ$G=(V,E)$が平面的である.
• $G$は単純なサイクル基底 (任意の辺$e\in E$に対して$e$を含む閉路が高々2つであるようなサイクル基底)を持つ (MacLaneの定理).
• $K_5$ 及び $K_{3,3}$ をマイナーとして含まない (Wagnerの定理).
• $K_5$ 及び $K_{3,3}$ を位相的マイナーとして含まない (Kuratowskiの定理).
• ある$k\in\mathbb{N}$が存在して, $G$の禁止マイナー $\mathrm{Forb}(G)$ ($G$をマイナーとして含まないような有限グラフの全体)に属する任意のグラフは木幅が高々$k$である (Seymour).
• $G$に対応するグラフ的マトロイド$M$の双対マトロイド$M^{*}$をとったとき, これが別のグラフ$G^{*}$に対応するグラフ的マトロイドとなる (このとき$G^*$は平面的グラフの双対グラフになっている).
• 抽象的双対を持つ.

他にもめっちゃ色々あったはず (学んだら追加していく).

（計算が）ヤバイ級数

は有名です(前者はバーゼル問題で後者は部分分数分解で計算できます)。それでは








はどうなるのでしょうか？？　収束するのは明らかです。計算してみましょう。
（厳密な議論が欠けている箇所が幾つかあるので注意してください）

級数をグッと睨むと、





と変形出来そうな気がします。ここでおもむろにwikipediaを参照すると




と書けるらしいので($B_k$はベルヌーイ数)、元の級数は





となります。ここでおもむろにwikipediaを参照すると、




という双曲線関数の謎テイラー展開（ローラン展開）が得られるので、収束半径を無視して$x=\pi$を代入して整理すると




従って





となります。
（ちなみに数値的にもこの値は合致します)

余談

ゼータ関数は



と書ける（らしい）ので、級数に代入して、総和と積分の交換が出来ると信じて更に収束半径諸々を無視して無理やり計算すると




となります（最後の等式は$\sin$のテイラー展開です)。

従って、(多分)




が成り立ちます（多分）

古典的確率論から測度論的確率論へ (条件付き期待値)

0. 概要

条件付き確率は確率論における重要な概念あり, マルチンゲールを定義するために不可欠です. 従って測度論的確率論を勉強していくと必ずこの概念に出会いますが, その理解は非常に難解(気持ちが分かりにくい)で, 一つの大きな壁であるといえます. 本記事は

• 測度論的確率論を勉強してみたけど条件付き期待値のキモチがいまいち分からない.
• なんとなく言葉は知ってるけどちゃんとした定義はよく知らない.

という人向けに, 直感的な説明とちゃんとした定義を織り交ぜて条件付き期待値について解説します. 本記事は測度論的確率論の基本的な概念を前提知識として仮定します.

本記事では古典的確率論における条件付き期待値から出発して測度論的確率論における条件付き期待値を「導出」していきます. 以前の記事で少しだけ条件付き期待値について書いてあるので, 理解の助けになるかもしれません.

1. 古典的確率論における条件付き期待値

条件付き期待値とは, $\mathrm{E}[X|\mathcal{G}]$で表されるスカラー値です. 古典的確率論においては条件付き確率を定義してから条件付き期待値を定義します. つまり$A,B$をそれぞれ事象として, $\mathrm{Pr}(A|B)=\mathrm{Pr}(A\cap B)/\mathrm{Pr}(B)$と定義した後に, 条件付き期待値を



と定義します. つまり古典的確率論では条件付き期待値は確率変数と事象の組に対してスカラー値を割り当てる関数と見なしていて, $\mathrm{E}[X|B]$は(確率変数, 事象)の組を受け取ってスカラー値を返す関数になるわけです. しかし, 測度論的確率論における条件付き期待値は全然異なっています.

2. 確率変数としての条件付き期待値

測度論的確率論では確率空間を$(\Omega,\mathcal{F},P)$の三つ組として定義し, 事象とは$\mathcal{F}$の元であると考えます. また, 確率変数は$\Omega\to\mathbb{R}$の関数であると考えます. 測度論的確率論ではまず条件付き期待値を定義してから条件付き確率を定義するので, 古典的確率論とは定義の順番が逆になります. そこでまず, 条件付き期待値を定義してみることにします.

$\mathcal{B}=\{B_1,\ldots,B_K\}$を$\Omega$の分割とします. つまり各$B_i\subseteq \Omega$であり, しかも$B_i\cap B_j=\emptyset$ (for $i\neq j$) かつ$\bigcup_{i=1}^K B_i=\Omega$を仮定します. 確率変数$X$と$\Omega$の分割$\mathcal{B}$に対し, 確率変数$Y:\Omega\to\mathbb{R}$を



とします. (Fig.1) ここで$\mathrm{E}[X|B_i]$は(古典的な意味での)条件付き期待値だと思ってください. 結論から言うとこの$Y$が条件付き期待値みたいなものになっていて, 気持ちとしては$Y=\mathrm{E}[X|\mathcal{B}]$になります.

FIg.1: $Y$の定義

　イメージとしては, $Y$は確率変数$X$を, 分割$\mathcal{B}$の下で出来るだけ近似しています. $Y$は各分割$B_i$内の二つの要素が区別出来ないという制約の下で出来るだけ$X$っぽい確率変数になっています. なので, より細かい分割に対して同じように$Y$を考えると, 関数としてはより「細かい」ものになっていきます. つまり分割$\mathcal{B}'$を分割$\mathcal{B}$より細かいもの(FIg.2 参照)とすると, $\mathrm{E}[X|\mathcal{B}']$は$\mathrm{E}[X|\mathcal{B}]$よりもより良い近似になっていることが分かります.

Fig.2: $\mathcal{B}$よりも$\mathcal{B}'$の方が細かい分割になっている.

さらに, $Y(\omega)$を$B_i$内で積分すると(直感的な議論だと思って読んでください)

つまり, $\int_{B_i}YdP=\int_{B_i}XdP$ という関係が成り立ちます(この関係が重要です).

3. 測度論的確率論における条件付き期待値の定義

測度論的確率論では事象とは$\sigma$-集合体の要素です. また, 前まではdisjointな事象の集まりを考えていましたが, ここでは部分$\sigma$-集合族について考えます.

確率変数$X$と部分$\sigma$-集合体$\mathcal{G}\subseteq \mathcal{F}$に対して, 条件付き期待値$Y=E[X|\mathcal{G}]$は$\Omega\to\mathbb{R}$は確率変数であり, 以下の条件を満たすものと定義します:

1. $Y$は$\mathcal{G}$-可測 (i.e. 任意の$a\in \mathcal{R}$に対して $\{\omega \in \Omega\,:\,Y(\omega)<a\} \in \mathcal{G}$)
2. 任意の$A\in\mathcal{G}$に対して, $\int_A YdP = \int_A XdP$.

条件2の気持ちは上の式で説明した通りです. 条件1は「近似」の制約の強さを規定しています. つまり「$\mathcal{G}$-可測である」という制約条件の中で$X$を近似したとき, もっともよく近似出来ている確率変数が$Y=\mathrm{E}[X|\mathcal{G}]$であると解釈します. なぜ条件1が制約条件を表すのかについては以前の記事や後に出てくる例を見ると分かり易いと思うので, 後ほど取り上げます.

そもそも本当に条件1,2を満たす$Y$が存在するのかについてですが, ラドン＝ニコディムの定理からalmost everywhereの意味で一意に定まります.

ここではラドン=ニコディムの定理を用いず, 有限加法族$\mathcal{G}$に対して条件付き期待値$Y=\mathrm{E}[X|\mathcal{G}]$をちゃんと構成してみます. すると条件付き期待値について何か掴めるようになると思います. まず有限加法族$\mathcal{G}\subseteq 2^{\Omega}$に対し, 以前の記事で述べた$\Omega$の「都合の良い」分割$\mathcal{B}=\{B_1,\ldots,B_k\}$をとってきます (存在性も証明してあります).
この$\mathcal{B}$に対して1節で考えた$Y$を考えます. すると実は$Y=\mathrm{E}[X|\mathcal{G}]$となることが示せます.

つまり, 有限加法族 $\mathcal{G}$ に対しては条件付き期待値$\mathrm{E}[X|\mathcal{G}]$を1節で説明した方法によって具体的に構成することが出来るようになりました.

また, 条件付き確率$\mathrm{Pr}(A|\mathcal{G})$は, 事象$A$の指示関数$1_A$を用いて



と定義されます.

4. 例 (命題論理式)

SAT(充足可能性判定)問題では命題論理式がCNF形式で与えられます. このとき「充足されるクローズの個数が最大となるような」割り当てを求めるという最大化問題を考えることができます. 例として次の論理式$\phi$を考えます.

また, 各節(clause)$C_j$を



とおきます.

$(x_1,x_2,x_3,x_4)$にそれぞれ等確率に $0$ or $1$ を割り当てると,

$\mathrm{Pr}(C_j$ が充足される$)=1-(0.5)^3$

となり, 確率変数 $X$ を「充足された節の個数」と定義すると, $\mathrm{E}[X]=3-3\cdot (0.5)^3=2.625$ となるはずです. ここで確率空間 $\Omega$ は $\{0,1\}^3$ で, $\sigma$ -集合体 $\mathcal{F}$ は $2^{\Omega}$ とします.

ここで, 4回の(公平なコインによる)コイントスによって$x_1,x_2,x_3,x_4$の割り当てがこの順にランダムに決まっていく過程を考えます.

・$x_1$の値が決定したとき:

$(x_1,x_2,x_3,x_4)$の割り当ては $(x_1,*,*,*)$ となります($*$はランダムビット). 従って事象としては$\{(x_1,r_2,r_3,r_4)\,:\,r_2,r_3,r_4\in \{0,1\}\}\in \mathcal{F}$が発生したことになります. そこでこの事象を含む最小の$\sigma$-集合体 $\mathcal{G}_1$ を考えます. $\mathcal{G}_1$は補集合で閉じていなければならないので

$\mathcal{G}_1=\{ \emptyset, (0,*,*,*), (1,*,*,*), (*,*,*,*)=\Omega \}$

となります. ここで$Y_1=\mathrm{E}[X|\mathcal{G}_1]$を考えましょう. 3節で説明した方法により, 次のように$Y_1$を具体的に構成できます: $\mathcal{G}_1$の「都合の良い」分割として$\mathcal{B}=\{(0,*,*,*),(1,*,*,*)\}$ をとります. これはちゃんと都合の良い分割になっています. ここで$\mathrm{E}[X|(0,*,*,*)],\,\mathrm{E}[X|(1,*,*,*)]$をそれぞれ計算してみます.

・$x_1=0$が定まったとき, 節$C_3$は確率1で充足されるので
$\mathrm{E}[X|(0,*,*,*)]=2-2\cdot (0.5)^2+1=2.5$

・$x_1=1$が定まったとき, 節$C_1,C_2$は確率1で充足されるので
$\mathrm{E}[X|(1,*,*,*)]=2+(1-(0.5)^2)=2.75$

以上より, $Y_1=\mathrm{E}[X|\mathcal{G}_1]$は




となります. 当然のことながら, $\mathrm{E}[Y_1]=0.5\times(2.5+2.75)=2.625=\mathrm{E}[X]$となっています.

・$x_1,x_2$の値が決定したとき:

先ほどと同様の考察を続けます. $\{(x_1,x_2,*,*)\}$を含む最小の$\sigma$-集合体$\mathcal{G}_2$は,



となります ($(0,*,*,*), (1,*,*,*)$が含まれていることに注意). そして分割$\mathcal{B}_2$としては



をとれます. (古典的な意味での)条件付き期待値をそれぞれ計算してやると,



となるので,



ここで, $\mathcal{G}_2$は$\mathcal{G}_1$よりも「細かい」ものになっていることがわかります. この後コイントスを続けていくとより細かいσ-集合体が得られ, 対応する条件付き期待値もまたより細かい関数になっていくことがわかると思います. そして最終的に4つの変数の割り当てが決定すると$\mathcal{G}_4=\mathcal{F}$となり, $Y_4=X$となります.

このように, 「過程が進んでいくにつれて情報が決定していき, 対応する$\sigma$-加法族が細かくなっていく」ことが重要で, その列$(\mathcal{G}_t)$をフィルトレーションと呼びます.

5. まとめ

古典的確率論における条件付き期待値から出発し, これを測度論的確率論における条件付き期待値の概念に(有限加法族に限定して)拡張していきました.
更に, 命題論理式の例を用いて, 観測される事象に応じて$\sigma$-集合体が細かくなっていき(フィルトレーション), それに応じて条件付き期待値がどんどん近似として精度の良いものになっていくことを見ていきました.

これらの概念はマルチンゲールを学ぶ出発点となるので, よく理解しておくと良いと思います.