discrepancy: ハムサンドイッチ定理の離散化 (確率論的手法)

本記事ではdiscrepancyと呼ばれる組合せ論(特に確率論的手法の文脈)でよく知られる概念について紹介します. この概念はハムサンドイッチ定理と呼ばれる定理を離散化したような概念とみなすことができます. discrepancyはその定義自体はとても簡単である一方で奥深い結果が多く知られており, 理論計算機科学においてはビンパッキング問題に対する近似アルゴリズムの設計にも応用されています. 後の章になっていくほどテクニカルになっていきます.

1. ハムサンドイッチ定理

ハムサンドイッチ定理とは, 直感的に説明すると「3次元空間内に配置された三つの物体は、ある平面でうまくスラッシュすることによって全ての物体の体積を半分にできる」ということ主張する定理です. 私は詳しくないのですが, wikipediaによると, より一般に$d$次元空間にある$d$個の「物体」（有限測度を仮定するが必ずしも連結である必要はない）はある$d-1$次元超平面によってそれぞれの測度を半分ずつにできる、という主張をハムサンドイッチの定理と呼ぶらしいです.

名前の由来はハムとそれを挟む2枚のパンからなる三つの物体は, 一回のナイフカットによって平等に二分割できるということから来るようです. 特に二次元($d=2$)の場合はパンケーキの定理とも呼ばれるようで, 限りなく薄い2枚のパンケーキを等分割するようにカットできるということを意味します (下図)

要するにハムサンドイッチ定理とは二つの物体を組み合わせたものはうまくナイフを入れることで等分できる, ということを主張しています. この定理を数学的に厳密に述べるのは難しいのですが, ここではそれを離散化した設定を考えます.

2. discrepancy

ハイパーグラフ$H=(V,E)$を考える (各$e\in E$は$e\subseteq V$を満たす). 関数$\chi\colon V\to\{-1,1\}$と集合$S\subseteq V$に対して$\chi(S)=\sum_{i\in V}\chi(i)$とし, $\chi$のdiscrepancyを
$$\begin{align*} \mathrm{disc}_{\chi}(H) = \max_{e\in E}|\chi(e)| \end{align*}$$
で定義します. 直感的には$\chi$は頂点集合$V$を二つに分けるナイフカットを意味しており, そのdiscrepancyは$\chi$がどれだけ二等分に近いかを表す指標とみなすことができます. この設定下ではdiscrepancyが最小となる$\chi$が最も公平な分割と思うことができます. すなわち, 以下で定義される最小discrepancyを考えてみましょう:
$$\mathrm{disc}(H):=\min_{\chi\colon V\to\{-1,1\}}\mathrm{disc}_{\chi}(H).$$

以後, 関数$\chi\colon V\to\{-1,1\}$を彩色と呼びます.

例えば$G=(V,E)$が通常の意味でのグラフだとすると, $\mathrm{disc}(G)=0$であることと$G$が二部グラフが同値になります.

図: グラフ$G=(V,E)$が二部グラフならば, それぞれの部集合を$\chi^{-1}(1),\chi^{-1}(-1)$とすれば, discrepancyを$0$にできる.

3. 行列を用いたdiscrepancyの表現

ハイパーグラフ$H=(V,E)$の接続行列$A_H\in\{0,1\}^{E\times V}$を,
$$A_H(e,v) = \begin{cases} 1 & \text{ if }v\in e,\\ 0 & \text{otherwise} \end{cases}$$
で定義します. 関数$\chi\colon V\to\{-1,1\}$をベクトル$\chi\in\{-1,1\}^V$と同一視すると, 行列$A\chi \in \mathbb{Z}^{E}$は, その第$e$成分が$\sum_{v\in V}\chi(v)$になるので,
$$\mathrm{disc}(H) = \min_{\chi\in\{-1,1\}^V}\left\| A_H\chi \right\|_{\infty}$$
と表せます. ここで$\|\cdot\|_{\infty}$は$\ell^{\infty}$-ノルムで, 各成分の最大絶対値を表します.　いくつかの論文ではこの形でdiscrepancyを議論していくこともあります. 

より一般に$A\in\{0,1\}^{m\times n}$に対して$\mathrm{disc}(A)$を
$$\mathrm{disc}(A) = \min_{\chi\in\{-1,1\}^V}\left\| A\chi \right\|_{\infty}$$
と定義することができ, さらにこの定義は一般の実行列$A\in\mathbb{R}^{m\times n}$に対して考えるもできます. これを行列$A$のdiscrepancyと呼びます.

