離散確率空間上の確率集中不等式

本来, 確率変数は「ランダムな値をとる」ものであり, その挙動を予想することは困難です. しかし「n個の確率変数の和」といった幾つかのタイプの確率変数は「大体このくらいの値を高確率でとる（集中する）」ことが理論的に保証できます. この議論は確率集中不等式を用いてなされるものであり, 物理学, 機械学習, 計算機科学 (特に乱択アルゴリズムの解析), グラフ理論といった非常に広範囲な分野の理論的支柱の一つとなっています. 今回は離散確率空間上で成り立ついろんな確率集中不等式について紹介します.

この記事で紹介するのは Chernoff bound, Jansonの不等式, Kim-Vu polynomial concentration です. よくある確率集中不等式の本や連続の世界では Bernsteinの不等式, Azumaの不等式, Talagrandの不等式などが出てきますが, それらはここでは割愛します. Talagrandの不等式についてはめちゃくちゃ面白いので機会があれば紹介したいと思っています.

1. Chernoff bound

独立な確率変数の和の集中性を示す結果で, もっとも代表的なものです. $X_1,\ldots,X_n$を$[0,1]$の値をとる独立な確率変数で, $\mathrm{E}[X_i]=p_i$, $S=X_1+\cdots+X_n$, $\mu=E[S]$とします.

定理1 (Chernoff bound).
任意の $t>0$ に対して

$\Pr[S\geq \mu+t] \leq \exp\left(-\frac{t^2}{2(\mu+t/3)}\right)$.

任意の $t\leq \mu$ に対して

$\Pr[S\leq \mu-t] \leq \exp\left(-\frac{t^2}{2(\mu-t/3)}\right)$.

系2.
任意の$\epsilon>0$に対して,

$\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\frac{\min\{\epsilon,\epsilon^2\}\mu}{3}\right)$

及び

$\Pr[S\leq (1-\epsilon)\mu] \leq \exp\left(-\frac{\epsilon^2 \mu}{2}\right).$

Remark.
しばしば, $\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\Omega(\epsilon \mu)\right)$ などと勘違いされますが, これは $\epsilon\geq 1$ でないと成り立ちません. また, Chernoff boundには Hoeffidingなどいろんな亜種が知られていて, [1, 2]などが詳しいです. 特に

定理3.

独立なベルヌーイ試行 $X_1,\ldots,X_n$ に対して, $S=X_1+\cdots+X_n$, $\mu=\mathrm{E}[S]$とおく. 任意の $R\geq 2\mathrm{e}\mu$に対して

$\Pr[S\geq R]\leq 2^{-R}$

が成り立つ.

という結果も知られています[2, Corollary 10.4].

1.1. Chernoff bound の証明 (途中まで)

Chernoff boundの証明は初見だとビックリするようなアイデアに基づくものになっており, マルコフの不等式 ($\Pr[X>a]\leq \mathrm{E}[X]/a$) を使います. 概略だけ述べると

$\Pr[S\geq\mu+t] = \Pr[\exp(\lambda S)\geq \exp(\lambda(\mu+t))] \leq \exp(-\lambda(\mu+t))\mathrm{E}[\exp(\lambda S)]$

for any $\lambda\geq 0$ なので, 右辺の $\mathrm{E}[\exp(\lambda S)]$ を上から抑えることを考えます. ここで$S$は独立確率変数の和なので, 積に分解でき

$\mathrm{E}[\exp(\lambda S)]=\prod_{i=1}^n \mathrm{E}[\exp(\lambda X_i)] = \prod_{i=1}^n (1-p_i(1-\mathrm{e}^{-\lambda}))$

となります. (個人的には$\exp(\lambda S)$を考えるあたりがビックリポイントなのですが, モーメントなどをよくよく考えるとなんとなく自然に感じられるようになります). あとはこの右辺を気合いで上から抑えます. 具体的には

$\exp(\lambda x)\leq 1-x+x\exp(\lambda)$ for $x\in[0,1]$

