巨大な頂点数のグラフ上のランダムウォークにおける対称性と臨界現象

洞 彰人 (岡山大学 環境理工学部)述森 義之 (岡山理科大学 理学部)記^{1}

ここでは、古典的な統計力学の簡単な拡散モデルに出ている臨界現象の分類を行い、基礎になる空間（グラフ）の対称性を記述する構造を述べる。また、 2 つの例 (Ehrenfest’s urn, Riffle shuffle) を揚げて、それぞれの場合について考察する。

1 Introduction

1.1 Model

\underline{⋆ Definition} Xを頂点集合、 Eを辺集合とするとき、 Γ = (X, E) を有限ダイグラフと定義する。 N(x) =

{y ∈ X|x → y} とし、 x から yへの推移確率を P_{x,y} ≥ 0 とすると、 ∑_{y∈N(x)} P_{x,y} = 1 である。

各成分が P_{x,y}の行列 P = [P_{x,y}]_{x,y∈X} を推移行列という。 (これからマルコフ連鎖とくに random walk ができる。 ) この推移行列 P は、ある種の対称性があり、後に出てくるさまざまな効果を及ぼす。

(P^{k})_{x,·}が始点が x で k回めの分布になる。

1.2 Convergence to equilibrium

まず、ゆるやかな条件のもとで、

(P^{k})_{x,y} ⟶^{k→∞} \frac{1}{|X|} (for ^{∀}x, y ∈ X)

である。そこで、次のような定義を行う。 \underline{⋆ Definition} variation distance (D(k))

D(k) = \frac{1}{2} ∑_{y∈X} |(P^{k})_{x,y} − \frac{1}{|X|}|
= \frac{1}{2|X|} ∑_{x,y∈X} |(P^{k})_{x,y} − \frac{1}{|X|}| .

1研究集会「表現論とその周辺」 (1996 年 11 月 5 日–11 月 8 日) 講演ノート

2 Examples

2.1 Ehrenfests’ urn and Hamming graph

まず最初に、 n 個のつぼと d 個のボールを用意する。つぼ、ボールともに個々の区別がつくものとする。各つぼに d 個のボールすべてを振り分けて入れる。

次に、ランダムにつぼを選びランダムにボールを 1 つ取り、ランダムにどこかのつぼに入れる。これを、何度か繰り返す。このことを数学的に表すと次のようになる。