蛇足になりますが, 関連する概念としてlinear discrepancyと呼ばれるものが知られています. この値は$m\times n$実行列$A$に対して定義でき,
$$\mathrm{lindisc}(H) = \max_{w\in[-1,1]^n}\min_{x\in \{-1,1\}^n} \left\| A(x-w) \right\|_{\infty}$$
で定義されます. この概念は元々は連続変数$w\in[-1,1]^n$を持つ線形計画問題を整数変数$x\in\{1,1\}^n$に丸めた際のギャップを考えるという文脈で定義されています.

4. discrepancyの計算量

考えるハイパーグラフ$H=(V,E)$の頂点数を$n$, ハイパー辺の個数を$m$で表します.

[Charikar, Newman, Nikolov, SODA11]によって, $m=O(n)$を満たすとき, 以下の二つの入力を区別することがNP困難であることが示されています:

• $\mathrm{disc}(H)=0$
• $\mathrm{disc}(H)=\Omega(\sqrt{n})$

例えば$m=n$を満たす任意のハイパーグラフ$H$に対して$\mathrm{disc}(H)\leq 6\sqrt{n}$であることが知られている (後述するがこの結果はSpencer's six standard deviations theoremと呼ばれる重要な結果) ので, 上記の困難性は定数倍を除いてタイトです.

5. ランダム彩色による上界

彩色$\chi\colon V \to \{-1,1\}$を一様ランダムにとってきたときのdiscrepancyを考えてみましょう. すなわち, 各$v\in V$に対して$\chi(v)$を$\pm 1$から一様ランダムに選びます. このとき, Hoeffding boundとunion boundを組み合わせることによって簡単に以下を示すことができます.

命題1 (ランダム彩色のdiscrepancy)

ハイパーグラフ$H=(V,E)$に対し, $n=|V|,m=|E|$とする. 一様ランダムに選ばれた彩色$\chi\colon V \to \{-1,1\}$を考えると, 以下が成り立つ:
$$\begin{align*} \Pr\left[\mathrm{disc}_\chi(H) \leq \sqrt{2n\log(3m)} \right] \geq \frac{1}{3}. \end{align*}$$

特に, $\mathrm{disc}(H)\leq \sqrt{2n\log(3m)}$である.

命題1の証明のために以下のHoeffding boundを用います:

補題1 (Hoeffding bound)

$X_1,\dots,X_\ell$を$\pm 1$に値をとる独立一様ランダムな確率変数とし, $X=\sum_{i\in[\ell]} X_i$とする. このとき, 任意の$t\geq 0$に対して

$$\begin{align*} \Pr\left[ |X| \geq t \right] \leq 2\exp\left(-\frac{t^2}{2\ell}\right). \end{align*}$$

[命題1の証明].

固定した辺$e\in E$に対して, 補題1より
$$\begin{align*} \Pr\left[\chi(e) > \sqrt{2n\log(3m)} \right] \leq \Pr\left[\chi(e) > \sqrt{2|e|\log(3m)}\right] \leq \frac{2}{3m}. \end{align*}$$
従って, $e\in E$に関するunion boundにより
$$\begin{align*} \Pr\left[\mathrm{disc}_{\chi}(H) > \sqrt{2n\log(3m)}\right] \leq \Pr\left[\exists e\in E,\,\chi(e)>\sqrt{2n\log(3m)}\right] \leq \frac{2}{3}. \end{align*}$$

すなわち, ランダムに選ばれた$\chi$のdiscrepancyは確率$1/3$で$\mathrm{disc}_\chi(H)\leq \sqrt{2n\log(3m)}$を満たす. (証明終)

証明から分かるように, $\log(3m)$の定数$3$は任意の定数$c>1$に対し$\log(cm)$に置き換えることが可能です.

6. Spencer's six standard deviation theorem

$m=O(n)$のとき, 5章では確率論的手法を使って$\mathrm{disc}(H)=O(\sqrt{n\log n})$が得られますが, 実はさらに改善して$\mathrm{disc}(H)=O(\sqrt{n})$を示すことができます[Spencer, 1985].

定理1 [Spencer's six standard deviation theorem]

$|V|=|E|$を満たす任意のハイパーグラフ$H=(V,E)$は$\mathrm{disc}(H)\leq 6\sqrt{|V|}$を満たす.

この結果は, その係数からSpencer's six standard deviation theoremと呼ばれます. 実はこの証明は$\chi$の存在性を鳩の巣原理から導出しており構成的ではないのですが, 後に構成論的な証明が与えられ[Bansal, 2010], 現在ではより簡単な証明も知られています[Lovett, Meka, 2015]. ここではhidden constantについてはoptimizeせず, 単に存在性($\mathrm{disc}(H)=O(\sqrt{n})$)を証明します.

証明では部分彩色 (partial coloring) という概念が鍵になります. 部分彩色とは関数$\chi\colon V\to\{-1,0,1\}$です. 部分彩色に対しても$\chi(e) = \sum_{v\in e} \chi(v)$とし, $\chi$のdiscrepancyを
$$\mathrm{disc}_{\chi}(H) = \max_{e\in E}\left| \chi(e) \right|$$
で定義することができます.

明らかに, 全ての頂点に$0$を割り当てる部分彩色を考えるとdiscrepancyが$0$となり最小値をとります. 従って, 部分彩色$\chi$であって

• 多くの頂点(少なくとも$0.01|V|$個以上の頂点) に$\pm 1$の値を割り当てる, かつ
• $\mathrm{disc}_{\chi}(H)$が小さい

ような部分彩色が望ましい部分彩色であるといえます. 以下の補題はそのような部分彩色の存在性を保証します.

補題2 (部分彩色補題)

ある定数$C_0$が存在して, $m\leq \frac{n}{10}$を満たす任意のハイパーグラフ$H=(V,E)$に対し, 以下の二つを同時に満たすある部分彩色$\chi\colon V\to \{-1,0,1\}$が存在する:

• $\chi(v)\in \{-1,1\}$を満たす頂点$v$が少なくとも$\frac{n}{10}$個ある.
• $\mathrm{disc}_\chi(H)\leq C_0\sqrt{n}$

補題2の証明が最もテクニカルなパートになるので次の章で紹介するとして, ここでは補題2$\Rightarrow$定理1を示します.

まずは証明のアウトラインを述べます. 元々は$m=n$という仮定でしたが, ダミー頂点を追加すれば相対的に$|E|\leq \frac{|V|}{10}$になるようにできるので, 与えられたハイパーグラフは$m=\frac{n}{10}$を満たすと仮定して良いです (ダミー頂点追加後の彩色に対するdiscrepancyは$O(\sqrt{O(n)})=O(\sqrt{n})$になるのでdiscrepancyのバウンドも大丈夫). これに対して補題2を適用して得られる部分彩色に対し, $0$が割り当てられた頂点部分集合からなる誘導部分ハイパーグラフに対して再帰に彩色を得て先ほどの部分彩色とマージするという方針になります. 一回の反復で塗られていない頂点の個数は$0.9$倍になるので, 全体のdiscrepancyは高々$\sum_{t=0}^\infty C_0 \sqrt{0.9^t n}=O(\sqrt{n})$になるという議論です.

[補題2$\Rightarrow$定理1]. 

以下の手順に従ってハイパーグラフの列$(H_t)_{t=0,1,\dots}$と各$H_t$上の部分彩色$\chi_t$を定義します:

1. $H_0 = (V_0,E_0) = H$とする.
2. For $t=1,2,\dots,$ do:
1. 部分彩色$\chi_t$を, $H_{t-1}$に対する補題2で存在性が保証される部分彩色とする.
2. $V_t=\{v\in V_{t-1}\colon \chi_t(v)= 0\}$, $E_t = \{e\cap V_t\colon e\in E_{t-1}$とし, $H_t=(V_t,E_t)$で定める.
3. $E_t=\emptyset$になったら終了する.

補題2の条件より, $|V_t| \leq 0.9|V_{t-1}|$ なので, 十分大きな$T=O(\log n)$に対して$E_T=\emptyset$となるため, 上の手順は有限ステップで終了します. このとき, $\chi_1,\dots,\chi_T$に対して彩色$\chi$を, $\chi(v) = \chi_i(v)$で定めます. ここで$i\in[T]$は$\chi_i(v)\neq 0$を満たす唯一の$i$とします. 

上で定義した$\chi$のdiscrepancyを評価します. 各辺$e\in E$に対して
$$\begin{align*} |\chi(e)| \leq \left|\sum_{v\in e}\chi(v)\right| \leq \sum_{t=1}^T \left| \sum_{e\in E_{t-1}\setminus E_t } \chi(e) \right| \leq \sum_{t=1}^T C_0\sqrt{0.9^t n} = O(\sqrt{n}) \end{align*}$$

を得ます.

7. 部分彩色補題の証明(スケッチ)

6章で紹介した補題2(部分彩色補題)を証明します. この証明はその鳩の巣原理からその存在性が保証されるため構成的ではありません. 部分彩色補題 (ひいては定理1) を満たす彩色$\chi$の構成については長年未解決だったのですが, Bansal (2010) によるブレイクスルーにより解決され, 現在ではLovett and Meka (2015) による(ランダムネスを用いる)簡単な構成法も知られています. 厳密な証明をしようとすると瑣末な部分のケアで煩雑になってしまい大変なので, できる限り本質を捉えつつ厳密性を捨てて, 分かった気になれる証明のスケッチを紹介します.

定義1 (エントロピー)

離散集合上に値をとる確率変数$X$に対し, そのエントロピー$\mathrm{H}(X)$を
$$\begin{align*} \mathrm{H}(X) = \mathbb{E}_{x\sim X}\left[\log\frac{1}{\Pr[X=x]}\right] = \sum_{x\in \mathsf{supp}(X)} \Pr[X=x]\log\frac{1}{\Pr[X=x]} \end{align*}$$
で定義します. ここで対数の底はlogとし, $\mathsf{supp}(X)$は$X$の台(support)と呼ばれる集合で, $\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定義されます.

なお, 連続値をとり密度関数が存在するような確率変数に対しても$\Pr[X=x]$を密度関数$f(x)$に置き換えて微分エントロピーという値が定義されます. すなわち, 密度関数$f$を持つ実数値をとる確率変数$X$の微分エントロピー$\mathrm{H}(X)$は

$$\begin{align*} \mathrm{H}(X)=\int_\mathcal{\mathsf{supp}(X)} f(x) \log\frac{1}{f(x)}\mathrm{d}x \end{align*}$$
で定義されます. エントロピーに関しては上記の定義と以下の性質のみを使います.

補題3 (エントロピーの劣加法性).

ランダムなベクトル$X=(X_1,\dots,X_n)$に対し, そのエントロピー$\mathrm{H}(X)$は
$$\mathrm{H}(X) \leq \sum_{i\in[n]}\mathrm{H}(X_i)$$ を満たす.

さて, 部分彩色補題の証明に戻ります. ランダムな彩色$\chi\colon V \to \{-1,1\}$を考え, パラメータ$w>0$と頂点部分集合$S$に対し, 確率変数
$$Z_S = \left\lfloor \frac{\chi(S)}{w\sqrt{|S|}}\right\rfloor$$
のエントロピー$\mathrm{H}(Z_S)$を考えます. 実際にはもう少し複雑な式を使って評価するのですが, ここでは以下の主張を認めて証明を進めていきます.

主張1.

パラメータ$w$を適切にとり, 部分集合$S$の要素数が十分大きいとき, $\mathrm{H}(Z_S)\leq 0.9$とできる.

なお, この主張は本当に成り立つかは分かりません(えっ...). 実際の証明ではもう少し複雑な式を使ってエントロピーを評価します. ここではその証明のアイデアを簡潔に説明するためにあえて「成り立つか分からない主張」を仮定します. ただ, この主張には一応の理由づけはできるので, 以下ではその妥当性を説明します (実際の研究の場面ではこのようなことは私はよくやります).

[主張1の妥当性の説明]

• 定義よりエントロピーはスケーリングで不変なので, $\mathrm{H}(Z_S)=\mathrm{H}(w\cdot Z_S) \approx \mathrm{H}(\chi(S)/\sqrt{|S|})$ (本当は切り下げの有無でのエントロピーの誤差の評価が必要).
  
• $\chi(S)$は平均$0$, 分散$1$の独立な確率変数$(\chi(v))_{v\in S}$の和なので, $|S|$が十分大きければ中心極限定理より$\chi(S)/\sqrt{|S|}$は漸近的に標準正規分布$\mathcal{N}(0,1)$で近似できる.
• 従って, $\mathrm{H}(\chi(S)/\sqrt{|S|}) \approx \mathrm{H}(\mathcal{N}(0,1)) = (1+\log(2\pi))/2 \approx 1.419$. なお, 正規分布の微分エントロピーについての事実を使っている(例えばこの記事参照).  本当はBerry--Esseenの不等式などを使ってエントロピーの誤差評価が必要.
• これらをまとめると, $\mathrm{H}(Z_S)\approx 1.419$なので, パラメータ$w$を適切にとり, 集合サイズ$|S|$が十分大きいならば, 近似精度を$0.001$未満にできて$\mathrm{H}(Z_S)\leq 1.42$にできる.

ハイパーグラフ$H$に対し, ランダムベクトル$Z=Z(\chi)=(Z_e)_{e\in E}$を考えます. ここで, 全ての辺$e$の要素数は十分大きいと仮定します (そうでない場合はサイズが小さいのでdiscrepancyに寄与しないため無視できる). するとエントロピーの劣加法性(補題3)と主張1より
$$\begin{align*} \mathrm{H}(Z) \leq \sum_{e\in E}\mathrm{H}(Z_e) \leq 1.42m \leq 0.2n \end{align*}$$
を得ます. エントロピーの定義より, averaging argumentにより, あるベクトル$z^*\in\mathbb{Z}^E$が存在して
$$\begin{align*} \log\frac{1}{\Pr[Z=z^*]} \leq 0.2n \end{align*}$$
となります. これを整理すると$\Pr[Z=z^*] \geq \mathrm{e}^{0.2n} > 2^{0.2n}$を得ます. ここでの確率は一様ランダムな彩色を考えていたので, 少なくとも$2^{0.8n}$個の$\chi\in \{-1,1\}^V$が存在して$Z(\chi)=z^*$を満たすことになります. そのような$\chi$の集合を$B\subseteq\{-1,1\}^V$とします. ここで, $|B|\geq 2^{0.8n}$より, ある二つのベクトル$\chi_1,\chi_2\in B$が存在して, $\|\chi_1-\chi_2\|_1 \geq 0.1n$となります (後述). そのような$\chi_1,\chi_2$に対して$\chi = \frac{1}{2}(\chi_1 - \chi_2)$と定義します. するとこの$\chi$は部分彩色補題の要件を満たしています:

• $\chi_1,\chi_2$の選び方より, $\chi(v)=0\iff \chi_1(v)=\chi_2(v)$となる$v\in V$は高々$0.9n$個あります.
• $\chi_1,\chi_2\in B$より, $Z(\chi_1)=Z(\chi_2)$です. すなわち, 任意の$e\in E$に対して
  $$\left\lfloor\frac{\chi_1(e)}{w\sqrt{|e|}} \right\rfloor = \left\lfloor \frac{\chi_2(e)}{w\sqrt{|e|}} \right\rfloor$$
  が成り立つので, $|\chi(e)| = |\chi_1(e) - \chi_2(e)| \leq w\sqrt{|e|} \leq w\sqrt{n}$です. これは$\mathrm{disc}_\chi(H)\leq w\sqrt{n}$を意味します.

以上より, 部分彩色補題(補題3)の証明が完了し, 同時に定理1の証明も完了しました. (証明終)

以上の証明では次の事実を用いています:

主張2.

集合$B\subseteq \{-1,1\}^n$が$|B|\geq 2^{0.8n}$を満たすならば, ある二つのベクトル$x,y\in B$が存在して$\|x - y \|_1\geq 0.1n$となる.

証明(概要). 一般に, 任意のベクトル$x\in \{-1,1\}^n$に対し$x$からハミング距離$\alpha n$以内にある点の個数は高々$\sum_{i=0}^{\alpha n} \binom{n}{i} \leq 2^{\mathrm{H}(\alpha)n}$を満たします (ここで$\mathrm{H}(\alpha):=\alpha\log_2\frac{1}{\alpha} + (1-\alpha)\log_2\frac{1}{1-\alpha}$はbinary entropy function). $\alpha=0.1$を代入すると, この個数は$2^{\mathrm{H}(0.1)n}< 2^{0.469n}<|B|$なので, 主張を満たす2点をとることができます. (証明終)

Further Reading

• 驚くべきことにスタンフォード大学では過去にdiscrepancyについての講義(おそらく集中講義?)があり, いくつかの講義ノートが公開されています.
• The Probabilistic Method (Alon and Spencer)の12章ではランダムな$\chi$の解析とsix-deviation theoremとBeck-Fiala theoremとHadamard行列に基づく下界の紹介がされています.
• ビンパッキング問題の近似アルゴリズムに対する応用については "A Logarithmic Additive Integrality Gap for Bin Packing" (Hoberg and Rothvoss, SODA2017) 参照. なお, 箇条書き一つ目のリンクにあるLecture 10のノートには少し弱い近似精度を持つビンパッキングの近似アルゴリズムについての解説があります.