7.4 Two General Settings D3 杉原堅也

7.4 節の内容 定理 7.4.1 定理 7.4.2 定理 7.4.3 　　この節でやることを大雑把に言うと， 　 ランダムグラフ G(n, p) を一般化したもの（正確にはもっと一般的なものを扱う）を対象として、マルチンゲールを定義し、2つの不等式を紹介する．

定義 1 A = {0, 1} B = {vw, wx, xv} A, B をある集合とし， を関数 g : B → A の集合とする． 例： A = {0, 1}, B をグラフG (節点数n) の節点ペアの集合， とすれば， g ∈ AB は n節点のグラフとみなせる．　 A = {0, 1} B = {vw, wx, xv} v g(vw)=1 g(wx)=1 g(xv)=0 w x 全ての節点ペア b ∈ B で p1b = p, p0b = 1－ p とすれば， g はランダムグラフ G(n, p).

定義 2 gradation を固定， を汎関数（e.g., クリーク数）とする． マルチンゲール を次のように定義． B1 定義 2 B2 B3 B4 gradation 　　　　　を固定， 　　　　　　　　　を汎関数（e.g., クリーク数）とする． マルチンゲール 　　　　　　　　　を次のように定義． b ∈ Bi で g(b)=h(b) = E[L(g)] : 定数． (h) = L(h) ． b ∈ Bi+1 で g(b)=h(b) Xi(g) の値は g(b) が「公開される」につれて L(g) に近づく．

定義 2 gradation を固定， を汎関数（e.g., クリーク数）とする． マルチンゲール を次のように定義． B1 定義 2 B2 B3 B4 gradation 　　　　　を固定， 　　　　　　　　　を汎関数（e.g., クリーク数）とする． マルチンゲール 　　　　　　　　　を次のように定義． b ∈ Bi で g(b)=h(b) b ∈ Bi+1 で g(b)=h(b) Xi の値は b ∈ Bi だけが寄与する． Xi+1 の値は b ∈ Bi+1－ Bi の寄与が新たに加わる．

リプシッツ条件 汎関数 L の，gradation 　 に関するリプシッツ条件． 　 全ての　　　　　　　に対し， 　 h, h’ が 上でのみ異なる

定理 7.4.1 定理 7.4.1 　 L が　　　　　　　　　　　　　　　　に関するリプシッツ条件を満足するとき，対応するマルチンゲールは 　 全ての　　　　　　　　　　　で，

系 7.2.2 （前回のスライド） X0,…,Xm をマルチンゲール、X0 = c とし、 |Xi+1–Xi| ≦ 1 が 0 ≦ i < m について成り立つとする。 このとき、次が成り立つ。

定理 7.4.1（証明） H wh’ を条件付き確率とすると H: b ∈ Bi+1 で h’(b) = h(b) となる 　 h’ ∈ AB の集合. H wh’ を条件付き確率とすると (条件は，b ∈ Bi+1 で h(b) = g(b))， （つまり，　　　　　　　　　　　　　　　　　　　　　　　　　　 　）

定理 7.4.1（証明） H H[h’] H: b ∈ Bi+1 で h’(b) = h(b) となる h’ ∈ AB の集合. qh* を以下の条件付き確率とすると，

定理 7.4.1（証明） h’ と h* は Bi+1－Bi 上でのみ異なるので， 仮定からリプシッツ条件　　　　　　　　　　　　が成立．

定理 7.4.2 定理 7.4.2 　　　　　　　　　 とおく． 　 L がリプシッツ条件を満足するとき， 　 全ての 　　 で，

定理 7.2.1（前回のスライド） X0,…,Xm をマルチンゲール、X0 = 0 とし、 |Xi+1–Xi| ≦ 1 が 0 ≦ i < m について成り立つとする。 l > 0 を任意に選ぶとき、次が成り立つ。 (Azumaの不等式)

系 7.2.2 （前回のスライド） X0,…,Xm をマルチンゲール、X0 = c とし、 |Xi+1–Xi| ≦ 1 が 0 ≦ i < m について成り立つとする。 このとき、次が成り立つ。 ※初期値が 0 でない場合に拡張しただけ。

準備 Alonら(1997)による本発表2つ目の設定． 確率空間を有限で独立な Yes/No choice とする．indexを i ∈ I． choice i は確率 pi で Yes． この確率空間上の確率変数 Y が与えられる． ・ I: 質問の有限集合. ・ 質問 i ∈ I をオラクルに投げると確率 pi で Yes. (choice) ・ 各質問の答えがYes/Noとなる確率は互いに独立． ・ 質問の答えによって決まる値が Y.

準備 i 以外の質問の答えを固定した時，質問 i の答えが反転しても Y は高々 ci だけ増減するとする． ci を i の effect と呼ぶ． C を全ての ci の上界とする． 　　　　 を choice i の分散とよぶ．