頂点集合を X = {1, 2,…, n}^{d}, 辺集合を E = {(x, y) ∈ X × X|#{i|x_{i} ≠ y_{i}} = 1} ただし x = (x_{i})_{i=1}^{d}, y = (y_{i})_{i=1}^{d}とする。このとき Γ = (X, E) は単純グラフ (Hamming graph H(d, n)) となり、 N(x) = {y ∈ X|(x, y) ∈ E} である。ここで N(x) = (n − 1)d であることに注意する。 P_{x,y}は次のようにかけるから、

P_{x,y} = \{ \begin{matrix}1/(n − 1)d & if y ∈ N(x) \\ 0 & if y ∉ N(x), \end{matrix}

n ≥ 3 のとき (P^{k})_{x,y} ⟶^{k→∞} \frac{1}{|X|} であり、 n = 2 のときは (P^{k})_{x,y} −̸→^{k→∞} \frac{1}{|X|} ((...)H(d, 2) は 2

部グラフ) である。特に n = 2 のとき、 Ẽ = E ∪ Δ, Γ̃ = (X, Ẽ) とすれば、

P_{x,y} = \{ \begin{matrix}1/(d + 1) & if y ∈ Ñ(x) \\ 0 & if y ∉ Ñ(x). \end{matrix}

である。

2.2 Riffle shuffle(Gilbert-Shannon-Reed model)

n 枚のカードを用意し、 A : 1 ∼ k番目と B : k + 1 ∼ n 番目に分ける。 (事象 1) これを次のように混ぜる。まず、 A の下から i 枚 (0 ≤ i ≤ k) 机に置き、次に Bの下から j枚 (1 ≤ j ≤ n − k) 机に置く。その次に、 A の下から l枚 (1 ≤ l ≤ k − i) 机に置く。これを、繰り返して A, Bが 0 枚になるまで行う。 (事象 2)

事象 1 では確率 ({n \atop k})/2^{n}をもつ 2 項分布で A, Bに分けられる。事象 2 では、 A, Bそれぞれに p, q枚残っているとき、 A から置かれる確率は p/(p + q)、 Bから置かれる確率は q/(p + q) となる。例えば、事象 1,2 では次のようにカードは動く。 (1 2 3 ⋯ n) → (1 2 3 ⋯ k | k + 1 k + 2 ⋯ n) → (k + 1 1 2 k + 2 3 ⋯ k n − 1 n)

この事象 1,2 において、 rising sequence は 1 つまたは、 2 つ含まれている。

注意『j, j + 1, ⋯, j + k が n 次の置換 (1, ⋯, n) ⟶ (σ(1), ⋯, σ(n)) に含まれる rising sequence であるとは、 σ^{−1}(j) < σ^{−1}(j+1) < ⋯ < σ^{−1}(j+k) であって、 σ^{−1}(j−1) > σ^{−1}(j) とσ^{−1}(j + k + 1) < σ^{−1}(j + k) が成り立つことである。』

それぞれを次のように定めると、 riffle shuffle での推移行列は以下のようになる。 Let X = S_{n}, R = {σ ∈ S_{n} | σ contains 2 rising sequences} ⊃ {(i, i + 1)|i = 1, ⋯, n − 1}, E = {(x, y) ∈ X × X|^{∃}σ ∈ R s.t. σx = y} ∪ Δ, where Δ = {(x, x) ∈ X × X}. Γ = (X, E) : ダイグラフ (ケーリーグラフ)

P_{x,y} = \{ \begin{matrix}\frac{n+1}{2^{n}} & if x = y \\ \frac{1}{2^{n}} & if ^{∃}σ ∈ R s.t. σx = y \\ 0 & otherwise. \end{matrix}

3 The cut-off phenomenon

3.1 Formulation

まず最初に次の 2 つのことを定義しておく。 {Γ_{λ} = (X_{λ}, E_{λ})|λ ∈ Λ} : directed family of graphs. |X_{λ}| → ∞ : infinite-volume limit このときそれぞれのλ ∈ Λに対して、 D_{λ}(k) は次のようになる。 D_{λ}(k) = \frac{1}{2|X_{λ}|} ∑_{x,y∈X_{λ}} |(P_{λ}^{k})_{x,y} − \frac{1}{|X_{λ}|}| (これは一定値に近づく。 )

Def. Cut-off phenomenon at \underline{level 1} ∃k_{λ} ∈ ℕ (for^{∀}λ ∈ Λ) が ”critical time” であるとは、つぎの (i),(ii) を満たすことである。 (i) k_{λ} → ∞ as λ → ∞ (ii) ^{∀}ε ∈ (0, 1),^{∃}λ_{ε} ∈ Λ,^{∃}h_{ε,λ} > 0 s.t.

∘ h_{ε,λ}/n_{λ} → 0 as λ → ∞

∘ if λ > λ_{ε}, 0 ≤ k ≤ k_{λ} − h_{ε,λ} ⇒ D_{λ}(k) ≥ 1 − ε

k ≥ k_{λ} + h_{ε,λ} ⇒ D_{λ}(k) ≤ ε.

ここで、 D_{λ}(k) とλの関係をグラフであらわし、 λの大きさを変化させると次のようになる。

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} k_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} D_{λ}(k)^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 1 ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 1 − ε ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ε  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} k_{λ}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} h_{ε,λ}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} λ < λ′  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} k_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} D_{λ′}(k)^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 1 ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 1 − ε ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ε  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} k_{λ′}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} h_{ε,λ′}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}

上の図よりも分るように、 λが十分大きいとき D_{λ}(k) には以下のことが言える。 λ >> 1 D_{λ}(k) = .. 1 for k ≤ k_{λ} − h_{ε,λ}

D_{λ}(k) = .. 0 for k ≥ k_{λ} + h_{ε,λ} したがって、このとき [k_{λ} − h_{ε,λ}, k_{λ} + h_{ε,λ}] は無視できる。

Def. Cut-off phenomenon at \underline{level 2} ∃k_{λ} ∈ ℕ,^{∃}h_{λ} > 0 (for^{∀}λ ∈ Λ)

(i) k_{λ} → ∞, h_{λ}/k_{λ} → 0 as λ → ∞ (ii) D_{λ}(⌊k_{λ} + θh_{λ}⌋) → c(θ) as λ → ∞ for θ ∈ ℝ

where 0 ≤ c(θ) ≤ 1, c(−∞) = 1, c(∞) = 0.

∘ ◯ Level 2 は critical time k_{λ}の近くでの詳細な現象を記述している。この k_{λ}を macroscopic time とみなせば、 |X_{λ}| ∼ ∞ となる。 θh_{λ} が限りなく小さいとき k_{λ}/h_{λ} は増大する。このとき、任意の ε ∈ (0, 1) に対して、

θ < −θ_{ε} ⇒ c(θ) > 1 − ε

θ > θ_{ε} ⇒ c(θ) < ε.

を満たすようなθ_{ε} > 0 で、 h_{ε,λ} = θ_{ε}h_{λ}とおくと、 λが大きければ、 D_{λ}(⌊k_{λ} + θh_{λ}⌋) = .. c(θ) for −θ_{ε} ≤ θ ≤ θ_{ε}となる。

(注意 k_{λ} + θh_{λ} ∈ [k_{λ} − θ_{ε}h_{λ}, k_{λ} + θ_{ε}h_{λ}].)

3.2 Results at level 2

