Oct. 14, 2011

確率と計算
来嶋 秀治 (九州大学)

本講演のねらい2「乱択アルゴリズムにおいて、乱数に真に求める性質は何か？」

本講演のねらい3「乱択アルゴリズムにおいて、乱数に真に求める性質は何か？」

1. 乱択の威力: ストリーム中の頻出アイテム検知
2. 高度な乱択技法: 組合せ的対象のランダム生成
3. 脱乱択化: ランダムウォークの脱乱択化

乱択の威力[ISAAC 2011]

1. ストリーム中の頻出アイテム検知
緒方 正虎, 山内 由紀子, 来嶋 秀治, 山下 雅史
九州大学

5

ストリームデータ中の頻出アイテム検知
問題: 頻出アイテム検知
Given: (0,1) x =(x1,…,xN) N (順々に)事前には、
N (or log Nの近似値)もわからない。

Find: all s  s.t. f(s)  N
但し f(s) は s が x 中で出現した回数
例1. POSデータ
 ={お茶, 菓子, 乾電池, …, 弁当}
x = お茶, 菓子, 乾電池, お茶, 弁当, ジュース, お茶, ….
例2. IPアドレス
  {0.0.0.0,…,255.255.255.255}
x = 123.45.67.89, 111.11.1.1., 123.45,67,89, 122.122.12.12…

6

頻出アイテム検知の領域複雑度
定理 [Karp, Shenker, Papadimitriou ‘03]

頻出アイテム検知を厳密に行うには，
(|| log (N/||)) bits が必要．

(N >> || >> 1/ とする)
定理 [Karp, Shenker, Papadimitriou ‘03]

決定的

頻出アイテム検知に対するO((1/) log N) bits の偽陽性(近似)アルゴリズムが存在．

(N >> || >> 1/ とする)
o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

単純化: o(log N) bitsで要素数を数えられるか？
問題: 要素数え上げ
Given: x = (a,…,a) N (順々に)Find: N

事前には、
N (or log Nの近似値)もわからない。

アルゴリズム: 数え上げ
0. Set n:= 0.
1. Read an input. If no more input, goto 3.
2. n++, Goto 1.
3. Output n (as N = n).
O(log N) bitso(log N) bits近似アルゴリズム？
 e.g. O(log log N) bits?

7単純化: o(log N) bitsで要素数を数えられるか？
問題: 要素数え上げ
Given: x = (a,…,a) N (順々に)Find: N

事前には、
N (or log Nの近似値)もわからない。

