ぱらぱらめくる『Quantum Probability and Spectral Analysis of Graphs』

目次
Preface
1 Quantum Probability and Orthogonal Polynomials
2 Adjacency Matrices
3 Distance-Regular Graphs
4 Homogeneous Trees
5 Hamming Graphs
6 Johnson Graphs
7 Regular Graphs
8 Comb Graphs and Star Graphs
9 The Symmetric Group and Young Diagrams
10 The Limit Shape of Young Diagrams
11 Central Limit Theorem for the Plancherel Measures of the Symmetric Groups
12 Deformation of Kerov's Central Limit Theorem
その他：Rでいじってみる

Quantum Probability and Spectral Analysis of Graphs (Theoretical and Mathematical Physics)

作者: Akihito Hora,Nobuaki Obata,L. Accardi
出版社/メーカー: Springer
発売日: 2007/07/04
メディア: ハードカバー
この商品を含むブログを見る

Preface
1 Quantum Probability and Orthogonal Polynomials
2 Adjacency Matrices
3 Distance-Regular Graphs
4 Homogeneous Trees
5 Hamming Graphs
6 Johnson Graphs
7 Regular Graphs
8 Comb Graphs and Star Graphs
9 The Symmetric Group and Young Diagrams
10 The Limit Shape of Young Diagrams
11 Central Limit Theorem for the Plancherel Measures of the Symmetric Groups
12 Deformation of Kerov's Central Limit Theorem
その他：Rでいじってみる

Preface

ベルヌーイ乱数を例にとって、その確率測度、モーメントの記述、代数的確率表現、ブラケット記法、確率変数に相当する行列の分解、そのグラフとの関係について概説し、本全体の章立ての説明をする
ベルヌーイ乱数Xとは、+1の値を取る確率が1/2、-1の値を取る確率が1/2であるような確率変数のこと
$P(X=+1) = = P(X=-1) = \frac{1}{2}$ のこと
これを、Xが取りうる値を実数直線全体でとらえなおすと、二つのデルタ関数 $\delta_{-1},\delta_{+1}$ を使って、 $\mu = \frac{1}{2} \delta_{-1} + \frac{1}{2}\delta_{+1}$ と書くこともできる。これが「確率密度関数」であり、確率測度
この確率測度を使えば、m次モーメントは $M_m(\mu) = \int_{-\infty}^{+\infty} x^m \mu(dx)$ と表せて、この値は、mが偶数のときに1、mが奇数のときに0となる
確率変数は、モーメントが表現できれば、別の表現の仕方をしてもよいとされているので、行列を使って表現することにする
天下り式に $A=\begin{pmatrix} 0 \; 1 \\ 1\; 0 \end{pmatrix}, e_0 = \begin{pmatrix}0 \\ 1 \end{pmatrix}, e_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ という行列と列ベクトルとを考えることにする
これらが、ベルヌーイ確率変数を表している、とはどういうことかというと、 $\langle e_0, A^m e_0\rangle = e_0^\dagger \cdot (A^m e_0)$ なる内積がmが偶数のときは1、mが奇数のときは0になるという意味で、m次モーメントになっているという点で「同じ」だから
さらに、このを分解してみよう。
- このとき $(A^+)^2 = 0, (A^-)^2 = 0, A^+ A^- = A^+, A^- A^+ = A^-$ であることに注意すると、 $\langle e_0, A^m e_0 \rangle = \langle e_0, (A^+ + A^-) ^m e_0 \rangle = \sum_{\epsilon_1,...,\epsilon_m \in \{\pm\}} \langle e_0, A^{\epsilon_m} ... A^{\epsilon_1} e_0 \rangle$ となることもわかる
さて。この $A,A^+,A^-$ を $e_0$ にm回作用するということと、その作用後のベクトル $A^m e_0$ とオリジナルのベクトル $e_0$ との内積を取るということを、グラフとして考えてみることにする
$e_0$ というのは、グラフの１点。 $e_1$ というのもグラフの１点と見る。そのとき $A=\begin{pmatrix} 0 \; 1 \\ 1\; 0 \end{pmatrix}$ というのは、 $e_0,e_1$ を２点として、その間にエッジのある（無向グラフの）隣接行列となっている。そして、 $A^+$ は第１頂点から第２頂点への有向エッジ、 $A^-$ は第２頂点から第１頂点への有向エッジになっていて、２頂点からなる有向グラフの隣接行列でもある
さて、その $A^+$ だが、これを $e_0$ に作用すると $e_1$ になり、さらに $A^+$ を作用すると $\begin{pmatrix}0 \\ 0 \end{pmatrix}$ となり、２頂点のグラフから消えてしまう。はじめに $A^+$ を作用し、次に $A^-$ を作用すると $e_0$ に戻ってくる。そういう意味で $\langle e_0, A^m e_0 \rangle$ は $e_0$ を出発し、m歩で、 $e_0$ に帰ってくる歩き方の数になっている（ $A^+$ と $A^-$ とに相当するステップを交互に取るしか、グラフ上を歩くすべはなく、mが偶数なら、元に戻るし、mが奇数なら、別の頂点に到達している)
以上が、とてもシンプルな例での、古典的確率変数、代数的確率表現、確率変数の行列表現とその分解、そのグラフとの対応とグラフ上の歩みの関係である

