#+begin_exercise Use indicator variables to show that #+name: eq:12 \begin{equation} \E X = \sum_{i=0}^{\infty} i\P{X=i} = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \1{j < i} \P{X=i} =p/q. \end{equation} #+begin_solution \begin{align*} \E X &= \sum_{i=0}^{\infty} i\P{X=i} \\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \1{j < i} \P{X=i} \\ &= \sum_{j=0}^{\infty} \sum_{i=0}^{\infty} \1{j < i} \P{X=i} \\ &= \sum_{j=0}^{\infty} \sum_{i=j+1}^{\infty} \P{X=i} \\ &= \sum_{j=0}^{\infty} \P{X > j} \\ &= \sum_{j=0}^{\infty} q^{j+1}\\ &= q \sum_{j=0}^{\infty} q^{j}\\ &= q/(1-q) = q/p. \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Look up the definition of a memoryless rv, and check that \(X\) is memoryless. #+begin_solution \begin{align*} \P{X\geq n+m\given X\geq m} &= \frac{ \P{X\geq n+m, X\geq m}}{\P{X\geq m}} \\ &= \frac{ \P{X\geq n+m}}{\P{X\geq m}} \\ &= \frac{ q^{n+m}}{q^m} \\ &= q^n= \P{X\geq n}. \end{align*} #+end_solution #+end_exercise {{{newthought(With this refresher,)}}} we can derive some useful properties of the minimum \(L=\min\{X, Y\}\), where \(X, Y\sim \Geo{p}\) and \(X, Y\) independent. For this we use that \begin{equation*} \P{g(X,Y}\in A\} \stackrel1= \E{\1{g(X, Y) \in A}} \stackrel2= \sum_{i}\sum_j \1{g(i, j)\in A} \P{X=i, Y=j}. \end{equation*} Step 1 is known as /the fundamental bridge/ and step 2 as /2D LOTUS/. #+begin_exercise What is the domain of \(L\)? Then, show that \begin{equation*} \P{L\geq i}=q^{2i} \implies L\sim\Geo{1-q^{2}}. \end{equation*} #+begin_hint For 2D LOTUS, take \(g(i,j) = \min\{i, j\}\). #+end_hint #+begin_solution \begin{align*} \P{L\geq k} &= \sum_{i}\sum_{j} \1{\min\{i,j\}\geq k} \P{X=i, Y=j}\\ &= \sum_{i\geq k} \sum_{j\geq k} \P{X=i}\P{Y=j}\\ &= \P{X\geq k}\P{Y\geq k} = q^{k} q^{k} = q^{2k}. \end{align*} \(\P{L > i}\) has the same form as \(\P{X > i}\), but now with \(q^{2i}\) rather than \(q^{i}\). #+end_solution #+end_exercise #+html:

#+begin_exercise Show that #+name: eq:3 \begin{equation} \E L=q^{2}/(1-q^{2}). \end{equation} #+begin_hint \(X\sim \Geo{1-q} \implies \E X = q/(1-q)\). Now use that \(L\sim\Geo{1-q^{2}}\). #+end_hint #+begin_solution Immediate from the hint and [[eq:12]]. #+end_solution #+end_exercise #+html:

#+begin_exercise Show that #+name: eq:39 \begin{equation} \E L + \E X = \frac q{1-q}\frac{1+2q}{1+q}. \end{equation} #+begin_hint Use that \(1-q^2=(1-q)(1+q)\). #+end_hint #+begin_solution \begin{align*} \E L + \E X &= \frac{q^{2}}{1-q^2} + \frac{q}{1-q} \\ &= \frac q{1-q}\left(\frac{q}{1+q} + 1\right)\\ &= \frac q{1-q} \frac{1+2q}{1+q} \end{align*} #+end_solution #+end_exercise {{{newthought(Now we can)}}} combine these facts with the properties of the maximum \(M=\max\{X, Y\}\). #+begin_exercise Show that #+name: eq:10 \begin{equation} 2\E X -\E L = \frac q{1-q} \frac{2+q}{1+q}. \end{equation} #+begin_solution \begin{align*} 2\E X - \E L &= 2\frac q{1-q} - \frac{q^2}{1-q^2}\\ &= \frac q{1-q}\left(2 - \frac{q}{1+q}\right)\\ &= \frac q{1-q}\left(\frac{2+2q}{1+q} - \frac{q}{1+q}\right)\\ &= \frac q{1-q}\frac{2+q}{1+q}. \end{align*} #+end_solution #+end_exercise Clearly, unless \(q=0\), \(\E L + \E X \neq 2\E X - \E L\), hence, \(\E M\) can only be one of the two and [[eq:6]] and [[eq:7]] cannot be both true. To convince ourselves that [[eq:10]], hence [[eq:6]], is indeed true, we pursue three ideas. {{{newthought(Here is the first)}}} idea. #+name: ex:1 #+begin_exercise Show for the PMF of \(M\) that \begin{align*} p_M(k) &= \P{M=k} = 2 pq^{k}(1-q^{k}) + p^2q^{2k}. \end{align*} #+begin_hint Use 2D LOTUS on \(g(x,y) = \1{\max\{x, y\} = k}\). #+end_hint #+begin_solution \begin{align*} \P{M=k} &= \P{\max\{X, Y\} = k} \\ &=p^{2}\sum_{ij}\1{\max\{i,j\} =k} q^i q^j\\ &=2 p^{2}\sum_{ij}\1{i=k}\1{j < k} q^i q^j + p^{2}\sum_{ij}\1{i=j=k} q^{i} q^j \\ &=2 p^{2}q^{k}\sum_{j < k} q^j + p^{2}q^{2k}\\ &=2 p^{2}q^{k}\frac{1-q^{k}}{1-q} + p^{2}q^{2k}\\ \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise With the previous exercise, show now that \(p_M(k) =2 \P{X=k} - \P{L=k}\). #+begin_solution It's just algebra \begin{align*} \P{M=k} &=2 p^{2}q^{k}\frac{1-q^{k}}{1-q} + p^{2}q^{2k}\\ &=2 pq^{k}(1-q^{k}) + p^{2}q^{2k}\\ &=2 pq^{k} +(p^{2}-2p) q^{2k}\\ &=2 \P{X=k} - \P{L=k}, \end{align*} where I use that \(p^{2}-2p = p(p-2) = (1-q)(1-q-2)=-(1-q)(1+q)=-(1-q^{2})\). #+end_solution #+end_exercise #+html:

#+begin_exercise Finally, show that \(\E M = 2 \E X - \E L\). #+begin_hint #+end_hint #+begin_solution \begin{align*} \E M &= \sum_k k \P{M=k} \\ &= \sum_{k}k (2\P{X=k} - \P{L=k}) \\ &= 2 \E X - \E L. \end{align*} #+end_solution #+end_exercise {{{newthought(The second idea.)}}} #+begin_exercise First show that \(\P{M \leq k} = (1-q^{k+1})^{2}.\) #+begin_solution \begin{align*} \P{M\leq k} &= \P{X\leq k, Y\leq k} \\ &= \P{X\leq k}\P{Y\leq k} \\ &= (1-\P{X > k})(1-\P{Y > k}) \\ &= (1-q^{k+1})^{2}. \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Simplify \(\P{M=k} = \P{M\leq k} - \P{M\leq k-1}\) to see that \(p_M(k) = 2\P{X=k} - \P{L=k}\). #+begin_solution \begin{align*} \P{M=k} &= \P{M\leq k} - \P{M\leq k-1}\\ &= 1-2 q^{k+1} + q^{2k+2} - (1 - 2q^{k} + q^{2k})\\ &= 2 q^{k}(1-q) + q^{2k}(q^{2}-1) \\ &= 2 \P{X=k} - q^{2k}(1-q^{2}) \\ &= 2 \P{X=k} - \P{L=k}. \end{align*} #+end_solution #+end_exercise {{{newthought(And the third)}}} third idea. #+name: ex:2 #+begin_exercise Explain that \begin{equation*} \P{L=i, M=k} = 2p^{2}q^{i+k}\1{k > i}+ p^{2}q^{2i}\1{i=k}). \end{equation*} #+begin_solution \begin{align*} \P{L=i, M=k} &= 2\P{X=i, Y=k}\1{k > i} + \P{X=Y=i}\1{i=k} \\ &= 2p^{2}q^{i+k}\1{k > i}+ p^{2}q^{2i}\1{i=k}. \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Use [[ex:2]] and marginalization to compute the marginal PMF \(\P{M=k}\). #+begin_hint Marginalize out \(L\). #+end_hint #+begin_solution \begin{align*} \P{M=k} &= \sum_{i} \P{L=i, M=k} \\ &= \sum_{i} (2p^{2}q^{i+k}\1{k > i}+ p^{2}q^{2i}\1{i=k}) \\ &= 2p^2q^k\sum_{i=0}^{k-1} q^{i}+ p^{2}q^{2k} \\ &= 2pq^k (1-q^{k})+ p^{2}q^{2k} \\ &= 2pq^k + (p^{2}-2p) q^{2k}, \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Use [[ex:2]] to compute \(\P{L=i}\). #+begin_hint Marginalize out \(M\). #+end_hint #+begin_solution \begin{align*} \P{L=i} &= \sum_{k} \P{L=i, M=k} \\ &= \sum_{k} (2p^{2}q^{i+k}\1{k > i}+ p^{2}q^{2i}\1{i=k}) \\ &= 2p^2q^i\sum_{k=i+1}^{\infty} q^{k}+ p^{2}q^{2i} \\ &= 2p^{2}q^{2i+1} \sum_{k=0}^{\infty}q^{k}+ p^{2}q^{2i} \\ &= 2pq^{2i+1} + p^{2} q^{2i}\\ &= pq^{2i}(2q+p)\\ &= (1-q)q^{2i}(q + 1), \quad p+q=1,\\ &= (1-q^{2})q^{2i}. \end{align*} #+end_solution #+end_exercise {{{newthought(In conclusion,)}}} we verified the correctness of \(\E M = 2\E X - \E L\) in three different (useful) ways. Let us now focus on exponential rvs rather than geometric rvs. ** Continuous memoryless rvs <