アルゴリズム:数え上げ
Remark
0.• Setn:= 0. N) bitsで表現可能．
NはO(log
1. Readan=input.
If no more input, goto 3.
 N
1,351,127,649,213
2.• n++,
Goto 1.
Nの近似はO(loglog N) bitsで表現可能
3. Output(as Nx=10n).12 N n1.351
つまり、指数部(=log N)がo(log N) bits領域で近似計算できるか？ということ。

o(log N) bits近似アルゴリズム？
表現はO(logN) bitsで可能
 e.g.logO(loglog N) bits?

8単純化: o(log N) bitsで要素数を数えられるか？
問題: 要素数え上げ
Given: x = (a,…,a) N (順々に)Find: N

事前には、
N (or log Nの近似値)もわからない。

アルゴリズム: 数え上げ
0. Set n:=0.
1. Read an input. If no more input, goto 3.
2. n++, Goto 1.
3. Output n (as N = n).
O(log N) bits

不可能？（決定的アルゴリズムでは）

9

10

確率的数え上げ
問題: 要素数え上げ
Given: x = (a,…,a) N (順々に)Find: N

事前には、
N (or log Nの近似値)もわからない。

 ポイントアルゴリズム: 確率的数え上げ
PTM では w.p. 1/2k を
0. Set k:=0.
O(log K) bitsで実現可能！
1. Read an input. If no more input, goto 3.
2. k++, w.p. 1/2k. Goto 1.
3. Output k (as N  2k).
O(log log N) bits

Thm. [Morris ‘78, Flajolet ‘85]
E[2k+1]  N+1

11

確率的数え上げ(改良型)
問題: 要素数え上げ
Given: x = (a,…,a) N (順々に)Find: N

事前には、
N (or log Nの近似値)もわからない。

アルゴリズム: 確率的数え上げ(改良型)
0. Set k:=0, l:=0.
1. Read an input. If no more input, goto 4.
2. l++, w.p. 1/2k.
𝑏
2b
3. If l==2 , k++, and set l := l’ w.p.
∙ 2−1 . Goto 1.
𝑙′
4. Output l and k (as N  l *2k ).
O(log log N) bits
Thm. [Ogata, Yamauchi, K., Yamashita ‘11]
E[l*2k]  N. Pr[|l*2k –N|/N > ] > 1- 

“改良型” を使うと、頻出アイテム検知も可能．(詳細略)ストリームデータ中の頻出アイテム検知
問題: 頻出アイテム検知
Given: (0,1) x =(x1,…,xN) N (順々に)Find: all s  s.t. f(s)  N
但し f(s) は s が x 中で出現した回数

o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

12

事前には、
N (or log Nの近似値)もわからない。

13

ストリームデータ中の頻出アイテム検知
問題: 頻出アイテム検知
Given: (0,1) x =(x1,…,xN) N (順々に)事前には、
N (or log Nの近似値)もわからない。

Find: all s  s.t. f(s)  N
但し f(s) は s が x 中で出現した回数

Thm. [Ogata, Yamauchi, K., Yamashita ‘11]

O(log log N) bits 領域の乱択近似アルゴリズムが存在.
詳細略
o(log N) bitsアルゴリズム？
 e.g. O(log log N) bits?

“ランダム生成”  “数える(積分)”2. 組合せ的対象のランダム生成
マルコフ連鎖モンテカルロ法(MCMC: Markov chain Monte Carlo)

joint with 松井知己 (中央大学)

15

例: 2行分割表のランダム生成
2元分割表

 各セルには非負整数が入る （与えられた）周辺和を満たす

問題
Given: 周辺和
出力: 分割表の一様ランダム生成

1218
5 4 3 7 5 6 30

16

例: 2行分割表のランダム生成
2元分割表

 各セルには非負整数が入る （与えられた）周辺和を満たす

1218
5 4 3 7 5 6 30

5 4 3 0 0 0 12
0 0 0 7 5 6 18

4 3 1 3 1 0 12
1 1 2 4 4 6 18

0 0 0 1 5 6 12
5 4 3 6 0 0 18

5 4 3 7 5 6 30
状態A

5 4 3 7 5 6 30
状態B

5 4 3 7 5 6 30
状態C問題
Given: 周辺和
出力: 分割表の一様ランダム生成

17

例: 2行分割表のランダム生成
2元分割表

 各セルには非負整数が入る （与えられた）周辺和を満たす

1218
5 4 3 7 5 6 30与えられた周辺和を満たす2行分割表の個数を求める問題
#P完全 (NP困難) [‘97 Dyer, Kannan, & Mount]問題
Given: 周辺和

マルコフ連鎖を用いた

出力: 分割表の一様ランダム生成

サンプリング法18

例: 2行分割表に対するマルコフ連鎖 [K & Matsui ‘06]
• j 列目（とj+1列目）を

j j+1

1/(n –1)の確率で選ぶ。
• j 列目と j+1列目に対して

4 3 2 3 0 0 12
1 1 1 4 5 6 18

推移可能な状態に5 4 3 7 5 6 30

等確率で推移する。
+k –k

2 3 5
1 4 5
3 7 10

1/4

+

–k +k

3 2
0 5

1/4

1/4

1/4

2 3
1 4

1 4
2 3

0 5
3 2

19

提案するマルコフ連鎖の特徴定理

提案したマルコフ連鎖 の定常分布は一様分布である.

略証: (X, Y), P(X, Y) > 0  P(Y, X) > 0 かつ P(X, Y) = P(Y, X)
X 4 3 2 3 0 0 12
1 1 1 4 5 6 18
5 4 3 7 5 6 30

Y

4 3 0 5 0 0 12

1 1 3 2 5 6 18
5 4 3 7 5 6 30

(detailed balance equation (X) P(X, Y) = (Y) P(Y, X) )

20

マルコフ連鎖の極限分布
任意の初期状態
推移を繰り返す

状態を出力
状態空間

x
x

x

・・・

x
x

漸近的に定常分布

21

MCMC法のアイデア
1. 所望の分布を定常分布にもつマルコフ連鎖を設計する．

2. 十分な回数推移させて，定常分布からサンプリングする．
何回?

状態空間

x
x

x

・・・

x
x

 (漸近的に)所望の分布に従うサンプリングを実現

問題点は何か？
「何回推移させれば十分か？」近似サンプリング法
 収束スピードの算定• mixing time, total variation distance
完璧サンプリング法
 マルコフ連鎖の推移シミュレーションを工夫 無限回の推移の結果を出力 ( 定常分布に厳密に従う)• Coupling from the past [Propp & Wilson 1996]

単調マルコフ連鎖の設計で効率化

22

MCMC完璧サンプリングの設計例
単調なマルコフ連鎖
 Isingモデル[Propp &Wilson 96]
 Pottsモデル（クラッターモデル）
 tiling [Wilson 01]
 2行分割表 [K & Matsui 06]
 離散化Dirichlet分布 [Matsui & K 07]
 待ち行列ネットワーク [K & Matsui 08]
 Q-Ising モデル [Yamamoto, K & Matsui 08]
それ以外のCFTP 根付き全張木 [Propp &Wilson 98]
乱数ベクトルの記憶容量に関する問題
 Wilson の read onceアルゴリズム [Wilson 00]
 Fillのinterruptibleアルゴリズム [Fill 98]

23

参考文献
• 来嶋秀治, 松井知己, “完璧にサンプリングしよう！”
オペレーションズ・リサーチ, 50 (2005),
第一話「遥かなる過去から」, 169--174 (no. 3),
第二話「天と地の狭間で」, 264--269 (no. 4),
第三話「終りある未来」, 329--334 (no. 5).
• 玉木久夫, 乱択アルゴリズム, 共立出版, 2008, 3000円
 「ORアーカイブ」でダウンロード可能
http://www.orsj.or.jp/~archive/menu/03_50.html

 来嶋のHP
http://www.kurims.kyoto-u.ac.jp/~kijima/
 “資料”からダウンロード可能 2行分割表の完璧サンプリング法のデモ (JAVAアプレット)

24サンプリングアルゴリズム --最近の動向と今後の課題
解決済み (多項式性)
 高次元凸体上の一様分布/対数凹分布[Dyer, Frieze, & Kannan 91], [Lovasz & Vempala 07]

 パーマネント/2部グラフの完全マッチング[Jerrum, Sinclair, & Vigoda 04], [Stefankovic, Vempala, & Vigoda 09]

Ising モデル/白黒画像 [Jerrum & Sinclair 93], [Propp &Wilson 96]

未解決問題 (多項式性):
 2元分割表 (u.a.r.) 順序イデアル (u.a.r.) Tutte多項式 マトロイド基 (u.a.r.) Pottsモデル

不可能性
一般の対数劣モジュラ分布に対して， [K 09+]
(RP  NPの下) 多項式時間サンプリング法は存在しない．

25

「乱択アルゴリズムにおいて、乱数に真に求める性質は何か？」

脱乱択化 (derandomization)

3. ランダムウォークの脱乱択化
来嶋 秀治 (九州大学)
古賀 健太郎 (FANUC)
牧野 和久 (東京大学)

27

ランダムウォーク
トークンがグラフ上をランダムウォークする.
 0: 初期分布 (トークンは確率0vで頂点vに居る)
 P: 推移確率行列 (確率Puvで頂点u頂点vに移動)
 時刻tの確率分布t:=0Pt (頂点vに居る確率 (t)v )

a
1/3

b

1/3

d

1/3

e
c

28

ランダムウォーク
トークンがグラフ上をランダムウォークする.
 0: 初期分布 (トークンは確率0vで頂点vに居る)
 P: 推移確率行列 (確率Puvで頂点u頂点vに移動)
 時刻tの確率分布t:=0Pt (頂点vに居る確率 (t)v )

.3

.2

d

a
.1
b

.4

e
c

29

ランダムウォーク (複数トークンによる分布の近似)
N個のトークンがグラフ上を独立にランダムウォークする.
 0: 初期配置 (0  0/N)
 P: 推移確率行列 (確率Puvで頂点u頂点vに移動)
 時刻tの期待配置t := 0Pt (t  t/N)

.3

.2

a
.1
b

d
.4

1/3
1/3

c

1/3

e

30

ランダムウォーク (複数トークンによる分布の近似)
N個のトークンがグラフ上を独立にランダムウォークする.
 0: 初期配置 (0  0/N)
 P: 推移確率行列 (確率Puvで頂点u頂点vに移動)
 時刻tの期待配置t := 0Pt (t  t/N)(Nが非常に大きければ, )トークンを約2:4:1:3の割合で隣接点にばらまいている.

.3

.2

a
.1

決定的過程でも大差ない?

b

d
.4

1/3
1/3

c

1/3

e

31

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t=0

e=<c,d,e>
1/3
1/3
e
1/3

32

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

33

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

34

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

35

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

36

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

37

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

38

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

39

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

40

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

41

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t(0,1)

e=<c,d,e>
1/3
1/3
e
1/3

42

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)
a=<d,b,c,a,a,a,b,c,c,c>
.2
.3
d
a
.1
b

