EE226: Random Processes in Systems Fall’06Problem Set 9 — Due December, 7Lecturer: Jean C. Walrand GSI: Assane GueyeThis problem set essentially reviews Convergence and Renewal processes. Not all exercisesare to be turned in. Only those with the sign F are due on Thursday, December 7that thebeginning of the class. Although the remaining exercises are not graded, you are encouragedto 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 9.1. FAssume that Xnconverges in probability to X and f(·) is a continuous bounded function.Show that f(Xn) converges in probability to f(X)Solution:We want to show that∀² > 0 P r{ω : |f(Xn(ω)) − f(X(ω))| > ²} → 0Xnconverges in probability to X implies that∀² > 0 P r{ω : |Xn(ω) − X(ω)| > ²} → 0Since f is continuous, we also have that for all ω and ²0, δ0> 0 there is an n(w) > 0 suchthat|Xn(ω) − X(ω)| < δ0⇒ |f(Xn(ω)) − f(X(ω))| < ²0or|f(Xn(ω)) − f(X(ω))| ≥ ²0⇒ |Xn(ω) − X(ω)| ≥ δ0Thus, letting N = max{n(w)}, we have for n > N{ω : |f(Xn(ω)) − f(X(ω))| ≥ ²0} ⊂ {ω : |Xn(ω) − X( ω)| ≥ δ0}andP {ω : |f(Xn(ω)) − f(X(ω))| ≥ ²0} ≤ P {ω : |Xn(ω) − X(ω)| ≥ δ0} → 0which ends the proof.Exercise 9.2. Bonus FFAssume that Xnconverges in distribution to some random variable X.Show that we can find (Yn, Y ), where Ynis a sequence of random variables such that Ynhassame distribution as Xn, Y has the same distribution as X, and Ynconverges almost surely(a.s) to Y .9-1EE226 Problem Set 9 — Due December, 7 Fall’06Solution:Let Ω = (0, 1) be our event space and for ω uniformly picked in Ω let Yn(w) = sup {x :FXn(x) < ω}. Ynhas distribution FXn. We want to show that Yn(ω) → Y (ω) for allbut a countable number of ω’s, where Y ≈dX. To show that, let us define for all ω,aω= sup{x : FX(x) < ω}, bω= inf{x : FX(x) > ω}, and Ωo= {x : (aω, bω) = ∅} where(aω, bω) is an open interval with the given end point. In words, Ωocontains all ω ∈ Ω suchthat lim inf F−1(ω) = lim sup F−1(ω). Now let Y (ω) = F−1X(ω), ∀ω ∈ Ωo.Ω − Ωois countable since the intervals (aω, bω) are disjoint (because of the use of sup andinf and each nonempty interval contains a different rational number; recall that the set ofrational numbers is countable).Now for any ω ∈ Ωosup F−1Xn(ω) ≤ F−1(ω) ≤ inf F−1Xn(ω)Taking the limit n → ∞ we have Yn(ω) = F−1Xn(ω) → Y (ω), ∀ω ∈ Ωo.Exercise 9.3. FIn the notes we have shown that if Xnconverges in probability to X, then it converges indistribution to X.Show that, conversely, if Xnconverges in distribution to a constant C, then it converges inprobability to C.Solution:Since Xnconverges in distribution to C, we haveFXn(x) → δ(x > C), ∀xNow let us computeP r[|Xn− C| > ²] = 1 − P r[|Xn− C| ≤ ²]= 1 − Pr[C − ² < Xn< C + ²]= 1 − (FXn(C + ²) − FXn(C − ² ))n→∞−−−→ 1 − (1 − 0)Thus Xnconverges in probability to C.Exercise 9.4. FProblem 21.2 of the course notes.Solution:Note that since ²n↓ 0, for all ² > 0 there exists n0(k, m) ≥ 1 such that ²n< ² and for allk, m ≥ n ≥ 1P r[|Xk− Xm| > ²] ≤ P r[|Xk− Xm| > ²n] ≤ 2−n9-2EE226 Problem Set 9 — Due December, 7 Fall’06Let Zn(k, m) = |Xk− Xm| for all k, m ≥ n ≥ 1. ThenXnP r[Zn(k, m) > ²] =Xn≤n0(k,m)P r[Zn(k, m) > ²] +Xn>n0(k,m)P r[Zn(k, m) > ²]≤Xn≤n0(k,m)P r[Zn(k, m) > ²] +Xn>n0(k,m)2−n< ∞Thus Borel-Cantelli Lemma implies that P r[Zn(k, m) > ², i.o] = 0. This tells that for all² > 0, and for all ω ∈ Ω, there exists n(², ω) = max{n0(k, m)} > 0 such that|Xk(w) − Xm(w)| < ², ∀k, m ≥ n(², ω)Sosupm,k|Xk(w) − Xm(w)| < ², ∀k, m ≥ n(², ω)Hence Xnis Cauchy a.s.Since the set of real numb er is complete, Xnconverges almost surely to a limit in R.Exercise 9.5. FProblem 21.9 of the course notes.Solution:For any given state i, let Ni(t) be the process that count the number of arrivals when theCTMC X(t) is in state i. Ni(t) is a Poisson process with rate λi.The proportion of time that X(t) is in state i is given byπi= limt→∞1tZ∞01[Xs=i]dsSoNi(t)t→ λiπiWe also have thatN(t) =XiNi(t)Hencelimt→∞N(t)t= limt→∞1tXiNi(t)=Xilimt→∞Ni(t)t(9.1)=Xiλiπi9-3EE226 Problem Set 9 — Due December, 7 Fall’06where to get equation 9.1 we use the fact that X(t) is positive recurrent and does not explode,thusN(t)tmust be finite (thus it is bounded and we can use the dominated convergencetheorem to justify swapping the lim and the sum).Exercise 9.6. FRecall that in the study of renewal process we defined the inter-arrival times T = Ti+1−Ti, i ≥1 to be iid with distribution F (t).Letf(t) =1(1 + t)2to be the corresponding pdf.Find E[τ] where τ is the time until the next jump for the stationary process, and λ the rateof jumps.This exercise misses the point it was supposed to make. Answer the the next question:Find a distribution for which 0 < λ < ∞ and E[τ] = ∞.Solution:HintA simple example isf(t) =c(1 + t)3Find the constant c and see next exercise for a more interesting discussion.Exercise 9.7. FIn the derivation of E[τ] in class we wroteE[τ] =Z∞0λt(1 − F (t))dt=λ2Z∞0λ(1 − F (t))dt2=λ2£t2(1 − F (t))¤∞0+λ2Z∞0t2f(t)dt (9.2)We claimed that the first term in the RHS of equation 9.2 vanishes because the mean ofT = T2− T1(inter-arrival time) should be finite.This argument is not quite correct; show the correct argument that is:t2(1 − F (t)) → 0 as t → ∞ if and only if E[T2] < ∞.Solution:Thanks to all the student for being cautious/pessimistic in this exercise.t2(1 − F (t)) → 0 as t → ∞ if E[T2] < ∞.One counterexample is:F (t) = 0, t < 0, and F (t) = 1 −c(t + 1)2ln(t + 1), t ≥ 09-4EE226 Problem Set 9 — Due December, 7 Fall’06It is easy to verify that t2(1 − F (t)) → 0 as t → ∞ if E[T2] = ∞. If however E[T2] < ∞ wehavet2(1 − F (t)) = t2Z∞tf(s)ds=Z∞tt2f(s)ds≤Z∞ts2f(s)ds bcse t < sBut sinceR∞0s2f(s)ds < ∞limt→∞Z∞ts2f(s)ds = 0Exercise 9.8. Bonus FFConsidering again the renewal process setting given in class, show that if the inter-arrivaltimes are iid uniform in [0, 1], then ²-coupling occurs in finite time.Solution:To show this we will start two processes, one (Ns(t)) with the stationary distribution as initialdistribution, and the other (Nx(t)) with some