ぱらぱらめくる『Free Probability and Random Matrices』
Free Probability and Random Matrices【電子書籍】[ James A. Mingo ]
- ジャンル: 本・雑誌・コミック > 洋書 > COMPUTERS & SCIENCE
- ショップ: 楽天Kobo電子書籍ストア
- 価格: 10,691円
- 姉妹編[http://users.uoa.gr/~dcheliotis/Seminario/FPSeminar.pdf:title=Lectures on the Combinatrorics of Free Probability
Lectures on the Combinatorics of Free Probability (London Mathematical Society Lecture Note Series)
- 作者: Alexandru Nica
- 出版社/メーカー: Cambridge University Press
- 発売日: 2006/09/07
- メディア: ペーパーバック
- この商品を含むブログを見る
- Asymptotic Freeness of Gaussian Random Matrices
- The Free Central Limit Theorem and Free Cumulants
- Free Harmonic Analysis
- Asymptotic Freeness for Gaussian, Wigner, and Unitary Random Matrices
- Fluctuations and Second Order Freeness
- Free Group Factors and Freeness
- Free Entropy : The Microstates Approach via Large Deviations
- Free Entropy : The on-microstates Approach via Free Fisher Information
- Operator-Valued Probability Theory and Block Random Matrices
- Deterministic Equivalents, Polynomials in Free Variables, and Analytic Theory of Operator-Valued Convolution
- Brown Measure
Asymptotic Freeness of Gaussian Random Matrices
- 確率測度
- 特性関数
- キュムラント母関数。特性関数の対数を取る。特性関数は0周りで正なので対数が取れる。。この係数がの(古典的な確率論での)キュムラント
- モーメントとキュムラントの間には、相互に変換関係が存在する
- 一次元標準正規確率変数には特徴がある
- 一次モーメントは0、二次モーメントは1
- 、
- このという値は、という集合を2つずつのペアに分ける場合の数になっている
- そのことは、2n個から、1番を取り出し、その相手方の選び方2n-1通りを考え、残りの2(n-1)個のペアの作り方の場合分けに相当することからという漸化式から示せる
- ここに、1次元標準正規分布のモーメントが、整数分割・組み合わせと結びついていることが示された
- 正規分布のモーメント・キュムラントと組み合わせとの関係の導入に引き続き、一般化が以下のようになされる
-
- ランダムな正規行列(GUE: Gaussian Unitary Ensemble)
- 行列の各成分が複素生起乱数であって、その平均は0、分散のもの
- と、共役転置でもある
- 共役転置という制約はあるが、それ以外は、行列の成分の実部・虚部の値は(正規分布制約の下で)独立
- 対角成分の虚部は0なので、都合、個の正規乱数によって行列が決まる。この個の乱数を長さの乱数ベクトルと見ると、多次元正規確率変数と同様の捉え方も可能となる。
- この長さN^2の正規乱数ベクトルは、N個の平均0、分散1/Nの正規乱数と、N(N-1)/2*2個の平均0、分散1/2Nの正規乱数になっており
- N^2個の変数同士の共分散は0である
- したがって、この分散共分散行列の逆行列(対角成分が(N,N,...,2N,2N,...)であって、非対角成分が0の行列)によって指定されるN^2次元正規分布に従う正規変数ベクトルによって定まるランダム行列であることがわかる
- また、正規変数ベクトルの場合に分散共分散行列が全体を決めていたが、行列の場合には、変数行列の二乗行列のトレースにその性質が備わっているという
- 具体的には、NxN正規行列は、それを規定する行列B(対角成分が(N,N,...,2N,2N,...)であって、非対角成分が0の行列)を用いて、長さN^2のベクトルとでなる内積が決まる。この内積の値は、XをNxN行列として扱ってを計算したときのトレースと比例関係にある
- したがってがと行列の二乗のトレースで置き換えて表現できることがわかる
- Rで確認しておく
- ランダムな正規行列(GUE: Gaussian Unitary Ensemble)
-
-
- このあたりの、「行列のべき乗のトレース」を問題にするあたりが、*-代数を使った代数的確率論で、行列を確率変数と見たときの、スペクトルに行列のべき乗のトレースを云々、という話につながる
- また、隣接行列のk乗の対角成分はk歩でのサイクルの歩き方の場合の数になることなどとも関係してくる。場合の数は、A->Bの歩き方の場合の数と、B->Cの歩き方の場合の数との積がA->B->Cの歩き方の場合の数になったりするから、ペアを作って、それらの積を取る、という処理が歩き方の場合の数の数え上げと関係する
- 隣接行列と異なるのは、隣接行列の場合には、エッジがあれば1、なければ0というような成分値であるのに対して、正規行列では、平均0、分散1(ないしは1/N,1/2N)というように、「確率変数」になっていること。したがって、「歩き方の場合の数」も数え上げる対象ではなく、「期待値」として取り扱う対象になっていること
-
- なお、特性関数・その係数としてのモーメント、キュムラント母関数・その係数としてのキュムラントの間に、組み合わせ関係・組み合わせを用いた分解公式がある(Cumulants_and_moments)があり、また、高階微分と組み合わせ論との関係にはWick's theoremというものがあり、量子力学で役割を果たすが、そのことについても、この章では触れられている
- この組み合わせのことを考え、さらにそれを幾何学的組み合わせ論に繋げるには、partitionとかnoncrossing partitionとかいう概念を理解することが有用らしいので、ぱらぱらめくる『Noncrossing partitions』をやってから、戻ってくることにする
The Free Central Limit Theorem and Free Cumulants
- この先は、ちょっと今の自分には無理。数学的に正しいことが整然と書かれているのはその通りなようだけれど、そのような構成がどういう『意味』を持っているかについての気持ちがついていかないと、「そー、それで」感に押し流される…
- 何かあるのだろう。正規分布のモーメントが、整数のペアリングと関係しており、ペアリングには、なんでも蟻のペアリングのnoncrossing partitions的なペアリングとがあり、その両者を区別することと、その区別に対応する、確率事象・統計モデルとの区別があるのだろうと思う
- ここまで書くと、「なんでもかんでも自由に組み合わせたり順列できたりする」か、何かしら制約のある中(Noncrossingがその制約)での自由な組み合わせ・順列の場合とで確率変数のモーメントが変わってくる→分布が異なる→「なんでも自由~正規乱数的」と言っても、制約依存だ、とそういう話、なのだろうと想像される
- それよりは、整数列の分割がトポロジー的な意味づけができることの方が、幾何には近そうな感じ。特に、曲面の幾何・・・
Free Harmonic Analysis
Asymptotic Freeness for Gaussian, Wigner, and Unitary Random Matrices
Fluctuations and Second Order Freeness
Free Group Factors and Freeness
Free Entropy : The Microstates Approach via Large Deviations
Free Entropy : The on-microstates Approach via Free Fisher Information
Operator-Valued Probability Theory and Block Random Matrices
Deterministic Equivalents, Polynomials in Free Variables, and Analytic Theory of Operator-Valued Convolution
Brown Measure
複体と代数的確率変数
- この文書(non-commutative probability theory for topological data analysis)をぱらぱらめくっている
- こちらで、グラフのスペクトル解析と代数的確率論についてメモした
- この文書は、、もう少し踏み込んで、単体的複体、その先にあるトポロジカルデータアナリシスにまで代数的確率論を進めている
- ものすごく大雑把に言うと
- 行列は確率変数
- この代数的確率変数には、古典的な変数の独立とは異なる独立の概念がある
- 行列はグラフでもある
- グラフは分解・合成ができる
- グラフの分解・合成には、グラフとしての「独立」があり、この「グラフとしての独立性が、行列としての独立性としてどう現れるのか」と言う話と、「確率変数としての独立性が、確率変数を表している行列にどのように現れるのか」とが繋がってくる
- グラフの分解・合成には、グラフスペクトル解析の流れのなかで、隣接行列・ラプラシアン・Normal行列の分解・合成ルールとして議論される
- その先に、「単体的複体」ー「代数的確率」ー「分解・合成」ー「独立」の議論が出てくる模様で、どのように独立で、どのように独立でないか、が、「単体的複体」のトポロジカル解析に結びつく、と言うこと(らしい)
- グラフでは、隣接行列とそのべき乗が、何歩で生き合えるかの情報を表す。特に、対角成分を考えるとそれはサイクルに関すること。この行列のべき乗が代数的確率論ではモーメント。ラプラシアンの場合は、木の情報
- 単体的複体になると、「サイクル」の代わりに、k-次単体となる。グラフにおける、クリーク
- ポセットに話を持っていくと、ベッチ数を係数とした式、オイラー標数とかになってくる
- 単体の頂点、エッジ、faces、高次facesを行・列に対応づけて、その帰属関係に向きも考慮して±1を立てると、単体的複体を表す行列ができる
- 単体的複体はそれをさらに進めることでやはり行列ができる
- 単体のオーバーラップ関係が、そこに行列演算の分離・分解・ルールなどを用いたものとして表現される
- Betti number, Betti curve, Betti forestとか、そんな具合に広がる模様
グラフ・スペクトル解析と代数的確率論のための雑多なメモ
- グラフを考える
- 無向グラフと有向グラフがある。有向グラフの中にはとくにDirected Acyclic Graph(DAG)と呼ばれるものがあり半順序・ポセットと関係がある
- グラフのノード集合は量子力学では、量子の取りうる「場所のようなもの」を表しており、ノード集合に連結情報を持たせたグラフの隣接行列は「物理量」を表しているとされる。行列には変換するものという見方もあり、「物理量は作用素」であるとの見方もされる。あるときにこの物理量を観察すると、状態に応じて「期待値」が観察される。物理量とその状態とから「期待値」が得られるという関係は、代数的確率論としてまとめられている。そのとき、グラフ~物理量~作用素は確率変数であると見られる
- ここで用いたのは隣接行列である。正方行列である
- DAG・ポセットの方では、グラフの接続行列というものを使う。
ノード数xエッジ数の非正方行列である - 半順序関係のTrue/Falseで正方行列の値の1/0を決める
- ポセットのノード集合には離散的確率質量分布の情報幾何的座標(座標)を付与することができる
- 座標が付与されたポセットは『ある確率的現象』とその『特定の確率質量分布』とを表している
- グラフを用いた確率的現象と分布との小まとめ
- グラフ自体は「確率的現象~確率変数」を表している
- グラフのノード数の長さのベクトルはその「確率的現象~確率変数」の特定の状態を表している
- 確率変数の特定の状態を「確率質量・密度(関数)」と呼ぶことにすれば、量子力学・物理量の方では、「状態を表すベクトル」と1対1対応する行列が存在することが知られており、それを「密度行列」と呼ぶ
- DAG・ポセットの方では、各ノードに確率質量を乗せることもできるし、それをポセットの半順序情報に基づいて表現しなおすと座標が各ノードに与えられる
- グラフの代数
- グラフのゼータ関数
- グラフのゼータ関数と言えば、伊原のゼータ関数。これは「サイクル」の長さ別の列挙総数の母関数
- グラフの隣接行列のk-乗の(i,j)成分はノードi からjへのk歩の歩き方の場合の数になるので、伊原のゼータ関数は、iからiへの歩き方の場合の数という意味では、隣接行列のk=0,1,.....-乗のトレース(対角成分の和)と関係しているとも(多分)言える
- 他方、接続行列・接続代数にもゼータ関数があって、これはまさにポセットで座標を扱うときに登場する関数。ゼータ関数は積分的な仕事をする。メビウス関数はその逆で微分的な仕事をする
- ただし、接続代数のゼータ関数が、「リーマンのゼータ関数〜素数の積」と繋がることの理解は、ちょっと難航しそうな感じ。なぜなら、このWiki記事の記載にある通り、接続代数のゼータ関数は「普通と違って」いて、Dirichlet seriesにまで戻らないとゼータ関数との共通性が見えない、と言うことらしいから("Zeta function of an incidence algebra, a function that maps every interval of a poset to the constant value 1. Despite not resembling a holomorphic function, the special case for the poset of integer divisibility (割り切れること) is related as a formal Dirichlet series to the Riemann zeta function." Wikiより引用)
- 他方、隣接行列や、エッジ行列を用いた「グラフの伊原ゼータ関数」の方は、サイクルをPrimesとする母関数である、と言う意味合いでの解釈が可能であり、リーマンのゼータ関数が、全自然数について、素数を用いて理解するための母関数である、と言う側面の対応が取りやすい
- このPDFはこの辺りを理解するために必要そうだ
- 確率変数の期待値とモーメント
- モーメント列はある意味で確率変数をよく特定する
- 確率変数の1次モーメントは平均値であり、いわゆる確率変数の期待値
- 隣接行列が属する*-代数的確率変数では、状態に対してがm次モーメントを表す
- 量子物理学的には、これが「観察されるモーメントの期待値」。それがスカラー値を持つということは、グラフのノードが「空間の座標」や「エネルギーの強さ」などの何かしらの「値」を持つものと想定していて、その値の平均やバラツキとしてのモーメントを観測する、という文脈(らしい)
- グラフノードに一様な分布があるとき、隣接行列の0乗に関する1次モーメント(平均)は1(ノード数を標準化したもの)になるようだ。隣接行列の1乗に関する1次モーメントはノードの次数の平均値になるだろう(グラフを二次元多様体と考え、ノードが多様体上に均一に分布していると考えれば、面積のようなものになるだろうか)
- 他方、ポセットの接続代数の方にも期待値というものがある。座標はそのノードに相当する期待値である。また指数型分布族表現(対数確率分布を線形分解した表現)の言葉では、線形要素(取りうる状態を並べたものに重みを与えたベクトル)に対応する期待値が座標である
- 特定のノードを基準にすること
- グラフは全体で一つの情報を表していて、特に1つのノードが特別ということはない、というのが原則である
- ただし、ある一つのノードを取り上げると、そこからのグラフ距離というものが定まる
- 隣接行列・隣接代数では、ある基準ノードからのグラフ距離によって階層的に排他的部分集合に分解して論を進めることがある
- これを利用すると、隣接行列を次の3つに分解することができる
- ノードx,yの間にエッジがあるとき、隣接行列Aの(x,y)成分は1。今、からx,yへの距離は、前者が1大きいか、後者が1大きいか、同じかの3通りになる
- これを用いてと分けるというのがその分解方法である
- 他方、ポセットにも基準ノードを定められることがある。例えば、ある1ノードが存在し、ポセット上の全てのノードに到達できるようなポセットや、その逆に、ポセット上の全てのノードからある1ノードに到達できるとしたとき、そのノードを基準ノードにすることで、ポセットの隣接行列の分解が可能になる
- グラフから作る正方行列と伊原のゼータ関数
- 基本は隣接行列
- エッジの隣り合わせ関係を表す行列(Edge matrix (エッジ本数x2)行、(エッジ本数x2)列の行列)
- グラフから全域木を取り出し、残ったエッジで作る正方行列も伊原のゼータ関数には使える
-グラフから作る非正方行列
-
- ノードxエッジの非正方行列〜接続行列。これからゼータ関数が作れる
- ノードとエッジの関係で行列を作るのがOKならば、グラフを単体的複体的に捉え、m次元単体とn次元単体との包含関係行列を考えることができて、。これは接続行列を含む
- そのほか
- 隣接代数的に考えるとき、3ノード間のグラフ距離関係を考えることがある。ノードx,y,zがあったときに、となっているとする。x,y の取り方によらずこのようなノードzの数がと一定であるようなグラフをDistance-regularグラフと呼ぶ。単純な素粒子を確率変数と見たときのグラフはこのような性質をもつらしい。逆に言うと隣接代数として見たときに単純な確率変数はdistance-regularだと言うことらしい
- Regularグラフと言うものも、ある。全てのノードの字数が等しいグラフのことで、これも隣接代数とその代数的確率論の展開がやりやすい(漸近的特性が定まりやすい)
- 独立
- 代数的確率論では、確率変数にいくつかの異なる「独立」の概念がある。これは期待値がある意味で変数ごとに分離して計算できると言うことを意味し、古典的な確率変数の古典的な独立の概念も、代数的確率論の枠組みで再定義できる
- 独立な確率変数は、複雑な確率現象を分解して理解する部品となる可能性の高いものであり、重要(なはず)
ぱらぱらめくる『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であるような確率変数のこと
- のこと
- これを、Xが取りうる値を実数直線全体でとらえなおすと、二つのデルタ関数 を使って、と書くこともできる。これが「確率密度関数」であり、確率測度
- この確率測度を使えば、m次モーメントはと表せて、この値は、mが偶数のときに1、mが奇数のときに0となる
- 確率変数は、モーメントが表現できれば、別の表現の仕方をしてもよいとされているので、行列を使って表現することにする
- 天下り式にという行列と列ベクトルとを考えることにする
- これらが、ベルヌーイ確率変数を表している、とはどういうことかというと、なる内積がmが偶数のときは1、mが奇数のときは0になるという意味で、m次モーメントになっているという点で「同じ」だから
- さらに、このを分解してみよう。
- このときであることに注意すると、となることもわかる
- さて。このをにm回作用するということと、その作用後のベクトルとオリジナルのベクトルとの内積を取るということを、グラフとして考えてみることにする
- というのは、グラフの1点。というのもグラフの1点と見る。そのときというのは、を2点として、その間にエッジのある(無向グラフの)隣接行列となっている。そして、は第1頂点から第2頂点への有向エッジ、は第2頂点から第1頂点への有向エッジになっていて、2頂点からなる有向グラフの隣接行列でもある
- さて、そのだが、これをに作用するとになり、さらにを作用するととなり、2頂点のグラフから消えてしまう。はじめにを作用し、次にを作用するとに戻ってくる。そういう意味ではを出発し、m歩で、に帰ってくる歩き方の数になっている(ととに相当するステップを交互に取るしか、グラフ上を歩くすべはなく、mが偶数なら、元に戻るし、mが奇数なら、別の頂点に到達している)
- 以上が、とてもシンプルな例での、古典的確率変数、代数的確率表現、確率変数の行列表現とその分解、そのグラフとの対応とグラフ上の歩みの関係である
1 Quantum Probability and Orthogonal Polynomials
- *-代数と、*-代数を複素数に対応付ける写像の組を考える。この写像がかつのとき、この写像を「状態」と呼び、*-代数と状態とのペアが代数的確率空間を定める
- 代数的確率空間を、(扱いやすいように)標準的な表現にする。単位ベクトルによって状態があらわされるように*-代数Aを変換することで、それがなされるので、と変換する。ただし、はAの要素に作用し、その結果、対応する、状態は単位ベクトルに対応することになり、がpre-Hilbertスペースになっているという。この標準化した表現はGelfand–Naimark–Segal(GNS)表現と呼ばれる
- Prefaceで書いたベルヌーイ確率変数に対応するフェルミオン・フォック空間というものがある。それを拡張・一般化した考え方にInteracting Fock Probability spacesというものがある。それを理解するために、ヤコビ・シークエンスというものが出てきて、このあたりから、「状態数が有限か無限か」などが併せて扱えるようになるとともに、上げ下げ作用の大きさにも規則的な制約を入れたりする必要が出てくる(無限空間で遠くに大きい値を与えすぎると、『確率分布』としてうまくなくなることに対応)
- また、測度空間を定めたとして、モーメントを計算できるのが代数的確率変数だが、モーメントの列は無限に続く。この無限に続くモーメント列にも、「ちゃんと有限状態数の空間でまともになるための条件」とか「ちゃんと無限状態数の空間でまともになるための条件」とかが明らかにされてくる。この条件はモーメントを要素とする行列のdeterminantの大小条件として説明されている
- また、正規直交基底をなす多項式とかも使われる。
- ちなみに、作用素行列は状態の上げ下げへと分解することはベルヌーイ変数で示したが、複雑な確率変数の状態空間を考えるときには、上げ下げでなく、同じ状態の割合を変えるような作用素もあって、それは、作用素行列の分解成分の「対角成分行列」として出てくる、などのことを知っておく必要がある
-
2 Adjacency Matrices
- グラフ、隣接行列、頂点の次数などの基本のおさらい
- グラフの隣接行列のスペクトルと言えば、固有値とその重複度とで尽くされる
- が個ある、という情報のこと
- この情報を確率測度的にと書くと、s箇所に高さが重複度に対応するデルタ関数が立っているような関数としても表現できる
- これを固有値分布とかスペクトルの分布とか呼ぶ。無限グラフなどの場合は、固有値とその重複度のペアであらわすより固有値分布で表すほうが便利
- グラフには頂点集合があるから、その上に関数を定義することができる。その関数に内積を定義することで、この「グラフ頂点を台とする関数」はヒルベルト空間に配置される
- グラフ頂点上にデルタ関数というのを定義することにする。これは、グラフのある頂点xに対して、自身に対して1を、非自身頂点に対して0を与えるような関数とする。こうするとなる関数の集合がでできるが、これは、先に作ったグラフの頂点集合を台とした関数のヒルベルト空間の正規直交基底になっている
- このヒルベルト空間の部分空間であって、先の正規直交基底で張られた部分空間はpreヒルベルト空間(内積空間)になるという。ここにGNS表現が持ち込めて、この部分空間は線形作用素の*-代数になる
- こんな感じで、どんなグラフ(無限グラフも含めて)も、その部分グラフに関して有限な*-代数があることになる。有限な部分グラフではどの頂点の次数も有限
- 結局、グラフがあったら、その隣接行列は部分空間の*-代数(*-subalgebra)になっていて、なので、この*-subalgebraの要素は隣接行列の多項式であらわされることになる
- グラフが有限なら直径が有限となるが、その直径がnのとき、なる隣接行列のn+1個のべき乗列は線形独立な*-代数の要素となり、*-代数の要素をこれらの線形式であらわすことができることになる
- こうなれば、グラフの隣接行列についてとなるようなをに関するスペクトルの分布としたい
- たとえば、グラフのある点に対して、のように置けば(はこのグラフの隣接行列の一つ)、っていうのは、点から自身に戻るm歩の歩き方の通りの数になる。これを点oにおけるVacuum stateと呼ぶ
- は点xから点yへのm歩の歩き方
- 今、グラフの頂点に重み係数を乗せて、点oから各点へのm歩の歩き方の通りの数に頂点重みをかけて足し合わせる計算を考える。これはある点oを基準として、m=0,1,2,....歩の歩き方の場合の数の重み付き加算になる。これをdeformed vacuum stateと呼ぶらしい
- 各点の「重みづけ」を点oとの関係(距離とか)を使ってパラメタ化するっていうのもやるらしい()のような感じで。これをカーネル(関数)と称する。このカーネルは頂点ペアごとに値が決まるので行列の形をしている。Qを用いて表す
- そのうえで、のdeterminant列を問題にするらしい
- グラフの層化分解と隣接行列の分解。ある点からの距離を使うと、グラフのすべての点がdisjoint なサブセットに分けられる
- 今、2点x,yとの関係は、ある点oからの距離を基準にして、かかかそのいずれでもないかの4通りに分けられる
- 隣接行列の(x,y)成分の値が0のときは、気にしないとする。(x,y)成分が1のときに、のどれか一つを1にして残りの2つの行列の成分は0にするように分解する。どれに1を与えるかは、の関係によることにする
- これをグラフの隣接行列の量子分解という
- 隣接代数についてはこちらに少しまとめ直しました
- 有限グラフのスペクトル分布のm次モーメントについてが成り立つ
3 Distance-Regular Graphs
- ベルヌーイ確率変数はとてもシンプルでグラフスペクトル的な扱いも単純であった
- 同様に扱いやすいグラフから入るのが常道
- その「代数的確率変数」という視点から、グラフの扱いやすさ( 漸近的に無限グラフが扱える、という意味で…と思われる)を表すと『Distance-Regular』という概念が登場するらしく、まずは、それを扱い、その例として、次章以降に具体的なDistance-Regular GraphsであるHomogeneous trees, Hamming graphs, Johnson graphs, odd graphsなどが具体的に論じられる
- ということで、まずはDistance-Regularという概念の説明から入る
- グラフの3点x,y,zを考える。(x,yの距離がk)であるとき、で、かつ、であるような点zがグラフにいくつあるかをと表すことにする。Distance-regular グラフのIntersection数という
- (もしくは)とも表せる
- このはx,yの取り方によって一般には変わるが、それが一定であるようなグラフのことをdistance-regularと呼ぶことにする。これがdistance-regular graphの定義である
- k-th 距離行列というものを定める。行列要素は2点間の距離がkのときに、k-th 距離行列の要素値を1とし、それ以外を0とするもの。0-th距離行列は、単位行列、1-th(1st)距離行列はいわゆる隣接行列…
- という式が成り立ったりする
- Distance-regular graphsの距離行列によtって構成された*-代数は、k-th距離行列が張る線形空間でもある(ことは容易に確かめられる)
- Distance-regular graphであることは、グラフのk-th距離行列が距離行列Aの多項式であらわせることと必要十分条件な関係にもある
- 隣接行列による*-代数を考え、k-th距離行列が隣接行列の多項式であらわされることとを併せて、vacuume stateなどを扱うことができるし、そのスペクトル分布などを議論することもできる
- k-th距離行列が作る*-代数には名前もついていてBose-Mesner 代数という
- ここでを考えるとき(スペクトルを考えるとき)、が大事になるのだったが
- なる関係になるという意味で、distance-regular グラフは隣接行列・隣接代数のスペクトル分解において特別な位置にあることがわかる
4 Homogeneous Trees
- 自由群と関係するhomogeneous tree
- 、
- たとえば、のhomogeneous tree についてという式が得られるという
- このグラフがあらわしている測度分布(このグラフで点oからランダムに歩いて行って、m歩目に自身に帰ってくる歩きかたの場合の数をm次モーメントとしたとして、そのようなモーメント列を持つ測度分布)がだということが分かった、ということなのだろう
- この分布をKesten 分布と言う
- ベルヌーイ分布の場合には、モーメントが偶奇で0,1を交代するということがわかっていて、それに対する測度分布がである、ということに対応する
- 頂点間距離に応じて要素値を決めて作る行列Q(カーネル行列)を加えることで、さらに、内積空間的に隣接代数・k-th距離行列代数などが表す世界が広がる
- グラフ構造と、*-代数の行列(を量子分解したもの)と、カーネル行列とを使って、極限としてが得られるが、この代数的確率変数が取りうる状態空間をとしてという四つ組を「(フリー)Fock space」と言う。このは「不変量」なのだという
- フォック空間は、グラフの階層化とも関係している。ある点を取り上げると、そこからの距離によってグラフの全ての点は階層的部分集合に分けられる。距離nの点がなす部分集合に対して、とすると、これはいい感じの直交基底の特徴という特徴を持つ。この基底が張る空間をグラフGの階層化に付随するフォック空間と呼ぶ
5 Hamming Graphs
6 Johnson Graphs
- 別のRegular graphsの例として、Johnson graphsとOdd graphsを扱う
- どちらも、どんどん大きくするルールを有するグラフ
- Johnson graphsには指数分布と幾何分布が関係づく
- Odd graphsにはtwo-sided Rayleigh 分布が関係づく
- Johnson graphsは、正の整数vとそれ以下の整数dとで決まるグラフ。という集合の部分集合のうち、要素数がd個のものを対象とする。その対象とする部分集合を頂点とするグラフで、部分集合同士で1個だけ要素が違うとき、お互いに辺を引くというルール
- Odd graphsはJohnson graphsに似ている。vに奇数 2k-1を定めることにする。集合の部分集合であって、要素数がk-1のそれを頂点とする。エッジは、要素を共有していない場合に引く、と言うルール
- このようにみてくると、古典的な確率分布は、何か、規則正しいグラフの隣接代数に紐づいた代数的確率変数となることが多いのではないか…と思えてきたりする
7 Regular Graphs
- 条件を緩めよう
- Distance-regularではなく、Regularなグラフ。すべての頂点の次数が等しいグラフ
- Distance-regular graphsではInvariantが出てきた。これを漸近的なInvariantに緩める。Regular graphsではそうなる(らしい)
- Growing (ルールを決めたらどんどん大きくできる)Regular graphsを考えることにする
- Growingだから、その漸近的極限が議論できる
- 整数格子はその例
- その議論がうまくまわるためにはある3つの制約がある
- その制約の下でのGrowing Regular Graphsについて漸近的不変量の議論がなされる
8 Comb Graphs and Star Graphs
- Independenceという考え方に話を切り替える
- Growing graphsを考える
- そのうえで、林衛s津行列を複数の独立ランダム変数の和にできるような場合を扱う
- 独立とは何かを定義しないと話が進まない
- 古典的な確率変数の場合の独立はのようなもの。これは可換な確率変数の独立
- いくつかの非古典的独立の定義がある
- 代数的確率変数の独立を考えるとき、確率変数をグラフと見るなら、グラフの積のようなものが登場するようだ
- それぞれのグラフにある1点を原点としてとり、そこをグラフの積の原点として、組み合わせるような「積」を「★積」と呼ぶ
- ある1つのグラフの原点を取り直して、そのグラフの全点を網羅し、それらについて★積をとったものと、隣接行列の積とに関係がある
9 The Symmetric Group and Young Diagrams
- この章以降は対称群を代数的確率論・量子確率論的に扱い、その漸近的極限を考えるらしい(グラフ一般の話ではないので、自分の本来の興味から外れるので、パラパラめくるのはここまでとする)