.4

c

t=1

e=<c,d,e>
1/3
1/3
e
1/3

43

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)

t=1

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

44deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

45

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

46

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

47

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

48

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

49

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t(1,2)

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

50

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t=2

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>
a
1/3
.4
1/3
e
.1
1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

51

deterministic RW (Propp機械; rotor-router)
N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) 時刻tの配置t (t  t ???)t=2

a=<d,b,c,a,a,a,b,c,c,c>d=<e,c,a>.2.3de=<c,d,e>aRemark1/3
 各トークンは単位時間に1回だけ移動..4
1/3
e.1
 各ノードは時刻tに居るトークンすべてを,
時刻t+1までに移動させる.
1/3cbb=<a,b,c>d=<a,a,a,c,e,e>52Propp機械はランダムウォークを模倣できるか?

N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) (エルゴード)マルコフ連鎖は定常分布に収束する
 時刻tの配置t (t  t ???)t=2
 “平滑化”される.
a=<d,b,c,a,a,a,b,c,c,c>
 Propp機械はランダムウォークを模倣できるか?
d=<e,c,a>.2
 “平滑化”できるか?
.3de=<c,d,e>a “だま”はできないのか?
Remark1/3

 各トークンは単位時間に1回だけ移動..4.1
 各ノードは時刻tに居るトークンすべてを,
