跳到主要内容

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

标签：

Author​

Yu, 祭音Myyura

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(β≠12),任意の [0,1] の値(β=12).\alpha = \begin{cases} \dfrac12 & (\beta\ne\dfrac12),\\ \text{任意の }[0,1]\text{ の値} & (\beta=\dfrac12). \end{cases}
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}

I(X;Y)I(X;Y) は通信路確率 γ\gamma の凸関数なので、最大値は γ=0,1\gamma=0,1 のいずれかで達成される。また、

I(0)−I(1)=h(αβ)−h(α(1−β))>0I(0)-I(1)=h(\alpha\beta)-h(\alpha(1-\beta))>0

である。実際、αβ≤1/2\alpha\beta\leq1/2 なら hh の単調性を用い、 αβ>1/2\alpha\beta>1/2 なら 1−αβ>α(1−β)1-\alpha\beta>\alpha(1-\beta) と h(p)=h(1−p)h(p)=h(1-p) を用いればよい。 従って一意な最大点は

γ=0\gamma = 0
本页目录