という不等式を使います. この先は式変形を頑張って整理するだけです. 詳しく知りたい方は, 例えば [3, 21.4節] などをご覧ください.

2. Janson の不等式

Erdős–Rényiグラフ $G(n,p)$ を考えます. ここで$G(n,p)$ とは $n$ 頂点のグラフで各辺が独立に確率 $p$ で接続されて得られたグラフのことです. このグラフに含まれる三角形の個数を $Y$ とします. また, 辺$e$に対し, $X_e$を「$G(n,p)$が$e$を含んでいたら $1$, そうでなければ $0$」と定めます. すると

$Y=\sum_{u,v,w} X_{uv}X_{vw}X_{wu}$

と表せます. 一見すると確率変数の和なので Chernoff bound を使えば集中性が示せそうな気がしますが, 一般に $X_{uv}X_{uw}X_{wu}$と$X_{u'v'}X_{v'w'}X_{w'u'}$ は辺素でない限り独立じゃないのでChernoff boundは使えません. ただ, 辺素な三角形のペアは非常にたくさんあり, 従属関係がスパースなので集中性が示せるんじゃないかという気がします. このように独立な01確率変数上で従属関係がスパースな indicator の和に対し非常に強い下界を与えるのが Janson の不等式です. ちなみにLovász local lemmaも似たような設定を考えてます.

より一般に述べるために, 次の設定を考えます:
有限集合 $E$ で添字づけられた01確率変数の族 $(X_e)_{e\in E}$ を考えます. $\mathrm{E}[X_e]=p_e$ とし, 相異なる $e,f\in E$ に対して $X_e$ と $X_f$ は独立であるとし. $E$上の部分集合族 $\mathcal{E}\subseteq 2^E$ に対して確率変数 $Y_{\mathcal{E}}$ を

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} \prod_{e\in F} X_e$

と定めます. 三角形の例だと, $E$は$\binom{n}{2}$通りの辺の全体$\binom{V}{2}$であり, $X_e$ は $G(n,p)$ が辺$e$を含んでいるかどうかの indicator です. また, $\mathcal{E}$ は集合で書くと

$\mathcal{E}=\{\{a,b,c\}:a,b,c\in E$ are distinct. $\}$

です. すると $Y_{\mathcal{E}}$ は $G(n,p)$が含む三角形の個数になります.

定理4 (Jansonの不等式).

任意の $t>0$ に対し以下が成り立つ:

$\Pr[Y_{\mathcal{E}}\leq \mathrm{E}[Y_{\mathcal{E}}]-t] \leq \exp\left(-\frac{t^2}{\nabla}\right)$.

ここで $\nabla$は

$\nabla=\sum_{F_1,F_2\in\mathcal{E}:\,F_1\cap F_2\neq\emptyset} \mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$.

2.1. 三角形の個数の下界の導出

$\mathcal{E}$を, 冒頭で述べたように三角形の辺集合の全体と定めます. まず期待値 $\mathrm{E}[Y_\mathcal{E}]$を評価してみると,

$\mathrm{E}[Y_{\mathcal{E}}]=\binom{n}{3}p^3\approx \frac{(np)^3}{6}$

が得られます. 次に定理4に出てくる $\nabla$ を評価します. 式はややこしそうに見えますがやることは簡単で, 辺を共有する二つの三角形$F_1,F_2$に関して $p^{|F_1\cup F_2|}$ を足しあげるだけです. 実際, indicatorの期待値は確率と等しく, 総和の中の $\mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$ は今回の例でいうと $F_1$と$F_2$の辺が全て $G(n,p)$ に現れる確率と等しくなるので, $p^{|F_1\cup F_2|}$ となります.

ここで $F_1,F_2$ は辺を共有するので, $|F_1\cup F_2|\leq 5$です. そこで三つの場合を考えます:
(i). $|F_1\cup F_2|=3$ の場合: このとき, $F_1=F_2$は同じ三角形を表すので, このような組$(F_1,F_2)$は全部で $O(n^3)$ 通りあります.