(A1) Ehrenfests’ urn (i.e. H(d, 2)) の場合. λ = d であるから、 k_{d} = \frac{d}{4} log d, h_{d} = \frac{d}{4}, となり、 c(θ) = Erf(e^{− \frac{θ}{2}} /2\sqrt{2}) である。ただし Erf(z) = \frac{2}{\sqrt{π}} ∫_{0}^{z} e^{−t^{2}}dt である。 (誤差関数)

[Diaconis-Graham-Morrison 1990]

(A2) H(d, n) の場合.λ = (d, n), n ≥ 3 であるから、

k_{(d,n)} = \frac{d}{2}(1 − \frac{1}{n}) log(n − 1)d, h_{(d,n)} = \frac{d}{2}(1 − \frac{1}{n}) となり、 c(θ) は次の 2 つの場合に分けられる。 \underline{case 1} d → ∞ かつ n/d → 0 のとき、

c(θ) = Erf(e^{− \frac{θ}{2}} /2\sqrt{2}) となる。 \underline{case 2} d → ∞ かつ n/d → τ ∈ (0, ∞) のとき、

c(θ) = F_{1/τ}(θ^{∗}) − F_{(1/τ)+(1/e^{θ/2}\sqrt{τ})}(θ^{∗}) となる。

ただし、 1/θ^{∗} = e^{\frac{θ}{2}} \sqrt{τ} log(1 + e^{− \frac{θ}{2}} \sqrt{τ}) であり、 F_{α} は Poisson 分布関数である。すなわち、

F_{α}(z) = ∑_{j=0}^{⌊z⌋} e^{−α} \frac{α^{j}}{j!} .

(B) Riffle shuffle (G-S-R model) の場合. λ = n であるから、 k_{n} = \frac{3}{2} log_{2} n, h_{n} = 1 となり、 c(θ) = Erf(2^{−θ}/4\sqrt{6}) である。 [Bayer-Diaconis 1992]

\underline{Remark} Level 1 となる例をあげておく。 ·S_{n}, GL(n, 𝔽_{q}), reflection group · Q-polynomial distance-regular graph · compact group, compact hypergroup

2 つの例に対して、 d, n を定めたときの critical time を掲載しておく。 (A1) Ehrenfests’ urn

d = 1000 ⇒ \frac{d}{4} log d = .. 1727

d = 10000 ⇒ \frac{d}{4} log d = .. 23026 (B) Riffle shuffle

n = 52 ⇒ \frac{3}{2} log_{2} n = .. 8.55

3.3 Method

P の対称性の効果には次のようなものがある。 ⋆ 群 (Hecke 環) や association scheme(Bose-Mesner 環) の指標や球関数の計算に帰着させる。 ⋆ 第２固有値の縮退距離正則なグラフの場合

spectrum( \begin{matrix}θ_{0} & θ_{1} & … & θ_{d} \\ m_{0} & m_{1} & … & m_{d} \end{matrix} )

κ : valency とすると、それぞれ固有値は−κ ≤ θ_{d} < ⋯ < θ_{1} < θ_{0} = κとなり、第１固有値の重複度 m_{0}は 1 である。これより、推移行列 P_{x,y}は、

P_{x,y} = \{ \begin{matrix}\frac{1}{κ} & if (x, y) ∈ E \\ 0 & if (x, y) ∉ E \end{matrix} ⇒ D(k)^{2} ≤ \frac{1}{4} ∑_{j=1}^{d} m_{j}(\frac{θ_{j}}{κ})^{2k}

となり、 m_{1}(\frac{θ_{1}}{κ})^{2k} は、次のようになる。

m_{1}(\frac{θ_{1}}{κ})^{2k} = exp\{log m_{1} + 2k log \frac{θ_{1}}{κ} \} ここでκ − θ_{1} → 0 と仮定すると、

= .. exp\{log m_{1} − 2k(1 − \frac{θ_{1}}{κ})\}.

次に、 k = _{\frac{1}{2(1− \frac{θ_{1}}{κ})}}(log m_{1} + θ) とおくと、 critical time k_{λ}は_{\frac{log m_{1}}{2(1− \frac{θ_{1}}{κ})}}で、 error width h_{λ}は_{\frac{1}{2(1− \frac{θ_{1}}{κ})}} である。ただし m_{1} は非常に大きいものとする。 (→ ∞)

ここで比較のために、 Cyclic group C_{p} (p : odd) を考えてみる。

P_{x,y} = \{ \begin{matrix}\frac{1}{2} & if y = x ± 1 \\ 0 & otherwise. \end{matrix}

この場合、 m_{1} = 1, κ = 2 となり、 (\frac{θ_{1}}{2} )^{2k} = cos^{2k} \frac{π}{p} = .. e^{−π^{2} \frac{k}{p^{2}}} となる。こんどは k = θp^{2}とおく、 D(⌊θp^{2}⌋) →^{p→∞} c(θ) : cont. fn. 0 ≤ c(θ) ≤ 1, c(−∞) = 1, c(∞) = 0 となる。これより、 k_{p} ≍ h_{p} ≍ p^{2}であるから、\underline{cut-off でない!!}