COMP2610/COMP6261 Tutorial 3 Solutions∗ Semester 2, 2018
. 20, 2018
We know that X is a binomial with parameters n, p. Thus,
p(X ≥n−1)=p(X =n−1)+p(X =n)
Copyright By PowCoder代写 加微信 powcoder
By Markov’s inequality,
When n = 2,
The bound from Markov’s inequality is
=n·pn−1 ·(1−p)+pn. p(X≥n−1)≤E[X]= n ·p.
p(X ≥1)=2·p·(1−p)+p2 =p·(2−p).
p(X ≥1)≤2·p.
2 · p − (2 · p − p2) = p2.
The difference between the two is
Thus, for the Markov bound to be within 0.01 of the exact probability, we will need p ≤ 0.1.
We need to code all sequences of length 100 with three or less 1’s. There is 1 sequence with zero 1’s.
There are 100 sequences with one 1 (one sequence for each possible position in which the 1 appears.)
Similarly, there are 100 and 100 sequences with two and three 1’s respectively. In total we have 23
100 100
1 + 100 + 2 + 3 = 166, 751.
If we want a uniform code over this number of elements, we need ⌈log2(166, 751)⌉ = 18
We need to find the probability of observing more than 3 1’s. Let K be the number of 1’s observed.
P(K >3)=1−P(K ≤3)=1−P(K =0)−P(K =1)−P(K =2)−P(K =3) = 1 − 0.995100 + 100 × 0.99599 × 0.005
100 98 2 100 97
+ 2 ×0.995 ×0.005 + 3 ×0.995 ×0.005
The number of 1’s, K, is a binomial random variable with probability of success 0.995. It has expectation E[K] = 100 × 0.005 = 0.5 and variance V[K] = 100 × 0.995 × 0.005 = 0.4975. By Chebyshev’s inequality we have
P(K ≥ 4) ≤ P(|K − 0.5| ≥ 3.5) = P(|K − E[K]| ≥ 3.5) ≤ V[K] = 0.4975 = 0.0406
This is larger than the probability we found in part (b), it is off by a factor of around 20.
∗Based in part on solutions by for the 2012 version of the course. 1
Using the definition of entropy
5. (a) (b)
TNβ :={x:|−N1 log2P(x)−H(X)|<β} so we are looking for k (the number of ones) such that
0.871=H(X)−0.1<−N1 log2P(k)
Yes, the specified lengths satisfy Kraft’s inequality: 3 × 2−3 + 10 × 2−4 = 1. For instance the three face cards (J, K, Q) could be coded as 001, 010, 011 and the ten non-face cards (A, 2, 3, . . . , 10) could be coded as 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 0000, 0001.
The code C1 is not prefix (0 is a prefix to 01) nor uniquely decodable (0110101 could decompose into 0 1101 01 or 01 10101). The code C2 is prefix free and thus uniquely decodable. The code C3 is not uniquely decodable (00 can be 00 or 0 0) and clearly not prefix free.
C1′ = {0, 10, 1110, 11110}, C2′ = C2 . For C3′ we need a code a with lengths 1,1,2, and 2. However, this cannot be done as the only codewords of length one are 0 and 1 and one of these will be a prefix to any other codeword.
No. The Kraft inequality tells us that for any prefix code
2−li ≤1 i
but for the given code lengths
Here, S0 is the set of all cards that we start with. We are looking for all the elements such that:
0 1/16 1/2
S0 −{A,K,2,…,5,J}
Hδ (bits) log2 13 = 3.70 log2 12 ≈ 3.59 log26≈2.59
2−li =1+1+1+3× 1 =17>1.
2 4 8 16 16
Yes, these lengths satisfy the Kraft inequality. For instance C = {0, 100, 101, 1100, 1101, 1110}. We have
H(X)=−1log1−1log1− 31 log 31 − 1 log 1
2 2 4 = 1.55.
4 128 128 128 128
(b) The expected code length is
L(C,X)=1×1+1×2+ 31 ×3+ 1 ×3=7. 2 4 128 128 4
(c) The code lengths for X are
⌈log 1 ⌉=1,⌈log 1 ⌉=2,⌈log 31 ⌉=3, and⌈log 1 ⌉=7.
2 1/2 2 1/4 2 1/128 2 1/128 An example of a prefix Shannon code for X would be:
The expected code length would be
CS ={0,10,110,1110001}
L(CS,X)=1×1+1×2+ 31 ×3+ 1 ×7=1.78125. 2 4 128 128
q 1 = 2 − 1 = 12 , q 2 = 2 − 2 = 41 , q 3 = 2 − 3 = 18 , q 4 = 2 − 3 = 81 , (e) By the definition of D(p||q) we have
(d) We have (And Z = 1)
2 21/2 4 21/4 128 2 1/8 128 2 1/8 = 31 ×log 31+ 1 ×4
=1×log 1/2+1×log 1/4+ 31 ×log 31/128+ 1 ×log 1/128
128 2 16 128 = 0.200.
So we have D(p||q) = L(C,X) − H(X) as we would expect. We also note that L(CS,X) is greater (i.e. the code is worse) than C.
(f) The steps of Huffman coding would be:
• from set of symbols {x1 , x2 , x3 , x4 } with probabilities {1/2, 1/4, 31/128, 1/128}, merge the two least likely symbols x3 and x4. The new meta-symbol x3x4 has probability 1/4.
• from set of symbols {x1, x2, x3x4} with probabilities {1/2, 1/4, 1/4}, merge the two least likely symbols x2 and x3x4. The new meta-symbol x2x3x4 has probability 1/2.
• from set of symbols {x1 , x2 x3 x4 } with probabilities {1/2, 1/2}, merge the two least likely symbols x1 and x2x3x4. The new meta-symbol x1x2x3x4 has probability 1, so we stop.
We then assign a bit for each merge step above. This is summarised below. We then read off the resulting codes by tracing the path from the final meta-symbol to each original symbol. This gives the code C = {0, 10, 110, 111}. (Note, we could equally derive C = CH depending on how we labelled the penultimate merge operation.)
1/2 1/2 1/201
1/4 1/4 0
31/128 0 1/4
Figure 1: Huffman code.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com