(ii). $|F_1\cup F_2|=4$ の場合: そもそも辺を共有する三角形で$|F_1\cup F_2|=4$となるものは存在しません.

(iii). $|F_1\cup F_2|=5$ の場合: $F_1$は三角形の全体$\mathcal{E}$から選ばれるので, $O(n^3)$通りの選び方があります. 一方で$F_2$は$F_1$と一本だけ辺を共有するため, 下図のような感じになります. すると $F_2$ の頂点の自由度は $1$ なので, $F_1$を固定したとき$F_2$は $O(n)$ 通りしかとれません. 従って組 $(F_1,F_2)$ は$O(n^4)$通りです.

Case (iii) における二つの三角形 $(F_1,F_2)$ に対して $F_1\cup F_2$ が表すグラフ.

以上より, $\nabla$は

$\nabla = O(n^3)p^3+O(n^4)p^5 = O(n^3p^3(1+np^2))$

となります. これを定理4 に代入すると,

$\Pr\left[Y_{\mathcal{E}} \leq \mathrm{E}[Y_{\mathcal{E}}]-t\right] \leq \exp\left(-\Omega\left(\frac{t^2}{(np)^3(1+np^2)}\right)\right)$

が得られます. 例えば $t=\mathrm{E}[Y_{\mathcal{E}}]\approx \frac{(np)^3}{6}$を代入すると,

$\Pr[G(n,p)$が三角形を含まない$]\leq \exp\left(-\Omega\left(\frac{(np)^3}{1+np^2}\right)\right) \leq \exp(-\Omega((np)^2))$

となるので, $p\geq \Omega(n^{-2/3})$ならば, $G(n,p)$ は指数的に高い確率で三角形を含む, ということが結論づけられます.

Remark.

実は Janson の不等式は多くの場合で指数部分が定数倍を除くとタイトなバウンドを与えていることが知られており[5], 非常に強力な不等式であることがわかります.

備忘録.

証明はChernoff boundと同様に $\mathrm{E}[\exp(-\lambda Y)]$ のバウンドをうまく与えるのですが, 独立性が成り立たないのが辛いポイントで, 「とりあえず$\lambda$で微分」「アイテム$e$を固定し, $X_e$と独立な部分和とそうでない部分和に分けて, 独立でない部分和に関してはFKG不等式を使ったり」などを工夫します.

3. The Kim-Vu polynomial concentration

文献[4]で示された定理を紹介します. 一般的な呼称がわからないのですが自分はとりあえず表題の通り呼んでいます. 2節で用いたセッティングをここでも流用します. すなわち, 台集合 $E$ 上の独立01確率変数 $(X_e)_{e\in E}$ と部分集合族 $\mathcal{E}\subseteq 2^E$ に対して, 新たな確率変数

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} w_F\prod_{e\in F} X_e$

の集中性を考えます. ここで $w_F>0$ は重みです. 2節では Janson の不等式を用いて下界だけ示しましたが, この節では集中性を述べる結果を紹介します. 上界も求められるためJansonより汎用性は高いように見えますが, 得られるバウンド自体は Janson よりも少し弱い結果になります.

ここでは, $Y_{\mathcal{E}}$ は $X_e$ を変数として見たとき多変数多項式になっていることに着目します. この節で紹介する定理は, この多項式の次数が小さいときに有効な結果になります.

準備として, 縮約について述べます. 部分集合 $A\subseteq E$ に対して, 確率変数 $Y_A$ を

$Y_A=\sum_{F\in\mathcal{E}:A\subseteq F} w_F \prod_{e\in F\setminus A} X_e$

と定めます. $A$を含むような$F$について, $A$以外の要素を掛けて足し上げているので, $Y_A$ は $Y_{\mathcal{E}}$ の $A$による縮約とみなすことができます.

