Problems - Algos PDF

Preview

Summary

Algos...

Description

1

Problems and Solutions

Hence, n

π2 1 X Pi ≤ P ց0 2 i n 6n i=1

Abhishek Sinha LIDS, MIT

From Eqn. (4), this implies, I. Chain inequality [1] Let X1 → X2 → X3 → X4 form a Markov Chain. Show that I (X1 ; X3 ) + I(X2 ; X4 ) ≤ I (X1 ; X4 ) + I (X2 ; X3 )

= = = = ≥

for any sequence of codebooks with ǫn → 0. Thus capacity of the channel is zero. III. Time-varying channels II. [1]

Solution We compute the following

=

lim sup Rn = 0

I(X1 ; X4 ) + I (X2 ; X3 ) − (I (X1 ; X3 ) + I (X2 ; X4 (1) )) p(X1 , X4 )p(X2 , X3 )p(X1 )p(X3 )p(X2 )p(X4 ) E log p(X1 )p(X4 )p(X2 )p(X3 )p(X1 , X3 )p(X2 , X4 ) p(X1 , X4 )p(X2 , X3 ) E log p(X1 , X3 )p(X2 , X4 ) p(X4 |X1 )p(X3 |X2 ) E log p(X3 |X1 )p(X4 |X2 ) p(X3 |X1 , X2 ) p(X4 |X1 ) (2) E log p(X3 |X1 ) p(X4 |X1 , X2 ) I(X2 ; X3 |X1 ) − I(X2 ; X4 |X1 ) (3)

Consider a time-varying discrete time memoryless channel. Let Y1 , Y2 , . . . , Yn be conditionally independent given X1 , X2 , . . .Q , Xn , with conditional distribution given by n p(y|x) = i=1 pi (yi |xi ). Let X = (X1 , X2 , . . . , Xn ), Y = (Y1 , Y2 , . . . , Yn ). Find maxp(x) I(X; Y ). Solution We simply compute, p(X, Y ) p(X )p(Y ) H (Y ) − H (Y |X) n X H (Y ) − H (Yi |Xi )

I(X; Y ) =

E log

=

0

=

Where Eqn 2 follows from the Markov property and Eqn 3 follows from the Information Inequality for the Markov Chain X2 → X3 → X4 , for each possible realization of X1 .

i=1

n n X   X Ii (Xi ; Yi ) H (Yi ) − H (Yi |Xi ) =

≤

i=1

i=1

II. Time-varying channel [1]

The inequality above becomes an equality iff the random n A train pulls out of the station ar constant velocity. The variables {Yi }i=1 are independent, i.e. if p(X) factorizes as, received signal energy thus falls off with time as i21. The total n Y received signal at time i is p(X) = pi (Xi ) 1 i=1 Yi = Xi + Zi , i For some distributtions pi (·) on the input alphabet. Now, we where Z1 , Z2 , . . . are i.i.d. ∼ N (0, N ). The transmitter con- can choose the distributions pi (·), such that, it maximizes straint for block length n is the one-slot capacityPIi (Xi ; Yi ). Call this value Ci . Hence, n n max X p(x) I(X; Y ) = i=1 Ci 1 x2i (w) ≤ P, w ∈ {1, 2, . . . , 2nR } n i=1 IV. Channels with two independent looks at Y.[1] Using Fano’s inequality, show that the capacity C is zero for this channel. Let Y1 and Y2 be conditionally independent and conditionally identically distributed given X . Show that I(X; Y1 , Y2 ) = 2I (X; Y1 ) − I (Y1 ; Y2 ) Solution We follow the same steps as in the proof of converse in section 9.2 upto Eqn. (9.52), to conclude that,   n 1 1 X Pi 1 + ǫn (4) Rn ≤ log 1 + 2 N n i=1 i2 Where ǫn → 0. Now we simply use the inequality, n X Pi i=1

i2

≤

n X i=1