1 Quantum Probability and Orthogonal Polynomials

*-代数と、*-代数を複素数に対応付ける写像の組を考える。この写像が $\psi(a^*a) \ge 0$ かつ $\psi(1_A) = 1$ のとき、この写像を「状態」と呼び、*-代数と状態とのペアが代数的確率空間を定める
代数的確率空間を、（扱いやすいように）標準的な表現にする。単位ベクトルによって状態があらわされるように*-代数Aを変換することで、それがなされるので、 $(A ,\psi) \to (\pi D, w)$ と変換する。ただし、 $\pi$ はAの要素に作用し、その結果、対応する、状態 $\psi$ は単位ベクトル $w$ に対応することになり、 $D$ がpre-Hilbertスペースになっているという。この標準化した表現はGelfand–Naimark–Segal(GNS)表現と呼ばれる
Prefaceで書いたベルヌーイ確率変数に対応するフェルミオン・フォック空間というものがある。それを拡張・一般化した考え方にInteracting Fock Probability spacesというものがある。それを理解するために、ヤコビ・シークエンスというものが出てきて、このあたりから、「状態数が有限か無限か」などが併せて扱えるようになるとともに、上げ下げ作用の大きさにも規則的な制約を入れたりする必要が出てくる（無限空間で遠くに大きい値を与えすぎると、『確率分布』としてうまくなくなることに対応）
また、測度空間を定めたとして、モーメントを計算できるのが代数的確率変数だが、モーメントの列は無限に続く。この無限に続くモーメント列にも、「ちゃんと有限状態数の空間でまともになるための条件」とか「ちゃんと無限状態数の空間でまともになるための条件」とかが明らかにされてくる。この条件はモーメントを要素とする行列のdeterminantの大小条件として説明されている
また、正規直交基底をなす多項式とかも使われる。
ちなみに、作用素行列は状態の上げ下げへと分解することはベルヌーイ変数で示したが、複雑な確率変数の状態空間を考えるときには、上げ下げでなく、同じ状態の割合を変えるような作用素もあって、それは、作用素行列の分解成分の「対角成分行列」として出てくる、などのことを知っておく必要がある

2 Adjacency Matrices

