R03-B-問2

問2

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

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

を満たすとき、この系列を $p(x)$ に関する典型系列であると言う。ここで、$H(X_1)$ は $X_1$ のエントロピーを表し、$p(x_1,x_2,\dots ,x_n)$ は同時確率分布を表す。全ての典型系列からなる集合を $A_{\epsilon }^{(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,\epsilon =0.01$ とする。$A_{\epsilon }^{(n)}$ に属する系列 $x$ に対する $S(x)$ の範囲を求めよ。

中文翻译

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

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

则称此序列为 $p(x)$ 的典型序列，其中 $H(X_1)$ 表示 $X_1$ 的熵，$p(x_1,x_2,\dots ,x_n)$ 表示联合概率分布。所有典型序列的集合记为 $A_{\epsilon }^{(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,\epsilon =0.01$，求属于 $A_{\epsilon }^{(n)}$ 的序列 $x$ 的 $S(x)$ 的范围。

---

o1

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

---

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

给定：

$$X=\{0,1\},p(0)=1-\alpha ,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)=-((1-\alpha )\log (1-\alpha )+\alpha \log (\alpha )).$$

   这是标准的 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)=nH(X_1).$$

---

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

题目给定：

$$\alpha =0.2,n=200,\epsilon =\mathrm{0.01.}$$

并定义

$$S(x)=\sum _{i=1}^n{x}_i,x_i\in \{0,1\}.$$

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

$$2^{-n(H(X_1)+\epsilon )}\le p(x_1,\dots ,x_n)\le 2^{-n(H(X_1)-\epsilon )},$$

其中

$$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 将不等式转化为“经验分布”形式

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

$$p(x)={\alpha }^{n\theta }(1-\alpha {)}^{n(1-\theta )},-\frac{1}{n}\log p(x)=-(\theta \log \alpha +(1-\theta )\log (1-\alpha )).$$

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

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

则典型集合的条件可写为

$$H(\alpha )-\epsilon \le -\frac{1}{n}\log p(x)\le H(\alpha )+\epsilon ,$$

即

$$H(\alpha )-\epsilon \le -(\theta \log \alpha +(1-\theta )\log (1-\alpha ))\le H(\alpha )+\epsilon .$$

从而得到

$$|-(\theta \log \alpha +(1-\theta )\log (1-\alpha ))-H(\alpha )|\le \epsilon .$$

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

---

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

对 $\alpha =0.2$ 来说，

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

用 ${\log }_2$ 来算，可得到大约

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

另一方面，

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

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

• ${\log }_2(0.2)\approx -2.321928$,
• ${\log }_2(0.8)\approx -0.321928$.

所以

$$-(\theta \log 0.2+(1-\theta )\log 0.8)=\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)-\epsilon ,H(0.2)+\epsilon ]$

我们要找所有 $\theta$ 使

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

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

1. 下界 $L=0.711928$:

   $$0.321928+2.0\theta \ge 0.711928⟹2.0\theta \ge 0.711928-0.321928=0.39⟹\theta \ge \mathrm{0.195.}$$

2. 上界 $U=0.731928$:

   $$0.321928+2.0\theta \le 0.731928⟹2.0\theta \le 0.731928-0.321928=0.41⟹\theta \le \mathrm{0.205.}$$

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

$$0.195\le \theta \le \mathrm{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)⟹p(x_1,\dots ,x_{10})=(1-\alpha {)}^7{\alpha }^3.$$

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

   $$H(X_i)=-(\alpha \log \alpha +(1-\alpha )\log (1-\alpha )),H(X_1,\dots ,X_n)=nH(X_1).$$

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

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