課程名稱︰資訊理論與編碼技巧 課程性質︰選修 課程教師︰吳家麟教授 <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$. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.254.237 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1522079923.A.C0F.html ※ 編輯: Glamsight (36.230.254.237), 03/26/2018 23:59:47