グラフ、隣接行列、頂点の次数などの基本のおさらい
グラフの隣接行列のスペクトルと言えば、固有値とその重複度とで尽くされる
$\lambda_1 < \lambda_2 < ... < \lambda_s$ が $w_1,w_2,...,w_s$ 個ある、という情報のこと
この情報を確率測度的に $\mu = \frac{1}{|V|} \sum_{i=1}^s w_i \delta_{\lambda_i}$ と書くと、s箇所に高さが重複度に対応するデルタ関数が立っているような関数としても表現できる
これを固有値分布とかスペクトルの分布とか呼ぶ。無限グラフなどの場合は、固有値とその重複度のペアであらわすより固有値分布で表すほうが便利
グラフには頂点集合があるから、その上に関数を定義することができる。その関数に内積を定義することで、この「グラフ頂点を台とする関数」はヒルベルト空間に配置される
グラフ頂点上にデルタ関数 $\delta_x(y)$ というのを定義することにする。これは、グラフのある頂点xに対して、自身に対して１を、非自身頂点に対して0を与えるような関数とする。こうすると $\{\delta_x:x \in V\}$ なる関数の集合がでできるが、これは、先に作ったグラフの頂点集合を台とした関数のヒルベルト空間の正規直交基底になっている
このヒルベルト空間の部分空間であって、先の正規直交基底で張られた部分空間はpreヒルベルト空間（内積空間）になるという。ここにGNS表現が持ち込めて、この部分空間は線形作用素の*-代数になる
こんな感じで、どんなグラフ（無限グラフも含めて）も、その部分グラフに関して有限な*-代数があることになる。有限な部分グラフではどの頂点の次数も有限
結局、グラフがあったら、その隣接行列は部分空間の*-代数(*-subalgebra)になっていて、 $A=A^*$ なので、この*-subalgebraの要素は隣接行列の多項式であらわされることになる
グラフが有限なら直径が有限となるが、その直径がnのとき、 $\{1=A^0,A,A^2,...,A^n\}$ なる隣接行列のn+1個のべき乗列は線形独立な*-代数の要素となり、*-代数の要素をこれらの線形式であらわすことができることになる
こうなれば、グラフの隣接行列について $\langle A^m \rangle = \inf_{-\infty}^{+\infty} x^m \mu(dx)$ となるような $\mu$ を $\langle \rangle$ に関するスペクトルの分布としたい
たとえば、グラフのある点 $o \in V$ に対して、 $\langle a \rangle _o = \langle \delta_o, a \rangle \delta_o$ のように置けば（ $a$ はこのグラフの隣接行列の一つ）、 $\langle A^m \rangle _o$ っていうのは、点 $o \in V$ から自身に戻るm歩の歩き方の通りの数になる。これを点oにおけるVacuum stateと呼ぶ
$\langle A^m \rangle _{xy} = \langle x A^m y \rangle$ は点xから点yへのm歩の歩き方
今、グラフの頂点に重み係数を乗せて、点oから各点へのm歩の歩き方の通りの数に頂点重みをかけて足し合わせる計算を考える。これはある点oを基準として、m=0,1,2,....歩の歩き方の場合の数の重み付き加算になる。これをdeformed vacuum stateと呼ぶらしい
各点の「重みづけ」を点oとの関係（距離とか）を使ってパラメタ化するっていうのもやるらしい( $q^{\partial(i,j)}$ )のような感じで。これをカーネル（関数）と称する。このカーネルは頂点ペアごとに値が決まるので行列の形をしている。Qを用いて表す
そのうえで、 $A^k$ のdeterminant列を問題にするらしい
グラフの層化分解と隣接行列の分解。ある点からの距離を使うと、グラフのすべての点がdisjoint なサブセットに分けられる
今、２点x,yとの関係は、ある点oからの距離を基準にして、 $\partial(o,x) = \partial(o,y)$ か $\partial(o,x) = \partial(o,y) + 1$ か $\partial(o,x) = \partial(o,y)-1$ かそのいずれでもないかの４通りに分けられる
隣接行列の(x,y)成分の値が0のときは、気にしないとする。(x,y)成分が1のときに、 $A^o,A^+,A^-$ のどれか一つを１にして残りの２つの行列の成分は０にするように分解する。どれに１を与えるかは、 $\partial(o,x),\partial(o,y)$ の関係によることにする
これをグラフの隣接行列の量子分解という
隣接代数についてはこちらに少しまとめ直しました
有限グラフのスペクトル分布 $\mu$ のm次モーメントについて $\int_{-\infty}^{+\infty} x^m \mu(dx) = \frac{1}{|V|} Tr(A^m)$ が成り立つ

3 Distance-Regular Graphs

