漸近的等分配性: 情報理論入門 9 - コンピュータフリーク

漸近的等分配性とは、非常に長い確率的な系列には、出てくる確率が高い「代表的な系列」のみが現れ、それらの確率値はほとんど等しくなるという性質です。この性質は情報理論のさまざまな場面に顔を出し、多くの結果の証明につながる重要な概念です。

問題設定

有限集合 $\mathcal{X}$ 上の値を取る確率分布 $p(x)$ があるとし、この分布に従って独立なサンプル $x_1, x_2, x_3 \cdots$ を取るとします。すなわち、$p(x_1, x_2, \cdots, x_n) = p(x_1) p(x_2) \cdots p(x_n)$ です。非常に長い系列をサンプルするとすると、系列には高い確率で特殊な性質が現れます。それはいったいどのような性質でしょうか。

たとえば $\mathcal{X} = \{0, 1\}$ とし、$p(0) = 0.1, p(1) = 0.9$ とすると、系列の大半は $1$ となり、対数の法則よりその割合は $0.9$ に近づいていくと考えられます。これを精緻化したのが、以下でみる代表的系列と漸近的等分配性です。

記法

確率変数 $X$ に対して、エントロピーを $H(X) = – \sum_{x \in \mathcal{X}} p(x) \log_2 p(x)$ と定義します。確率変数 $X, Y$ の相互情報量を $I(X; Y)$ により表します。集合 $\mathcal{X}$ の要素数を $|\mathcal{X}|$ により表します。

代表的系列

漸近的等分配性とは、非常に長い系列には、代表的な系列のみが現れることを示す理論です。代表的な系列とは、$\mathcal{X} = \{0, 1\}, p(0) = 0.1, p(1) = 0.9$ の例でいうと、$0.9$ の割合で $1$ が含まれ、$0.1$ の割合で $0$ が含まれる系列です。これを一般の確率分布に拡張して定式化すると、以下のようになります。

定義: 代表的系列

確率分布 $p(x)$ に従う独立同分布な確率変数 $X_1, X_2, \cdots, X_n$ と正数 $\varepsilon > 0$ について、$\varepsilon$-代表的系列を以下の性質を満たす系列 $x_1, x_2, \cdots, x_n$ とする。$$2^{-n(H(X) + \varepsilon)} \le p(x_1, x_2, \cdots, x_n) \le 2^{-n(H(X) – \varepsilon)}$$ また、この性質を満たす系列の集合を $A^{(n)}_{\varepsilon} \subset \mathcal{X}^n$ と表す。

例: 二値分布

$\mathcal{X} = \{0, 1\}, p(0) = 0.1, p(1) = 0.9$ とし、$n = 20, \varepsilon = 0.1$ とします。$$H(X) = – 0.1 \log_2 0.1 – 0.9 \log_2 0.9 \approx 0.469$$ であるので、代表的系列は $$A^{(20)}_{0.1} = \{x \in \mathcal{X}^n \mid 0.000375 \le p(x) \le 0.00600\}$$ となります。確率を具体的に計算すると、$1$ が $2$ 個または $3$ 個含まれる長さ $20$ の系列が $A^{(20)}_{0.1}$ に含まれることが分かります。

(p(1)\) が大きいため、全てが $1$ である系列 $x_{\text{onlyone}} = 111\cdots1$ が $\mathcal{X}^{20}$ の中で最も $p(x)$ が大きくなりますが、そのような確率値を取る系列は少ない（$x_{\text{onlyone}}$ のみである）ことから、代表的系列からは除外されています。この意味は次の漸近的等分配性定理でより明らかになります。

漸近的等分配性

十分 $n$ が大きいと、系列は代表的系列のみになるというのが漸近的等分配性です。具体的には、以下の定理でまとめられます。

定理: 漸近的等分配定理

