問2

定常無記憶情報源 $X_1X_2 \dots$ を考える。この情報源のアルファベットを有限集合 $\chi$ とし、各 $X_i$ は確率分布 $p(x)$ に従うものとする。任意に固定された $\varepsilon > 0$ に対し、系列 $(x_1, x_2, \dots, x_n) \in \chi^n$ が

$$2^{-n(H(X_1)+\varepsilon)} \leq p(x_1, x_2, \dots, x_n) \leq 2^{-n(H(X_1)-\varepsilon)}$$

を満たすとき、この系列を $p(x)$ に関する典型系列であると言う。ここで、$H(X_1)$ は $X_1$ のエントロピーを表し、$p(x_1, x_2, \dots, x_n)$ は同時確率分布を表す。全ての典型系列からなる集合を $A_\varepsilon^{(n)}$ と表記する。次の各問いに答えよ。ただし、$X = \{0, 1\}, p(0) = 1 - \alpha, p(1) = \alpha$ とする。ここで $\alpha \in (0, 1)$ は定数である。

1. $(x_1, x_2, \dots, x_{10}) = (0, 1, 1, 0, 0, 0, 0, 1, 0, 0)$ に対し、$p(x_1, x_2, \dots, x_{10})$ を求めよ。
2. $H(X_i)$ ($i = 1, 2, \dots, n$) および $H(X_1, X_2, \dots, X_n)$ を求めよ。
3. $x = (x_1, x_2, \dots, x_n)$ に対し、$S(x) = \sum_{i=1}^n x_i$ とおく。$\alpha = 0.2, n = 200, \varepsilon = 0.01$ とする。$A_\varepsilon^{(n)}$ に属する系列 $x$ に対する $S(x)$ の範囲を求めよ。

中文翻译

设定常无记忆信息源 $X_1X_2 \dots$，其字母表为有限集合 $\chi$，各 $X_i$ 遵循概率分布 $p(x)$。对任意固定的 $\varepsilon > 0$，若序列 $(x_1, x_2, \dots, x_n) \in \chi^n$ 满足：

$$2^{-n(H(X_1)+\varepsilon)} \leq p(x_1, x_2, \dots, x_n) \leq 2^{-n(H(X_1)-\varepsilon)}$$

则称此序列为 $p(x)$ 的典型序列，其中 $H(X_1)$ 表示 $X_1$ 的熵，$p(x_1, x_2, \dots, x_n)$ 表示联合概率分布。所有典型序列的集合记为 $A_\varepsilon^{(n)}$。回答以下问题：

1. 对序列 $(x_1, x_2, \dots, x_{10}) = (0, 1, 1, 0, 0, 0, 0, 1, 0, 0)$，求其 $p(x_1, x_2, \dots, x_{10})$。
2. 求 $H(X_i)$ 和联合熵 $H(X_1, X_2, \dots, X_n)$。
3. 对于 $x = (x_1, x_2, \dots, x_n)$，令 $S(x) = \sum_{i=1}^n x_i$，已知 $\alpha = 0.2, n = 200, \varepsilon = 0.01$，求属于 $A_\varepsilon^{(n)}$ 的序列 $x$ 的 $S(x)$ 的范围。

---

o1

以下的推导中，默认对数均为以 2 为底（即 $\log \equiv \log_2$）。若题目中未特别指定底数，信息论中常用 $\log_2$ 计算熵。

---

1. 求 $\displaystyle p(x_1, x_2, \dots, x_{10})$

给定：

$$X = \{0,1\},\quad p(0) = 1 - \alpha,\quad p(1) = \alpha.$$

并且 $\{X_i\}$ 独立同分布(i.i.d.)。
题目中的具体序列是

$$(x_1, x_2, \dots, x_{10}) = (0,\,1,\,1,\,0,\,0,\,0,\,0,\,1,\,0,\,0).$$

数一数其中“1”的个数与“0”的个数：

• “1”的个数 = 3
• “0”的个数 = 7

由于 $X_i$ 相互独立，故该序列的概率为

$$p(x_1,x_2,\dots,x_{10}) = (1-\alpha)^{\text{(“0”的个数)}} \,\alpha^{\text{(“1”的个数)}} = (1-\alpha)^{7} \,\alpha^{3}.$$

---

2. 求 $H(X_i)$ 与 $H(X_1, X_2, \dots, X_n)$

1. 单个符号的熵 $H(X_i)$

   对伯努利随机变量 $X_i$（取值 0 或 1），其熵为

   $$H(X_i) = -\bigl((1-\alpha)\log(1-\alpha) + \alpha\log(\alpha)\bigr).$$

   这是标准的 Bernoulli($\alpha$) 熵公式。

2. 联合熵 $H(X_1, X_2, \dots, X_n)$

   由于 $X_1, X_2, \dots, X_n$ 独立同分布(i.i.d.)，故其联合熵为

   $$H(X_1, X_2, \dots, X_n) = \sum_{i=1}^n H(X_i) = n \, H(X_1).$$

---

3. 对典型集合中序列的 $S(x)$ 取值范围

题目给定：

$$\alpha = 0.2,\quad n = 200,\quad \varepsilon = 0.01.$$

并定义

$$S(x) \;=\; \sum_{i=1}^n x_i,\quad x_i \in \{0,1\}.$$

典型集合 $A_\varepsilon^{(n)}$ 的定义是：