例えば $\mathcal{E}$ を 前節で考えた三角形をなす辺集合の族とし, $A=\{\{1,2\}\}$ を辺$12$のみからなる集合としましょう (今は大集合$E$は$\binom{n}{2}$個の辺集合であることに注意). すると, $Y_A$ は辺$\{1,2\}$を含む三角形 $F$ に対して 辺$\{1,2\}$を除去して足し上げたものになっているため,

$Y_A = \sum_{u\in V\setminus\{1,2\}} X_{1,u}X_{2,u}$

となります. イメージとしては $G(n,p)$ が 辺集合$A$ を含むという事象を条件つけたときの $Y_{\mathcal{E}}$ を表しています.


定理5 (The Kim-Vu polynomial concentration).

$Y_{\mathcal{E}}$ を $k$ 次多項式とする. すなわち, 任意の $F\in\mathcal{E}$ に対して $|F|\leq k$ が成り立つとする. $a_k=8^k\sqrt{k!}$とし,

$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]$,

$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}].$

と定める. 任意の$\lambda>1$に対して

$\Pr\left[|Y_\mathcal{E}-\mathrm{E}[Y_{\mathcal{E}}]|\geq a_k \sqrt{\Xi(\mathcal{E})\Xi'(\mathcal{E})}\lambda^k\right]\leq O(\exp(-\lambda+(k-1)\log n))$

が成り立つ.

3.1. $G(n,p)$ が含む三角形の個数の集中性

三角形の個数は $Y_{\mathcal{E}}$ として表せるため, 定理5により集中性が示せます. $A\subseteq E$に対して $\mathrm{E}[Y_A]$ を評価する必要がありますが, $A$を一辺 $\{1,2\}$ のみからなる集合のとき, 冒頭の例で述べた事実を使うと

$\mathrm{E}[Y_A]= \sum_{u\in V\setminus \{1,2\}} p^2 = O(np^2)$

となります. $A=\{\{1,2\},\{1,3\}\}$ ならば, $A$を含む $F$ としては三角形123しかありえないので, $\mathrm{E}[Y_A]=p$ です. つまり, $A$は増えれば増えるほど $Y_A$ は減っていく一方なので, 

$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]=O(n^3p^3)$,

$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}]=O(np^2)$

が成り立ちます. これを定理5に突っ込むと

$\Pr\left[|Y_{\mathcal{E}}-\mathrm{E}[Y_{\mathcal{E}}]|\geq  \Theta(n^2p^{2.5})\lambda^3\right] \leq O(\exp(-\lambda+2\log n))$

となります. 例えば $\lambda=3\log n$ を代入すると, 確率 $1-O(n^{-1})$ で

$\frac{(np)^3}{6}-O(n^2p^{2.5}(\log n)^3) \leq$三角形の個数 $\leq \frac{(np)^3}{6}+O(n^2p^{2.5}(\log n)^3)$

が成り立つことが簡単に示せます.

[1]. Concentration Inequalities and Martingale Inequalities: A Survey, F. Chung, and L. Lu, Internet Mathematics Vol. 3, No. 1: pp. 79-127 (2006).

[2]. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, B. Doerr, arXiv:1801.06733, (2018).

[3]. Introduction to Random Graphs, A. Frieze, and M. Karoński, Cambridge University Press, (2016).

[4]. Concentration of multivariate polynomials and its applications, J. H. Kim, and V. H. Vu, Combinatorica, Vol. 20, No. 3, pp. 417-434 (2000).

[5]. The lower tail: Poisson approximation revisited, S. Janson, and L. Warnke, Random Structures and Algorithms, Vol. 48, No. 2, pp. 219-246 (2014).

マトロイドの基の数え上げの決定的多項式時間近似アルゴリズム

$\mathcal{M} = (E,\mathcal{B})$ をマトロイドとします. ここで $E$ は台集合で$|E|=n$を満たし, $\mathcal{B}$ は基の全体とします. マトロイドの独立性オラクルが与えられたとき, $|\mathcal{B}|$ を求めるという問題を考えます.

マトロイドの数え上げは例えばグラフの全域木の総数やグラフのreliability (分配関数みたいなもの)の計算を求める問題を含んでおり, かなり多くの研究結果があります. 今回の記事では

Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