n  X 1  π2 P Pi ≤ 6 i2 i=1

Solution

I(X; Y1 , Y2 ) = = =

H (Y1 , Y2 ) − H (Y1 , Y2 |X)

H (Y1 , Y2 ) − 2H (Y1 ) + 2H (Y1 ) − 2H (Y1 |X)   Since, p(Y1 , Y2 |X) = p(Y1 |X)p(Y2 |X)

2I(X; Y1 ) − I (Y1 ; Y2 )

2

V. Tall, fat people [1] Suppose the average height of people in a room is 5 feet. Suppose that average weight is 100 lb. (a) Argue that no more than one-third of the population is 15 feet tall. (b) Find an upper bound on the fraction of 300-lb 10-footers in the room.

of the covariance matrix KX Z , in particular the correlation coefficient ρX Z . We have, ρX Z = E(XZ ) = EY E(XZ |Y ) = EY E(X|Y )E(Z|Y )

(5)

Where we have used the fact that X → Y → Z forms a Markov chain. WOLOG, we may assume that E(X) = E(Y ) = E(Z) = 0. Thus the conditional expectations of bivariate normal distributions can be easily worked out to be

σX Y E(X|Y ) = ρ1 σY Assign a uniform distribution on the set of all people in σZ the room. Hence, fraction of a population satisfying some Y E(Z|Y ) = ρ2 σY attributes is simply probability of selecting a person having the same attributes. Please see John Tsitsiklis’ probability text for reference on (a) bivariate normal distribution. Let us sample a person from the room and let the random Thus ρX Z = EY ρ1 ρ2 σX 2σZ Y 2 = ρ1 ρ2 σ X σ Z . Hence, σY variables H and W denote the height and weight of the person selected. I(X ; Z) = h(X ) + h(Z) − h(X, Z) We have, using Markov’s inequality : 1 1 σ2 σ2 1  = ln 2 2 X Z 2 2 = ln ) 2 (1 − ρ σ 1 5 1 − ρ12 ρ22 σX Z 2 E(H ) 1 ρ2 = = P(H = 15) ≤ P(H ≥ 15) ≤ 15 15 3 VIII. An interesting elementary problem on functional (b) equation Similarly, we have Solution

1 2 1 P(W ≥ 300) ≤ 3 P(H ≥ 10) ≤

Now, P(H = 10, W = 300)

≤

P(H ≥ 10, W ≥ 300) 1 ≤ P(W ≥ 300) ≤ 3

VI. Bottleneck channel (Problem 7.25) [1] Solution Assume p(X) is chosen as the capacity achieving distribution for the channel X → Y C

= I(X; Y ) ≤ I(X; V ) =

≤

≤

H (V ) − H (V |X)

H (V ) log k

Let B be the set of all functions f from the set of positive reals to the set of positive reals such that f (3x) ≥ f (f (2x)) + x,

∀x ∈ R+

Find the maximum real number τ such that for all such functions f ∈ B, the following holds: f (x) ≥ τ x Solution For any function f ∈ B, we have the following series of inequalities valid for all x ∈ R+ : f (3x) ≥ f (f (2x)) + x ≥ τ f (2x) + x ≥ 2τ 2 x + x = (1 + 2τ 2 )x, i.e., f (x) ≥

(1 + 2τ 2 ) x, ∀x ∈ R+ 3 (1+2τ 2 )

Hence by definition of τ , we have τ ≥ , i.e. 21 ≤ 3 1 τ ≤ 1 . Now to show that τ = , we simply note that the Where the first inequality follows from data-processing in2 1 x, ∀x ∈ R belongs to the set B . function g(x) = + equality, the second inequality follows from non-negativity 2 of conditional entropy and finally the third inequality follows from the fact that |V | = k . IX. An interesting elementary problem on SNR VII. Gaussian mutual information (Problem 9.11) [1] Solution

Consider the positive quantities {a1 , a2 , . . . , an } and σ 2 . Define the SNR for the user i as

ai , i = 1, 2, . . . , n γi = P It is enough to derive the joint distribution of the random 2 j6=i aj + σ variable (X, Z). Since the random variables, (X, Y, Z) are jointly Gaussian, we know that (X, Z) is also jointly Gaussian. Prove that for any 0 < α < 1, number of users with SNR at Hence, their distribution is completely specified in terms least α is at most 1 + α1 .

3

Solution Assume that m is the number of users with γi ≥ α. Then for each such user i, we have by definition ai P ≥α 2 j6=i aj + σ

i.e.,

X X 1 aj + σ 2 ≥ aj ai ≥ α j6=i

j6=i

Adding ai to both sides, we have X 1 (1 + )ai ≥ aj = S α

XIV. Exercise 4.19 from A LGORITHMS - VAZIRANI [3] For every edge e = (i, j), update its cost to le′ = le + ci . Find the shortest path from s → t, ∀t ∈ V in this updated edge-capacitated directed graph. XV. Problem 2 from P UTNAM 1999 It is assumed implicitly that p(x) is a polynomial with real coefficients. Then the roots of p(x) are of the form αi ± jβi , i.e. we have, for some C > 0 and m ∈ N m Y   p(x) = C (x − αi )2 + βi2 i=1

Expanding this product out, we get

j

Where, S ≡ we have

i.e.,

P

j

aj . Summing over all m users with γi ≥ α, 1 (1 + )S ≥ mS α

p(x) =

k X (fi (x))2 i=1

For some polynomials fi ’s and some k ∈ N.



XVI. Exercise 4.13 from A LGORITHMS - VAZIRANI [3] 1 m≤1+  α

X. Exercise 14.8 from R ANDOMIZED A LGORITHMS [2] From Lemma 14.17, we know that for any generator g of Z∗p , g k is a quadratic residue if and only if k is even. Since p − 1 is even, it is clear that exactly half of the elements of Z∗p are quadratic residues. To find a quadratic non-residue, just select an element a from Z∗p u.a.r and compute the Legendre symbol [p1]. If it is −1 then stop, otherwise repeat. Clearly, the above algorithm has a probability of exactly 21 of selecting a quadratic non-residue at each step. Hence on the average we need Ω(log(p)) iterations.

(a) Remove all the edges of the graph with length more than L. Run the BFS from s to determine whether t is reachable from s or not in this reduced graph. XVII. Exercise 4.5 from A LGORITHMS - VAZIRANI [3] Run BFS on the graph G , noting the distances of each vertex v as they are discovered. If the vertex u is discovered at k th iteration (i.e. the shortest path length s → u is k), check how many vertices of in the neighbor of u was discovered at k − 1 th iteration. Record the number of shortest path from s → u as P N (u) = v N (v), where the sum extends over all neighbors of v which are discovered at iteration k − 1. XVIII. Exercise 4.7 from A LGORITHMS - VAZIRANI [3]

First traverse the tree and compute the distance of every node t from s along the tree. Call these distances d(·). Now Consider a set of points S = {(xi , yi ), i = 1, 2, . . . , n}, check whether the Bellman-Ford equality holds for every such that each of the points in the set forms a vertex of the vertex v, i.e.,   conv(S). Then any algorithm which actually computes the d(u) + luv , ∀v ∈ V d(v) = min u:(u,v)∈E convex hull of S would output the points in the set S in a sorted order. Hence we have at least Ω(n log n) complexity of If it holds then the tree is a shortest-path tree, otherwise not. any algorithm for finding the convex hull of S . Note that the above steps can be completed in linear time. The justification of the above algorithm is simple : the Bellman-Ford fixed point equation has an unique solution and XII. Exercise 4.21 from A LGORITHMS - VAZIRANI [3] that solution is optimal. (a) Construct a graph G(V, E) as follows. The set of vertices are labelled by the currency set C. And the length of edge XIX. Exercise 4.8 from A LGORITHMS - VAZIRANI [3] lij = log rij , ∀(i, j) ∈ C 2 , i 6= j. Then finding the shortest No it is not. Use the example of Figure 4.12 from the book path in the graph G from the node s to the node t gives an with the added constant 3. optimum sequence of such exchanges. (b) We just need to detect the presence of negative cycles in XX. Exercise 5.3 from A LGORITHMS - VAZIRANI [3] the graph G . To determine whether there exists such an edge or not, just check whether |E| ≥ |V |. In that case there exists such an XIII. Exercise 4.20 from A LGORITHMS - VAZIRANI [3] edge for the originally connected graph. Find the shortest path from s → t in all the graphs G(V, Fk′), To determine such an edge, compute a spanning tree of the where Fk′ = E ∪ {ek }, ek being the k th edge from the set E ′ . graph G. Any edge that is not part of the spanning tree can Find the minimum of all of the shortest path. be deleted without sacrificing the connectivity of G . XI. Exercise 9.1 from R ANDOMIZED A LGORITHMS [2]

4

XXI. Exercise 5.4 from A LGORITHMS - VAZIRANI [3] th

Take the i connected component of G. If it has mi edges and ni vertices, we know that mi ≥ n i − 1 Summing over all k components we have |E| ≥ n − k. 

XXVIII. Exercise 5.26 from A LGORITHMS - VAZIRANI [3] (a) Consider the degree-sequence (3, 3, 1, 1). It satisfies the conditions mentioned in the problem. Now note that d 1 = d 2 = 3 implies that vertices 1 and 2 have edges to all other 3 vertices. This implies that any vertex in the graph can’t have degree less than 2. Clearly vertices 3 and 4 violates this condition.

XXII. Exercise 5.6 from A LGORITHMS - VAZIRANI [3] Consider the edges of two trees T1 and T2 in the order of increasing weights. If the trees are not the same, there must exist an index where the edge-weights differ (and we have two different edges). Replacing the higher-weighted edge with the lower one and keeping everything else the same reduces the weight of one of the trees. Hence both the trees can’t be MST. 

XXIX. Exercise 5.23 from A LGORITHMS - VAZIRANI [3] First remove the nodes U and all the edges that are incident on them. Since the nodes U are leaves in the desired spanning tree, the nodes V \ U must form an MST. So find an MST T on the induced graph V \ U . Now for all u ∈ U , add the lightest edge connecting u to T . XXX. Exercise 6.2 from A LGORITHMS - VAZIRANI [3]

XXIII. Exercise 5.8 from A LGORITHMS - VAZIRANI [3] No. Both contain the minimum-weight edge in it.

Construct a graph G(V, E) with node sets V = [[n]] and edges {(i, j), i < j} of length (200 − (aj − ai ))2 , ∀i < j . CLearly G is a DAG. Find the shortest path on this DAG.

XXIV. Exercise 5.20 from A LGORITHMS - VAZIRANI Do a BFS from a node s ∈ V and group the vertices in two sets depending on the parity of their distances from s. This results in a bipartite graph B. Now apply B IPARTITE M ATCHING algorithm on B to find the maximum matching and check whether it is perfect or not. Second part: Find MST T with negative edge weights. Put all edges that are not in the tree T into the set E ′ . XXV. Exercise 5.21(c) from A LGORITHMS - VAZIRANI [3] For a given edge e = (a, b) ∈ E, consider the graph Ge (V, E \ {e}). Do a BFS on Ge to check whether a and b are connected in Ge . If yes, then the path π(a → b) plus the edge e forms a cycle, else not. XXVI. Exercise 5.31 from A LGORITHMS - VAZIRANI [3]

XXXI. Exercise 6.8 from A LGORITHMS - VAZIRANI [3] The sub-problems we consider for DP iteration are maximum length of longest commone substring ending precisely at the ith and j th position of the string-arrays x and y, which we call P [i, j], i = 1, 2, . . . , n, j = 1, 2, . . . , m. Then we have the following DP iterations: for i=1:n for j=1:m if(i==1 || j==1) P(i,j)=(a[i]==b[j]); else if(a[i]==b[j]) P(i,j)=P(i-1,j-1)+1; else P(i,j)=0; endif endfor endfor

Do the SJF (Shortest Job First), i.e. sort the customers according to their service times and serve the customers in the order of increasing service times. Then finding the max in the matrix P [i, j] gives the To prove optimality, consider an exchange argument. Consider maximum common substring length. any two consecutive customers (in any scheduling order) and switch their order of service. Show that serving the customer XXXII. Exercise 6.9 from A LGORITHMS - VAZIRANI [3] with lower service time first always improves the overall cost. Assume that the cut-locations are provided in an array a[·]. Consider the sub-problem of cutting the string from a[i] to a[j] and record the optimal cost in the (i, j)th element of the Consider a graph G(V, E) with vertices denoting the vari- matrix P [i, j]. Then, we have ables and there is an edge between vi and vj if there is P [i, j] = min (P [i, k] + P [k, j] + a[j] − a[i] + 1) an equality constraint xi = xj . Now for every inequality k:i (1 + ǫ)#(I)} ∪ {Y < (1 − ǫ)#(I) ≤ 2αN

(20)

P((1 − ǫ)#(I) ≤ Y ≤ (1 + ǫ)#(I)) ≥ 1 − 2αN

(21)

Where the R.H.S. estimate is at least 1 − δ if 2αN ≤ δ if N ≥ Θ(ln(1/δ)).

Rearranging, 1+

(1 − ǫ)#(I)) ≤ P(Z ≥ N/2)  N pe + (1 − p) ≤ eN/2   1 + 41 (e − 1) N √ ≤ e N ≤ α

Hence,

Hence from Theorem 6.19, we have λ2 ≥ d −

≤

(8)

XLI. Exercise 4.2 from R ANDOMIZED A LGORITHMS [2] √ Consider 2n/2−1 = 12 N number of packets with the first digit of origin 1 and last n/2 digits of origin being zeros, n |Γ(W )| |W | + ≥ (1 + (1 − λ2 /d)/2)|W | (9) i.e., we consider the packets on the vertices with address of 2 |V \ W | the form 1xx . . . xx||000 . . . 00, where the separator is after n/2 √ bits. Because of the bit-fixing routing strategy, all these XXXIX. Exercise 9.2 from R ANDOMIZED A LGORITHMS 1 2 N packets has to visit the vertex 000 . . . 00||000 . . . 00 [2] before taking the edge leading to 000 . . . 00||100 . . . 00 . Since It is sufficient to check whether xmin ≤ x ≤ xmax and a single packet can be √ sent over that edge per slot, this strategy requires at least Ω( N ) steps. ymin ≤ y ≤ ymax , which requires Θ(n) steps.

Thus,

6

XLII. Microsoft Research Puzzle 1.

Similarly,

n X Prove that the digit sum of any (positive integral) multiple H (Yi |X n , Y i−1 ) H (Y n |X n ) = of 11 is even. i=1 Proof: Consider a positive integer n which reads = 0 + 0 + . . . + 0 + H (Yn |X n , Y n−1 ) a1 a2 . . . ak when written in decimal (ai ∈ {0, 1, 2, . . . , 9}). = H (p) Now write 11n = (10 + 1)n = a1 a2 . . . ak 0 + a1 a2 . . . ak . Perfoming operations in modulo 10, we conclude that the digit Thus, sum (modulo 10) is 2(a1 +a2 +. . . ak ) mod 10 which is even. I(X n ; Y n ) = H (Y n ) − H (Y n |X n ) = H (Y1 ) + (n − 2)H (p)

Since, 0 ≤ H (Y1 ) ≤ 1, we have XLIII. Problem 7.3 from I NFORMATION T HEORY, C OVER 1 lim I(X n ; Y n ) = H (p)  AND T HOMAS [1] n→∞ n   L (b) We know that the capacity of a BSC without feedback is Given that Y = X Z and X ⊥ Z where Zi ∈ {0, 1} are identically distributed but not necessarily independent. given by C = 1 − H (p), where p is the parameter of the BSC. Clearly if H (p) > 1 − H (p), i.e. H (p) > 21 , i.e. 0.11 < p < Assume a fixed distribution p(X) of X. We have, 0.88 then the above limit is higher than the capacity of the I(X; Y ) = H (Y ) − H (Y |X) (22) BSC without feedback. = H (Y ) − H (Z|X) (23) XLV. Problem 7.10 from I NFORMATION T HEORY, C & T[1] = H (Y ) − H (Z) (24) (a) Since the channel is symmetric, we have H (Y |X) = ≥ H (Y |Z) − H (Z) (25) H (1/2) = 1. Also for the symmetric channel capacity achiev= H (X|Z) − H (Z) (26) ing input distribution is uniform. Hence C = log 5−1 ≈ 1.322 = H (X) − H (Z) (27) bits/ch. use. n (b) Consider the following codebook of length 2 X H (Zi ) (28) ≥ H (X) − C = {11, 13, 31, 33, 45} (33) i=1 H (X) − nH (p, 1 − p) (29) L Where (23) follows from the fact Y = X Z, (24) follows from X ⊥ Z, (25) follows from the factL that conditioning reduces entropy, (26) follows from Y = X Z, (27) follows from X ⊥ Z, (28) follows from independence bound of entropy and (29) follows from the fact that {Zi } are identically distributed. Now (29) holds for any fixed input distribution p(X ). Hence, =

max I(X; Y ) ≥ p(X )

= =

H (X )|p∼U − nH (p, 1 − p) (30) n(1 − H (p, 1 − p)) nC

(31) (32)

Where U denotes u.i.i.d. distribution on X.  XLIV. Problem 7.33 from I NFORMATION T HEORY, C & T[1] (a) Due to feedback, we have Xi+1 = Yi , ∀i = 1, 2 . . . , n − 1. Hence we have, H (Y n ) =

H (Y1 ) +

n−1 X

H (Yi+1 |Y i )

X

H (Yi+1 |X2 , X3 , . . . , Xi+1 )

i=1 n−1

= =

H (Y1 ) + H (Y1 ) +

i=1 n−1 X i=1

=

H (Yi+1 |Xi+1 )

H (Y1 ) + (n − 1)H (p)

C is a zero-error code of length 2, because given any two distinct codewords (a1 , b1 ) and (a2 , b2 ) from C, it can be easily verified that either the first symbol a1 and a2 is nonconfusing or the second symbol b1 and b2 is non-confusing. Hence the code C has rate log |C|/2 = log 5/2 ≈ 1.16 > 1. XLVI. A N U PPER - BOUND ON THE Z ERO -E RROR -C APACITY OF THE CHANNEL [1] We can obtain an upper-bound on the ZEC of the channel by a simple sphere-packing-argument. Consider any zeroerror-code Cn of length n for the given 5-symbol type-writer channel. Consider a particular codeword x ∈ C. Clearly, any word y in the box around x such that yi − xi mod (5) ≤ 1, ∀i = 1, 2, . . . n can not belong to Cn , due to zero-error property (Otherwise y could be potentially confused with x). Hence every such ball Bx (in ℓ1 norm) around each codeword x ∈ C contains exactly one codeword. Also, it is easy to see that if x 6= y then Bx ∩ By = φ. Otherwise, if z ∈ Bx ∩ By , then z could be potentially confused with both x and y. Pick an index i such that xi − yi ≥ 2. Since z ∈ Bx , we have zi − xi = 0, 1. Similarly, zi − yi = 0, 1, wh...