Homework 1: Pulse Sequence SimulationsTurn in (1) a PDF with your simulation results and discussions, and (2) your MATLAB code. Include comments in your code to improve readability.1. Bloch Equation SimulationsIn the first part, we will take a closer look at the transient and steady states of rapid gradient echo (GRE) sequences using Bloch equation simulations. Follow Dr. Brian Hargreaves’s tutorial that was shared through our class email list. The MATLAB scripts xrot.m, yrot.m, zrot.m, throt.m, and freeprecess.m will be especially helpful.1A. Steady state signal comparison. Simulate the steady state signal levels for bSSFP (center of pass band), SSFP-FID, and SSFP-Echo.(i) Follow Brian’s tutorial to implement sssignal.m, gresignal.m, and gssignal.m. For bSSFP, you can use sssignal.m. For SSFP-FID/Echo, start with gresignal.m and gssignal.m, and then add an option to specify the position of gradient spoiling in TR for SSFP-FID/Echo.(ii) Read and use the provided template HW_1A_bSSFPandGRE_SS_v0.m, which calls the scripts sssignal.m for bSSFP, and gresignal.m and gssignal.m for SSFP-FID/Echo.(iii) Assume the parameters: bSSFP TE/TR = 2.5/5 ms, SSFP-FID TE/TR = 2/10 ms, and SSFPEcho TE/TR = 8/10 ms. Plot and compare the steady state signal levels over a range of flip angles (0-180o) and different tissue T1 and T2: (a) T1 = 1000 ms and T2 = [100, 200, 500, 1000] ms, (b) T2 = 40 ms and T1 = [100, 200, 500, 1000] ms. (See slides for Lectures 2 and 3.)(iv) Discuss your observations.1B. Catalyzation for bSSFP. Simulate the approach to steady state for a bSSFP sequence.(i) Read and test the provided templates HW_1B_bSSFP_main_v0.m and bSSFPprepfunc_halfTheta.m, which simulate the (θ/2-TR/2 preparation) scheme we introduced in class.(ii) Implement linear ramp catalyzation with N TRs and excitation angles [1:N]/N.(iii) Assume the parameters: RF θ = 70o and Δϕ = π, TR = 5 ms, 200 TRs, tissue T1/T2 = 600/100 ms. RF phase cycling (e.g., Δϕ = π) should be consistently applied throughout the catalyzation and regular TRs. Compare no preparation, θ/2-TR/2 preparation, and linear ramp catalyzation with number of TRs = [5, 10, 20]. For each preparation scheme, plot the transition to steady state for a range of off-resonance frequencies (±400 Hz) as an image (magnitude) and specifically for spins in the center of the pass band and stop band (magnitude and phase). (See slides for Lectures 2 and 3.)(iv) Discuss your observations.2. Extended Phase Graph SimulationsIn the second part, we will use the extended phase graph (EPG) formalism to simulate rapid GRE sequences. Use the MATLAB scripts sent to the class email list as a starting point.2A. Gradient-spoiled GRE. Simulate the evolution of phase states for a gradient-spoiled GRE (SSFP-FID) sequence.(i) Review epg_cpmg_hhw.m, which simulates turbo spin echo (TSE). Modify the script to simulate SSFP-FID by looping through each TR, which consists of an RF excitation at the beginning of TR and one gradient spoiler at the end of TR.Bonus: Compare the EPG simulations of gradient-spoiled GRE with Bloch simulations.2B. RF-spoiled GRE. Simulate the evolution of phase states for a gradient-spoiled and RFspoiled GRE sequence.(i) Based on your work in 2A, add quadratic RF phase spoiling to simulate an RF-spoiled GRE sequence. Remember to demodulate the received signal by the same phase as the RF pulse.(ii) Assume the parameters: RF θ = 60o and quadratic Δϕ based on ϕ0 = [2, 5, 117o], TR = 20 ms, 400 TRs, tissue T1 = 1000 ms and T2 = [100, 500, 1000] ms. Plot the evolution of all F and Z states as an image (magnitude), as well as the evolution of F0 (magnitude and phase), for these parameter choices. Compress the dynamic range of your images (e.g., |Img|^p, p
1. Shannon lower bound. Let X be a continuous random variable with mean zero and variance σ2. R(D) is the corresponding rate-distortion function for mean-squared distortion. (a) Show the lower bound: . (b) Using the joint distribution shown in Figure 1, show the upper bound on R(D): (1) Are Gaussian random variables harder or easier to describe in bits – in the sense of achieving small mean squared error distortion – than other random variables with the same variance? Z ∼ N 0, σDσ2−2D 2 σ −D σ2 ‘$? &% ?u X – – -Xˆ Figure 1: Joint distribution for upper bound on rate distortion function. The circle with the dot represents multiplication. 2. Rate distortion for uniform source with Hamming distortion. Consider a source X uniformly distributed on the set {1,2,…,m}. Find the rate distortion function for this source with Hamming distortion, i.e.,via the following steps: (a) Argue that R(D) = 0 when . (b) Show that for 1) for any joint distribution (X,Xˆ) satisfying the distortion constraint D. Hint: Fano’s inequality. (c) Find distribution p(xˆ|x) that achieves the above lower bound when 0 . Hint: Consider the form below.(d) Use the above parts to write down the rate-distortion function R(D) for D ≥ 0. 3. Rate distortion for two independent sources. Can one simultaneously compress two independent sources better than by compressing the sources individually? This problem addresses this question. Let {Xi} be iid ∼ p(x) with distortion d(x,xˆ) and rate distortion function RX(D). Similarly, let {Yi} be iid ∼ p(y) with distortion d(y,yˆ) and rate distortion function RY (D). Suppose the {Xi} process and the {Yi} process are independent of each other. Suppose we now wish to describe the process {(Xi,Yi)} subject to distortions E[d(X,Xˆ)] ≤ D1 and E[d(Y,Yˆ)] ≤ D2. Thus a rate RX,Y (D1,D2) is sufficient, where(a) Show RX,Y (D1,D2) ≥ RX(D1) + RY (D2). (b) Does equality hold? 4. Distortion-rate function. Let D(R) = min E[d(X,Xˆ)] (2) p(xˆ|x):I(X;Xˆ)≤R be the distortion rate function. (a) Is D(R) increasing or decreasing in R? (b) Is D(R) convex or concave in R? (c) Let X1,X2,…,Xn be i.i.d. ∼ p(x). Suppose one is given a code () withWe want to show that). Give reasons for the following steps in the proof: (3) (4) (5) ! (6) (7) (8)
1. Polar codes encoding and decoding.Figure 1: Polar code encoding circuit with N = 4 for problem 2. W is a BEC, and Xi’s, Yi’s and Ui’s are binary. For parts (a) to (c), assume that U1 and U2 are both frozen to 0, while U3 and U4 are the message bits. (a) What is the rate of the code? (b) Perform encoding for input message (U3,U4) = (1,1) and find the codeword (X1,X2,X3,X4). (c) Perform successive cancellation decoding for received vector (Y1,Y2,Y3,Y4) = (1,?,?,1). Does the decoding succeed, and if yes, what is the decoded message (U3,U4)? Now we try to understand how the choice of the frozen bits impacts the decoding. We also look at the suboptimality of successive cancellation decoding. For parts (d) and (e), assume that U2 and U3 are both frozen to 0, while U1 and U4 are the message bits. (d) Perform successive cancellation decoding for received vector (Y1,Y2,Y3,Y4) = (1,?,?,0) and verify that the decoding fails when decoding U1. (e) Perform optimal maximum likelihood decoding for the same received as part (d), i.e., (Y1,Y2,Y3,Y4) = (1,?,?,0). In this case, you can perform maximum likelihood decoding by • First computing the codeword (X1,X2,X3,X4) for all 4 possible input messages (U1,U4). • Then finding the input message(s) (U1,U4) for which you could receive (Y1,Y2,Y3,Y4) = (1,?,?,0). If more than one such message exists, declare failure. Does the decoding succeed and, if yes, what is the decoded message (U1,U4)? 2. Proving polarization for the BEC. In polar coding, we preprocess the input so that the n identical uses of a symmetric memoryless channel become n synthetic channel uses with very different capacities. We state a polarization theorem, which says that as n → ∞, the fraction of almost noiseless channels approaches C and the fraction of almost useless channels approaches 1 − C, where C is the capacity of the original channel. In this question, we consider the binary erasure channel (BEC) with erasure probability p and prove the polarization theorem rigorously. For the BEC W with erasure probability p, define M(W) = pp(1 − p) as its mediocrity. (a) When is the mediocrity of a channel 0? (b) Consider the polarized channels W+ and W− we have seen in the class for m = 1. Are they also BECs? If so, what are M(W+) and M(W−)? (c) Recall the tree of channel capacities obtained by recursively applying the polarization formula to the BECs. Suppose an ant walks on the tree of channel capacities starting at W and choosing W+ and W− with equal probability 1/2. Upon reaching each channel W˜ (e.g., W˜ = W+), it chooses W˜ + (W++) and W˜ − (W+−) with equal probability 1/2. Let Fm denote the distribution of the erasure probabilities for n = 2m and let F0 = p (with probability 1). What are the distributions F1 and F2? (d) Let Mm denote the average mediocrity of the channels for the distribution Fm. For instance M0 = pp(1 − p). What is M1? Prove that. (e) Let. Prove that Mm ≤ ρm. (f) Let mediocre(m,ϵ) denote the fraction of the n = 2m channnels with mediocritystrictly larger than pϵ(1 − ϵ). Show that mediocre(m,ϵ) → 0 as m → ∞. (g) Let g(m,ϵ) and b(m,ϵ) denote the fraction of the channels with erasure probability strictly smaller than ϵ (i.e., good channels) and strictly larger than 1−ϵ (i.e., bad channels) respectively. Show that p ≥ b(m,ϵ)(1 − ϵ). (Hint: recall that the expected erasure probability under Fm is the same for all m and equal to p.) (h) Define g(ϵ) := limm→∞ g(m,ϵ). Argue that g(m,ϵ) ≥ g(m,δ) for any ϵ ≥ δ. Conclude that g(ϵ) ≥ g(δ) for any ϵ ≥ δ. (i) Prove that g(ϵ) ≥ 1 − p. Thus, for any given ϵ ∈ (0,1), the fraction g(ϵ) of good channels becomes at least C = 1 − p as m → ∞. 3. Convexity of rate distortion function. Assume (X,Y ) ∼ p(x,y) = p(x)p(y|x). In this problem, you will show that for fixed p(x), I(X;Y ) is a convex function of p(y|x). (a) The log sum inequality states that for n positive numbers a1,a2,··· ,an, and b1,b2,··· ,bn, we havewith equality if and only if =constant. Using this inequality (you don’t have to prove this inequality), show that D(p||q) is convex in (p,q), i.e., λD(p1||q1) + (1 − λ)D(p2||q2) ≥ D(λp1 + (1 − λ)p2||λq1 + (1 − λ)q2) (b) Let p1(y|x) and p2(y|x) be two different conditional distributions. For i ∈ {1,2}, let pi(x,y) = pi(y|x)p(x), i.e., their corresponding joint distributions. For 0 ≤ λ ≤ 1, let pλ(y|x) =∆ λp1(y|x) + (1 − λ)p2(y|x). Show that pλ(y) = λp1(y) + (1 − λ)p2(y) (c) The mutual information between random variables X and Y can be alternatively written as I(X;Y ) = D(p(x,y)||p(x)p(y)) Using this in addition to the results of the previous parts show that for fixed p(x), I(X;Y ) is convex in p(y|x). (d) Using the previous part, show that the rate distortion function R(I)(D) is convex in the distortion parameter D.
1. Minimizing Channel Probability of Error. J – Encoder Xn – Memoryless Channel PY |X Y n – Decoder Jˆ – Message Estimate of Message J is a message uniformly distributed on {1,2,…,M} passed into the system. The encoder maps message J onto its corresponding n-length codeword Xn from codebook cn = {Xn(1),Xn(2),…,Xn(M)}. The encoded message is sent through a memoryless channel characterized by PY |X, and we receive Y n as output. The decoder is responsible for estimating J from Y n; it is a function Jˆ that maps Y n to one of the symbols in {1,2,…,M,error}. We define the probability of error Pe = P(Jˆ(Y n) ̸= J). Show that Pe, for a fixed codebook cn, is minimized by: Jˆ(yn) = argmax1≤j≤MP(J = j|Y n = yn). 2. The two-look Gaussian channel. – –X(Y1,Y2) Consider the ordinary Gaussian channel with two correlated looks at X, i.e., Y = (Y1,Y2), where Y1 = X + Z1 (1) Y2 = X + Z2 (2) with a power constraint P on X, and (Z1,Z2) ∼ N2(0,K), where . (3) Find the capacity C for (a) ρ = 1 (b) ρ = 0 (c) ρ = -1 Hint: The formula for the differential entropy of a Gaussian random vector can be found in the book (refer to Theorem 8.2). It can also be derived based on the formulas for differential entropy and the Gaussian PDF. 3. Output power constraint. Consider an additive white Gaussian noise channel with an expected output power constraint P. Thus Y = X + Z, Z ∼ N(0,σ2), Z is independent of X, and EY 2 ≤ P. Find the channel capacity. 4. Gaussian mutual information Suppose that (X,Y,Z) are jointly Gaussian and that X → Y → Z forms a Markov chain. Let X and Y have correlation coefficient ρ1 and let Y and Z have correlation coefficient ρ2. Find I(X;Z). Hint: Refer to Theorem 8.2 in the textbook. In the case of a bivariate normal distribution,, where ρX,Y is the correlation coefficient and σA is the standard deviation of random variable A. 5. Bottleneck channel Suppose a signal X ∈ X = {1,2,…,m} goes through an intervening transition X −→ V −→ Y : p(v|x) V p(y|v) XY where X = {1,2,…,m}, Y = {1,2,…,m}, and V = {1,2,…,k}. Here p(v|x) and p(y|v) are arbitrary and the channel has transition probability p(y|x) = Pv p(v|x)p(y|v). Show C ≤ logk. 6. Joint typicality. Let (Xi,Yi,Zi) be i.i.d. according to p(x,y,z). With finite alphabets, we will say that (xn,yn,zn) is jointly typical (written () if • p(xn) ∈ 2−n(H(X)±ϵ) • p(yn) ∈ 2−n(H(Y )±ϵ) • p(zn) ∈ 2−n(H(Z)±ϵ) • p(xn,yn) ∈ 2−n(H(X,Y )±ϵ) • p(xn,zn) ∈ 2−n(H(X,Z)±ϵ) • p(yn,zn) ∈ 2−n(H(Y,Z)±ϵ) • p(xn,yn,zn) ∈ 2−n(H(X,Y,Z)±ϵ) Note that p(a) ∈ 2−n(k±ϵ) means that . Now suppose () is drawn according to p(xn)p(yn)p(zn). Thus have the same marginals as p(xn,yn,zn) but are independent. Find (bounds on) in terms of the entropies H(X), H(Y ), H(Z), H(X,Y ), H(X,Z), H(Y,Z) and H(X,Y,Z).
1. Time-varying channels. Consider a time-varying discrete memoryless channel. Let Y1,Y2,…,Yn be conditionally independent given X1,X2,…,Xn, with conditional distribution given by p(y|x) = Qni=1 pi(yi|xi) (where pi(yi|xi) is a BSC(δi) as shown in figure). Let X = (X1,X2,…,Xn), Y = (Y1,Y2,…,Yn). 01 PPPPPPP1 −PPδiPPPδδPii P–1Pq 01 1 − δi In this problem, we show that maxI(X;Y) = PX (a) Show that I(X;Y) )) for any PX. Hint: Use a chain of inequalities similar to the channel coding converse proof. (b) Find a distribution over X for which I(X;Y) = 2. Jointly typical sequences. We will calculate the jointly typical set for a pair of random variables connected by a binary symmetric channel, and the probability of error for jointly typical decoding for such a channel. 0 Q 0.9 -3 0 Q Q Q Q Q Q 0.1 Q Q 0.1 Q Q Q Q Q 1 -Qs 1 0.9 We will consider a binary symmetric channel with crossover probability 0.1. The input distribution that achieves capacity is the uniform distribution, i.e., p(x) = (1/2,1/2), which yields the joint distribution p(x,y) for this channel given by XY 0 0 0.45 1 0.05 0.05 0.45 The marginal distribution of Y is also (1/2,1/2). (a) Calculate H(X), H(Y ), H(X,Y ) and I(X;Y ) for the joint distribution above. (b) Let X1,X2,…,Xn be drawn i.i.d. according the Bernoulli(1/2) distribution. Of the 2n possible input sequences of length n, which of them are typical, i.e., member of) for ϵ = 0.2? Which are the typical sequences in)? (c) The jointly typical set) is defined as the set of n-sequence pairs (xn,yn) that satisfy the following equations:The first two equations correspond to the conditions that xn and yn are in and) respectively. Consider the last condition, which can be rewritten to state that ). Let k be the number of places in which the sequence xn differs from yn (k is a function of the two sequences). Then we can write (1) (2) (3) An alternative way at looking at this probability is to look at the binary symmetric channel as an additive channel Y = X ⊕ Z, where Z is a binary random variable that is equal to 1 with probability p, and is independent of X. In this case, (4) (5) (6) (7) Show that the condition that (xn,yn) is jointly typical is equivalent to the condition that xn is typical and zn = yn − xn is typical. (d) We now calculate the size of) for n = 25 and ϵ = 0.2. Here is a table of the probabilities and numbers of sequences of with k ones k 0 1 0.071790 0.152003 1 25 0.199416 0.278800 2 300 0.265888 0.405597 3 2300 0.226497 0.532394 4 12650 0.138415 0.659191 5 53130 0.064594 0.785988 6 177100 0.023924 0.912785 7 480700 0.007215 1.039582 8 1081575 0.001804 1.166379 9 2042975 0.000379 1.293176 10 3268760 0.000067 1.419973 11 4457400 0.000010 1.546770 12 5200300 0.000001 1.673567 (Sequences with more than 12 ones are omitted since their total probability is negligible (and they are not in the typical set).) What is the size of the set)? (f) Now consider a particular sequence yn = 000000…0, say. Assume that we choose a sequence Xn at random, uniformly distributed among all the 2n possible binary n-sequences. What is the probability that the chosen sequence is jointly typical with this yn? (Hint: this is the probability of all sequences xn such that yn−xn ∈(g) Now consider a code with 29 = 512 codewords chosen at random, uniformly distributed among all the 2n sequences of length n = 25. One of these codewords, say the one corresponding to i = 1, is chosen and sent over the channel. As calculated in part (e), the received sequence, with high probability, is jointly typical with the codeword that was sent. What is probability that one or more of the other codewords (which were chosen at random, independently of the sent codeword) is jointly typical with the received sequence? (Hint: You could use the union bound but you could also calculate this probability exactly, using the result of part (f) and the independence of the codewords) (h) Given that a particular codeword was sent, the probability of error (averaged over the probability distribution of the channel and over the random choice of other codewords) can be written as Pr(Error|xn(1) sent) = X p(yn|xn(1)) (8) yn:yncauses error There are two kinds of error: the first occurs if the received sequence yn is not jointly typical with the transmitted codeword, and the second occurs if there is another codeword jointly typical with the received sequence. Using the result of the previous parts, calculate this probability of error. (Hint: You could use the union bound but you could calculate it more accurately using the fact that the probability of error does not depend on which codeword was sent, by the symmetry of the random coding argument.) 3. BSC with feedback. Suppose that feedback is used for a binary symmetric channel with crossover probability parameter p. Each time a channel output is received, it becomes the next transmission: X1 is Bern(1/2), X2 = Y1, X3 = Y2, …, Xn = Yn−1. Find lim). How does it compare to the capacity of this channel? 4. Fano’s inequality. Let Pr(X = i) = pi, i = 1,2,…,m and let p1 ≥ p2 ≥ p3 ≥ ··· ≥ pm. The minimal probability of error predictor of X is Xˆ = 1, with resulting probability of error Pe = 1 − p1. Maximize H(X) subject to the constraint 1 − p1 = Pe to find a bound on Pe in terms of H. This is Fano’s inequality in the absence of conditioning. Hint: Consider PMF (p2/Pe,p3/Pe,…,pm/Pe).
1. Bad codes. Which of these codes cannot be a Huffman code for any probability assignment? Justify your answers. (a) {0,10,11}. (b) {00,01,10,110}. (c) {01,10}. 2. Coin Toss Experiment and Golomb Codes Kedar, Mikel and Naroa have been instructed to record the outcomes of a coin toss experiment. Consider the coin toss experiment X1,X2,X3,… where Xi are i.i.d. Bern(p) (probability of a H (head) is p), p = 15/16. (a) Kedar decides to use Huffman coding to represent the outcome of each coin toss separately. What is the resulting scheme? What compression rate does it achieve? (b) Mikel suggests he can do a better job by applying Huffman coding on blocks of r tosses. Construct the Huffman code for r = 2. (c) Will Mikel’s scheme approach the optimum expected number of bits per description of source symbol (coin toss outcome) with increasing r? How does the space required to represent the codebook increase as we increase r? (d) Naroa suggests that, as the occurrence of T is so rare, we should just record the number of tosses it takes for each T to occur. To be precise, if Yk represents the number of trials until the kth T occurred (inclusive), then Naroa records the sequence: Zk = Yk − Yk−1, k ≥ 1, (1) where Y0 = 0 i. What is the distribution of Zk, i.e., P(Zk = j),j = 1,2,3,…? ii. Compute the entropy and expectation of Zk. iii. How does the ratio between the entropy and the expectation of Zk compare to the entropy of Xk? Give an intuitive interpretation. (e) Consider the following scheme for encoding Zk, which is a specific case of Golomb Coding. We are showing the first 10 codewords. Z Quotient Remainder Code 1 0 1 1 01 2 0 2 1 10 3 0 3 1 11 4 1 0 0 1 00 5 1 1 0 1 01 6 1 2 0 1 10 7 1 3 0 1 11 8 2 0 00 1 00 9 2 1 00 1 01 10 2 2 00 1 10 i. Can you guess the general coding scheme? Compute the expected codelength of this code. ii. What is the decoding rule for this Golomb code? iii. What makes this codebook suitable for efficient encoding and decoding? 3. Arithmetic Coding. 0.3 0.1 0.106 !” = [0,1) !) = [0.1,0.3) !, = [0.1,0.12) !. = [0.106,0.12) Figure 1: Illustration of arithmetic coding. Note: Throughout this problem, we will work with digits rather than bits for simplicity. So the logarithms will be base 10 and the compressor will output digits {0,1,…,9}. This problem introduces a simplified version of arithmetic coding, which is itself based on Shannon-Fano-Elias coding. Arithmetic coding takes as input a sequence xn ∈ Xn and a distribution q over X. The encoder maintains an interval which is transformed at each step as follows: • Start with I0 = [0,1). • For i = 1,…,n: – Divide Ii−1 into |X| half-open subintervals with length of proportional to q(x), i.e., for x ∈ X. – Set Figure 1 shows an example of this for X = {R,G,B}, (q(R),q(G),q(B)) = (0.1,0.2,0.7) and x3 = GRB. At the end of this process, the encoder selects a number in the interval In and outputs the digits after the decimal point for that number. In the example shown, the encoder can output 11, which corresponds to 0.11 ∈ [0.106,0.12). While 1103 (corresponding to 0.1103) is also a valid output, the encoder tries to output the shortest possible valid sequence. The YouTube video https://youtu.be/ FdMoL3PzmSA might be helpful for understanding this process even better. (a) Briefly explain how the decoding might work in a sequential manner. You can assume that the decoder knows the alphabet, the distribution q and the length of the source sequence n. (b) What is the length of interval In in terms of q and xn? (c) For the following intervals In obtained by following the above-described process for some xn, find the length of the shortest output sequence (in digits): i. [0.095,0.105) ii. [0.11,0.12) iii. [0.1011,0.102) In general, if the interval length is ln, then the shortest output sequence has at most digits. (d) Show that the length l(xn) for the arithmetic encoding output satisfies(e) Suppose that Xn i.i.d.∼ X which has PMF P, and we use arithmetic coding with q = P. Then show thatCompare this to Huffman coding over blocks of length n with respect to compression rate and computational complexity. (f) Suppose both the encoder and the decoder have a prediction algorithm (say a neural network) that provides probabilities qi(x|xi−1) for all i’s and all x ∈ X. How would you modify the scheme such that you achieveThus, if you have a prediction model for your data, you can apply arithmetic coding on it – good prediction translating to high probability, in turn translating to short compressed representations. 4. Entropy Rate. Consider the Markov process from class taking values in {H,T} with the joint probability distribution given as n P(X1 = x1,…,Xn = xn) = P(X1 = x1)YP(Xi = xi|Xi−1 = xi−1) i=2 where and for all i > 1. (a) Directly compute P(X2 = H) and extend that result to show that the process is stationary (we are only looking for the main idea, no need to write a long proof). (b) Compute H(Xn|Xn−1,…,X1) as a function of n and find the limit as n → ∞. (c) Compute) as a function of n and find the limit as n → ∞. How does this relate to the result in part (b)? 5. Individual Sequences and a Universal Compressor. Note: Ignore integer constraints on codeword lengths throughout this problem. Notation: h2(p) = −plog2 p − (1 − p)log2(1 − p) (= binary entropy function). Let xn be a given arbitrary binary sequence, with n0 0’s and n1 1’s (n1 = n−n0). You are also provided a compressor Cq which takes in any arbitrary distribution q on {0,1} as a parameter, and encodes xn using:bits per symbol where (a) Given the sequence xn, what binary distribution q(x) will you choose as a parameter to the compressor Cq, so that L¯q(xn) is minimized. Your answer (values of q(0) and q(1)) will be expressible in terms of n, n0 and n1. (b) When compressing any given individual sequence xn, we also need to store the parameter distribution q(x) (required for decoding). Show that you can represent the optimal parameter distribution q(x) from part (a) using log(n + 1) bits. You can assume that the decoder knows the length of the source sequence n. (c) Show that the effective compression rate for compressing xn (in bits per source symbol) with the distribution q from part (a) is h2(n1/n) + log(n + 1)/n. (d) Now suppose that we apply the scheme above to Xn sampled from an i.i.d. Ber(p) distribution. Show that the expected compression rate approaches h2(p) as n → ∞, i.e., the scheme is a universal compressor for i.i.d. sources. 6. Extending to Shannon Codes For a general source, let . Then, X −n∗u 2 ≤ 1. u∈U We want to consider a new source p∗(u) = 2−n∗u. p∗(u) does not sum to 1 over U, but we claim that we can add a finite number of new symbols to extend the source to U∗ ⊇ U such that p∗(u) is dyadic over U∗. Prove this claim. Hint: How can you reduce this problem to showing that certain rational numbers have a finite binary representation? 7. Decoding LZ77 We encoded a binary sequence using LZ77; we now want to decode the resulting bitstream. We first decode it into the triplets and obtain: (0, 0, 1) (0, 0, 0) (1, 5, 1) (8, 2, 1) (a) (b) (c) (d) Recall that the first entry of the triplet indicates how far back in the sequence you must go to start decoding the phrase; the second entry of the triplet indicates how many elements from that point should be “copied” into your newest phrase entry; and the final entry of the tuple indicates the new element (unseen in the past sequence) that should be added. Specify how these triplets will now be decoded to reconstruct the original source sequence.
1. Data Processing Inequality. The random variables X, Y and Z form a Markov triplet (X − Y − Z) if p(z|y) = p(z|y,x), and or, equivalently, if p(x|y) = p(x|y,z). If X, Y , Z form a Markov triplet (X − Y − Z), show that: (a) H(X|Y ) = H(X|Y,Z) and H(Z|Y ) = H(Z|X,Y ) (b) H(X|Y ) ≤ H(X|Z) (c) I(X;Y ) ≥ I(X;Z) and I(Y ;Z) ≥ I(X;Z) (d) I(X;Z|Y ) = 0 where the conditional mutual information of random variables X and Y given Z is defined by2. Two looks. Let X,Y1, and Y2 be binary random variables. Assume that I(X;Y1) = 0 and I(X;Y2) = 0. (a) Does it follow that I(X;Y1,Y2) = 0? Prove or provide a counterexample. (b) Does it follow that I(Y1;Y2) = 0? Prove or provide a counterexample. 3. Prefix and Uniquely Decodable codes Consider the following code: u Codeword(a) Is this a Prefix code? (b) Argue that this code is uniquely decodable, by describing an algorithm for the decoding. 4. Relative entropy and the cost of miscoding. Let the random variable X be defined on {1,2,3,4,5,6} according to pmf p. Let p and another pmf q be Symbol p(x) q(x) C1(x) C2(x) 1 1/2 1/2 0 0 2 1/8 1/4 100 10 3 1/8 1/16 101 1100 4 1/8 1/16 110 1101 5 1/16 1/16 1110 1110 6 1/16 1/16 1111 1111 (a) Calculate H(X), D(p||q) and D(q||p). (b) The last two columns above represent codes for the random variable. Verify that codes C1 and C2 are optimal under the respective distributions p and q. (c) Now assume that we use C2 to code X. What is the average length of the codewords? By how much does it exceed the entropy H(X), i.e., what is the redundancy of the code? (d) What is the redundancy if we use code C1 for a random variable Y with pmf q? 5. (Strong) LLN and AEP. Let X1,X2,… be independent identically distributed random variables drawn according to the probability mass function p(x),x ∈ {1,2,…,m}. Thus). We know that in probability. Let, where q is another probability mass function on {1,2,…,m}. (a) Evaluate lim), where X1,X2,… are i.i.d. ∼ p(x). (b) Now evaluate the limit of the log likelihood ratio when X1,X2,… are i.i.d. ∼ p(x). Thus the odds favoring q are exponentially small when p is true. 6. AEP. Let Xi for i ∈ {1,…,n} be an i.i.d. sequence from the p.m.f. p(x) with alphabet X = {1,2,…,m}. Denote the expectation and entropy of X by µ := E[X] and H := −Pp(x)logp(x) respectively. For ϵ > 0, recall the definition of the typical setand define the following set . In what follows, ϵ > 0 is fixed. (a) Does? (b) Does? (c) Show that for all n, . (d) Show that for all n sufficiently large: . 7. An AEP-like limit and the AEP (Bonus) (a) Let X1,X2,… be i.i.d. drawn according to probability mass function p(x). Find the limit in probability as n → ∞ of . (b) Let X1,X2,… be an i.i.d. sequence of discrete random variables with entropy H(X). Let Cn(t) = {xn ∈ X n : p(xn) ≥ 2−nt} denote the subset of n-length sequences with probabilities ≥ 2−nt. i. Show that |Cn(t)| ≤ 2nt. ii. What is limn→∞ P(Xn ∈ Cn(t)) when t < H(X)? And when t > H(X)?
1. Example of joint entropy. Let p(x,y) be given by @ @Y X @ 0 1 0 1 0 Find (a) H(X),H(Y ). (b) H(X | Y ),H(Y | X). (c) H(X,Y ). (d) H(Y ) − H(Y | X). (e) I(X;Y ). (f) Draw a Venn diagram for the quantities in (a) through (e). Numerically round the answers to three decimal places. 2. Entropy of Hamming Code. Hamming code is a simple error-correcting code that can correct up to one error in a sequence of bits. Now consider information bits X1,X2,X3,X4 ∈ {0,1} chosen uniformly at random, together with check bits X5,X6,X7 chosen to make the parity of the circles even. (eg: X1 + X2 + X4 + X7 = 0 mod 2)Thus, for example,becomesThat is, 1011 becomes 1011010. (a) What is the entropy H(X1,X2,…,X7) of X := (X1,…,X7)? Now we make an error (or not) in one of the bits (or none). Let Y = X ⊕ e, where e is equally likely to be (1,0,…,0),(0,1,0,…,0),…,(0,0,…,0,1), or (0,0,…,0), and e is independent of X. (b) Show that one can recover the message X perfectly from Y. (Please provide a justification, detailed proof not required.) (c) What is H(X|Y)? (d) What is I(X;Y)? (e) What is the entropy of Y? 3. 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: (a) H(X,g(X)) = (b) H(X) + H(g(X) | X) (1) = H(X); (2) H(X,g(X)) (c) = (d) H(g(X)) + H(X | g(X)) (3) ≥ H(g(X)). (4) Thus H(g(X)) ≤ H(X). 4. Coin flips. A fair coin is flipped until the first head occurs. Let X denote the number of flips required. , . (b) A random variable X is drawn according to this distribution. Construct an “efficient” sequence of yes-no questions of the form, “Is X contained in the set S?” that determine the value of X. Compare H(X) to the expected number of questions required to determine X. 5. Minimum entropy. In the following, we use H(p1,…,pn) ≡ H(p) to denote the entropy H(X) of a random variable X with alphabet X := {1,…,n}, i.e., . What is the minimum value of H(p1,…,pn) = H(p) as p ranges over the set of ndimensional probability vectors? Find all p’s which achieve this minimum. 6. Mixing increases entropy. Let pi > 0, i = 1,2,…m. Show that the entropy of a random variable distributed according to (p1,…,pi,…,pj,…,pm), is less than the entropy of a random variable distributed according to ( 7. Infinite entropy. [Bonus] This problem shows that the entropy of a discrete random variable can be infinite. (In this question you can take log as the natural logarithm for simplicity.) (a) Let. Show that A is finite by bounding the infinite sum by the integral of (xlog2 x)−1. (b) Show that the integer-valued random variable X distributed as: P(X = n) = (Anlog2 n)−1 for n = 2, 3, … has entropy H(X) given by:(c) Show that the entropy H(X) = +∞ (by showing that the sum diverges).
1. 1. Computer question using Matlab (continuation of previous homeworks). a) In Matlab, regress U.S. real per capita consumption growth on a constant and U.S. data incomegrowth by OLS and calculate the t-stat . Estimate and AR(1) model for the residuals and estimate the model again using a) Cochrane-Orcutt and b) Prais-Winsten. Compare the estimates and the t-stats. b) In Matlab, estimate the same model by Maximum Likelihood. Compare to the previous estimates.
1. A common model in economics is one where a typical agent’s log wage is a sum of a random walk and independent white noise. Define yt such that yt = yt−1 + ut, where ut is white noise with variance σu2, and define wt = yt + et, where et is white noise with variance σe2. (The innovations u and e are independent.) Econometricians has estimated this model by matching the moments of empirical wages to the theoretical moments of this model. wt is not stationary (it is not stable so it cannot be stationary), so econometricians instead finds the moments of ∆wt. Find the variance, and the autocovariances of order one and two for ∆wt. 2. Assume that an agent’s wage income follows the AR(1) process yt = µ + βyt−1 + et (∗) where et is white noise with variance σe2 and β < 1. Assume the agent’s wage was 100$ period 0. a) What is the agent’s expected wages in period t (for any t > 0)? b) If the discount rate is 0.9 percent, what is the discounted (conditional) expected value of all future income (Σ)? (Hint: use the formula for geometric sums in δ times β. It takes a few more steps to get the expression for the mean term, but make sure you at least get the stochastic term right.) 3. Computer question using Matlab (continuation of previous homeworks). a) In Matlab, regress real per capita U.S. data income growth on it own lag and a constant. (AnAR(1) model.) Using a t-test, can you reject that income growth is white noise? b) Also estimate and AR(2) mode for income growth. Can you reject the AR(2) in favor of anAR(1)? 4. In Matlab. Simulate an AR(1) model a thousand times for different values of the coefficient a to the lag (you can include a constant or not, but estimate the same model as you simulate). Let T = 40 Use values of a equal to 0.5, 0.9, and 0.99. Show that as a gets larger ˆa gets more biased towards zero.
1. a) Let xt = α0 + 5 ∗ ut + ut−1 , where ut is white noise. Find the autocovariances for xt in terms of σu2 (the variance of ut). b) Given the stationary AR(1) process xt = 3 + .5 ∗ xt−1 + ut where Eu2t = 3. Find the variance of xt, and the first 3 autocovariances and autocorrelations. 2. Given the AR(1) process: et = aet−1 + ut , with a = 0.5. Let E be the vector (e1,e2,e3). a) Assuming e0 is a fixed numbert, find the variance matrix Ω = var(e). b) Assuming et is stationary, find the variance matrix Ω = var(e). 3. Define the lag polynomials a(L) = a0 + a1 L and b(L) = b0 + b1L + b2L2. (Notice: in the notes, and in class, it is often assumed a0 = 1 and b0 = 1. This is just for simplification and doesn’t matter for any results since you can always re-scale the data and the lag-polynomial such that the first coefficient becomes unity (write a(L) as a0 a′(L) where the lag polynomial and similarly for b(L)). The constant a0 will not affect the properties of the lag-polynomial that we care about.) Assume a0 = 1, a1 = −2, b0 = 3, b1 = −.3, and b2 = .5 . i) If xt = 3,xt−1 = −3,xt−2 = −2, xt−3 = 9, and xt−4 = 9, what is a(L)xt? and b(L)xt? (This should be a number.) ii) Find the roots of a(L) and b(L). iii) What is c(L) = a(L)b(L)? What are the roots of c(L)? iv) Find the coefficients to the constant (identify), L, and L2 in the lag-polynomial b−1(L). 4. Computer question (continuation of previous homeworks). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) Calculate the residuals e. Regress et on et−1? Is there evidence of autocorrelation (Use t-tests.)
– Yi = aXi + ui , by OLS. Here a is a scalar and we assume for simplicity that there is no intercept and that in the true underlying model (not censured or truncated) the error term has mean 0. Assume that you only have 2 observations: X0 = (1,2), Y 0 = (2,5). The OLS estimate ˆa is 2.4 and the residuals are 0.4 and –0.2 (they do not sum to zero because we have no constant). a) (10%) Calculate the White robust standard error for ˆa. b) (10%) Now assume that the two observations above form a group and we have a second groupwhere (for computational simplicity) we also assume X0 = (1,2), Y 0 = (2,5) . So your data are now X0 = (1,2,1,2), Y 0 = (2,5,2,5). ˆa is still 2.4 and the residuals as before (repeated). b) (20%) Calculate the Robust standard error if you cluster on the two groups. 2. Computer question (continuation of previous homeworks). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) Calculate the residuals, take the absolute value, and regress them on each of the regressors. Do you find evidence of heteroskedasticity? (Use t-tests.) b) An alternative “test:” plot the residuals against each of the regressors. Do the residuals lookhomoskedastic? c) Assume that you are told that the variance of the residuals is proportional to the square of theinterest rates. Estimate the relation using the efficient GLS estimator. d) Program up and estimate the standard errors using the White robust estimator.
1. Computer question (Monte Carlo). Using Matlab, you will examine how the OLS estimator performs as a function of the sample size and the distribution of the regressors (we condition on the regressors, so think of this as picking different configurations of the regressors). You will use the normal random number generator to generate the error terms, the regressors, and the dependent variable. First, for N=500 draw a vector w of normal errors and construct X1i = 2 + wi2. Draw another vector v of (standard) normal errors and construct X2i = 1 + wi2 + 4 ∗ log(vi2). There is no particular logic to the regressors except I make them correlated and not mean 0. a) Now set N=20, Also draw a vector e of normal errors with variance 3 and construct Y = ι + 2X1 + 4X2 + e (this means that you only use the first 20 observations of the X’s). Estimate βˆ and construct the t-test for β1 = 2 and save it. You do this 100 times and count how often the t-stat exceed the critical value for a 5% two-sided test (using the t-distribution with N-3 degrees of freedom). Next we will try and figure out if the asymptotic distribution of the t-stat is a good approximation for N=20 and N=200. (You can try other values, when you have the loops set up, you should be able to just change one character to re-run the program). c) Set N=200. Draw a vector of standard normal errors and construct z = e2 − 1 (the is a simple way to construct a mean zero error that is not normal). Construct Y = ι + 2X1 + 4X2 + z. Estimate βˆ1 and construct the asymptotic t-test for β1 = 2 and save it. You do this 100 times and count how often the t-stat exceed the critical value for a 5% two-sided test (using the normal distribution). Does the asymptotic test perform better for the higher value of N? 2. Computer question (continuation of previous homeworks). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) Perform the following Chow tests (assuming the data are normally distributed—even if you rejected this in the previous question). a) Examine if the coefficients are the same before and after year 2008. (Use the appropriate test). b) Examine if the coefficient to the interest rate is the same before and after year 2008 (assumingthat the coefficient to income is not changing).
1. Consider the model yt = β0 + β1x1t + β2x2t + ut . Rewrite the model so that the restriction β1 = β2 becomes a single zero restriction that you can test using a t-test. (This should be easy, but it is often useful in practice.) 2. Almost the same question but super relevant for practice): A sample consists of males andfemales. We have a dummy Dm for males and a dummy Df for females. Consider the regression equation yi = β + βmDim + βfDif + ui . a) Show explicitly that there is perfect multi-collinearity in this model. So you now drop the constant to get rid of the collinearity and want to estimate yi = βmDim + βfDif + ui . b) Explain how you can rewrite the model such that βf = βm becomes a single zero restriction that you can test using a t-test. 3. Computer question (continuation of homework 1, 2, and 3). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) Calculate the t-test for each of the parameters and display the P-values. b) Test if the coefficient to income growth is identical to the coefficient for the interest rate. (Thetests don’t make much economic sense, but this exercise is about the tools.) Explain how you could use a t-test (how) or an F-test. Verify in Matlab that the P-values are identical for the two alternative tests. c) Test if the coefficients to income growth and the coefficient to the interest rate are both zero.(This means that you do one test for this.) How does the P-value compare to the ones that you get if you test the coefficients one-by-one using t-tests? d) Test if (simultaneusly) the coefficients to income growth is equal to the constant and if thecoefficient to the interest rate are equal to the constant. (This is two linear constraints, not economically meaningful, but that is not the goal here.)
1. More Frisch-Waugh! Assume that your run a regression with 2 regressors (think of demeanedregressors). Assume the fitted value is Yˆ = X1 + 4X2 . Assume that you instead run the regression (∗) Y = γ1 X1 + γ2 M1X2 + error , where M1 is the residual maker from regressing on X1. If P1 is the projection matrix on X1 and P1X2 = 1.5X1 , what would be the estimated values of γ1 and γ2 in the regression (*)? 2. For the bivariate Normal distribution, derive the formula for the conditional density f(X2|X1). , where all the “OLS-assumptions” – including normality of ϵt – hold. The regressors Dkt are quarterly dummy variables, such that D1t = 1 in the 2nd quarter ; 0 otherwise D2t = 1 in the 3rd quarter ; 0 otherwise D3t = 1 in the 4th quarter ; 0 otherwise Now assume that ¯y = 5 and if we let ¯yj ; j = 2,3,4 denote the average of the y-values in the kth quarter, assume that y¯2 = 4 , y¯3 = 2 , y¯4 = 0 . Also assume that ¯x = 0 and that xt is orthogonal to Dk ; k = 1,2,3. Based on the given information, find the values of the OLS-estimates βˆ0,βˆ1,βˆ2 and βˆ3. 3. Computer question (continuation of homeworks 1 and 2). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) Calculate the residual maker M and (using Matlab) calculate and display the eigenvalues and eigenvectors of M. b) Generate the C matrix and the diagonal matrix of eigenvalues Λ (in the notation of class) and verify that CΛC′ = M. Display the values of C and Λ. 4. Computer question. a) Generate two vectors of standard normally distributed variables e1 and e2 of length N = 100. b) Generate X1 = e1 and let X2 = e1 + e2 and calculate the variance-covariance matrix Σ for X = (X1,X2). (You can do that by hand, of course, but you will need to use it in the next question.) c) Find a square root Σ1/2 of Σ using Matlab. d) Calculate Y = (Y1,Y2) as Y = Σ−1/2X. e) Calculate the covariance between Y1 and Y2 and verify that it is (close to) zero.
1. Frisch-Waugh with 2 regressors. Assume you regresss yi = β1x1i + β2x2i + error . In vector notation: Y = β1X1 + β2X2 + error . Now ′ X1X1 X1′X2 ! ′ (X X) = X1′X2 X2′X2 . Find the vector of parameters β = (β1,β2)′, writing in terms of the inner products (like etc.). It is not hard to invert X′X, because the inner products are scalars. If you find it easier, you can assume without loss of generality that the units are chosen such that = 1 and (“Without loss of generality,” because we can change the units of the regressors without changing the results.) Now regress X2 = X1ξ + error , and find the fitted value P1X2 = X1 ∗ ξˆ (remember that P1X2 is proportional to X1) and the residual M1X2 = X2− P1X2. Finally, regress Y = (M1X2)β2 , and verify that the βˆ2 that you get from this second regression is the same as the βˆ2 from the original regression. 2. Computer question (continuation of homework 1). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) Regress income growth on the interest rate and take the residual which we can call MrY . b) Regress consumption growth on MrY and compare the estimated coefficient to the one from the first regression. c) Regress consumption growth on the interest rate and take the residual which we can call MrC d) Regress MrC on MrY and compare the estimated coefficient to the one from the first and second regressions. e) Draw a series of iid mean zero terms and add to income growth, getting Y ∗ and regress consumption on Y ∗ (income with measurement error) and the interest rate. Verify that the estimated coefficient to income gets closer to zero when there is measurement error. What happens to the coefficient to the interest rate? Repeat the regression with a much higher variance of the measurement error (“larger” measurement errors). What happens?
1. Computer question (continuation of previous homeworks). In Matlab, regress real per capita U.S. data consumption growth on income growth and the interest rate using the posted dataset. (This is the what you did in homework 1.) a) You are told that income growth is not exogenous to consumption growth, but lagged incomegrowth is. Suggest a suitable IV estimator. (Just words here.) b) In Matlab, estimate the coefficients using your suggested IV estimator. c) Try a different instrument and see if the IV estimate is different. c) Calculate the standard errors of the coefficients and compare to the estimated standard errorsfrom an OLS regression. d) Based on the IV estimation, test if the coefficient to income growth is zero. (NOTE: I mention that you can use the lagged variable here, because you already have it available. It is, or was, rather common to lagged variables used as instruments without much discussion and that is very often not a good idea. So do not take the setup of this problem as a suggestion for doing good empirical economics, but rather as a study of the IV estimator.) 2. Computer Monte Carlo IV question. Set N=20 and N=2000. Do the following S times (set S to a large number, I think 10,000 is good, but if your computer is slow, pick a lower number): and draw N(0,1) vectors U and V . Draw an N(0,σz2) vector Z, for σz2 = 10. Generate X = Z + σuU , for σu = 1, 5, or 50. Then generate Y = αX + σuU + V , for α = 1. For which values of σu do you think the is instrument weak (try and guess before you see the MC results)? In each Monte Carlo draw, estimate the reduced form, and save the estimated coefficient. In each Monte Carlo draw, estimate αOLS and αIV by OLS and IV, respectively, and save the coefficient and the t-statistic. Print the mean and standard error (across your S simulations) of the estimated coefficients and the t-statistic for each of the three values of σu and the two values of N. For which values of these parameters do the estimated values look more biased and imprecise? Note. I haven’t done this new exercise myself. So, you should show your results in class next
Required reading: Wright and Recht, Ch. 8. 1 (Exercise 1 in Wright and Recht, Ch. 8) Prove that, if f is convex and x ∈ dom(f), the subdifferential ∂f(x) is closed and convex. Reminder: A set S ⊆ Rn is closed if the limit of any convergent sequence (vn)n≥1 of elements of S is also an element of S: vn ∈ S for all n = 1,2,… and v = lim vn exists =⇒ v ∈ S. n→∞ 2 (Exercise 5 in Wright and Recht, Ch. 8) For the following norm functions f over Rn, find the subdifferential ∂f(x) and the directional derivative f0(x,v) for all x,v ∈ Rn: (a) The `1 norm. (b) The `∞ norm f(x) = kxk∞ = max |xi|. 1≤i≤n (c) The `2 (Euclidean) norm . 3 (Exercise 7 in Wright and Recht, Ch. 8) Find the subdifferential ∂f(x) of the piecewise-linear convex function f : Rn → R defined by , where ai ∈ Rn and bi ∈ R for i = 1,…,m. 4 Suppose that f is defined as a maximum of m convex, continuously differentiable functions; that is, f(x) = max1≤i≤m fi(x). Show thatX X ∂f(x) = λi∇fi(x) : λi ≥ 0, λi = 1 . i:fi(x)=f(x) i:fi(x)=f(x) 1