$$2^{-n\bigl(H(X_1)+\varepsilon\bigr)} \;\;\le\;\; p(x_1,\dots,x_n) \;\;\le\;\; 2^{-n\bigl(H(X_1)-\varepsilon\bigr)},$$

其中

$$p(x_1,\dots,x_n) = \alpha^{\sum x_i}\,(1-\alpha)^{\,n-\sum x_i} = \alpha^{S(x)}\,(1-\alpha)^{\,n - S(x)}.$$

---

3.1 将不等式转化为“经验分布”形式

令 $\displaystyle \theta = \frac{S(x)}{n}$。则

$$p(x) = \alpha^{n\theta}\,(1-\alpha)^{\,n(1-\theta)}, \quad -\frac1n \log p(x) = -\Bigl(\,\theta\log\alpha + (1-\theta)\log(1-\alpha)\Bigr).$$

记伯努利($\alpha$) 的熵为

$$H(\alpha) = -\bigl(\alpha\log \alpha + (1-\alpha)\log(1-\alpha)\bigr).$$

则典型集合的条件可写为

$$H(\alpha) - \varepsilon \;\;\le\; -\frac1n\log p(x) \;\;\le\; H(\alpha) + \varepsilon,$$

即

$$H(\alpha) - \varepsilon \;\;\le\; -\Bigl(\theta\log\alpha + (1-\theta)\log(1-\alpha)\Bigr) \;\;\le\; H(\alpha) + \varepsilon.$$

从而得到

$$\bigl|\, -(\theta\log\alpha + (1-\theta)\log(1-\alpha)) \;-\; H(\alpha)\bigr| \;\le\; \varepsilon.$$

也就是说，只有当 $\theta$ 使得该式在 $\pm \varepsilon$ 的范围内成立，$x$ 才会落在典型集合里。

---

3.2 在 $\alpha = 0.2$ 时的线性化简

对 $\alpha = 0.2$ 来说，

$$H(\alpha) = -\bigl(0.2\log 0.2 + 0.8\log 0.8\bigr).$$

用 $\log_2$ 来算，可得到大约

$$H(0.2) \approx 0.7219\quad (\text{比特}).$$

另一方面，

$$-\bigl(\theta\log 0.2 + (1-\theta)\log 0.8\bigr)$$

在 $\log_2$ 下其实是一个关于 $\theta$ 的线性函数(可由数值代入后发现)。
具体计算(保留 4~5 位小数即可)：

• $\log_2 (0.2) \approx -2.321928$,
• $\log_2 (0.8) \approx -0.321928$.

所以

$$-\bigl(\theta\log 0.2 + (1-\theta)\log 0.8\bigr) = \theta\cdot 2.321928 \;+\; (1-\theta)\cdot 0.321928 = 0.321928 \;+\; 2.0\,\theta.$$

再核对一下 $\theta=0.2$ 时

$$0.321928 \;+\; 2.0\times 0.2 = 0.321928 + 0.4 = 0.721928,$$

正好与 $H(0.2)$ 符合。

---

3.3 令该线性函数落入 $[\,H(0.2)-\varepsilon,\;H(0.2)+\varepsilon]$

我们要找所有 $\theta$ 使

$$0.321928 \;+\; 2.0\,\theta \;\in\; \bigl[\,0.721928 - 0.01,\;0.721928 + 0.01\bigr] = [\,0.711928,\;0.731928\,].$$

令此区间为 $[\,L, U]$，则

1. 下界 $L = 0.711928$:

   $$0.321928 + 2.0\,\theta \;\ge\; 0.711928 \quad\Longrightarrow\quad 2.0\,\theta \;\ge\; 0.711928 - 0.321928 = 0.39 \quad\Longrightarrow\quad \theta \;\ge\; 0.195.$$

2. 上界 $U = 0.731928$:

   $$0.321928 + 2.0\,\theta \;\le\; 0.731928 \quad\Longrightarrow\quad 2.0\,\theta \;\le\; 0.731928 - 0.321928 = 0.41 \quad\Longrightarrow\quad \theta \;\le\; 0.205.$$

因此对于 $\theta = \frac{S(x)}{n}$，我们得到

$$0.195 \;\le\; \theta \;\le\; 0.205.$$

最后将 $n = 200$ 代回：

$$S(x) = n\,\theta \;\in\; [\,200 \times 0.195,\;200 \times 0.205\,] = [\,39,\;41\,].$$

因为 $S(x)$ 必须是整数，所以

$$S(x) \in \{\,39,\;40,\;41\}.$$

---

总结答案

1. $p(x_1,\dots,x_{10})$：

   $$(x_1,\dots,x_{10}) = (0,1,1,0,0,0,0,1,0,0) \quad\Longrightarrow\quad p(x_1,\dots,x_{10}) = (1-\alpha)^7 \,\alpha^3.$$

2. 熵 $H(X_i)$ 与联合熵

   $$H(X_i) = -\bigl(\alpha\log \alpha + (1-\alpha)\log (1-\alpha)\bigr), \quad H\bigl(X_1, \dots, X_n\bigr) = n\,H(X_1).$$

3. 典型集合中 $S(x)$ 的范围
   在 $\alpha=0.2, n=200, \varepsilon=0.01$ 条件下，属于典型集合 $A_\varepsilon^{(n)}$ 的序列 $x$ 必须满足

   $$S(x) \;\in\; \{\,39,\,40,\,41\}.$$