という論文の内容について, 簡略に紹介したいと思います. ここで載せたリンクはarXivのものですが, この論文はFOCS 2018に採択されています[1]. 論文そのものはlog-concave polynomialという凄い道具について解析をしており, その一つの応用としてマトロイドの数え上げ近似をするという内容なのですが, 凄い道具の解析は凄い難しく私も咀嚼しきれていないため, 本記事では凄い道具をどのように使って数え上げ近似をするのかについて焦点を絞ります.

論文の概要: log-concave polynomialに関する理論を築いた. その帰結として, ランク $r$ に対して, 独立性オラクルの下でマトロイドの基の総数の$2^{O(r)}$-近似を出力する多項式時間決定的アルゴリズムを与えた. 二つのマトロイドの共通基の個数も同様の近似比のアルゴリズムを与えた. 近似解はマトロイドの基多面体上のある最適化問題を解くことによって得られる.

0. マトロイドの基の数え上げについて

マトロイドの基の数え上げは割と長く研究されていて, これまでは Balanced matroid と呼ばれるクラスのマトロイドに対してはMCMCに基づく多項式時間乱択近似アルゴリズムが知られていました. この辺の話題はNIPS2018のチュートリアルでも関連した話題が取り扱われており, 注目の高さが伺えます.

グラフの全域木の総数は行列木定理により簡単に数えることが出来ます. ではこれを拡張してマトロイドの基は数えられるのでしょうか？

結論から言うとマトロイドの基の数え上げはとても難しいと信じられています. 具体的に言うとバイナリマトロイドの基の数え上げは#P-困難であることが知られています. 従って方向性としては近似アルゴリズムを考えるのが自然です. しかし近似率にも下界が知られており, 独立性オラクルモデルを多項式回呼び出すどんな決定的アルゴリズムも近似比は (P≠NPとは独立に) $2^{\Omega(n/(\log n)^2)}$になることが知られています [2]. この結果の系として, ランク $r\gg\log n$であれば近似比の下界

$2^{\Omega(r/(\log n)^2)}$          ...(1)

が導出されます.

冒頭で述べた通り, balanced matroidと呼ばれるクラスのマトロイドに対してはMCMCに基づく近似アルゴリズムが知られています[3]. 用語を知っている人向けに言うと, このアルゴリズムは
Balanced matroid ならば $\mathcal{M}$ とそのいかなるマイナーに対してもnegative correlationが成り立つので, base exchange graph上のランダムウォークにより基の(近似的な)一様サンプリングが可能になる. そこで Jerrum, Valiand and Vaziraniによる有名な結果 (サンプリングと数え上げ近似の関係) を使うと基の数え上げの近似が出来る.

という流れになっています. 噛み砕いて言うとbalanced matroidだと base exchange graph ($\mathcal{B}$が頂点集合で, 基交換公理によって行き来できる基同士を辺で結んだ巨大なグラフ) がエクスパンダーになっていて定常分布（ここでは一様分布）に早く収束し, 基の一様サンプリングが出来ます. そして実は一様サンプリングが出来れば数え上げで良い近似が出来るという結果が元からあるのでそれを使って数え上げの近似を行う, という流れです. 一般のマトロイドに対して base exchange graph がエクスパンダーかどうかはMihail-Vazirani 予想と呼ばれ, 長年未解決でしたが, 近年解決されたそうです (2019年1月時点ではarXiv上ですが).

重要な用語の定義を述べていきます. サイズ $n$ の台集合$E$上の集合族 $\mathcal{S}$ 及び $\mathcal{S}$上の確率測度 $\mu$ に対して

$g_\mu (x_1,\ldots,x_n) := \sum_{F\in \mathcal{S}} \mu(F)\prod_{e\in F} x_e$