時刻t+1までに移動させる.

1/3

e

1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>誤差の下界定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.

53

54

だまのできる例
定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.
t=0<b,b,b,b,a,a,a,a><a,a,a,a,b,b,b,b>
a

b

55

だまのできる例
定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.
t=1<b,b,b,b,a,a,a,a><a,a,a,a,b,b,b,b>
a

b

56

だまのできる例
定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.
t=2<b,b,b,b,a,a,a,a><a,a,a,a,b,b,b,b>
a

b

57

だまのできる例
定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.
t=3<b,b,b,b,a,a,a,a><a,a,a,a,b,b,b,b>
a

b

58

だまのできる例
定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数.
t=4<b,b,b,b,a,a,a,a><a,a,a,a,b,b,b,b>
a

b

59

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=0ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>60

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=1ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>61

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=2ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>62

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=3ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>63

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=4ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>64

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=5ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>65

だまのできる例2
h=<a,b,c,d,e,f,g,h>ha=<a,b,c,d,e,f,g,h>t=6ab=<a,b,c,d,e,f,g,h>g=<a,b,c,d,e,f,g,h>
g

b

f

c
c=<a,b,c,d,e,f,g,h>f=<a,b,c,d,e,f,g,h>ee=<a,b,c,d,e,f,g,h>d
d=<a,b,c,d,e,f,g,h>誤差の下界定理 [K, Koga, Makino 10+]ある多重有向グラフG=(V,E),
ある初期状態, あるrotor-routerが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊸ ⊭∨≭∩≷≷

但し, mは多重グラフの頂点数,枝数,
(𝑇)

𝜒𝑤 :

