跳到主要内容

九州大学 システム情報科学府 情報理工学専攻 2019年8月実施 情報理論

标签：

Author​

Yu

Description​

【問 1】​

下図は, 定常 22 重マルコフ情報源 SS の状態遷移図である. 下記の設問に答えよ.

(1) 上図の状態遷移図を元に, このマルコフ情報源 SS の遷移確率行列 AA を求めよ. ただし, 状態 "0000","1010", "0101" の順に, 行を記せ.

(2) 時点 00 で状態 "00" にいたとして, 時点 22 で状態 "10" にいる確率はいくらか答えよ.

(3) 上記のマルコフ情報源 SS の定常分布 w⃗=(w1,w2,w3)\vec{w} = (w_1,w_2,w_3) を求めよ. ただし, wiw_i の添え字 i=1,2,3i = 1,2,3 は状態 "0000", "1010", "0101" にそれぞれ対応するものとする.

(4) 定常 22 重マルコフ情報源 X1,X2,…X_1,X_2,\dots のエントロピーレート lim⁡n→∞1nH(X1,X2,…,Xn)\lim_{n \rightarrow \infty} \frac{1}{n}H(X_1,X_2,\dots,X_n) が H(X3∣X1,X2)H(X_3|X_1,X_2) に一致することを示せ. ただし, H(X3∣X1,X2)H(X_3|X_1,X_2) は条件付きエントロピーである.

(5) 上記のマルコフ情報源 SS に対するエントロピーレート H(S)H(S) を求めよ.

【問 2】​

X,YX,Y を {0,1}\{0,1\} に値をとる確率変数とする. パラメータ α,β,γ∈[0,1]\alpha,\beta,\gamma \in [0,1] に対し,

P(X=0)=α,P(X=1)=1−α,P(Y=0∣X=0)=β,P(Y=1∣X=0)=1−β,P(Y=0∣X=1)=γ,P(Y=1∣X=1)=1−γ,\begin{aligned} P(X = 0) = \alpha &,\quad P(X = 1) = 1 - \alpha,\\ P(Y = 0|X = 0) = \beta &,\quad P(Y = 1|X = 0) = 1 - \beta,\\ P(Y = 0|X = 1) = \gamma &,\quad P(Y = 1|X = 1) = 1 - \gamma, \end{aligned}

とする. 22 値エントロピー関数を