Solitaire Game ソリティアゲーム － 1人で遊ぶゲーム (e.g., パズル，クロンダイク) Paul はある値 Y を見つけるため，（いつも正しく答えを返す）オラクルに質問 i ∈ I を投げる． 　　 － Paul は前の質問に依存した質問を選んでよい． 　　 － Paul の戦略は決定木で表せる． root 3 Yes 1つのパスに対してY の値が1つ決まる No 2 1 Yes No パス（line of questioning）が含むchoice i の分散の合計を そのline of questioning の分散とよぶ． 3 4 Yes ・・・ Yes No

定理 7.4.3 定理 7.4.3 全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する． 　 全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する． 　 Paul の戦略において，任意のline of questioningの分散が高々 σ2 のとき，全ての α> 0 に対し， ただし，α (> 0) は　　　　　　　　　　　　を満たす．

定理 7.4.3 の応用 ε= δ = 1とする． 　　C = O(1) のとき，α→∞ かつ α= o(σ) とすれば， 　 右辺は

定理 7.4.3 の応用 たいてい Paul は全ての i ∈ I を質問するので， 　 ランダムグラフ G(n, p) 上で枝リプシッツ条件を満たす Y を考える．ただし，p = p(n) → 0 とする． I を　　　　　 個の節点ペアに枝があるかない(Yes/No)とし， 　　全ての pi = p （ランダムグラフ）, C = 1 （リプシッツ条件）なので， 　 このとき，α→ ∞，　　　　　　　　　 ならば，右辺は

グラフ特徴量のリプシッツ条件 （前回のスライド） グラフ上の特徴量 f について、枝 1 本だけ異なる 2 つのグラフ H,H’ において | f(H)–f(H’)| ≦ 1 が成り立つとき、f は枝リプシッツ条件を満たすという。同様に、頂点 1 個だけ異なる 2 つのグラフ H,H’ において上式が成り立つとき、頂点リプシッツ条件を満たすという。

定理 7.4.3 (再褐) 定理 7.4.3 全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する． 　 全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する． 　 Paul の戦略において，任意のline of questioningの分散が高々 σ2 のとき，全ての α> 0 に対し， ただし，α (> 0) は　　　　　　　　　　　　を満たす．

定理 7.4.3 （証明） 簡単のため E[Y] = 0 とする． また，upper tailを示す．つまり， を示す． とおくと， は ． 　 　　　　　　　　　　　　は　　　　　 ． 以降，　　　　　　　　　　　　　　　　　　　　　 を示せばよい． なぜなら， Markov Bound

定理 7.4.3 （証明） まず次のことを示す． 全てのε> 0 に対し，δ> 0 が存在して， 　 全てのε> 0 に対し，δ> 0 が存在して， 　　0 ≦ p ≦ 1 と |a|≦ δ に対し， 左辺を a に関してテイラー展開． （左辺） = 1 + 0 + a2p(1－p)/2 + ・・・ aj ( j ≧3 ) の係数は，高々 δを， |a| ≦δが　　　　　　　　　　を満たすように取ると， 1 + x ≦ ex を使って右辺を得る．

定理 7.4.3 （証明） 決定木の深さに関する数学的帰納法で(7.2)を示す． M = 0 のとき，Y は定数なので成立． Paul の最初の質問に対して， 　　p: 確率，c: effect，v = p(1－p)c2 を分散とする． 　　また，μy, μn を最初のオラクルがYes/Noを返すときの Y の条件付き期待値とする． 　　・ E[Y] = 0 なので，0 = pμy + (1－p)μn. 　　・ effect の定義から，|μy －μn|≦ c. 　　・ パラメータ b (|b| ≦ c) を用いて， 　　　μy = (1－p)b, μn = －pb とかく． root Yes No μy μn Yes No Yes ・・・ Yes No No

定理 7.4.3 （証明） μy = (1－p)b, μn = －pb． 先に示した から， μy μn ・・・ root Yes No 先に示した から， root Yes No μy μn Yes No Yes ・・・ Yes No No

定理 7.4.3 （証明） Ay をオラクルがYesを返したときの e λ(Y－μy) の条件付き期待値とする．(E[ Y－μy | Yes ] =0.) An をオラクルがNoを返したときの e λ(Y－μn) の条件付き期待値とする．(E[ Y－μn | No ] =0.) Yes/Noが帰ってきたとき，部分木に関して Y の分散は高々σ2－ v，深さは M－1． 帰納法の仮定から， root Yes No μy μn Yes No Yes ・・・ Yes No No

定理 7.4.3 （証明） root Yes No μy μn Yes No Yes ・・・ Yes No No