課程名稱︰資訊理論與編碼技巧
課程性質︰選修
課程教師︰吳家麟教授 <3
開課學院：電機資訊學院
開課系所︰資訊工程學系
作業日期（年月日）︰106年03月05日
作業時限（年月日）：106年03月26日
備註：
由於加上我自己寫的答案，導致過長，故預計分三篇。
(如本篇低於百P則僅此一篇)
答案僅供參考喔 ╮(╯◇╰)╭
作業 : 1-4 共 12
I. Must done
1. (Prob. 2.1 of [1])
Coin flips.
Afair coin is flipped until the first head occurs. Let
$X$ denote the number of flips required.
(a) Find the entropy $H(X)$ in bits. The following
expression may be useful:
$$sum _{n=0} ^{infty} r ^{n} = frac{1}{1-r},
sum _{n=0} ^{infty} n r ^{n} = frac{r}{(1-r)^{2}}.
$$
solution:
Recall the definition of this $X$, it is the number of
trials required to flip the first successful trial under
Bernoulli trials, with success probability $q$; That is,
$X$ has a negative binomial distribution, and the p.m.f.
of it could be
$$ p(x)
= binom{x-1}{1-1} q ( 1-q ) ^{x-1}
= q(1-q)^{x-1}
$$
for all natural number $x$. By the definition of entropy,
we have the entropy of $X$:
$$ H(X)
= - sum _{x=1} ^{infty } p(x) log p(x)
= - sum _{x=1} ^{infty }
q(1-q)^{x-1} log q(1-q)^{x-1}
= [ - q ( log q ) sum _{x=1} ^{infty} (1-q) ^{x-1} ]
+ [ - q ( log (1-q) )
sum _{x=1} ^{infty} (x-1) (1-q) ^{x-1}
]
$$
Introducing $n = x - 1$ and $r = 1-q$, we get
$$ H(X)
= [ -q ( log q ) sum _{n=0} ^{infty } r ^{n} ]
+ [ -q ( log (1-q) ) sum _{n=0} ^{infty } n r ^{n} ]
= [ -q ( log q ) frac{1}{1-r} ]
+ [ -q ( log (1-q) ) frac{r}{(1-r)^{2}} ]
= [ -q ( log q ) frac{1}{q} ]
+ [ -q ( log (1-q) ) frac{1-q}{q^{2}} ]
= frac{-(q log q + (1-q) log (1-q))}{q}
= H(q)/q (bits).
$$
(b) A random variable $X$ is drawn according to this
distribution. Find an ``efficient'' sequence of yes-no
questions of the form, ``Is $X$ contained in the set $S$?''
Compare $H(X)$ to the expected number of questions
required to determine $X$.
solution:
Consider a sequence $S_{n}$ of yes-no questions: ``Is
$X=n$?'' Clearly, the index of $S_{n}$ is equal to $X$
if and only if $X=n$. Then, the expected number of $S_{n}$
required to determine $X$ is equal to $Ex [X] = q/(1-q)$.
Moreover, we can evaluate the their relative:
$$ H(X) >= E[X], if q <= q_{0};
H(X) < E[X], if q > q_{0},
$$
where $q_{0}$ is the root of $H(q)/q - q/(1-q)$, near
$0.577886$.
2. (Prob. 2.3 of [1])
Minimum entropy.
What is the minimum value of $H(p_{1},...,p_{n}) =
H(vec{p})$ as $vec{p}$ ranges over the set of
$n$-dimensional probability vectors? Find all $vec{p}$'s
that achieve this minimum.
solution:
First, we show the minimum value of $H(vec{p})$ is zero.
By the definition of entropy, the minimum value of
$H(vec{p})$ must be not small than $0$; that is,
$$ H(\vec{p})
= - sum _{x=1} ^{n} p_{x} log p_{x} >= 0.
$$
Assume that the minimum value of $H(\vec{p})$ greater
that $0$. Take $p_{1} = 1$ and $p_{2},..., p_{n} = 0$.
By the definition of $0\log 0$, the entropy in this case
is
$$ H(\vec{p})
= - (1 \log 1 + 0 \log 0 + ... + 0 \log 0)
= -(1 \log 1 + (n-1) 0 )
= 0.
$$
So, it is a contradiction because that $H(\vec{p})$ must
be nonzero. Therefore the minimum value of $H(p_{1},...,
p_{n})$ is $0$.
Second, we show $H^{-1}(0) = {(1,0,...,0),(0,1,0,...,0),
(0,...,0,1)}$. Denoting $S = {(1,0,...,0),(0,1,0,...,0),
(0,...,0,1)}$. Assume that there is a $vec{p} not in S$
such that $H(vec{p}) = 0$; that is, $vec{p} in H^{-1}(0)
-S$. Then, there is a $x$ such that $p_{x} != 0,1$.
Since $p_{x}$ must between $0$ and $1$, $log p_{x}$ must
be negative and implies
$$ H(vec{p}) >= - p_{x} log p_{x} > 0.
$$
Thus, it is a contradiction because that $H(vec{p})$ must
be $0$. So, the $vec{p}$ achieves minimum value $0$ of
$H(vec{p})$ must be $(1,0,...,0),(0,1,0,...,0),$ or
$(0,...,0,1)$.
3. (Prob. 2.4 of [1])
Entropy of functions of a random variable.
Let $X$ be a discrete random variable. Show that the
entropy of a function of $X$ is less than or equal to
the entropy of $X$ by justifying the following steps:
$$ H(X,g(X))
overset{(a)}{=} H(X) + H(g(X) | X)
overset{(b)}{=} H(X),
H(X,g(X))
overset{(c)}{ =} H(g(X)) + H(X | g(X))
overset{(d)}{>=} H(g(X)).
Thus, $H(g(X)) leq H(X)$.
solution:
First, we show the steps (a) and (b). Take $X_{1} = g(X)$
and $X _{2} = X$. By the definition of entropy, we have
the following equation:
$$ H(X,g(X)) = H(X_{2},X_{1}) = H(X_{1},X_{2}).
$$
By the entropy chain rule (Theorem 2.5.1), we have the
following equation:
$$ H(X_{1},X_{2})
= H(g(X)|X) + H(X)
\overset{(a)}{=} H(X) + H(g(X)|X).
$$
Denote the p.m.f. of $(X_{1},X_{2})$ by $p(x_{1},x_{2})$.
Assume that there is a $x_{2} \in \mathcal{X}_{2}$, where
$mathcal{X}_{2}$ is the alphabet of $X_{2}$, such that
$p(x_{1},x_{2}) != 0,1$ for some $x_{1} in mathcal{X}_{1}
- { g(x_{2}) }$, where $mathcal{X}_{1}$ is the alphabet
of $X_{1}$. Since $X_{1} = g(X) = g(X_{2})$, $p(g(x_{2}),
x_{2})$ must be $1$. Clearly, it is a contradiction
because that $p(x_{1},x_{2})$ must be not a zero or one.
That is, we have:
$$ H(g(X)|X=x)
= - sum _{x_{1} in mathcal{X}_{1}}
p(x_{1},x_{2}) log p(x_{1},x_{2})
= - p(g(x_{2}),x_{2}) log p(g(x_{2}),x_{2})
- sum _{substack{x_{1} in mathcal{X}_{1}
x_{1} != g(x_{2})}
}
p(x_{1},x_{2}) log p(x_{1},x_{2})
= - 1 log 1 - (| mathcal{X}_{1} | - 1 ) 0 log 0
= 0
$$
for $x in mathcal{X}_{2}$, and the step (b) is true.
Similarly, we take $X_{1}^{*} = X$ and $X_{2}^{*} = g(X)$,
and we have:
$$ H(X,g(X))
= H(X_{1}^{*},X_{2}^{*})
overset{(c)}{=} H(g(X)) + H(X|g(X)).
$$
By the definition of entropy, $H(X|g(X))$ must be greater
than $0$. So, the step (d) is true. Therefore the proof
is true; i.e., $H(g(X)) <= H(X,g(X)) = H(X)$.
4. (Prob. 2.5 of [1])
Zero conditional entropy.
Show that if $H(Y|X) = 0$, then $Y$ is a function of $X$
[i.e., for all $x$ with $p(x) > 0$, there is only one
possible value of $y$ with $p(x,y) > 0$].
solution:
Denote the alphabets of $X$ and $Y$ by $mathcal{X}$ and
$mathcal{Y}$, respectively, and denote the p.m.f. of
$(X,Y)$ by $p(x,y)$. By the definition of entropy, we
have:
$$ H(Y|X) = sum _{x in mathcal{X}} p_{X}(x) H(Y|X=x),
$$
where $p_{X} (x) = sum _{y in mathcal{Y}} p(x,y)$.
Assume that $Y$ is not a function of $X$.
We consider the case: there is a $x_{0} in mathcal{X}$
such that $p(x,y) != 0,1$ for all $y \in \mathcal{Y}$.
Clearly, for these $x_{0}$, $p(x,y) > 0$ implies
$$ H(Y|X=x_{0})
= - sum _{y in mathcal{Y}}
frac{p(x_{0},y)}{p(x_{0})}
log frac{p(x_{0},y)}{p(x_{0})}
> 0
$$
and
$$ H(Y|X)
= sum _{x in mathcal{X}} p_{X}(x) H(Y|X=x)
> p_{X}(x_{0}) H(Y|X=x_{0})
> 0.
$$
So, it is a contradiction, in this case, because that
$H(Y|X)$ must be zero; that is, for all $x in mathcal{X}$,
there is a $y in mathcal{Y}$ such that $p(x,y) = 0$ or
$1$. By the definition of p.m.f., for all $x in mathcal{X}$,
there is an unique $y in mathcal{Y}$ such that $p(x,y) = 1$
($because 0 <= p_{X}(x) = sum _{y in mathcal{Y}} p(x,y)
<= 1$). Clearly, it is a contradiction because that
$H(Y|X) = 0$. Therefore $Y$ must be a function of $X$.