#+begin_exercise Show that \(\E X = 1/\lambda\). #+begin_hint Use partial integration. #+end_hint #+begin_solution It is essential that you know both methods to solve this integral. \begin{align*} \E X &= \int_{0}^{\infty} x f_{X}(x) \d x \\ &= \int_{0}^{\infty} x \lambda e^{-\lambda x} \d x \\ &= - xe^{-\lambda x} \biggr|_{0}^{\infty} + \int_{0}^{\infty} e^{-\lambda x} \d x \\ &= - \frac 1 \lambda e^{-\lambda x} \biggr|_{0}^{\infty} = \frac 1 \lambda. \end{align*} Substitution is also a very important technique to solve such integrals. Here we go again: \begin{align*} \E X &= \int_{0}^{\infty} x f_{X}(x) \d x \\ &= \int_{0}^{\infty} x \lambda e^{-\lambda x} \d x \\ &= \frac 1 \lambda \int_{0}^{\infty} u e^{- u} \d u, \end{align*} by the substitution \(u=\lambda x \implies \d u = \d (\lambda x) \implies \d u = \lambda \d x \implies \d x = \d u / \lambda\). With partial integration (do it!), the integral evaluates to \(1\). #+end_solution #+end_exercise {{{newthought(Now we can)}}} shift our attention to the rvs \(L\) and \(M\). #+begin_exercise Show that \(F_L(x) = 1-e^{-2\lambda x}\). #+begin_hint Using independence and the specific property of the r.v. \(L\) that \(\{L > x\} \iff \{X > x, Y > x\}\): #+end_hint #+begin_solution With the hint, \begin{align*} G_L(x) = \P{L > x} &= \P{X > x, Y > x} = G_X(x)^{2} = e^{-2\lambda x}. \end{align*} The result follows since \(F_{L}(x) = 1-G_{L}(x)\). #+end_solution #+end_exercise Clearly, this implies that \(L\sim \Exp{2\lambda}\) and \(\E L = 1/(2\lambda) = \E X /2\). Hence, we see that [[eq:35]] holds now. Moreover, with the same trick we see that the distribution function \(F_{M}\) for the maximum \(M\) is given by \begin{equation*} F_{M}(v) = \P{M\leq v} = \P{X \leq v, Y \leq v} = (F_{X}(v))^{2} = (1-e^{-\lambda v})^{2}. \end{equation*} Of course this is a nice trick, but it is not a method that allows us to compute the distribution for more general functions of \(X\) and \(Y\). For more general cases, we have to use the fundamental bridge and LOTUS, that is, for any set[fn::If you like maths, you should be quite a bit more careful about what type of set \(A\) is acceptable. Here such matters are of no importance.] \(A\) in the domain of \(X \times Y\) \begin{equation*} \begin{split} \P{g(X, Y) \in A} &= \E{\1{g(X,Y)\in A}} = \iint \1{g(x,y) \in A} f_{X,Y}(x,y) \d x \d y \\ &= \iint_{g^{-1}(A)} f_{X,Y}(x, y) \d x \d y = \iint_{\{(x,y): g(x,y) \in A\}} f_{X,Y}(x,y) \d x \d y. \end{split} \end{equation*} The joint CDF \(F_{X,Y}\) then follows because \(F_{X,Y}(x,y) = \P{X\leq x, Y\leq y} = \E{\1{X\leq x, Y\leq y}}\). A warning is in place: conceptually this approach is easy, but doing the integration can be very challenging (or impossible). However, this expression is very important as this is the preferred way to compute distributions by numerical methods and simulation. #+begin_exercise Use the fundamental bridge to re-derive the above expression for \(F_M(v)\). #+begin_solution \begin{align*} \P{M\leq v} &= \E{\1{M\leq v}} \\ &=\int_0^{\infty} \int_0^{\infty} \1{x\leq v, y\leq v} f_{XY}(x,y) \d x \d y \\ &= \int_0^{\infty} \int_0^{\infty} \1{x\leq v, y\leq v} f_{X}(x) f_{Y}(y) \d x \d y \\ &= \int_0^{v} f_{X}(x) \d x \int_0^{v} f_{Y}(y) \d y \\ &= F_{X}(v) F_Y(v) = (F_X(v))^2. \end{align*} #+end_solution #+end_exercise #+name: ex:6 #+begin_exercise Show that the density of \(M\) has the form \(f_{M}(v)=\partial_{v} F_M(v) = 2(1-e^{-\lambda v}) \lambda e^{-\lambda v}\).[fn::We write \(\partial_{v}\) as a shorthand for \(\d/\d v\) in the 1D case, and for \(\partial/\partial_{v}\) the partial derivative in the 2D case.] #+begin_solution \begin{equation*} f_M(v) = F_M'(v) = 2 F_X(v) f_X(v) = 2(1-e^{-\lambda v}) \lambda e^{- \lambda v}. \end{equation*} #+end_solution #+end_exercise #+html:

#+begin_exercise Use the density \(f_{M}\) to show that \(\E M = 2\E X - \E L\). #+begin_solution \begin{align*} \E M &= \int_{0}^{\infty} v f_M(v) \d v = \\ &= 2 \lambda \int_{0}^{\infty} v (1-e^{-\lambda v}) e^{-\lambda v} \d v = \\ &= 2 \lambda \int_{0}^{\infty} v e^{-\lambda v} \d v - 2 \lambda \int_{0}^{\infty} v e^{-2 \lambda v} \d v \\ &= 2 \E X - \E L, \end{align*} where the last equality follows from the previous exercises. #+end_solution #+end_exercise Recalling that we already obtained \(\E L = \E X/ 2\), we see that \(\E M = 2 \E X - \E L = 3\E X/2\), which settles the truth of [[eq:35]]. {{{newthought(We can also)}}} compute the densities \(f_{M}(y)\) (and \(f_{L}(x)\) by marginalizing the joint density \(f_{L,M}(x,y)\). However, for this, we first need the joint distribution \(F_{L,M}\), and then we can get \(f_{L,M}\) by differentiation, i.e., \(f_{X,Y} = \partial_{x}\partial_y F_{X,Y}\). Let us try this approach too. #+begin_exercise Use the fundamental bridge to show that for \(u\leq v\), \begin{equation*} F_{L,M}(u,v) = \P{L\leq u, M\leq v} = 2\int_0^u (F_Y(v)- F_Y(x)) f_X(x) \d x. \end{equation*} #+begin_solution First the joint distribution. With \(u\leq v\), \begin{align*} F_{L,M}(u,v) &= \P{L\leq u, M \leq v} \\ &= 2\iint \1{x \leq u, y\leq v, x\leq y} f_{X,Y}(x,y)\d x \d y \\ &= 2\int_0^u \int_x^v f_Y(y) \d y f_X(x) \d x & \text{independence} \\ &= 2\int_0^u (F_Y(v)- F_Y(x)) f_X(x) \d x. \end{align*} #+end_solution #+end_exercise #+name: ex:25 #+begin_exercise Take partial derivatives to show that \begin{equation*} f_{L,M}(u,v) = 2f_X(u) f_Y(v)\1{u\leq v}. \end{equation*} #+begin_solution Taking partial derivatives, \begin{align*} f_{L,M}(u,v) &=\partial_v\partial_{u}F_{L,M}(u,v) \\ &=2 \partial_v\partial_{u} \int_0^u (F_Y(v)- F_Y(x)) f_X(x) \d x \\ &=2 \partial_v \left\{(F_Y(v)- F_Y(u)) f_X(u) \right \} \\ &=2 f_X(u)\partial_v F_Y(v) \\ &=2 f_X(u)f_Y(v). \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise In [[ex:25]] marginalize out \(L\) to find \(f_M\), and marginalize out \(M\) to find \(f_L\). #+begin_solution \begin{align*} f_M(v) &= \int_0^{\infty} f_{L,M}(u,v) \d u \\ &= 2 \int_0^{v} f_{X}(u) f_Y(v) \d u \\ &= 2 f_Y(v) \int_0^{v} f_{X}(u) \d u \\ &= 2f_Y(v) F_X(v), \\ f_L(u) &= \int_0^{\infty} f_{L,M}(u,v) \d v \\ &= 2 f_{X}(u) \int_u^{\infty} f_Y(v) \d v \\ &= 2 f_{X}(u) G_{Y}(u). \end{align*} #+end_solution #+end_exercise {{{newthought(We did a)}}} number of checks for the case \(X, Y, \iid, \sim\Exp{\lambda}\), but I have a second way to check the consistency of our results. For this I use the idea that the geometric distribution is the discrete analog of the exponential distribution. Now we study how this works, and that by taking proper limits we can obtain the results for the continuous setting from the discrete setting. First, let's try to obtain an intuitive understanding of how \(X\sim \Geo{\lambda/n}\) approaches \(Y\sim\Exp{\lambda}\) as \(n\to\infty\). For this, divide the interval \([0, \infty)\) into many small intervals of length \(1/n\). Let \(X\sim \Geo{\lambda/n}\) for some \(\lambda > 0\) and \(n\gg 0\). Then take some \(x\geq 0\) and let \(i\) be such that \(x\in[i/n, (i+1)/n)\). #+begin_exercise Show that #+name: eq:53 \begin{equation} \P{X/n \approx x} \approx \frac{\lambda} n \left(1-\frac \lambda n\right)^{x n}. \end{equation} #+begin_solution First, \begin{align*} \P{X/n \approx x} &= \P{X/n \in [i/n, (i+1)/n]} = \P{X \in [i, i+1]} = p q^{i} \\ &\approx p q^{n x} = \frac{\lambda} n \left(1-\frac \lambda n\right)^{xn}, \end{align*} since \(p=\lambda/n\), \(q=1-p=1-\lambda/n\), and \(i=nx\). #+end_solution #+end_exercise Next, introduce the highly intuitive notation[fn::In your math classes you learned that \(\lim_{n\to \infty} 1/n = 0\). Doesn't this definition therefore imply that \(\d x = 0\)? Well, no, because \(\d x\) is not a real number but an infinitesimal. Infinitesimals allow us to consider a quantity that is so small that it cannot be distinguished from 0 within the real numbers.] \(\d x = \lim_{n\to \infty} 1/n\), and use the standard limit[fn::This is not entirely trivial to prove. If you like mathematics, check the neat proof in Rudin's Principles of mathematical analysis.] \((1-\lambda/n)^n\to e^{-\lambda}\) as \(n\to\infty\) to see that [[eq:53]] converges to \begin{equation*} \P{X/n \approx x} \to \lambda e^{-\lambda x} \d x = f_{X}(x) \d x,\quad\text{ as } n \to \infty. \end{equation*} # In fact, working with infinitesimals such as \(\d x\) is one of my favorite methods, for instance to derive densities. # The intuition is that \(\d x\) is some really small number but not zero. # In a tiny bit more formal words, \(0<\d x < 1/n\) for any \(n\), but \(\d x \neq 0\). # For details, check out the web; search on `nonstandard calculus'. # However, while the method is very intuitive, it's easy to mess up. (Power tools are nice, but often only when you know how to handle them and practice a lot.) # If you don't want to learn this, no problem, it will not be part of the course proper. If you don't like this trick with \(\d x\), here is another method, based on moment-generating functions. #+begin_exercise Derive the moment-generating function \(M_{X/n}(s)\) of \(X/n\) when \(X\sim \Geo{p}\). Then, let \(p = \lambda/n\), and show that \(\lim_{n\to\infty}M_{X/n}(s) = M_{Y}(s)\), where \(Y \sim \Exp{\lambda}\). #+begin_hint If you recall the Poisson distribution, you know that \(e^{\lambda} = \sum_{i=0}^{\infty}\lambda^{i}/i!\). In fact, this is precisely Taylor's expansion of \(e^{\lambda}\). #+end_hint #+begin_solution \begin{align*} M_{X/n}(s) &= \E{e^{s X/n}} = \sum_{i} e^{s i/n} p q^{i} = p\sum_{i} (qe^{s/n})^{i} = \frac{p}{1-qe^{s/n}}. \end{align*} With \(p=\lambda/n\) this becomes \begin{align*} M_{X/n}(s) &= \frac{\lambda/n}{1-(1-\lambda/n) (1+s/n + 1/n^{2}\times(\cdots))} \\ &= \frac{\lambda/n}{\lambda/n - s/n + 1/n^{2}\times (\cdots)} \\ &= \frac{\lambda}{\lambda - s + 1/n\times(\cdots)} \\ &\to \frac{\lambda}{\lambda - s}, \quad\text{as } n\to \infty, \end{align*} where we write \(1/n^{2}\times(\cdots)\) for all terms that will disappear when we take the limit \(n\to \infty\). This is just handy notation to hide details in which we are not interested. #+end_solution #+end_exercise With these limits in place, we can relate the minimum \(L=\min\{X, Y\}\) for the discrete and the continuous settings. #+begin_exercise Suppose that \(X, Y\sim \Geo{\lambda/n}\), then check that \(\lim_{n\to\infty}\E{L/n} = 1/2\lambda\). #+begin_hint Use [[eq:3]]. #+end_hint #+begin_solution \begin{align*} \E{L/n} &= \frac 1 n \E L = \frac 1 n \frac{q^2}{1-q^{2}} \\ &= \frac 1 n \frac{(1-\lambda/n)^2}{1-(1-\lambda/n)^{2}} \\ &= \frac 1 n \frac{1-2 \lambda/n + (\lambda/n)^2}{2 \lambda /n + (\lambda/n)^{2}} \\ &= \frac{1-2 \lambda/n + (\lambda/n)^2}{2 \lambda + \lambda^{2}/n} \\ &\to \frac 1{2\lambda}. \end{align*} #+end_solution #+end_exercise Clearly, \(1/2\lambda=\E X/2\) when \(X\sim\Exp{\lambda}\). Here is yet another check on the correctness of \(f_M(x)\). #+begin_exercise Show that the PMF \(\P{M=k}\) for the discrete \(M\) in [[ex:1]] converges to \(f_M(x)\) of [[ex:6]] when \(n\to \infty\). Take \(k\) suitable. #+begin_solution Take \(p=\lambda/n\), \(q=1-\lambda/n\), and \(k \approx x n\), hence \(k/n \approx x\). Then, \begin{align*} \P{M/n=k/n} &= 2 p q^{k/n}(1-q^{k/n}) + p^2q^{2k/n} \\ &= 2 \frac \lambda n \left(1-\frac \lambda n\right)^{k/n}\left(1-\left(1-\frac \lambda n\right)^{k/n}\right) + \frac{\lambda^2}{n^2}\left(1-\frac \lambda n \right)^{2k/n} \\ &\to 2 \lambda \d x e^{-\lambda x} \left(1 - e^{-\lambda x}\right) + \lambda^{2} \d x^{2}e^{-2\lambda}. \end{align*} Now observe that the second term, proportional to \(\d x^{2}\) can be neglected. #+end_solution #+end_exercise {{{newthought(Finally, I have)}}} a third way to check the above results, namely by verifying [[eq:7]], i.e. \(\E{M-L} = \E X\). For this, we compute the joint CDF \(f_{L, M-L}(x, y)\). With this, you'll see directly how to compute \(\E{M-L}\). #+name: ex:27 #+begin_exercise Use the fundamental bridge to obtain \begin{equation*} F_{L,M-L}(x,y) = (1- e^{-2\lambda x}) (1-e^{-\lambda y}) = F_L(x) F_Y(y). \end{equation*} #+begin_hint The idea is not difficult, but the technical details require attention, in particular the limits in the integrations. #+end_hint #+begin_solution \begin{align*} F_{L, M-L}(x, y) &=\P{L\leq x, M-L\leq y}\\ &= 2\P{X\leq x, Y-X \leq y, X \leq Y} \\ &= 2\int_0^{\infty} \int_0^{\infty} \1{u\leq x, v-u\leq y, u \leq v} f_{X,Y}(u, v) \d u \d v\\ &= 2\int_0^{\infty} \int_0^{\infty} \1{u\leq x, v-u\leq y, u\leq v} \lambda^2e^{-\lambda u}e^{-\lambda v}\d u \d v\\ &= 2\int_0^{x} \int_0^{\infty} \1{u\leq v\leq u+y} \lambda^2e^{-\lambda u}e^{-\lambda v}\d v \d u\\ &= 2\int_0^{x} \lambda e^{-\lambda u} \int_u ^{u + y} \lambda e^{-\lambda v}\d v \d u\\ &= 2\int_0^{x} \lambda e^{-\lambda u} (-e^{-\lambda v}) \biggr|_u^{u+y}\d u \\ &= 2\int_0^{x} \lambda e^{-\lambda u} (e^{-\lambda u} - e^{-\lambda (u+y)})\d u \\ &= 2\lambda\int_0^{x} e^{-2 \lambda u}\d u - 2\lambda \int_{0}^{x} e^{-\lambda (2u+y)}\d u \\ &= 2\lambda\int_0^{x} e^{-2 \lambda u}\d u - 2\lambda e^{-\lambda y }\int_{0}^{x} e^{-2 \lambda u}\d u \\ &= (1-e^{-\lambda y}) 2 \lambda \int_0^{x} e^{-2 \lambda u} \d u\\ &= (1-e^{-\lambda y}) ( -e^{-2\lambda u}) \biggr|_0^{x} \\ &= (1-e^{-\lambda y})(1- e^{-2\lambda x}). \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Conclude that \(M-L\) and \(L\) are independent, and \(M-L\sim Y\). #+begin_solution As \(F_{L,M-L}(x,y) = F_Y(y) F_L(x)\). So the CDF factors as a function of \(x\) only and a function of \(y\) only. This implies that \(L\) and \(M-L\) are independent, and moreover that \(F_{M-L}(y) = F_Y(y)\), so \(M-L \sim Y\). We can also see this from the joint PDF: \begin{equation*} f_{L, M-L}(x,y) = \partial_x \partial_y (F_Y(y) F_L(x)) = f_Y(y) f_L(x), \end{equation*} so the joint PDF (of course) also factors. The independence now follows from BH 7.1.21. #but it is also okay to conclude it directly from the CDF factoring as a function of \(x\) only and a function of \(y\) only. Because \(L\) and \(M-L\) are independent, the conditional density equals the marginal density: \begin{equation*} f_{M-L|L}(y|x) = \frac{f_{L, M-L}(x, y)}{f_L(x)} = \frac{f_Y(y) f_L(x)}{f_L(x)} = f_Y(y). \end{equation*} #+end_solution #+end_exercise By the above exercise, we find that \(\E{M-L} = \E Y = \E X\), as \(X\) and \(Y\) are iid. {{{newthought(This makes me)}}} wonder whether \(M-L\) and \(L\) are also independent for the discrete case, i.e., when \(X, Y\) iid and \(\sim \Geo{p}\). Hence, we should check that for /all/ \(i, j\) #+name: eq:34 \begin{equation} \P{L=i, M-L=j} = \P{L=i} \P{M-L=j}. \end{equation} #+begin_exercise Use [[ex:2]] to see that \begin{equation*} \P{L=i, M-L=j} = 2p^2q^{2i+j} \1{j\geq 1} + p^2q^{2i}\1{j=0}. \end{equation*} #+begin_hint Realize that \(\P{L=i, M-L=j}= \P{L=i, M=i+j}\). Now fill in the formula of [[ex:2]]. #+end_hint #+end_exercise Now for the RHS. #+begin_exercise Derive that \begin{equation*} \P{M-L=j} = \frac{2p^2q^{j}}{1-q^2}\1{j\geq 1} + \frac{p^2q^{j}}{1-q^2}\1{j=0}. \end{equation*} #+begin_solution Suppose \(j > 0\) (for \(j=0\) the maths is the same). Then, \begin{align*} \P{M-L=j} &=2\sum_{i=0}^{\infty}\P{X =i, Y=i+j } = &=2\sum_{i=0}^{\infty}p q^i pq^{i+j} = &=2p^{2}q^{j}\sum_{i=0}^{\infty}q^{2i} = &=2p^{2}q^{j}/(1-q^2). \end{align*} #+end_solution #+end_exercise Recalling that \(\P{L=i} = (1-q^2)q^{2i}\), it follows right away from [[eq:34]] that \(L\) and \(M-L\) are independent. Interestingly, from [[ex:27]] we see \(M-L\sim Y\) for the continuous case. However, here, for the geometric case, \(\P{M-L=j} \neq pq^{j} = \P{Y=j}\). This explains why \(\E M \neq \E L + \E X\) for geometric rvs: we should be more careful in how to split \(M\) in terms of \(L\) and \(X\). {{{newthought(All in all)}}}, we have checked and double checked all our expressions and limits for the geometric and exponential distribution. We had success too: the solution of the last exercise provides the key to understand why [[eq:6]] and [[eq:7]] are true for exponentially distributed rvs, but not for geometric random variables. In fact, in the solutions we can see the term corresponding to \(X=Y=i\) for \(X,Y\sim \Geo{p}\) becomes negligibly small when \(n\to 0\). In other words, \(\P{X=Y}>0\) when \(X\) and \(Y\) are discrete, but \(\P{X=Y}=0\) when \(X\) and \(Y\) are continuous. Moreover, by [[ex:27]], \(\E M = \E{L + M-L} = \E L + \E{M-L}\), but \(\E{M-L} \neq \E X\). So, to resolve our leading problem we should reconsider \(\E{M-L}\). ** The solution <