任意の $\varepsilon, \varepsilon’ > 0$ について、十分大きい $n$ において、$\text{Pr}[x \in A^{(n)}_\varepsilon] > 1 – \varepsilon’$ である。
$|A^{(n)}_\varepsilon| \le 2^{n(H(X) + \varepsilon)}$ である。
十分大きい $n$ において、$|A^{(n)}_\varepsilon| \ge (1 – \varepsilon) 2^{n(H(X) – \varepsilon)}$ である。

第一の性質がまさしく十分 $n$ が大きいときに系列は代表的系列のみになることを表しています。第二と第三の性質より、$|\mathcal{X}|^n$ パターン存在する系列のうち、およそ $2^{H(X)}$ パターンのみが代表的系列であることを示しています。代表的系列はその定義から、それぞれが実現する確率はほとんど等しいので、十分長い系列は、$A^{(n)}_\varepsilon$ からの一様サンプルで近似できるというのが漸近的等分配性です。

証明

1. $$\begin{align*}\text{Pr}[x \in A^{(n)}_\varepsilon] &\stackrel{(a)}{=} \text{Pr}\left[-n(H(X) + \varepsilon) \le \log_2 p(x) \le -n(H(X) – \varepsilon)\right] \\ &\stackrel{(b)}{=} \text{Pr}\left[H(X) – \varepsilon \le -\frac{1}{n} \log_2 p(x) \le H(X) + \varepsilon \right] \\ &\stackrel{(c)}{=} \text{Pr}\left[H(X) – \varepsilon \le -\frac{1}{n} \sum_{i = 1}^n \log_2 p(x_i) \le H(X) + \varepsilon \right]\end{align*}$$ ただし、(a) は代表的系列の定義に対数を適用し、(b) は両辺を $-n$ で割り、(c) は $x$ が独立であることを用いた。大数の法則より、中辺は $$-\frac{1}{n} \sum_{i = 1}^n \log_2 p(x_i) \to \mathbb{E}_{X}[-\log_2 p(X)] = H(X)$$ に確率 $1$ で収束する。よって、十分大きく $n$ をとると、$$H(X) – \varepsilon \le -\frac{1}{n} \sum_{i = 1}^n \log_2 p(x_i) \le H(X) + \varepsilon$$ は任意に高い確率で満たされる。

2. $$\begin{align*}1 &\stackrel{(a)}{=} \sum_{x \in \mathcal{X}^n} p(x) \\ &\stackrel{(b)}{\ge} \sum_{x \in A^{(n)}_\varepsilon} p(x) \\ &\stackrel{(c)}{\ge} \sum_{x \in A^{(n)}_\varepsilon} 2^{-n(H(X) + \varepsilon)} \\ &= |A^{(n)}_\varepsilon| 2^{-n(H(X) + \varepsilon)}\end{align*}$$ ただし、(a) は確率分布の定義より、(b) は $A^{(n)}_{\varepsilon} \subset \mathcal{X}^n$ と $p(x) \ge 0$ より、(c) は代表的系列の定義より成り立つ。よって、$$|A^{(n)}_\varepsilon| \le 2^{n(H(X) + \varepsilon)}$$ である。

3. 十分大きく $n$ を取ると、$$\begin{align*} 1 – \varepsilon &\stackrel{(a)}{\le} \text{Pr}[x \in A^{(n)}_\varepsilon] \\ &= \sum_{x \in A^{(n)}_\varepsilon} p(x) \\ &\stackrel{(b)}{\le} \sum_{x \in A^{(n)}_\varepsilon} 2^{-n(H(X) – \varepsilon)} \\ &= |A^{(n)}_\varepsilon| 2^{-n(H(X) – \varepsilon)}\end{align*}$$ ただし、(a) は本定理第一の結果を、(b) は代表的系列の定義を用いた。よって、$$|A^{(n)}_\varepsilon| \ge (1 – \varepsilon) 2^{n(H(X) – \varepsilon)}$$ である。

同時代表的系列と同時漸近的等分配性

代表的系列と漸近的等分配性は同時分布についても同様の結果が得られます。ここでは、同時分布 $p(x, y)$ からの独立なサンプル系列 $(x_1, y_1), (x_2, y_2), \cdots$ を考えます。$(x_i, y_i)$ と $(x_j, y_j)~(i \neq j)$ は独立ですが、$x_i$ と $y_i$ は独立ではないことに注意してください。