ベルヌーイ確率変数はとてもシンプルでグラフスペクトル的な扱いも単純であった
同様に扱いやすいグラフから入るのが常道
その「代数的確率変数」という視点から、グラフの扱いやすさ( 漸近的に無限グラフが扱える、という意味で…と思われる)を表すと『Distance-Regular』という概念が登場するらしく、まずは、それを扱い、その例として、次章以降に具体的なDistance-Regular GraphsであるHomogeneous trees, Hamming graphs, Johnson graphs, odd graphsなどが具体的に論じられる
ということで、まずはDistance-Regularという概念の説明から入る
グラフの３点x,y,zを考える。 $\partial(x,y)=k$ (x,yの距離がk）であるとき、 $\partial(x,z)=i$ で、かつ、 $\partial(y,z)=j$ であるような点zがグラフにいくつあるかを $p_{i,j}^k$ と表すことにする。Distance-regular グラフのIntersection数という
$p_{i,j}^k = |\{z \in V | \partial(x,z) = i, \partial(y,z)=j\}$ （もしくは $p_{i,j}^k = |\{z \in V | \partial(x,z) = i, \partial(y,z)=j\,\partial(x,y)=k\}$ ）とも表せる
この $p_{i,j}^k$ はx,yの取り方によって一般には変わるが、それが一定であるようなグラフのことをdistance-regularと呼ぶことにする。これがdistance-regular graphの定義である
k-th 距離行列というものを定める。行列要素は２点間の距離がkのときに、k-th 距離行列の要素値を１とし、それ以外を０とするもの。0-th距離行列は、単位行列、1-th(1st)距離行列はいわゆる隣接行列…
- $A_i A_j = \sum_{k=|i-j|}^{i+j} p_{ij}^k A_k$ という式が成り立ったりする
- Distance-regular graphsの距離行列 $A_1$ によｔって構成された*-代数は、k-th距離行列が張る線形空間でもある（ことは容易に確かめられる）
Distance-regular graphであることは、グラフのk-th距離行列が距離行列Aの多項式であらわせることと必要十分条件な関係にもある
隣接行列による*-代数を考え、k-th距離行列が隣接行列の多項式であらわされることとを併せて、vacuume stateなどを扱うことができるし、そのスペクトル分布などを議論することもできる
k-th距離行列が作る*-代数には名前もついていてBose-Mesner 代数という
ここで $\langle \delta_o, A^m \delta_o \rangle = \int_{-\infty}^{+\infty} x^m \mu(dx)$ を考えるとき（スペクトルを考えるとき）、 $w_\epsilon (x) = |\{y \in V_{n+\epsilon}; y \sim x\}|, \epsilon \in \{+,-,o\}$ が大事になるのだったが
$w_\epsilon (x) = p_{1,n+\epsilon}^n$ なる関係になるという意味で、distance-regular グラフは隣接行列・隣接代数のスペクトル分解において特別な位置にあることがわかる

4 Homogeneous Trees

自由群と関係するhomogeneous tree
- $p_{11}^0 =\kappa$
- $p_{1,n}^{n-1} = \kappa -1, n = 2,3,...$
- $p_{1,n-1}^n = 1, n= 1,2,3,...$
- $p_{1,n}^n = 0, n=0,1,2,...$
- $A = A^+ + A^-$ 、 $A^o = 0$
たとえば、 $k=5$ のhomogeneous tree について $\langle \delta_o, A^m \delta_o \rangle> = \frac{\kappa}{2\pi} \int_{-2\sqrt{\kappa -1}}^{+2\sqrt{\kappa-1}} x^m \frac{\sqrt{4(\kappa-1) - x^2}}{\kappa^2-x^2} dx$ という式が得られるという
このグラフがあらわしている測度分布（このグラフで点oからランダムに歩いて行って、m歩目に自身に帰ってくる歩きかたの場合の数をm次モーメントとしたとして、そのようなモーメント列を持つ測度分布）がだということが分かった、ということなのだろう
- この分布をKesten 分布と言う
- ベルヌーイ分布の場合には、モーメントが偶奇で0,1を交代するということがわかっていて、それに対する測度分布が $\frac{1}{2} (\delta_{-1} + \delta{+1})$ である、ということに対応する

頂点間距離に応じて要素値を決めて作る行列Q（カーネル行列）を加えることで、さらに、内積空間的に隣接代数・k-th距離行列代数などが表す世界が広がる
グラフ構造と、*-代数の行列（を量子分解したもの）と、カーネル行列とを使って、極限として $\langle \Psi_0 (B^+ + B^-)^m \Psi_0 \rangle$ が得られるが、この代数的確率変数が取りうる状態空間を $\Gamma$ として $(\Gamma, \{\Psi_n\},B^+,B^-)$ という四つ組を「（フリー）Fock space」と言う。この $\Gamma$ は「不変量」なのだという
フォック空間は、グラフの階層化とも関係している。ある点を取り上げると、そこからの距離によってグラフの全ての点は階層的部分集合に分けられる。距離nの点がなす部分集合 $V_n$ に対して、 $\Psi_n = |V_n|^|-1/2} \sum_|x \in V_n} \delta_x$ とすると、これはいい感じの直交基底の特徴 $\langle \Psi_m, \Psi_n \rangle = \delta_{mn}$ という特徴を持つ。この基底が張る空間をグラフGの階層化に付随するフォック空間と呼ぶ

5 Hamming Graphs

ハミンググラフの定義としては、有限個の要素を持つ集合Fについて、そのd次デカルト積を要素とする。要素間の距離は要素のdペアについて、異なっている個数とする。それを実現したグラフがハミンググラフ
組み合わせ論的にいろいろなことが調べられている

6 Johnson Graphs

