東京大学 情報理工学系研究科 電子情報学専攻 2015年度 専門 第5問

标签：

• Tokyo-University
• Markov-Source-Stationary-Distribution
• Binary-Markov-Source-Run-Length-and-Entropy-Rate
• Entropy-Rate

Author

diohabara

Description

以下のような状態遷移図で示される二元単純マルコフ情報源を考える。

以下の問いに答えよ。

(1) 状態 $s_0,s_1$ の定常確率 $w_0,w_1$ を求めよ。

(2) 定常状態において出力 $1$ の発生する確率を求めよ。

(3) 出力系列から, 直前および直後が $0$ である $1$ の連続 ($1$ のラン)を任意に一つ取り出した時, その長さが $1,2,k$ である確率をそれぞれ求めよ。

(4) $1$ のランの平均長を求めよ。

(5) この情報源のエントロピーを求めよ。

(6) (2) で求めた生成確率でランダムに $1$ が発生する情報源のエントロピーを求めよ。この値と (5) で求めた値の違いについて論ぜよ。

(なお、計算に当たっては, $\log_23 = 1.58 ,\log_25 = 2.32$ を必要に応じて用いよ。)

题目描述

考虑上图状态转移图所表示的二元一阶马尔可夫信息源，回答下列问题。

(1) 求状态 $s_0,s_1$ 的平稳概率 $w_0,w_1$。

(2) 求平稳状态下输出符号 $1$ 的概率。

(3) 从输出序列中任取一段前后均为 $0$ 的连续 $1$（即一个 $1$ 游程），分别求其长度为 $1$、$2$、$k$ 的概率。

(4) 求 $1$ 游程的平均长度。

(5) 求该信息源的熵率。

(6) 构造一个以 (2) 所求概率独立随机地产生 $1$ 的信息源，求其熵，并讨论该值与 (5) 结果的差异。

计算时可按需使用 $\log_2 3=1.58$、$\log_2 5=2.32$。

考点

• 马尔可夫信源的平稳分布：要求由图中的状态转移概率求 $w_0,w_1$ 及稳态输出概率。
• 二元马尔可夫游程统计：要求建立 $1$ 游程长度的几何分布并计算指定长度概率与均值。
• 熵率与记忆性：要求按状态条件熵求信源熵率，并与同边缘分布的无记忆信源比较。

Kai

(1)

状態遷移図より以下の方程式が成り立つ

$$\begin{aligned} w_0 &= 0.9w_0 + 0.2w_1 \\ w_1 &= 0.1w_0 + 0.8w_1 \\ w_0 &+ w_1 = 1 \end{aligned}$$

これを解いて、

$$(w_0,w_1) = (\frac{2}{3},\frac{1}{3})$$

(2)

(1) より求める確率は

$$0.1w_0 + 0.8w_1 = \frac{1}{3}$$

(3)

長さ $k$ のランの場合、最初の $01$ を固定してその後 $l − 1$ 個のランが連続して現れ、その後 $0$ が出る確率を考えればよい。

この確率は $0.8^{k−1} \cdot 0.2$。よって、求める確率はそれぞれ $0.2、0.16、0.2 \cdot 0.8^{k−1}$ である。

(4)

求める平均長を $x$ とすると

$$\begin{aligned} x &= 0.2\sum_{k=1}^{\infty}k \cdot 0.8^{k-1} \\ 0.8x &= 0.2\sum_{k=1}^{\infty} \cdot 0.8^k \\ &= 0.2\sum_{l=2}^{\infty}(l - 1)\cdot 0.8^{l-1} \\ \end{aligned}$$

両辺の差を取って

$$\begin{aligned} 0.2x &= 0.2 + 0.2\sum_{k=2}^{\infty}0.8^{k-1} \\ &= 0.2\sum_{k=1}^{\infty}0.8^k = \frac{0.2}{1 - 0.8} = 1 \end{aligned}$$

よって、$x = 5$ となる。

(5)

求めるエントロピーは

$$\begin{aligned} &\quad \frac{2}{3}\big(-\frac{9}{10}\log(\frac{9}{10}) - \frac{1}{10}\log(\frac{1}{10})\big) + \frac{1}{3}\big(-\frac{8}{10}\log(\frac{8}{10}) - \frac{2}{10}\log(\frac{2}{10})\big) \\ &= \frac{2}{3}(\log10 - \frac{9}{5}\log3) + \frac{1}{3}(\log10 - \frac{13}{5}) \\ &= \log10 - 1.2 \cdot 1.58 - \frac{13}{15} \\ &= 1 + 2.32 - 1.896 - 0.867 = 3.32 - 2.763 \\ &= 0.557 \end{aligned}$$

(6)

確率 $\frac{1}{3}$ で $1$ が発生する際のエントロピーは $-\frac{1}{3}\log(\frac{1}{3}) - \frac{2}{3}\log(\frac{2}{3}) = \log3 - \frac{2}{3} = 0.913[\text{bit}]$ となり、(5) よりも大きくなる。