EE226: Random Processes in Systems Fall’06Problem Set 6 — Due Novemb er, 2Lecturer: Jean C. Walrand GSI: Assane GueyeThis problem set essentially reviews properties of random process, the Wiener Filter, andMarkov chains. Not all exercises are to be turned in. Only those with the sign F are dueon Thursday, Novemberndat the beginning of the class. Although the remaining exercisesare not graded, you are encouraged to go through them.We will discuss some of the exercises during discussion sections.Please feel free to point out errors and notions that need to be clarified.Exercise 6.1. Show the following properties of the autocorrelation of wide sense stationaryrandom processes.1.rx(k) = r∗x(−k)Deduce that for a real process the autocorrelation is symmetric.2.rx(0) ≥ 0 and rx(0) ≥ |rx(k)|3. ifrx(0) = rx(k0)for some k0, then rx(k) is periodic with period k0.Solution: Hint(1) and (2) are easy to check by writing the definition of autocorrelation and taking conjugate.(3) Add solutionExercise 6.2. FFor each of the following, determine whether the process isi. WSSii. Stationary (in the strict sense)1. x(n) = A where A is a random variable with pdf fA(a).2. x(n) = A cos(nω0) where A is a Gaussian random variable with mean µAand varianceσ2A.3. x(n) = A cos(nω0+φ) where φ is a uniform random variable in [−π, π], A is a constant.4. x(n) = A cos(nω0) + B sin(nω0) where A and B are uncorrelated zero mean randomvariables with variance σ2.6-1EE226 Problem Set 6 — Due November, 2 Fall’065. A Bernoulli process with P [x(n) = 1] = 1 − P [x(n) = −1] = p6. y(n) = x(n) − x(n − 1) where x(n) is a Bernoulli process.Solution: Hint(1) WSS and SSS because we have independent samples from the distribution of A (iid).(2) The mean is µAcos(nω0) which depends on time. So it the process is not WSS (thus notSSS)(3) The mean is zero and the autocorrelation E[x(n + m)x(n)] =A22cos(mω0) so the processis WSS.Process is also SSS: first note that (nω0+ φ)mod(2π) is uniform in (0, 2π) independently ofn. Since cos(···) is 2π-periodic, we havecos(nω0+ φ) ≈Dcos((nω0+ φ)(mod2π)) ≈Dcos(Φ)where Φ is uniform in (0, 2π). Thus the distribution does not depend on n and thus it isstationary.(4) Process is WSS. Not always SSS.(5) Process is iid thus it is SSS(6) Process is WSS and SSS. In fact the distribution of y(n) ∈ {−2, 0, 2} is independent tothe time n.Exercise 6.3. Consider a random process X(t) defined byX(t) = U cos(ω0t) + V sin(ω0t) − ∞ < t < ∞where ω0is constant and U and V are r.v.’s.(a) Show that the condition E(U) = E(V ) = 0 is necessary for X(t) to be stationary.(b) Show that X(t) is WSS if and only if U and V are uncorrelated with equal variance;that is, E(UV ) = 0 and E(U2) = E(V2) = σ2Solution: Hint(a) Write the mean and verify that the only way to make it constant is to have E(U) =E(V ) = 0.(b) Write the correlation and verify that the only way to cancel the terms that depend on tis to have E(UV ) = 0 and E(U2) = E(V2) = σ2.Exercise 6.4. F(Part (a) is Optional)(a) We have derived the causal Wiener filter in discrete time.Let X(t) and Y (t) be two zero mean jointly WSS random processes with correlation functionsKX(τ), KY(τ) and KXY(τ). Derive the the causal Wiener filter of this problem.(b) Consider the (discrete) systemXn= αXn−1+ Wn−1(6.1)Yn= Xn+ Vn(6.2)6-2EE226 Problem Set 6 — Due November, 2 Fall’06where α is a constant, |α| < 1, (Vn, Wn) are uncorrelated white Gaussian noise sequenceswith variance 1.(1) Suppose that X0∼ N(0, σ2) and independent of (Vn, Wn). Derive the Kalman filterupdate equations for the MMSE of Xngiven Y0, . . . , Yn. What will the filter approach asn → ∞?(2) Now suppose that {Xn} is stationary and satisfies equations 6.1 and 6.2. Derive thecausal Wiener filter of {Xn} based on the Yn’s. How does this relate the previous question?Solution: Hint(a) This follows the same steps we have taken to derive the discrete time Wiener filter. Theonly new thing is the use of Laplace transform instead of z-transform.(b)-(1) The Kalman filter update equations are:ˆxn= αˆxn−1+ rn(yn− αˆxn−1)rn=snsn+ σ2vsn= α2σ2n−1+ σ2wσ2n= (1 − rn)snSince the system is observale/reachable we have a stationary solution. The solution is ob-tained by solving (for r, s, σ2):r =ss + 1s = α2σ2+ 1σ2= (1 − r)sSubstituting in the equations and solving a second order equation yield tos =α2+√α4+ 42σ2= r =α2+√α4+ 42 + α2+√α4+ 4So the steady state kalman filter can be written as:ˆxn=2α2 + α +√α4+ 4ˆxn−1+α2+√α4+ 42 + α2+√α4+ 4yn(2) Noticing that x(n) is the output of the LTI filter Q(z) =11−αz−1with input w(n) we haveSx(z) = Q(z)Q∗(1/z∗)Sw(z) =1(1 − αz−1)(1 − αz)6-3EE226 Problem Set 6 — Due November, 2 Fall’06Using the fact that x(n) and v(n) are uncorrelated we haveSy(z) = Sx(z) + Sv(z) =1(1 − αz−1)(1 − αz)+ 1To derive the Wiener filter, all we need is to compute Sxy(z) and to find a factorization ofSy(z).First notice thatRxy(k) = E[x(n + k)y∗(n)] = E[x(n + k)(x∗(n) + v∗(n))] = E[x(n + k)x∗(n)] = Rx(k)Thus Sxy(z) = Sx(z).NowSy(z) =1 + (1 − αz−1)(1 − αz)(1 − αz−1)(1 − αz)=2 + α2− αz−1− αz(1 − αz−1)(1 − αz)=(a − bz)(a − bz−1)(1 − αz−1)(1 − αz)wherea =√α2+ 2α + 2 +√α2− 2α + 22b =√α2+ 2α + 2 −√α2− 2α + 22Choose H(z) =a−bz−11−αz−1(is causal and has causal inverse), the causal Wiener filter is givenby:W (z) = H−1(z)[H(z)S−1y(z)Sxy(z)]+=1 − αz−1a − bz−1·1 − αza − bz1(1 − αz−1)(1 − αz)¸+=1 − αz−1a − bz−1·1(a − bz)(1 − αz−1)¸+The expression inside the [·]+can be decomposed into the form:1(a − bz)(1 − αz−1)=ca − bz+dz−11 − αz−1wherec =aa − αband d =αa − αb6-4EE226 Problem Set 6 — Due November, 2 Fall’06Thus, taking the inverse z-transform of each term of the sum gives1(a − bz)(1 − αz−1)↔ca³ab´n1(n ≤ 0) + dαn1(n ≥ 1)The first term is anti causal, so we only keep the the zero index coefficient, the second oneis causal so we can keep it. Overall we get·1(a − bz)(1 − αz−1)¸+=1a − αb+αa − αbz−11 − α−1=1a − αb11 − α−1Now the Causal Wiener filter is given byW (z) =1 − αz−1a − bz−11a − αb11 − α−1=1a − αb1a − bz−1So the estimate ˆx(n) is given by:ˆx(n) =baˆx(n − 1) +1a(a − αb)y(n)To compare this the steady Kalman filter we