別のRegular graphsの例として、Johnson graphsとOdd graphsを扱う
どちらも、どんどん大きくするルールを有するグラフ
Johnson graphsには指数分布と幾何分布が関係づく
Odd graphsにはtwo-sided Rayleigh 分布が関係づく
Johnson graphsは、正の整数vとそれ以下の整数dとで決まるグラフ。 $\{1,2,...,v\}$ という集合の部分集合のうち、要素数がd個のものを対象とする。その対象とする部分集合を頂点とするグラフで、部分集合同士で１個だけ要素が違うとき、お互いに辺を引くというルール
Odd graphsはJohnson graphsに似ている。ｖに奇数 2k-1を定めることにする。集合 $\{1,2,...,2k-1\}$ の部分集合であって、要素数がk-1のそれを頂点とする。エッジは、要素を共有していない場合に引く、と言うルール
このようにみてくると、古典的な確率分布は、何か、規則正しいグラフの隣接代数に紐づいた代数的確率変数となることが多いのではないか…と思えてきたりする

7 Regular Graphs

条件を緩めよう
Distance-regularではなく、Regularなグラフ。すべての頂点の次数が等しいグラフ
Distance-regular graphsではInvariantが出てきた。これを漸近的なInvariantに緩める。Regular graphsではそうなる（らしい）
Growing (ルールを決めたらどんどん大きくできる）Regular graphsを考えることにする
Growingだから、その漸近的極限が議論できる
整数格子はその例
その議論がうまくまわるためにはある３つの制約がある
その制約の下でのGrowing Regular Graphsについて漸近的不変量の議論がなされる

8 Comb Graphs and Star Graphs

Independenceという考え方に話を切り替える
Growing graphsを考える
そのうえで、林衛s津行列を複数の独立ランダム変数の和にできるような場合を扱う
独立とは何かを定義しないと話が進まない
古典的な確率変数の場合の独立は $E(XYXXYXY) = E(X^4)E(Y^3)$ のようなもの。これは可換な確率変数の独立
いくつかの非古典的独立の定義がある
- 期待値で定める独立性
  - 古典独立の場合、 $E[X^{p1}Y^{q1}X^{p2}...X^{pn}Y^{qn}] = E[X^{p1+...+pn}]E[Y^{q1+...+qn}]$
  - ブール独立の場合、 $E[X^{p1}Y^{q1}X^{p2}...X^{pn}Y^{qn}] = E[X^{p1}]E[Y^{q1}]...E[X^{pn}]E[Y^{qn}]$
  - 単調独立の場合、 $E[X^{p1}Y^{q1}X^{p2}...X^{pn}Y^{qn}] = E[X^{p1+...+pn}]E[Y^{q1}]E[Y^{q2}]...E[Y^{qn}]$
  - 反単調独立の場合、 $E[X^{p1}Y^{q1}X^{p2}...X^{pn}Y^{qn}] = E[X^{p1}]E[X^{p2}]...E[X^{pn}]E[Y^{q1+...+qn}]$
- さらに、単項式 $X^p$ を多項式にしても成り立つ
- 自由独立性の場合は、簡単な式にならない
  - $P_1(x),Q_1(x),...,P_n(x),Q_n(x) \in C[x]$ が $E[P_i(X)]=E[Q_i(Y)] = 0 (\forall 1 \le i \le n)$ を満たすならば、 $E[P_1(X)Q_1(Y)...P_n(X)Q_n(Y)] = 0$
  - また、この定義により $\forall P(x),Q(x) \in C[x]$ のとき、 $P(X)$ と $Q(Y)$ とが自由独立
  - ただし、 $C(X)$ は多項式全体を表し、 $C(x)$ は関係式の無い単なる文字を現すものとする
  - なんでこんなことをやっているのか、見通しが悪いが、X,Yが自由独立な時に、それぞれの平均値が0となるように変数のシフトを行うと、それらについて、 $E[P(X)] =E[Q(Y)]=0$ 隣、 $E[XY] = E[X]E[Y]$ となると言う、「独立っぽさ」が見えてくる、と言う、そんな定義になっているそうだ
代数的確率変数の独立を考えるとき、確率変数をグラフと見るなら、グラフの積のようなものが登場するようだ
- それぞれのグラフにある１点を原点としてとり、そこをグラフの積の原点として、組み合わせるような「積」を「★積」と呼ぶ
- ある１つのグラフの原点を取り直して、そのグラフの全点を網羅し、それらについて★積をとったものと、隣接行列の積とに関係がある