定義: 同時代表的系列

確率分布 $p(x, y)$ に従う独立同分布な確率変数 $(X_1, Y_1), (X_2, Y_2), \cdots, (X_n, Y_n)$ と正数 $\varepsilon > 0$ について、$\varepsilon$-同時代表的系列を以下の性質をすべて満たす系列 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ とする。$$2^{-n(H(X, Y) + \varepsilon)} \le p(x_1, y_1, x_2, y_2, \cdots, x_n, y_n) \le 2^{-n(H(X, Y) – \varepsilon)}$$ $$2^{-n(H(X) + \varepsilon)} \le p(x_1, x_2, \cdots, x_n) \le 2^{-n(H(X) – \varepsilon)}$$ $$2^{-n(H(Y) + \varepsilon)} \le p(y_1, y_2, \cdots, y_n) \le 2^{-n(H(Y) – \varepsilon)}$$ また、この性質を満たす系列の集合を $A^{(n)}_{\varepsilon} \subset (\mathcal{X} \times \mathcal{Y})^n$ と表す。

定理: 同時漸近的等分配定理

任意の $\varepsilon, \varepsilon’ > 0$ について、十分大きい $n$ において、$\text{Pr}[(x, y) \in A^{(n)}_\varepsilon] > 1 – \varepsilon’$ である。
$|A^{(n)}_\varepsilon| \le 2^{n(H(X, Y) + \varepsilon)}$ である。
十分大きい $n$ において、$|A^{(n)}_\varepsilon| \ge (1 – \varepsilon) 2^{n(H(X, Y) – \varepsilon)}$ である。
$\hat{x} = (\hat{x}_1, \hat{x}_2, \cdots, \hat{x}_n) \sim p(x), \hat{y} = (\hat{y}_1, \hat{y}_2, \cdots, \hat{y}_n) \sim p(y)$ と、それぞれの系列を独立に周辺分布からサンプルする。このとき、$$\text{Pr}[(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon] \le 2^{-n(I(X; Y) – 3\varepsilon)}$$ が成り立ち、十分大きい $n$ について $$\text{Pr}[(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon] \ge (1 – \varepsilon)2^{-n(I(X; Y) + 3\varepsilon)}$$ が成り立つ。

第一と第二と第三の命題は通常の漸近的等分配定理とほとんど同じです。第四の性質については同時分布特有のものです。これは、元の確率分布 $p(x, y)$ の相互情報量が小さい（=独立に近い）ならば、それぞれを独立にサンプルしても代表的系列が高い確率で得られる一方、相互情報量が大きい（=独立から遠い）ならば、それぞれを独立にサンプルしても代表的系列は得られないことを示しています。

証明

1. 通常の漸近的等分配定理の証明と同様に、大数の法則より、$$\text{Pr}\left[H(X) – \varepsilon \le -\frac{1}{n} \sum_{i = 1}^n \log_2 p(x_i) \le H(X) + \varepsilon \right]$$ $$\text{Pr}\left[H(Y) – \varepsilon \le -\frac{1}{n} \sum_{i = 1}^n \log_2 p(y_i) \le H(Y) + \varepsilon \right]$$ $$\text{Pr}\left[H(X, Y) – \varepsilon \le -\frac{1}{n} \sum_{i = 1}^n \log_2 p(x_i, y_i) \le H(Y) + \varepsilon \right]$$ は任意に高い確率で満たされる。よって、これら全てが同時に満たされる確率も、ブールの不等式より任意に高くできる。ゆえに、十分大きい $n$ において、$$\text{Pr}[(x, y) \in A^{(n)}_\varepsilon] > 1 – \varepsilon’$$ である。

2. $$\begin{align*}1 &\stackrel{(a)}{=} \sum_{(x, y) \in \mathcal{X}^n \times \mathcal{Y}^n} p(x, y) \\ &\stackrel{(b)}{\ge} \sum_{(x, y) \in A^{(n)}_\varepsilon} p(x, y) \\ &\stackrel{(c)}{\ge} \sum_{(x, y) \in A^{(n)}_\varepsilon} 2^{-n(H(X, Y) + \varepsilon)} \\ &= |A^{(n)}_\varepsilon| 2^{-n(H(X, Y) + \varepsilon)}\end{align*}$$ ただし、(a) は確率分布の定義より、(b) は $A^{(n)}_{\varepsilon} \subset \mathcal{X}^n$ と $p(x) \ge 0$ より、(c) は代表的系列の定義より成り立つ。よって、$$|A^{(n)}_\varepsilon| \le 2^{n(H(X, Y) + \varepsilon)}$$ である。

3. 十分大きく $n$ を取ると、$$\begin{align*} 1 – \varepsilon &\stackrel{(a)}{\le} \text{Pr}[(x, y) \in A^{(n)}_\varepsilon] \\ &= \sum_{(x, y) \in A^{(n)}_\varepsilon} p(x) \\ &\stackrel{(b)}{\le} \sum_{(x, y) \in A^{(n)}_\varepsilon} 2^{-n(H(X) – \varepsilon)} \\ &= |A^{(n)}_\varepsilon| 2^{-n(H(X, Y) – \varepsilon)}\end{align*}$$ ただし、(a) は本定理第一の結果を、(b) は代表的系列の定義を用いた。よって、$$|A^{(n)}_\varepsilon| \ge (1 – \varepsilon) 2^{n(H(X, Y) – \varepsilon)}$$ である。

4. $$\begin{align*} \text{Pr}[(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon] &= \sum_{(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon} p(\hat{x}) p(\hat{y}) \\ &\stackrel{(a)}{\le} \sum_{(x, y) \in A^{(n)}_\varepsilon} 2^{-n(H(X) – \varepsilon)} 2^{-n(H(Y) – \varepsilon)} \\ &\stackrel{(b)}{\le} 2^{n(H(X, Y) + \varepsilon)} 2^{-n(H(X) – \varepsilon)} 2^{-n(H(Y) – \varepsilon)} \\ &= 2^{-n(H(X) + H(Y) – H(X, Y) – 3\varepsilon)} \\&\stackrel{(c)}{=} 2^{-n(I(X; Y) – 3\varepsilon)}\end{align*}$$ ただし、(a) は代表的系列の定義を、(b) は本定理第二の結果を、(c) では $$\begin{align*} H(X) + H(Y) – H(X, Y) &= \mathbb{E}[-\log p(X) – \log p(Y) + \log p(X, Y)] \\ &= \mathbb{E}[-\log \frac{p(X, Y)}{p(X) p(Y)}] \\ &= \mathbb{E}[-\log \frac{p(X \mid Y)}{p(X)}] \\ &= I(X; Y) \end{align*}$$ 用いた。また、十分 $n$ が大きいとき、$$\begin{align*} \text{Pr}[(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon] &= \sum_{(\hat{x}, \hat{y}) \in A^{(n)}_\varepsilon} p(\hat{x}) p(\hat{y}) \\ &\stackrel{(a)}{\ge} \sum_{(x, y) \in A^{(n)}_\varepsilon} 2^{-n(H(X) + \varepsilon)} 2^{-n(H(Y) + \varepsilon)} \\ &\stackrel{(b)}{\ge} (1 – \varepsilon) 2^{n(H(X, Y) – \varepsilon)} 2^{-n(H(X) + \varepsilon)} 2^{-n(H(Y) + \varepsilon)} \\ &= (1 – \varepsilon) 2^{-n(H(X) + H(Y) – H(X, Y) + 3\varepsilon)} \\&\stackrel{(c)}{=} (1 – \varepsilon) 2^{-n(I(X; Y) – 3\varepsilon)}\end{align*}$$ ただし、(a) は代表的系列の定義を、(b) は本定理第三の結果を、(c) では $$\begin{align*} H(X) + H(Y) – H(X, Y) = I(X; Y) \end{align*}$$ 用いた。