#+begin_exercise Show that #+name: eq:41 \begin{equation} 2\E{(Y-X) \1{Y > X}} = \frac{2q} {1-q^{2}}. \end{equation} #+begin_hint Reread BH.7.2.2. to realize that \(\E{M-L} = \E{|X-Y|}\). Relate the latter expectation to the expression in the problem. #+end_hint #+begin_solution \begin{align*} \E{(Y-X) \1{Y > X}} &= p^2\sum_{ij} (j-i)\1{j > i} q^iq^j\\ &= p^2\sum_{i} q^i\sum_{j=i+1}^{\infty}(j-i)q^j\\ &= p^2\sum_{i} q^i q^{i}\sum_{k=1}^{\infty}kq^k, \quad k = j-i\\ &= p\sum_{i} q^{2i}\E X \\ &= \frac{p}{1-q^{2}}\E X \\ &= \frac{p}{1-q^{2}}\frac q p \\ &= \frac{q}{1-q^{2}}. \end{align*} #+end_solution #+end_exercise #+html:

#+begin_exercise Combine the above with the expression for \(\E L\) of [[eq:3]] to obtain [[eq:10]] for \(\E M = 2\E X - \E L\), thereby verifying the correctness of [[eq:40]]. #+begin_solution \begin{align*} \E L + 2 \E{(Y-X) \1{Y > X}} = \frac{q^{2}}{1-q^2} + \frac{2q}{1-q^{2}} = \frac q{1-q}\frac{q+2}{1+q}, \end{align*} where I use that \(1-q^{2}=(1-q)(1+q)\). #+end_solution #+end_exercise While [[eq:40]] is correct, I am still not happy with the second part of [[eq:40]] as I find it hard/unintuitive to interpret. Restarting again from scratch, here is another attempt to rewrite \(\E M\) by using \(Z\sim \FS{p}\), i.e., \(Z\) has the first success distribution with parameter \(p\), in other words, \(Z \sim X+1\) with \(X\sim\Geo{p}\). #+begin_exercise Explain that #+name: eq:44 \begin{equation} \E M = \E L + \E{ Z \1{M > L}}, \end{equation} #+begin_solution To see why this might be true, I reason like this. After `seeing' \(L\), we want to restart. Let \(Z\) be the time from the restart to \(M\). When \(Z\sim \Geo{p}\), it might happen that \(Z=0\) (with positive probability \(p\)). But if \(Z=0\), then \(M=L\), and it that case, we should not restart. Hence, if \(Z\sim \Geo{p}\) we are `double counting' when \(Z=0\). By including the condition \(M > L\) and by taking \(Z\sim\FS{p}\) (so that \(Z > 0\)) I can prevent this. #+end_solution #+end_exercise #+html:

#+begin_exercise Show that \begin{equation*} \E{Z\1{M > L}} = \frac{2q} {1-q^{2}}, \end{equation*} i.e., the same as [[eq:41]], hence [[eq:44]] is correct. #+begin_hint Observe that \(Z\) is independent from \(X\) and \(Y\), hence from \(M\) and \(L\) #+end_hint #+begin_solution With the hint: \begin{align*} \E{Z\1{M > L}} = \E Z \E{\1{M > L}} = \E Z \P{M > L} = \frac 1 p \frac{2pq}{1-q^{2}} = \frac{2q}{1-q^{2}}, \end{align*} We know that \(\E Z = 1 + \E X = 1 + q/p = 1/p\), while \begin{align*} \P{M > L} &= 1-\P{X=Y} = 1-\sum_{i=0}^{\infty} \P{X=Y=i} \\ &= 1-\frac{p^{2}}{1-q^{2}} = \frac{1 - q^{2} + p^{2}}{1-q^{2}} = \frac{2pq}{1-q^{2}}. \end{align*} #+end_solution #+end_exercise {{{newthought(I am nearly)}}} happy, but I want to see that [[eq:44]], which is correct for discrete rvs, has also the correct limiting behavior. #+begin_exercise Show that \(\E{Z/n\1{M > L}} \to 1/\lambda\), which is the expectation of an \(\Exp{\lambda}\) rv! #+begin_solution By independence, \begin{equation*} \E{Z/n\1{M > L}} = \E{Z/n} \P{M > L}. \end{equation*} Then, \begin{equation*} \P{M > L} = \frac{2pq}{1-q^{2}} = \frac{2\lambda/n (1-\lambda/n)}{1-(1-\lambda/n)^{2}} = \frac{2\lambda/n (1-\lambda/n)}{2\lambda/n -\lambda^{2}/n^{2}} = \frac{2 (1-\lambda/n)}{2 -\lambda/n} \to 1, \end{equation*} and \begin{equation*} \E{Z/n} = \frac 1 n \E Z = \frac 1 n \frac 1 p = \frac 1 {n \lambda/ n} = 1/\lambda. \end{equation*} #+end_solution #+end_exercise Finally I understand why \(\E M = \E L + \E X\) for \(X,Y\sim \Exp{\lambda}\) and why this is not true for discrete \(X, Y\). For discrete rvs, \(L\) and \(M\) can be equal, while for continuous rvs, this is impossible[fn::A bit more carefully formulated: the event \(\{L=M\}\) has zero probability for continuous rvs.] It took a long time, and a lot of work, to understand how to resolve the confusing problem, but I learned a lot. In particular, I find [[eq:44]] a nice and revealing equation. Finally, if you like to train with the tools you learned, you can try your hand at analyzing the same problem, but now for uniform \(X, Y\).