# トークン @ w V , @ 時刻 T > 0 in Propp 機械(𝑇)
𝜇𝑤 : E[# トークン] @ w V , @ 時刻 T > 0 in RW

66

(𝑇)

主結果 2

𝜒𝑤 :

# トークン @ w V , @ 時刻 T > 0 in Propp 機械67(𝑇)

𝜇𝑤 : E[# トークン] @ w V , @ 時刻 T > 0 in RW

定理 [K, Koga, Makino 10+]対応する推移確率行列Pの固有値がすべて非負ならば,任意の多重有向グラフ, 任意の初期状態, 任意のrotor-router,
任意の頂点w, 任意の時刻tについて,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊷ ∨∲≭ ⊡ ≮∩ ⊵ ≭≡≸ ≮ ∫ ≮ ∫ ∳⊶ ⊷ ∴≭≮ ∫ ≏∨≭∩≷≷≩∲≦∱∻∺∺∺∻⊷≧ ≩但し, n,mは多重グラフの頂点数,枝数. niはJordan cellのサイズ.
Remark「推移確率行列Pの固有値がすべて非負」という条件.
 reversible lazy Markov chainはこの条件を満たす.
 MCMC法で使われるマルコフ連鎖
 +Pが対称  Pは半正定値行列

68

Propp機械はランダムウォークを模倣できるか?

N個のトークンがグラフ上を移動する.
 0: 初期配置 (0 = 0) : “rotor router” (比率Puvで頂点u頂点vに“順次”移動) (エルゴード)マルコフ連鎖は定常分布に収束する
 時刻tの配置t (t  t ???)t=2
 “平滑化”される.
a=<d,b,c,a,a,a,b,c,c,c>
 Propp機械はランダムウォークを模倣できるか?
d=<e,c,a>.2
 “平滑化”できるか?
.3de=<c,d,e>a “だま”はできないのか?
Remark1/3

 各トークンは単位時間に1回だけ移動..4.1
 各ノードは時刻tに居るトークンすべてを,
時刻t+1までに移動させる.

1/3

e

1/3

b

c

b=<a,b,c>d=<a,a,a,c,e,e>

チップ数に依存しない.

先行研究と本研究の成果
定理 [Cooper & Spencer 2006]
Zd上で, 任意の初期状態, 任意のrotor-router,
任意の頂点w, 任意の時刻tについて,(dのみに依存する)定数Cdが存在して,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊷ ≃
≤
≷
≷

70

単一頂点誤差に関する先行研究
2006

Cooper, Spencer

2007

Cooper, Doerr,
Spencer, Tardos

2008

Cooper, Doerr,
Friedrich, Spencer

無限のk正則木上のPropp機械

2009

Doerr, Friedrich

2010+

K, Koga, Makino(this work)

Z2上のPropp機械 C2  7.83 (上右下左) C2  7.29 (上下左右)

Zd上のPropp機械
 誤差  Cd
Z1上のPropp機械
 C1  2.29
 誤差  ( 𝑘𝑇)

at time T

有限多重有向グラフ G上のPropp機械
 誤差 4mn+O(m){0,1}d上のPropp機械
 誤差 O(d3) (頂点数のpoly log)

主結果 2定理 [K, Koga, Makino 10+]対応する推移確率行列Pの固有値がすべて非負ならば,任意の多重有向グラフ, 任意の初期状態, 任意のrotor-router,
任意の頂点w, 任意の時刻tについて,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊷ ∨∲≭ ⊡ ≮∩ ⊵ ≭≡≸ ≮ ∫ ≮ ∫ ∳⊶ ⊷ ∴≭≮ ∫ ≏∨≭∩≷≷≩∲≦∱∻∺∺∺∻⊷≧ ≩但し, n,mは多重グラフの頂点数,枝数. niはJordan cellのサイズ.
Remark「推移確率行列Pの固有値がすべて非負」という条件.
 reversible lazy Markov chainはこの条件を満たす.
 MCMC法で使われるマルコフ連鎖
 (+) Pが対称  Pは半正定値行列

71

72

主結果 3
定理 [K, Koga, Makino 10+]{0,1}d超立方体の稜線グラフに対して,
任意の初期状態, 任意のrotor-router,
任意の頂点w, 任意の時刻tについて,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊷ ∳ ≤∳ ∫ ≏∨≤∲∩≷≷∲

JohnsonグラフJ(d,c) =(VJ,EJ)
VJ={S  {1,…,d} | |S|=c},
EJ={ {S,T}  VJ2 | |ST|=2 }定理 [K, Koga, Makino 10+]
JohnsonグラフJ(d,c)に対して,
任意の初期状態, 任意のrotor-router,
任意の頂点w, 任意の時刻tについて,⊯⊯⋂∨≔ ∩ ⊡ ⊹∨≔ ∩⊯⊯ ⊷ ∲≣∳⊢ ∨≤ ⊡ ≣∩∲ ∫ ≏∨≣∳⊢ ∨≤ ⊡ ≣∩∩≷≷頂点数に対して対数多項式上界

(𝑇)

𝜒𝑤 :

# トークン @ w V , @ 時刻 T > 0 in Propp 機械
73

(𝑇)
証明概略
𝜇𝑤 : E[# トークン] @ w V , @ 時刻 T > 0 in RW≴≘≘≶∨≴∩ ∺∽ ⋂∨≶≳∩
≳∽∰ ≮
≯
≘
∨
≴
∩
≳ ≶ ∨ ≩∩ ∺∽ ≭ ≩≮ ≴ ⊸ ∰ ≪ ≩ ∼ ≘ ≶ ∻Cooper & Spencer 2006の手法を

≘
≘
∨
≔
∩
∨
≔
∩
⋂≷ ⊡ ⊹ ≷ ∽≶∲≖ ≩∽∰≘≶∨≔ ⊡∱∩ ⊡∱補題 1⊡≐ ≔ ⊡≳≶∨≩∩⊡∱∨⊽≶ ∨≩∩∻ ≷∩ ⊡ ≐ ≔ ⊡≳≶∨≩∩∨≶∻ ≷∩⊢ ∺推移確率行列Pで理解「時刻t以前Propp機械, 時刻t以後RW」過程. (初期配置は0(と同一)とする.)
(w;t,T): 時刻Tの期待トークン配置.

≔ ⊡∱≘⋂∨≔ ∩ ⊡ ⊹∨≔ ∩ ∽ ∨⊳ ∨≷∻ ≴ ∫ ∱∻ ≔ ∩ ⊡ ⊳ ∨≷∻ ≴∻ ≔ ∩∩∺
≷

≷

≴∽∰

⊳ ∨≷ ∻ ≴ ∫ ∱ ∻ ≔ ∩ ⊡ ⊳ ∨≷ ∻ ≴ ∻ ≔ ∩ ∽∨≴∩ ⊡∱≘≶≘ ≘ ⊡≶∲≖ ≩∽≘≶∨≴⊡∱∩

Remark (w;T,T) = T
 (w;0,T) = T

⊢
⊡
⊡
⊡
≔
≴
∱
≔
≴
≐ ∨⊽≶ ∨≩∩∻ ≷∩ ⊡ ≐ ∨≶∻ ≷∩

74

関連研究

 IDLA (Internal Diffusion-Limited Aggregation)• Levine & Peres 2005
 Information Spreading• Doerr, Friedrich, & Sauerwald 2008
• Doerr, Friedrich, Kunnemann, & Sauerwald 2009
 Hitting time, Cover time
• Friedrich & Sauerwald 2010
• Holroyd & Propp 2010+
cf. [K, Koga, Makino 10+]定理 [Holroyd & Propp 2010+]
単一トークンのPropp機械を考える.
Ftv := 時刻0からtまでに頂点vを訪れた回数.
任意の有限グラフについて,|Ftv/t - *v|  O(mn/t)

ただし*は対応するマルコフ連鎖の定常分布.

|tv/N - tv| O(mn/N)

今後の課題 上下界の一致. (O(mn), (m))
 組合せ構造に由来するグラフに対するpolylogの上界.
 Blanket time vs Mixing time.
 MCMC法の脱乱択化.
 乱数とは？
 乱択アルゴリズムにおける「乱数」の持つべき性質は？
 準モンテカルロ (quasi Monte Carlo) カオス系列 (Chaos time series)

P. Gopalan, A. Klivans. R. Meka, D. Stefankovic, S. Vempala, E. Vigoda
An FPTAS for #Knapsack and Related Counting Problems, (FOCS 2011)75

4. まとめ
1. 乱択の威力: ストリーム中の頻出アイテム検知
 O(log log N)領域計算法
2. 高度な乱択技法: ランダム生成  数える
3. 脱乱択化: ランダムウォークの脱乱択化

今後の課題77「乱択アルゴリズムにおいて、乱数に真に求める性質は何か？」今後の課題78「乱択アルゴリズムにおいて、乱数に真に求める性質は何か？」

講演者の現在確率的アルゴリズムについて、いろいろ研究• 最速RW (hitting time, cover time)[with 野中良哲, 小野廣隆, 山下雅史]•順列集合上のオンライン線形最適化[with 安武 翔太, 畑埜 晃平, 瀧本 英二, 竹田 正幸]•自動掃除ロボットは部屋の隅を上手に掃除できるか？
[with 平原昂樹, 山下雅史]
etc.

The endThank you for the attention.