h(p)={−plog⁡p−(1−p)log⁡(1−p),for0<p<1,0,forp=0,1h(p) = \left \{ \begin{aligned} -p\log p - (1 - p)\log(1 - p) , \quad &\text{for} \quad 0 < p < 1, \\ 0,\qquad \qquad \qquad \qquad \qquad \qquad &\text{for} \quad p = 0,1 \end{aligned} \right.

とする. 以下の問いに答えよ.

(1) 条件付きエントロピー H(Y∣X)H(Y|X) を 22 値エントロピー関数を用いて表現せよ.

(2) β=1−γ\beta = 1 - \gamma とする. このとき, 相互情報量 I(X;Y)I(X;Y)を最大化するα\alpha を求めよ. また I(X;Y)I(X;Y) の最大値を 22 値エントロピー関数と α,β\alpha,\beta を用いて表現せよ.

(3) α,β\alpha,\beta をある値に固定する. ただし, 0<α<10 < \alpha < 1 とする. 相互情報量 I(X;Y)I(X;Y) を最小化する γ\gamma の値を α,β\alpha,\beta を用いて表せ. また, その最小値を示せ.

(4) α,β\alpha,\beta をある値に固定する. ただし, 0<α<1,β>120 < \alpha < 1 ,\beta > \frac{1}{2} とする. 相互情報量 I(X;Y)I(X;Y) を最大化する γ\gamma の値を求めよ.

题目描述​

【问题 1】原题状态迁移图给出了平稳二阶 Markov 信源 SS，其状态为 00、10、01。回答：

  1. 根据状态图求信源 SS 的转移概率矩阵 AA，矩阵行按 00、10、01 的顺序排列。

  2. 若时刻 00 处于状态 00，求时刻 22 处于状态 10 的概率。

  3. 求信源 SS 的平稳分布 w⃗=(w1,w2,w3)\vec w=(w_1,w_2,w_3)，其中 w1,w2,w3w_1,w_2,w_3 依次对应状态 00、10、01。

  4. 对平稳二阶 Markov 信源 X1,X2,…X_1,X_2,\ldots，证明其熵率

    lim⁡n→∞1nH(X1,X2,…,Xn)\lim_{n\to\infty}\frac1n H(X_1,X_2,\ldots,X_n)

    等于条件熵 H(X3∣X1,X2)H(X_3\mid X_1,X_2)。

  5. 求上图 Markov 信源 SS 的熵率 H(S)H(S)。

【问题 2】令 X,YX,Y 为取值于 {0,1}\{0,1\} 的随机变量。对参数 α,β,γ∈[0,1]\alpha,\beta,\gamma\in[0,1]，给定

P(X=0)=α,P(X=1)=1−α,P(Y=0∣X=0)=β,P(Y=1∣X=0)=1−β,P(Y=0∣X=1)=γ,P(Y=1∣X=1)=1−γ.\begin{aligned} P(X=0)&=\alpha,&P(X=1)&=1-\alpha,\\ P(Y=0\mid X=0)&=\beta,&P(Y=1\mid X=0)&=1-\beta,\\ P(Y=0\mid X=1)&=\gamma,&P(Y=1\mid X=1)&=1-\gamma. \end{aligned}

定义二元熵函数

h(p)={−plog⁡p−(1−p)log⁡(1−p),0<p<1,0,p=0,1.h(p)= \begin{cases} -p\log p-(1-p)\log(1-p),&0<p<1,\\ 0,&p=0,1. \end{cases}

回答：

  1. 用二元熵函数表示条件熵 H(Y∣X)H(Y\mid X)。
  2. 设 β=1−γ\beta=1-\gamma，求使互信息 I(X;Y)I(X;Y) 最大的 α\alpha；并用二元熵函数及参数 α,β\alpha,\beta 表示 I(X;Y)I(X;Y) 的最大值。
  3. 固定 α,β\alpha,\beta 且 0<α<10<\alpha<1，用 α,β\alpha,\beta 表示使 I(X;Y)I(X;Y) 最小的 γ\gamma，并给出该最小值。
  4. 固定 α,β\alpha,\beta 且 0<α<10<\alpha<1、β>12\beta>\frac12，求使 I(X;Y)I(X;Y) 最大的 γ\gamma。

考点​

  • 二阶马尔可夫信源：由状态图构造转移矩阵，计算多步转移概率和平稳分布。
  • 熵率与条件熵：利用二阶马尔可夫性和熵的链式法则证明熵率公式，并据稳态权重求具体熵率。
  • 条件熵与互信息：用二元熵函数表达给定二元信道的条件熵和输出熵。
  • 信道容量与参数优化：在对称或固定转移参数下对输入分布或信道参数优化互信息，求最大值或最小值及其达到条件。

Kai​

【問 1】​

(1)​

[3401412012010]\begin{bmatrix} \frac{3}{4} & 0 & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 1 & 0 \end{bmatrix}

(2)​

A2=[9161431638121812012]⇒P=14A^2 = \begin{bmatrix} \frac{9}{16} & \frac{1}{4} & \frac{3}{16} \\ \frac{3}{8} & \frac{1}{2} & \frac{1}{8} \\ \frac{1}{2} & 0 & \frac{1}{2} \end{bmatrix} \Rightarrow P = \frac{1}{4}

(3)​

{w1+w2+w3=1w⃗A=w⃗⇒w⃗=(12,14,14)\left\{ \begin{aligned} &w_1 + w_2 + w_3 = 1 \\ &\vec{w}A = \vec{w} \end{aligned} \right. \Rightarrow \vec{w} = (\frac{1}{2},\frac{1}{4},\frac{1}{4})

(4)​

lim⁡n→∞1nH(X1,X2,…,Xn)=lim⁡n→∞1n[H(X1)+H(X2∣X1)+H(X3∣X1,X2)+⋯+H(Xn∣X1,…,Xn−1)]=lim⁡n→∞1n[H(X1)+H(X2∣X1)+H(X3∣X1,X2)+⋯+H(Xn∣Xn−2,Xn−1)]=lim⁡n→∞1n[H(X3∣X1,X2)+⋯+H(Xn∣Xn−2,Xn−1)]=lim⁡n→∞n−2nH(X3∣X1,X2)=H(X3∣X1,X2)\begin{aligned} \lim_{n \rightarrow \infty} \frac{1}{n}H(X _1,X_2,\dots,X_n) &= \lim_{n \rightarrow \infty} \frac{1}{n}[H(X_1) + H(X_2|X_1) + H(X_3|X_1,X_2) + \cdots + H(X_n|X_1,\dots,X_{n-1})] \\ &= \lim_{n \rightarrow \infty} \frac{1}{n}[H(X_1) + H(X_2|X_1) + H(X_3|X_1,X_2) + \cdots + H(X_n|X_{n-2},X_{n-1})] \\ &= \lim_{n \rightarrow \infty}\frac{1}{n}[H(X_3|X_1,X_2) + \cdots + H(X_n|X_{n-2},X_{n-1})] \\ &= \lim_{n \rightarrow \infty}\frac{n-2}{n}H(X_3|X_1,X_2)\\ &= H(X_3|X_1,X_2) \end{aligned}

(5)​

H(S)=w1H(14)+w2H(12)+w3H(1)=54−38log⁡23H(S) = w_1\mathcal{H}(\frac{1}{4}) + w_2\mathcal{H}(\frac{1}{2}) + w_3\mathcal{H}(1) = \frac{5}{4} - \frac{3}{8}\log_2 3

【問 2】​

(1)​

H(Y∣X)=αh(β)+(1−α)h(γ)H(Y|X) = \alpha h(\beta) + (1 - \alpha)h(\gamma)

(2)​

α=12\alpha = \frac{1}{2}
max⁡αI(X;Y)=1−h(β)\max_{\alpha}I(X;Y) = 1 - h(\beta)

(3)​

γ=β\gamma = \beta
min⁡γI(X;Y)=0\min_{\gamma}I(X;Y) = 0

(4)​

I(X;Y)=H(Y)−H(Y∣X)=h(αβ+(1−α)γ)−αh(β)−(1−α)h(γ)f(γ)=h(αβ+(1−α)γ)−(1−α)h(γ)の最大値問題を解くことになる\begin{aligned} I(X;Y) &= H(Y) - H(Y|X) = h(\alpha\beta + (1 - \alpha)\gamma) - \alpha h(\beta) - (1 - \alpha)h(\gamma) \\ f(\gamma) &= h(\alpha\beta + (1 - \alpha)\gamma) - (1 - \alpha)h(\gamma)\text{の最大値問題を解くことになる} \end{aligned}
γ=0\gamma = 0
本页目录