という関数を定めます. この関数を $\mu$ の generating polynomial と呼びます. 以下では特に$\mathcal{S}$に属する任意の集合がサイズ$r$であるような場合のみを考えます (例えばマトロイドの基族). これまで知られている結果として, この関数が $\mathrm{Im}(x_i)>0$ for every $i=1,\ldots,n$ なる任意の点 $\mathbf{x}=(x_1,\ldots,x_n)$に対して $g(\mathbf{x})\neq 0$ を満たす (この性質を real stable と呼びます) ならば, $\mu$に対して自然に定義される$\mathcal{S}$上のランダムウォークは定常分布$\mu$に収束するというのがあります. これによって数え上げの近似っぽいことが出来ます.
マトロイドの基上の一様分布に対するgenerating polynomialがreal stableであればそのマトロイドがbalancedであるということが知られています.

ここまでで述べたように, 基の数え上げに対するアルゴリズムとしてはMCMCに基づくものが基本形でした (特定のマトロイドに関してはad-hocに数え上げるアルゴリズムは存在する). しかし今回紹介する論文では, 決定的なアルゴリズムで近似比が $2^{O(r)}$ となるものを提案します. これは近似比の下界(1)と比較すると右肩にちょっとだけギャップがありますが, とても面白いアルゴリズムです.

1. エントロピーを用いた$|\mathcal{B}|$の近似

情報理論や物理学ではエントロピーという概念がよく知られています. ここでは, 基族上の確率測度 $\mu:\mathcal{B}\to\mathbb{R}_{\geq 0}$ に対して

$H(\mu)=\sum_{F\in\mathcal{B}}\mu(B)\log\frac{1}{\mu(B)}$

をエントロピーと呼びます. もし$\mu$が$\mathcal{B}$上の一様分布ならば, $H(\mu)=\log|\mathcal{B}|$ が成り立ちます. もしもランク$r$のマトロイドの基族$\mathcal{B}$上の一様分布$\mu$に対し,
$H(\mu)-r \leq \beta \leq H(\mu)$
を満たす $\beta$ が計算できたとすると, $\exp(\beta)$ は $|\mathcal{B}|$ の$2^{O(r)}$-近似になっています. この$\beta$を計算することを考えます.

台集合$E$の要素 $e\in E$ に対し, $\mu_e:=\mu(\{F\in\mathcal{B}:F\ni e\})$ と定めます. つまり$\mu_e$はアイテム$e$を含む確率 (marginal probability) に対応しています. 論文中では次の結果を証明しています:

Theorem 1.
もしも$\mu$の generating polynomial $g_\mu$ が log-concaveならば, そのエントロピー $H(\mu)$ について, $H(\mu)\geq \sum_{e\in E} \mu_e\log\frac{1}{\mu_e}$ が成り立つ.

Theorem 2.
マトロイドの基族$\mathcal{B}$上の一様分布$\mu$に対応する generating polynomial は log-concave である.

また, エントロピーの劣加法性より, 以下の事実が簡単に確認できます:

Proposition 3.
$H(\mu) \leq \sum_{e\in E}\left(\mu_e\log\frac{1}{\mu_e}+(1-\mu_e)\log\frac{1}{1-\mu_e}\right)=\sum_{e\in E}H(\mu_e)$.

ここで, 関数 $f:x\mapsto (1-x)\log\frac{1}{1-x}$ は $0\leq x\leq 1$に対して $f(x)\leq x$が成り立ちます. 従って, ランク$r$のマトロイドの基族$\mathcal{B}$を考え, $x=\mu_e$を代入して$e\in E$について総和をとると,

$\sum_{e\in E}\mu_e\log\frac{1}{1-\mu_e}\leq \sum_{e\in E}\mu_e \leq \sum_{F\in\mathcal{B}}r\cdot \mu(F)=r$

が得られます. ここで Theorem 1 と Proposition 3 を組み合わせると,

$\sum_{e\in E}(1-\mu_e)\log\frac{1}{\mu_e}\geq H(\mu)-r$

となるので, 系として

Corollary 4.

ランク$r$のマトロイドの基族$\mathcal{B}$上の分布$\mu$に対し, その generating polynomial が log-concave ならば,

