The 123 Theorem

こんにちは. のぶしみです. 最近Mathlogという数学の記事共有サービスを使って記事を書くことにハマっておりまして, つい最近, エキスパンダーグラフの紹介記事を書きました. しかし今まで5年以上このブログをやってきているので, メジャーなトピックはmathlogで紹介し, マイナーなトピックは引き続きこのブログで紹介していきたいと思います.

そこで今回は123 Theoremと呼ばれる定理を紹介します. 変わった名前ですが, 次の定理です:

定理 (123 Theorem)

$X,Y$を同じ分布に従う実数上の二つの独立な確率変数とする. このとき

$$\Pr[|X-Y|\geq 2] \leq 3 \Pr[|X-Y|\geq 1].$$

123 Theoremという名前は不等式に出てくる三つの定数に由来します. 私がこの定理に初めて出会ったのは2021年1月に研究室の後輩とAlon & Spencer の The Probabilistic Method の輪読していた時に第1章の演習問題として出題されていた時でした. 私は基本的に本を読むときは演習問題は頑張って解く習慣があるので, 頑張って証明しようしたのですがかなり苦戦して, 結局丸一日を溶かして以下のようにして示すことが出来ました. 実は同じ証明が[1]に載っていてビックリしたので紹介します.

証明.

$x_1,\ldots,x_m\in\mathbb{R}$を$X$の分布に従って独立にサンプリングされた$m$個の点とし, $T_r=\{(i,j):|x_i-x_j|\leq r\}$とする ($(i,i)\in T_r$とする). まず

$|T_2| \leq 3|T_1|$ ......(1)

を示す. この主張は定理の離散化みたいなもので, 実は(1)を示せば良いということが以下の議論から分かります:

$$\mathrm{E}[|T_2|]=m+m(m-1)\Pr[|X-Y|\leq 2]$$

$$\mathrm{E}[|T_1|]=m+m(m-1)\Pr[|X-Y|\leq 1]$$

および(1)より

$$m+m(m-1)\Pr[|X-Y|\leq 2] \leq 3m+3m(m-1)\Pr[|X-Y|\leq 1].$$

これを整理すると,

$$\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1] + \frac{2}{m-1}.$$

これが任意の$m$に対して成り立つので, $m\to\infty$とすれば,

$$\forall\epsilon>0,\,\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1]+\epsilon.$$

即ち定理の主張が従う.

(1)の証明.

有向区間グラフの言葉で説明する. $\{x_1,\ldots,x_m\}$および$r>0$に対し, 有向グラフ$G_r$を, $V(G_r)=[m]=\{1,\ldots,m\}$, $E(G_r)=T_r$とする. 特に$(i,j)\in E(G_r)$ならば$(j,i)\in E(G_r)$でもあるので, 向きを付けることに本質的な意味はないが, 辺の本数=$|T_r|$として議論していきたいので有向グラフを考えることにする. つまり, $|E(G_2)|\leq 3|E(G_1)|$を示せば良い. 

二つのグラフ$G_1,G_2$を考える. 頂点$i$のグラフ$G_r$における出次数を$\deg_r^+(i)$とする. つまり, $\deg_r^+(i)=|\{j\in[m]:(i,j)\in E(G_r)\}|$であり, 自己ループも1としてカウントする.

主張(1)の証明は$m$に関する帰納法で行う. $m=1$なら$T_r=\{(1,1)\}$なので(1)は成り立つ. $m\geq 2$の場合を考える. $i\in[m]$を$G_1$内で最大出次数を持つ頂点とする. このとき, $\deg^+_2(i) \leq 3\deg^+_1(i)$が成り立つことを言う. もし$\deg^+_2(i)>3\deg^+_1(i)$とすると, 数直線上の区間 $[x_i+1,x_i+2]$ と $[x_i-2,x_i-1]$ のどちらかに必ず$>\deg^+_1(i)$個の点がある (下図).

図. もし$\deg_2^+(i)>3\deg_1^+(i)$なら, より出次数の大きい点がとれる.

これは$\deg^+_1(i)$が最大であることに矛盾します. 従って $\deg_2^+(i)\leq 3\deg_1^+(i)$です. $G_1$と$G_2$からそれぞれ頂点$i$を削除して得られるグラフを$G'_1$, $G'_2$とすれば, 帰納法の仮定より$|E(G'_2)|\leq 3|E(G'_1)|$であり, $|E(G_r)|=|E(G'_r)|+2\deg^+_r(i)+1$なので,

$$|E(G_2)|\leq 3|E(G'_1)|+6\deg^+_1(i)+1<|E(G_1)|$$

となり(1)が成り立つ.

補足

123 Theoremはタイトな例を作ることができ, 例えば$\Pr[|X-Y|\leq 2] \leq 2.99\Pr[|X-Y|\leq 1]$は一般には成り立ちません: $\{2,4,6,\ldots,2n\}$上の一様分布を考え, この分布に従う独立な二つの確率変数$X,Y$を考えます. このとき,

$$\Pr[|X-Y|\leq 2] = \frac{3}{n}-\frac{2}{n^2},$$

$$\Pr[|X-Y|\leq 1] = \Pr[X=Y]=\frac{1}{n}$$

より, $\Pr[|X-Y|\leq 2] = 3\Pr[|X-Y|\leq 1] - \frac{2}{n^2}.$

参考文献

[1] N. Alon and R. Yuster. The 123 Theorem and its extensions, Journal of Combinatorial Theory, Series A, 72(2)322--331, 1995.