$H(\mu)\geq \sum_{e\in E}\mu_e\log\frac{1}{\mu_e}\geq H(\mu)-r$

が成り立つ.

2. 提案アルゴリズム

前節の結果より, marginal probability $\mu_e$ を計算出来れば良いのですが, それはそもそも「アイテム$e$を含む基の個数は？」という問題の答えになっているため, 基の数え上げよりも難しそうです. そこで$\mu_e$を計算せずに済む方法を考えます.

マトロイド$M$の基族 $\mathcal{B}$ 上の一様分布 $\mu$ に対して, $n$次元ベクトル $(\mu_e)_{e\in E}=(\mu_1,\ldots,\mu_n)$ を考えると, 基多面体 $\mathcal{P}_M$ に属する点の一つになっていることがわかります. ここで, 基多面体とは, それぞれの基の indicator vector の凸包として定義されます.

$(\mu_1,\ldots,\mu_n) = \frac{1}{|\mathcal{B}|}\sum_{F\in \mathcal{B}} 1_F$

より確かに marginal distribution のなすベクトルは基多面体$\mathcal{P}_M$内の点に含まれています. そこで, 次の最適化問題を考えます:

maximize: $\sum_{i=1}^n H(p_i)$
s.t.
     $(p_1,\ldots,p_n)\in \mathcal{P}_M$.

Proposition 3より, この問題の最適値 $\beta$ は求めたいエントロピー$H(\mu)=\log|\mathcal{B}|$の上界になっています. しかも, 目的関数は$p$について凹関数になっており, マトロイドの独立性オラクルがあれば$\mathcal{P}_M$上で分離オラクルが構成でき, 楕円体法を用いて多項式時間で解くことができます.

次に, 最適解 $p\in\mathcal{P}_M$ を考えます. 実は(論文中で示されているのですが) marginal distributionが$p$となるような$\mathcal{B}$上の分布$\hat{\mu}$で, generating polynomial $g_{\hat{\mu}}$が log-concave となるものが構成出来ます (つまり, $p_e=\hat{\mu}_e$が成り立つ). この$\hat{\mu}$に対して Corollary 4を適用すると,

$H(\hat{\mu})\geq \sum_{e\in E}\hat{\mu}_e\log\frac{1}{\hat{\mu}_e}=\sum_{e\in E}p_e\log\frac{1}{p_e}\geq \sum_{e\in E}H(p_e)-r\geq H(\mu)-r$.

更に, $H(\hat{\mu})\leq H(\mu)$ が成り立つ (一様分布$\mu$がエントロピーを最大化する) ので, 結果として, 最適化問題の最適値$\beta$に対して

$\beta-r \leq H(\mu)=\log|\mathcal{B}|\leq \beta$

が成り立つので, 近似比 $2^{O(r)}$ が成り立ちます.

3. まとめ

アルゴリズムは単純ですが, 近似比の保証において「generating polynomial $g_\mu$ が log-concaveならば〜」というステートメントが多く出ています. ここで紹介した論文の貢献としては log-concave function の解析にあって, 提案アルゴリズムはその応用先の一つでしかありません (とはいっても重要な結果です). 著者たちは更に別の続編とも言うべき論文 (こちらは2019年1月時点ではarXivに上がっているだけですが) で, Mihail-Vazirani 予想を解決しマトロイドのbase の数え上げに対してMCMCに基づく FPRAS を提案しており, 今後も離散の世界における log-concave 性が発展していくことになるかと思います (連続の世界ではlog-concave はすでに注目されていていろんなことが知られています).


[1]. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids, N. Anari, S. O. Gharan, and C. Vinzant, In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS) , 2018.

[2]. On the problem of approximating the number of bases of a matroid, Y. Azar, A. Z. Broder, and A. M. Frieze, Information Processing Letters Volume 50, Issue 1, 1994.

[3]. Balanced matroids, T. Feder, and M. Mihail, In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), 1992.