1.8: Exercises

Exercise 1.1

Consider a sequence \(A_{1}, A_{2}, \ldots\) of events each of which have probability zero.

1. Find \(\operatorname{Pr}\left\{\sum_{n=1}^{m} A_{n}\right\}\) and find \(\lim _{m \rightarrow \infty} \operatorname{Pr}\left\{\sum_{n=1}^{m} A_{n}\right\}\). What you have done is to show that the sum of a countably infinite set of numbers each equal to 0 is perfectly well defined as 0.
2. For a sequence of possible phases, \(a_{1}, a_{2}, \ldots\) between 0 and \(2 \pi\), and a sequence of singleton events, \(A_{n}=\left\{a_{n}\right\}\), find \(\operatorname{Pr}\left\{\bigcup_{n} A_{n}\right\}\) assuming that the phase is uniformly distributed.
3. Now let \(A_{n}\) be the empty event \(\phi\) for all \(n\). Use \ref{1.1} to show that \(\operatorname{Pr}\{\phi\}=0\).

Answer

Exercise 1.2

Let \(A_{1}\) and \(A_{2}\) be arbitrary events and show that \(\operatorname{Pr}\left\{A_{1} \cup A_{2}\right\}+\operatorname{Pr}\left\{A_{1} A_{2}\right\}=\operatorname{Pr}\{A_1\}+\operatorname{Pr}\{A_2\}\). Explain which parts of the sample space are being double counted on both sides of this equation and which parts are being counted once.

Answer

Exercise 1.3

Let \(A_{1}, A_{2}, \ldots\), be a sequence of disjoint events and assume that \(\operatorname{Pr}\left\{A_{n}\right\}=2^{-n-1}\) for each \(n \geq 1\). Assume also that \(\Omega=\bigcup_{n=1}^{\infty} A_{n}\).

1. Show that these assumptions violate the axioms of probability.
2. Show that if \ref{1.3} is substituted for the third of those axioms, then the above assumptions satisfy the axioms.

This shows that the countable additivity of Axiom 3 says something more than the finite additivity of (1.3).

Answer

Exercise 1.4

This exercise derives the probability of an arbitrary (non-disjoint) union of events, derives the union bound, and derives some useful limit expressions.

1. For 2 arbitrary events \(A_{1}\) and \(A_{2}\), show that

   \(A_{1} \bigcup A_{2}=A_{1} \bigcup\left(A_{2}-A_{1}\right) \quad \text { where } A_{2}-A_{1}=A_{2} A_{1}^{c}\)

   Show that \(A_{1}\) and \(A_{2}-A_{1}\) are disjoint Hint: This is what Venn diagrams were invented for.

2. For an arbitrary sequence of events, \(\left\{A_{n} ; n \geq 1\right\}\), let \(B_{1}=A_{1}\) and for each \(n \geq 2\) define \(B_{n}=A_{n}-\bigcup_{j=1}^{n-1} A_{j}\). Show that \(B_{1}, B_{2}, \ldots\), are disjoint events and show that for each \(m \geq 2\), \(\bigcup_{n=1}^{m} A_{n}=\bigcup_{n=1}^{n} B_{n}\). Hint: Use induction.
3. Show that

   \(\operatorname{Pr}\left\{\bigcup_{n=1}^{\infty} A_{n}\right\}^{\}}=\operatorname{Pr}\left\{\bigcup_{n=1}^{\infty} B_{n}\right\}^{\}}=\sum_{n=1}^{\infty} \operatorname{Pr}\left\{B_{n}\right\}\)

   Hint: Use the axioms of probability for the second equality.

4. Show that for each \(n\), \(\operatorname{Pr}\left\{B_{n}\right\} \leq \operatorname{Pr}\left\{A_{n}\right\}\). Use this to show that

   \(\operatorname{Pr}\left\{\bigcup_{n=1}^{\infty} A_{n}\right\}^{\}} \leq \sum_{n=1}^{\infty} \operatorname{Pr}\left\{A_{n}\right\}\)

5. Show that \(\operatorname{Pr}\left\{\bigcup_{n=1}^{\infty} A_{n}\right\}=\lim _{m \rightarrow \infty} \operatorname{Pr}\left\{\bigcup_{n=1}^{m} A_{n}\right\}\). Hint: Combine parts c) and b).. Note that this says that the probability of a limit of unions is equal to the limit of the probabilities. This might well appear to be obvious without a proof, but you will see situations later where similar appearing interchanges cannot be made.
6. Show that \(\operatorname{Pr}\left\{\bigcap_{n=1}^{\infty} A_{n}\right\}=\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{\bigcap_{i=1}^{n} A_{i}\right\}\). Hint: Remember deMorgan’s equali­ties.

Answer

Exercise 1.5

Consider a sample space of 8 equiprobable sample points and let \(A_{1}, A_{2}, A_{3}\) be three events each of probability 1/2 such that \(\operatorname{Pr}\left\{A_{1} A_{2} A_{3}\right\}=\operatorname{Pr}\left\{A_{1}\right\} \operatorname{Pr}\left\{A_{2}\right\} \operatorname{Pr}\left\{A_{3}\right\}\).

1. Create an example where \(\operatorname{Pr}\left\{A_{1} A_{2}\right\}=\operatorname{Pr}\left\{A_{1} A_{3}\right\}=\frac{1}{4}\) but \(\operatorname{Pr}\left\{A_{2} A_{3}\right\}=\frac{1}{8}\). Hint: Make a table with a row for each sample point and a column for each event and try different ways of assigning sample points to events (the answer is not unique).
2. Show that, for your example, \(A_{2}\) and \(A_{3}\) are not independent. Note that the definition of statistical independence would be very strange if it allowed \(A_{1}, A_{2}, A_{3}\) to be independent while \(A_{2}\) and \(A_{3}\) are dependent. This illustrates why the definition of independence requires \ref{1.13} rather than just (1.14).

Answer

Exercise 1.6

Suppose \(X\) and \(Y\) are discrete rv’s with the PMF \(\mathrm{p}_{X Y}\left(x_{i}, y_{j}\right)\). Show (a picture will help) that this is related to the joint distribution function by

\(\mathrm{p}_{X Y}\left(x_{i}, y_{j}\right)=\lim _{\delta>0, \delta \rightarrow 0}\left[\mathrm{~F}\left(x_{i}, y_{j}\right)-\mathrm{F}\left(x_{i}-\delta, y_{j}\right)-\mathrm{F}\left(x_{i}, y_{j}-\delta\right)+\mathrm{F}\left(x_{i}-\delta, y_{j}-\delta\right)\right]\)

Answer

Exercise 1.7

A variation of Example 1.3.2 is to let \(M\) be a random variable that takes on both positive and negative values with the PMF

\(\mathrm{p}_{M}(m)=\frac{1}{2|m|(|m|+1)}\)

In other words, \(M\) is symmetric around 0 and \(|M|\) has the same PMF as the nonnegative rv \(N\) of Example 1.3.2.

1. Show that \(\sum_{m \geq 0} m \mathrm{p}_{M}(m)=\infty\) and \(\sum_{m<0} m \mathrm{p}_{M}(m)=-\infty\). (Thus show that the expectation of \(M\) not only does not exist but is undefined even in the extended real number system.)
2. Suppose that the terms in \(\sum_{m=-\infty}^{\infty} m \mathrm{p}_{M}(m)\) are summed in the order of 2 positive terms for each negative term (i.e., in the order 1, 2, 1, 3, 4, 2, 5, ...). Find the limiting value of the partial sums in this series. Hint: You may find it helpful to know that

   \(\lim _{n \rightarrow \infty}\left[\sum_{i=1}^{n} \frac{1}{i}-\int_{1}^{\}n} \frac{1}{x} d x\right]^\}=\gamma,\)

   where \(\gamma\) is the Euler-Mascheroni constant, \(\gamma=0.57721 \cdots\).

3. Repeat part b) where, for any given integer \(k>0\), the order of summation is \(k\) positive terms for each negative term.

Answer

Exercise 1.8

1. For any given rv \(Y\), express \(\mathrm{E}[|Y|]\) in terms of \(\int_{y<0} \mathrm{~F}_{Y}(y) d y\) and \(\int_{y \geq 0} \mathrm{~F}_{Y}^{\mathrm{c}}(y) d y\).
2. Show that \(\mathrm{E}[|Y-\alpha|]\) is minimized by setting \(\alpha\) equal to the median of \(Y\) (i.e., the value of \(Y\) for which \(\mathrm{F}_{Y}(y)=1 / 2\)). Hint: Use a graphical argument.

Answer

Exercise 1.9

Let \(X\) be a rv with distribution function \(\mathrm{F}_{X}(x)\). Find the distribution function of the following rv’s.

1. The maximum of \(n\) IID rv’s, each with distribution function \(\mathrm{F}_{X}(x)\).
2. The minimum of \(n\) IID rv’s, each with distribution \(\mathrm{F}_{X}(x)\).
3. The difference of the rv’s defined in a) and b); assume \(X\) has a density \(\mathrm{f}_{X}(x)\).

Answer

Exercise 1.10

Let \(X\) and \(Y\) be rv’s in some sample space \(\Omega\) and let \(Z=X+Y\), i.e., for each \(\omega \in \Omega, Z(\omega)=X(\omega)+Y(\omega)\).

1. Show that the set of \(\omega\) for which \(Z(\omega)=\pm \infty\) has probability 0.
2. To show that \(Z=X+Y\) is a rv, we must show that for each real number \(\alpha\), the set \(\{\omega \in \omega:X(\omega)+Y(\omega)\leq\alpha\}\) is an event. We proceed indirectly. For an arbitrary positive integer \(n\) and an arbitrary integer \(k\), let \(B(n, k)=\{\omega: X(\omega) \leq k \alpha / n\} \cap\{Y(\omega) \leq(n+1-k) \alpha / n\}\). Let \(D(n)=\bigcup_{k} B(n, k)\) and show that \(D(n)\) is an event.
3. On a 2 dimensional sketch for a given \(\alpha\), show the values of \(X(\omega)\) and \(Y(\omega)\) for which \(\omega \in D(n)\). Hint: This set of values should be bounded by a staircase function.
4. Show that

   \(\{\omega: X(\omega)+Y(\omega) \leq \alpha\}=\bigcap_{n} B(n)\)

   Explain why this shows that \(Z=X+Y\) is a rv.

Answer

Exercise 1.11

1. Let \(X_{1}, X_{2}, \ldots, X_{n}\) be rv’s with expected values \(\bar{X}_{1}, \ldots, \bar{X}_{n}\). Show that \(\mathrm{E}\left[X_{1}+\cdots+X_{n}\right]=\bar{X}_{1}+\cdots+\bar{X}_{n}\). You may assume that the rv’s have a joint density function, but do not assume that the rv’s are independent.
2. Now assume that \(X_{1}, \ldots, X_{n}\) are statistically independent and show that the expected value of the product is equal to the product of the expected values.
3. Again assuming that \(X_{1}, \ldots, X_{n}\) are statistically independent, show that the variance of the sum is equal to the sum of the variances.

Answer

Exercise 1.12

(Stieltjes integration)

1. Let \(h(x)=u(x)\) and \(\mathrm{F}_{X}(x)=u(x)\) where \(u(x)\) is the unit step, i.e., \(u(x)=0\) for \(-\infty<x<0\) and \(u(x)=1\) for \(x \geq 0\). Using the definition of the Stieltjes integral in Footnote 22, show that \(\int_{-1}^{1} h(x) d \mathrm{~F}_{X}(x)\) does not exist. Hint: Look at the term in the Riemann sum including \(x=0\) and look at the range of choices for \(h(x)\) in that interval. Intuitively, it might help initially to view \(d \mathrm{~F}_{X}(x)\) as a unit impulse at \(x=0\).
2. Let \(h(x)=u(x-a)\) and \(\mathrm{F}_{X}(x)=u(x-b)\) where \(a\) and \(b\) are in (1, +1). Show that \(\int_{-1}^{1} h(x) d \mathrm{~F}_{X}(x)\) exists if and only if \(a \neq b\). Show that the integral has the value 1 for a < b and the value 0 for a > b. Argue that this result is still valid in the limit of integration over \((-\infty, \infty)\).
3. Let \(X\) and \(Y\) be independent discrete rv’s, each with a finite set of possible values. Show that \(\int_{-\infty}^{\infty} \mathrm{F}_{X}(z-y) d \mathrm{~F}_{Y}(y)\), defined as a Stieltjes integral, is equal to the distribution of \(Z=X+Y\) at each \(z\) other than the possible sample values of \(Z\), and is undefined at each sample value of \(Z\). Hint: Express \(\mathrm{F}_{X}\) and \(\mathrm{F}_{Y}\) as sums of unit steps. Note: This failure of Stieltjes integration is not a serious problem; \(\mathrm{F}_{Z}(z)\) is a step function, and the integral is undefined at its points of discontinuity. We automatically define \(\mathrm{F}_{Z}(z)\) at those step values so that \(\mathrm{F}_{Z}\) is a distribution function (i.e., is continuous from the right). This problem does not arise if either \(X\) or \(Y\) is continuous.

Answer

Exercise 1.13

Let \(X_{1}, X_{2}, \ldots, X_{n}, \ldots\) be a sequence of IID continuous rv’s with the common probability density function \(\mathrm{f}_{X}(x)\); note that \(\operatorname{Pr}\{X=\alpha\}=0\) for all \(\alpha\) and that \(\operatorname{Pr}\left\{X_{i}=X_{j}\right\}=0\) for all \(i \neq j\). For \(n \geq 2\), define \(X_{n}\) as a record-to-date of the sequence if \(X_{n}>X_{i}\) for all \(i<n\).

1. Find the probability that \(X_{2}\) is a record-to-date. Use symmetry to obtain a numerical answer without computation. A one or two line explanation should be adequate.
2. Find the probability that \(X_{n}\) is a record-to-date, as a function of \(n \geq 1\). Again use symmetry.
3. Find a simple expression for the expected number of records-to-date that occur over the first \(m\) trials for any given integer \(m\). Hint: Use indicator functions. Show that this expected number is infinite in the limit \(m \rightarrow \infty\).

Answer

Exercise 1.14

(Countinuatiton of Exercise 1.13)

1. Let \(N_{1}\) be the index of the first record-to-date in the sequence. Find \(\operatorname{Pr}\left\{N_{1}>n\right\}\) for each \(n \geq 2\). Hint: There is a far simpler way to do this than working from part b) in Exercise 1.13.
2. Show that \(N_{1}\) is a rv.
3. Show that \(\mathrm{E}\left[N_{1}\right]=\infty\).
4. Let \(N_{2}\) be the index of the second record-to-date in the sequence. Show that \(N_{2}\) is a rv. Hint: You need not find the distribution function of \(N_{2}\) here.
5. Contrast your result in part c) to the result from part c) of Exercise 1.13 saying that the expected number of records-to-date is infinite over an an infinite number of trials. Note: this should be a shock to your intuition — there is an infinite expected wait for the first of an infinite sequence of occurrences, each of which must eventually occur.

Answer

Exercise 1.15

(Another direction from Exercise 1.13)

1. For any given \(n \geq 2\), find the probability that \(X_{n}\) and \(X_{n+1}\) are both records-to-date. Hint: The idea in part b) of 1.13 is helpful here, but the result is not.
2. Is the event that \(X_{n}\) is a record-to-date statistically independent of the event that \(X_{n+1}\) is a record-to-date?
3. Find the expected number of adjacent pairs of records-to-date over the sequence \(X_{1}, X_{2}, \ldots\) Hint: A helpful fact here is that \(\frac{1}{n(n+1)}=\frac{1}{n}-\frac{1}{n+1}\).

Answer

Exercise 1.16

1. Assume that \(X\) is a nonnegative discrete rv taking on values \(a_{1}, a_{2}, \ldots\), and let \(Y=h(X)\) for some nonnegative function \(h\). Let \(b_{i}=h\left(a_{i}\right), i \geq 1\), \(i \geq 1\) be the \(i^{t h}\) value taken on by Y. Show that \(\mathrm{E}[Y]=\sum_{i} b_{i} \mathrm{p}_{Y}\left(b_{i}\right)=\sum_{i} h\left(a_{i}\right) \mathrm{p}_{X}\left(a_{i}\right)\). Find an example where \(\mathrm{E}[X]\) exists but \(\mathrm{E}[Y]=\infty\).
2. Let \(X\) be a nonnegative continuous rv with density \(\mathrm{f}_{X}(x)\) and let \(h(x)\) be differentiable, nonnegative, and strictly increasing in \(x\). Let \(A(\delta)=\sum_{n} h(n \delta)[\mathrm{F}(n \delta)-\mathrm{F}(n \delta-\delta)]\), i.e., \(A(\delta)\) is the \(\delta t h\) order approximation to the Stieltjes integral \(\left.\int\right\} h(x) d \mathrm{~F}(x)\). Show that if \(A(1)<\infty\), then \(A\left(2^{-k}\right) \leq A\left(2^{k-1}\right)<\infty\). Show from this that \(\left.\int\right\} h(x) d \mathrm{~F}(x)\) converges to a finite value. Note: this is a very special case, but it can be extended to many cases of interest. It seems better to consider these convergence questions as required rather than consider them in general.

Answer

Exercise 1.17

1. Consider a positive, integer-valued rv whose distribution function is given at integer values by

   \(\mathrm{F}_{Y}(y)=1-\frac{2}{(y+1)(y+2)} \quad\text { for integer } y>0\)

   Use \ref{1.35} to show that \(\mathrm{E}[Y]=2\). Hint: Note the PMF given in (1.31).

2. Find the PMF of \(Y\) and use it to check the value of \(\mathrm{E}[Y]\).
3. Let \(X\) be another positive, integer-valued rv. Assume its conditional PMF is given by

   \(\mathrm{p}_{X \mid Y}(x \mid y)=\frac{1}{y} \quad \text { for } 1 \leq x \leq y\)

   Find \(\mathrm{E}[X \mid Y=y]\) and show that \(\mathrm{E}[X]=3 / 2\). Explore finding \(\mathrm{p}_{X}(x)\) until you are convinced that using the conditional expectation to calculate \(\mathrm{E}[X]\) is considerably easier than using \(\mathrm{p}_{X}(x)\).

4. Let \(Z\) be another integer-valued rv with the conditional PMF

   \(\mathrm{p}_{Z \mid Y}(z \mid y)=\frac{1}{y^{2}} \quad \text { for } 1 \leq z \leq y^{2}\)

   Find \(\mathrm{E}[Z \mid Y=y]\) for each integer \(y \geq 1\) and find \(\mathrm{E}[Z]\).

Answer

Exercise 1.18

1. Show that, for uncorrelated rv’s, the expected value of the product is equal to the product of the expected values (by definition, \(X\) and \(Y\) are uncorrelated if \(\mathrm{E}[(X-\bar{X})(Y-\bar{Y})]\}=0)\).
2. Show that if \(X\) and \(Y\) are uncorrelated, then the variance of \(X+Y\) is equal to the variance of \(X\) plus the variance of \(Y\).
3. Show that if \(X_{1}, \ldots, X_{n}\) are uncorrelated, the the variance of the sum is equal to the sum of the variances.
4. Show that independent rv’s are uncorrelated.
5. Let \(X\), \(Y\) be identically distributed ternary valued random variables with the PMF \(\mathrm{p}_{X}(-1)=\mathrm{p}_{X}(1)=1 / 4\); \(\mathrm{p}_{X}(0)=1 / 2\). Find a simple joint probability assignment such that \(X\) and \(Y\) are uncorrelated but dependent.
6. You have seen that the moment generating function of a sum of independent rv’s is equal to the product of the individual moment generating functions. Give an example where this is false if the variables are uncorrelated but dependent.

Answer

Exercise 1.9

Suppose \(X\) has the Poisson PMF, \(\mathrm{p}_{X}(n)=\lambda^{n} \exp (-\lambda) / n !\) for \(n \geq 0\) and \(Y\) has the Poisson PMF, \(\mathrm{p}_{Y}(m)=\mu^{n} \exp (-\mu) / n ! \text { for } n \geq 0\). Assume that \(X\) and \(Y\) are independent. Find the distribution of \(Z=X+Y\) and find the conditional distribution of \(Y\) conditional on \(Z = n\).

Answer

Exercise 1.20

1. Suppose \(X\), \(Y\) and \(Z\) are binary rv’s, each taking on the value 0 with probability 1/2 and the value 1 with probability 1/2. Find a simple example in which \(X\), \(Y\), \(Z\) are statistically dependent but are pairwise statistically independent (i.e., \(X\), \(Y\) are statistically independent, \(X\), \(Z\) are statistically independent, and \(Y\), \(Z\) are statistically independent). Give \(\mathrm{p}_{X Y Z}(x, y, z)\) for your example. Hint: In the simplest examle, only 4 of the joint values for \(x, y, z\) have positive probabilities.
2. Is pairwise statistical independence enough to ensure that

   \(\mathrm{E}\left[\prod_{i=1}^{n} X_{i}\right]
   ^\}= \prod_{i=1}^{n} \mathrm{E}\left[X_{i}\right]\)

   for a set of rv’s \(X_{1}, \ldots, X_{n}\)?

Answer

Exercise 1.21

Show that \(\mathrm{E}[X]\) is the value of \(\alpha\) that minimizes \(\mathrm{E}\left[(X-\alpha)^{2}\right]\).

Answer

Exercise 1.22

For each of the following random variables, find the interval \(\left(r_{-}, r_{+}\right)\) over which the moment generating function \(g(r)\) exists. Determine in each case whether \(g_{X}(r)\) exists at the end points \(r_{-}\) and \(r_{+}\). For parts a) and b) you should also find and sketch \(g(r)\). For part c), \(g(r)\) has no closed form.

1. Let \(\lambda\), \(\theta\), be positive numbers and let \(X\) have the density

   \(\mathrm{f}_{X}(x)=\frac{1}{2} \lambda \exp (-\lambda x) ; x \geq 0 ; \quad \mathrm{f}_{X}(x)=\frac{1}{2} \theta \exp (\theta x) ; x<0\)

2. Let \(Y\) be a Gaussian random variable with mean \(m\) and variance \(\sigma^{2}\).
3. Let \(Z\) be a nonnegative random variable with density

   \(\mathrm{f}_{Z}(z)=k(1+z)^{-2} \exp (-\lambda z) ; \quad z \geq 0\)

   where \(\lambda>0\) and \(k=\left[\int_{z \geq 0}(1+z)^{2} \exp (-a z) d z\right]^{-1}\). Hint: Do not try to evaluate \(g_{Z}(r)\). Instead, investigate values of \(r\) for which the integral is finite and infinite.

Answer

Exercise 1.23

Recall that the MGF of the nonnegative exponential rv with density \(e^{-x}\) is \((1-r)^{-1}\) for \(r<r_{+}=1\). In other words, \(g\left(r_{+}\right)\) does not exist and \(\lim _{r \rightarrow r_{+}} g(r)=\infty\), where the limit is over \(r<r_{+}\). In this exercise, you are to assume that \(X\) is an arbitrary rv for which \(g\left(r_{+}\right)\) does not exist and show that \(\lim _{r \rightarrow r_{+}} g(r)=\infty\) where the limit is over \(r<r_{+}\).

1. Explain why

   \(\lim _{A \rightarrow \infty} \int_{0}^{\}A} e^{x r_{+}} d \mathrm{~F}(x)=\infty\)

2. Show that for any \(\epsilon>0\) and any \(A>0\),

   \(g\left(r_{+}-\epsilon\right) \geq e^{-\epsilon A} \int_{0}^{\}A} e^{x r_{+}} d \mathrm{~F}(x)\)

3. Choose \(A=1 / \epsilon\) and show that

   \(\lim _{\epsilon \rightarrow 0} g\left(r_{+}-\epsilon\right)=\infty\)

Answer

Exercise 1.24

1. Assume that the MGF of the random variable \(X\) exists (i.e., is finite) in the interval \(\left(r_{-}, r_{+}\right)\), \(r_{-}<0<r_{+}\), and assume \(r_{-}<r<r_{+}\) throughout. For any finite constant \(c\), express the moment generating function of \(X-c\), i.e., \(\mathbf{g}(X-c)(r)\), in terms of \(\mathrm{g}_{X}(r)\) and show that \(\mathrm{g}_{(X-c)}(r)\) exists for all \(r\) in \(\left(r_{-}, r_{+}\right)\). Explain why \(\mathrm{g}_{(X-c)}^{\prime \prime}(r) \geq 0\).
2. Show that \({g}_{(X-c)}^{\prime \prime}(r)=\left[g_{X}^{\prime \prime}(r)-2 c g_{X}^{\prime}(r)+c^{2} g_{X}(r)\right] e^{-r c}\).
3. Use a) and b) to show that \({g}_{X}^{\prime \prime}(r) \mathrm{g}_{X}(r)-\left[\mathrm{g}_{X}^{\prime}(r)\right]^{2} \geq 0\), Let \(\gamma_{X}(r)=\ln g_{X}(r)\) and show that \(\gamma_{X}^{\prime \prime}(r) \geq 0\). Hint: Choose \(c=\mathrm{g}_{X}^{\prime}(r) / \mathrm{g}_{X}(r)\).
4. Assume that \(X\) is non-deterministic, i.e., that there is no value of \(\alpha\) such that \(\operatorname{Pr}\{X=\alpha\}=1\). Show that the inequality sign \(“\geq”\) may be replaced by “>” everywhere in a), b) and c).

Answer

Exercise 1.25

A computer system has \(n\) users, each with a unique name and password. Due to a software error, the \(n\) passwords are randomly permuted internally (i.e. each of the \(n!\) possible permutations are equally likely. Only those users lucky enough to have had their passwords unchanged in the permutation are able to continue using the system.

1. What is the probability that a particular user, say user 1, is able to continue using the system?
2. What is the expected number of users able to continue using the system? Hint: Let \(X_{i}\) be a rv with the value 1 if user \(i\) can use the system and 0 otherwise.

Answer

Exercise 1.26

Suppose the rv \(X\) is continuous and has the distribution function \(\mathrm{F}_{X}(x)\). Consider another rv \(Y=\mathrm{F}_{X}(X)\). That is, for each sample point \(\omega\) such that \(X(\omega)=x\), we have \(Y(\omega)=\mathrm{F}_{X}(x)\). Show that \(Y\) is uniformly distributed in the interval 0 to 1.

Answer

Exercise 1.27

Let \(Z\) be an integer valued rv with the PMF \(\mathrm{p}_{Z}(n)=1 / k\) for \(0 \leq n \leq k-1\). Find the mean, variance, and moment generating function of \(Z\). Hint: An elegant way to do this is to let \(U\) be a uniformly distributed continuous rv over (0, 1] that is independent of \(Z\). Then \(U + Z\) is uniform over (0, \(k\)]. Use the known results about \(U\) and \(U + Z\) to find the mean, variance, and MGF for \(Z\).

Answer

Exercise 1.28

1. Let \(Y\) be a nonnegative rv and \(y>0\) be some fixed number. Let \(A\) be the event that \(Y \geq y\). Show that \(y \mathbb{I}_{A} \leq Y\) (i.e., that this inequality is satisfied for every \(\omega \in \Omega\)).
2. Use your result in part a) to prove the Markov inequality

Answer

Exercise 1.29

1. Show that for any \(0<k<n\)

   \(\left(\begin{array}{l}
   \} n \\
   k+1
   \end{array}\right)^{\}} \leq\left(\begin{array}{l}
   n \\
   k
   \end{array}\right) \frac{n-k}{k}\)

2. Extend part a) to show that, for all \(\ell \leq n-k\),

   \(\left(\begin{array}{c}
   \} n \\
   k+\ell
   \end{array}\right)^{\}} \leq\left(\begin{array}{l}
   n \\
   k
   \end{array}\right)\left[\frac{n-k}{k}\right]^{\ell}\)

3. Let \(\tilde{p}=k / n\) and \(\tilde{q}=1-\tilde{p}\). Let \(S_{n}\) be the sum of \(n\) binary IID rv’s with \(\mathrm{p}_{X}(0)=q\) and \(\mathbf{p}_{X}(1)=p\). Show that for all \(\ell \leq n-k\),

   \(\mathbf{p}_{S_{n}}(k+\ell) \leq \mathrm{p}_{S_{n}}(k)\left(\frac{\tilde{q} p}{\tilde{p} q}\right)^{\ell\}}\)

4. For \(k / n>p\), show that \(\operatorname{Pr}\left\{S_{n} \geq k n\right\} \leq \frac{\tilde{p} q}{\tilde{p}-p} \mathrm{p}_{S_{n}}(k)\).
5. Now let \(\ell\) be fixed and \(k=\lceil n \tilde{p}\rceil\) for fixed \(\tilde{p}\) such that \(1>\tilde{p}>p\). Argue that as \(n \rightarrow \infty \),

   \(\mathrm{p}_{S_{n}}(k+\ell) \sim \mathrm{p}_{S_{n}}(k)\left(\frac{\tilde{q} p}{\tilde{p} q}\right)^{\ell{\}}} \quad \text { and }\quad \operatorname{Pr}\left\{S_{n} \geq k n\right\} \sim \frac{\tilde{p} q}{\tilde{p}-p} \mathrm{p}_{S_{n}}(k)\)

Answer

Exercise 1.30

A sequence \(\left\{a_{n} ; n \geq 1\right\}\) of real numbers has the limit 0 if for all \(\epsilon>0\), there is an \(m(\epsilon)\) such that \(\left|a_{n}\right| \leq \epsilon\) for all \(n \geq m(\epsilon)\). Show that the sequences in parts a) and b) below satisfy \(\lim _{n \rightarrow \infty} a_{n}=0\) but the sequence in part c) does not have a limit.

1. \(a_{n}=\frac{1}{\ln (\ln (n+1))}\)
2. \(a_{n}=n^{10} \exp (-n)\)
3. \(a_{n}=1\) for \(n=10^{\ell}\) for each positive integer \(\ell\) and \(a_{n}=0\) otherwise.
4. Show that the definition can be changed (with no change in meaning) by replacing \(\epsilon\) with either \(1 / k\) or \(2^{-k}\) for every positive integer \(k\).

Answer

Exercise 1.31

Consider the moment generating function of a rv \(X\) as consisting of the following two integrals:

\(\mathrm{g}_{X}(r)=\int_{-\infty}^{\}0} e^{r x} d \mathrm{~F}(x)+\int_{0}^{\}\infty} e^{r x} d \mathrm{~F}(x)\)

In each of the following parts, you are welcome to restrict \(X\) to be either discrete or continuous.

1. Show that the first integral always exists (i.e., is finite) for \(r \geq 0\) and that the second integral always exists for \(r \leq 0\).
2. Show that if the second integral exists for a given \(r_{1}>0\), then it also exists for all \(r\) in the range \(0 \leq r \leq r_{1}\).
3. Show that if the first integral exists for a given \(r_{2}<0\), then it also exists for all \(r\) in the range \(r_{2} \leq r \leq 0\).
4. Show that the range of \(r\) over which \({g}_{X}(r)\) exists is an interval from some \(r_{2} \leq 0\) to some \(r_{1} \geq 0\) (the interval might or might not include each endpoint, and either or both end point might be 0 or \(\infty\)).
5. Find an example where \(r_{1}=1\) and the MGF does not exist for \(r=1\). Find another example where \(r_{1}=1\) and the MGF does exist for \(r=1\). Hint: Consider \(f_{X}(x)=e^{-x}\) for \(x \geq 0\) and figure out how to modify it to \(\mathrm{f}_{Y}(y)\) so that \(\int_{0}^{\infty} e^{y} f_{Y}(y) d y<\infty\) but \(\int_{0}^{\infty} e^{y+\epsilon y} f_{Y}(y)=\infty\) for all \(\epsilon>0\).

Answer

Exercise 1.32

Let \(\left\{X_{n} ; n \geq 1\right\}\) be a sequence of independent but not identically distributed rv’s. We say that the weak law of large numbers (WLLN) holds for this sequence if for all \(\epsilon>0\)

\(\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{\left|\frac{S_{n}}{n}-\frac{\mathrm{E}\left[S_{n}\right]}{n}\right| \geq \epsilon\right\}^\}=0 \quad \text { where } S_{n}=X_{1}+X_{2}+\cdots+X_{n}\quad(\text{WL})\)

1. Show that the WLLN holds if there is some constant \(A\) such that \(\sigma_{X_{n}}^{2} \leq A\) for all \(n\).
2. Suppose that \(\sigma_{X_{n}}^{2} \leq A n^{1-\alpha}\) for some \(\alpha<1\) and for all \(n\). Show that the WLLN holds in this case.

Answer

Exercise 1.33

Let \(\left\{X_{i} ; i \geq 1\right\}\) be IID binary rv’s. Let \(\operatorname{Pr}\left\{X_{i}=1\right\}=\delta\), \(\operatorname{Pr}\left\{X_{i}=0\right\}=1-\delta\). Let \(S_{n}=X_{1}+\cdots+X_{n}\). Let \(m\) be an arbitrary but fixed positive integer. Think! then evaluate the following and explain your answers:

1. \(\lim _{n \rightarrow \infty} \sum_{i: n \delta-m \leq i \leq n \delta+m} \operatorname{Pr}\left\{S_{n}=i\right\}\)
2. \(\lim _{n \rightarrow \infty} \sum_{i: 0 \leq i \leq n \delta+m} \operatorname{Pr}\left\{S_{n}=i\right\}\)
3. \(\lim _{n \rightarrow \infty} \sum_{i: n(\delta-1 / m) \leq i \leq n(\delta+1 / m)} \operatorname{Pr}\left\{S_{n}=i\right\}\)

Answer

Exercise 1.34

Use the Berry-Esseen result, (1.83), to prove the WLLN under the restriction that \(\left.\mathrm{E}\left[|X|^{3}\right]\right\} \text { exists }\). Note: This is not intended as a reasonable way to prove the WLLN. Rather, it is to better understand what the convergence result of \ref{1.83} implies. It appears that the CLT, without something extra about convergence, does not establish the WLLN.

Answer

Exercise 1.35 Details in the proof of Theorem 1.5.3

1. Show that if \(X_{1}, X_{2}, \ldots\), are IID, then the truncated versions \(\breve{X}_{1}, \breve{X}_{2}, \ldots\), are also IID.
2. Show that each \(\breve{X}_{i}\) has a finite mean \(\mathrm{E}[\breve{X}]^\}\) and finite variance \(\sigma_{\breve{X}}^{2}\). Show that the variance is upper bounded by the second moment around the original mean \(\bar{X}\), i.e., show that \(\sigma_{\breve{X}}^{2} \leq \mathrm{E}\left[|\breve{X}-\mathrm{E}[X]|^{2}\right]\).
3. Assume that \(\check{X}_{i}\) is \(X_{i}\) truncated to \(\bar{X} \pm b\). Show that \(|\breve{X}-\bar{X}| \leq b\) and that \(|\breve{X}-\bar{X}| \leq|X-\bar{X}|\). Use this to show that \(\sigma_{\breve{X}}^{2} \leq b \mathrm{E}[|\breve{X}-\bar{X}|]^\} \leq 2 b \mathrm{E}[|X|]\).
4. Let \(\breve{S}_{n}=\breve{X}_{1}+\cdots+\breve{X}_{n}\) and show that for any \(\epsilon>0\),

   \(\operatorname{Pr}\left\{\left|\frac{\breve{S}_{n}}{_{\}}n}-\mathrm{E}[\breve{X}]\right|_{\}} \geq \frac{\epsilon}{2}\right\}^{\}} \leq \frac{8 b \mathrm{E}[|X|]}{n \epsilon^{2}}\)

5. Sketch the form of \(\mathrm{F}_{\breve{X}-\bar{X}}(x)\) and use this, along with (1.35), to show that for all su­ciently large \(b\), \(|\mathrm{E}[\breve{X}-\bar{X}]| \leq \epsilon / 2\). Use this to show that

   \(\operatorname{Pr}\left\{\left|\frac{\breve{S}_{n}}{n}-\mathrm{E}[X]\right| \geq \epsilon\right\}^\} \leq \frac{8 b \mathrm{E}[|X|]}{n \epsilon^{2}} \quad \text { for all large enough }b\)

6. Use the following equation to justify (1.94).

   \(\begin{aligned}
   \operatorname{Pr}\left\{\left|\frac{S_{n}}{n}-\mathrm{E}[X]\right|>\epsilon\right\}^\}=&\left.\operatorname{Pr}\left\{\left|\frac{S_{n}}{n}-\mathrm{E}[X]\right|>\epsilon \bigcap\right\} S_{n}=\breve{S}_{n}\right\}^\} \\
   &\left.+\operatorname{Pr}\left\{\left|\frac{S_{n}}{n}-\mathrm{E}[X]\right|>\epsilon \bigcap\right\} S_{n} \neq \breve{S}_{n}\right\}
   \end{aligned}\)

Answer

Exercise 1.36

Let \(\left\{X_{i} ; i \geq 1\right\}\) be IID rv’s with mean 0 and infinite variance. Assume that \(\left.\mathrm{E}\left[\left|X_{i}\right|^{1+h}\right]\right\}=\beta\) for some given \(h\), \(0<h<1\) and some finite \(\beta\). Let \(S_{n}=X_{1}+\cdots+X_{n}\).

1. Show that \(\operatorname{Pr}\left\{\left|X_{i}\right| \geq y\right\} \leq \beta y^{-1-h}\)

2. Let \(\left\{\breve{X}_{i} ; i \geq 1\right\}\) be truncated variables \(\breve{X}_{i}=\left\{\begin{array}{rll}
   b & : & X_{i} \geq b \\
   \} X_{i} & : & -b \leq X_{i} \leq b \\
   \}-b & : & X_{i} \leq-b
   \end{array}\right.\)

   Show that \(\mathrm{E}\left[\breve{X}^{2}\right]^\} \leq \frac{2 \beta b^{1-h}}{1-h}\) Hint: For a nonnegative rv \(Z\), \(\left.\mathrm{E}\left[X^{2}\right]\right\}=\int_{0}^{\infty} 2 z \operatorname{Pr}\{Z \geq z\} d z\) (you can establish this, if you wish, by integration by parts).

3. Let \(\breve{S}_{n}=\breve{X}_{1}+\ldots+\breve{X}_{n}\). Show that \(\operatorname{Pr}\left\{S_{n} \neq \breve{S}_{n}\right\}^\} \leq n \beta b^{-1-h}\).
4. Show that \(\operatorname{Pr}\left\{\left|\frac{S_{n}}{n}\right| \geq \epsilon \leq \beta\left[\frac{2 b^{1-h}}{(1-h) n \epsilon^{2}}+\frac{n}{b^{1+h}}\right]\right.\).
5. Optimize your bound with respect to b. How fast does this optimized bound approach 0 with increasing \(n\)?

Answer

Exercise 1.37 (MS convergence -> convergence in probability)

Assume that \(\left\{Z_{n} ; n \geq\right. 1\}\) is a sequence of rv’s and \(\alpha\) is a number with the property that \(\left.\lim _{n \rightarrow \infty} \mathrm{E}\left[\left(Z_{n}-\alpha\right)^{2}\right]\right\}=0\).

1. Let \(\epsilon>0\) be arbitrary and show that for each \(n \geq 0\),

   \(\operatorname{Pr}\left\{\left|Z_{n}-\alpha\right| \geq \epsilon\right\} \leq \frac{\operatorname{E}\left[\left(Z_{n}-\alpha\right)^{2}\right]}{\epsilon^{2}}\)

2. For the \(\epsilon\) above, let \(\delta>0\) be arbitrary. Show that there is an integer \(m\) such that \(\left.\mathrm{E}\left[\left(Z_{n}-\alpha\right)^{2}\right]\right\} \epsilon^{2} \delta\) for all \(n \geq m\).
3. Show that this implies convergence in probability.

Answer

Exercise 1.38

Let \(X_{1}, X_{2} \ldots\), be a sequence of IID rv’s each with mean 0 and variance \(\sigma^{2}\). Let \(S_{n}=X_{1}+\cdots+X_{n}\) for all \(n\) and consider the random variable \(S_{n} / \sigma \sqrt{n}-S_{2 n} / \sigma \sqrt{2 n}\). Find the limiting distribution function for this sequence of \(r v^{\prime} s\) as \(n \rightarrow \infty\). The point of this exercise is to see clearly that the distribution function of \(S_{n} / \sigma \sqrt{n}\) is converging but that the sequence of rv’s is not converging.

Answer

Exercise 1.39

A town starts a mosquito control program and the rv \(Z_{n}\) is the number of mosquitos at the end of the \(n\)th year (\(n\) = 0, 1, 2, . . .). Let \(X_{n}\) be the growth rate of mosquitos in year \(n\); i.e., \(Z_{n}=X_{n} Z_{n-1}\); \(n \geq 1\). Assume that \(\left\{X_{n} ; n \geq 1\right\}\) is a sequence of IID rv’s with the PMF \(\operatorname{Pr}\{X=2\}=1 / 2\); \(\operatorname{Pr}\{X=1 / 2\}=1 / 4\); \( \operatorname{Pr}\{X=1 / 4\}=1 / 4\). Suppose that \(Z_{0}\), the initial number of mosquitos, is some known constant and assume for simplicity and consistency that \(Z_{n}\) can take on non-integer values.

1. Find \(\mathrm{E}\left[Z_{n}\right]\) as a function of \(n\) and find \(\lim _{n \rightarrow \infty} \mathrm{E}\left[Z_{n}\right]\).
2. Let \(W_{n}=\log _{2} X_{n}\). Find \(\mathrm{E}\left[W_{n}\right]\) and \(\mathrm{E}\left[\log _{2}\left(Z_{n} / Z_{0}\right)\right]\) as a function of \(n\).
3. There is a constant \(\alpha\) such that \(\lim _{n \rightarrow \infty}(1 / n)\left[\log _{2}\left(Z_{n} / Z_{0}\right)\right]=\alpha\) with probability 1. Find \(\alpha\) and explain how this follows from the strong law of large numbers.
4. Using (c), show that \(\lim _{n \rightarrow \infty} Z_{n}=\beta\) with probability 1 for some \(\beta\) and evaluate \(\beta\).
5. Explain carefully how the result in \ref{a} and the result in \ref{d} are possible. What you should learn from this problem is that the expected value of the log of a product of IID rv’s might be more significant that the expected value of the product itself.

Answer

Exercise 1.40

Use Figure 1.7 to verify (1.55). Hint: Show that \(y \operatorname{Pr}\{Y \geq y\} \leq \int_{z \geq y} z d \mathrm{~F}_{Y}(z)\) and show that \(\lim _{y \rightarrow \infty} \int_{z \geq y} z d \mathrm{~F}_{Y}(z)=0\) if \(\mathrm{E}[Y]\) is finite.

Answer

Exercise 1.41

Show that \(\prod_{m \geq n}(1-1 / m)=0\). Hint: Show that

\(\left(1-\frac{1}{m}\right)^{\}}=\exp \left(\ln \left(1-\frac{1}{m}\right)\right)^{\}} \leq \exp \left(-\frac{1}{m}\right)\)

Answer

Exercise 1.42

Consider a discrete rv \(X\) with the PMF

\(\begin{aligned}
\mathrm{p}_{X}(-1) &=\left(1-10^{-10}\right) / 2, \\
\mathrm{p}_{X}(1) &=\left(1-10^{-10}\right) / 2, \\
\mathrm{p}_{X}\left(10^{12}\right) &=10^{-10}.
\end{aligned}\)

1. Find the mean and variance of \(X\). Assuming that \(\left\{X_{m} ; m \geq 1\right\}\) is an IID sequence with the distribution of \(X\) and that \(S_{n}=X_{1}+\cdots+X_{n}\) for each \(n\), find the mean and variance of \(S_{n}\). (no explanations needed.)
2. Let \(n=10^{6}\) and describe the event \(\left\{S_{n} \leq 10^{6}\right\}\) in words. Find an exact expression for \(\operatorname{Pr}\left\{S_{n} \leq 10^{6}=\mathrm{F}_{S_{n}}\left(10^{6}\right)\right.\)
3. Find a way to use the union bound to get a simple upper bound and approximation of \(1-\mathrm{F}_{S_{n}}\left(10^{6}\right)\).
4. Sketch the distribution function of \(S_{n}\) for \(n=10^{6}\). You can choose the horizontal axis for your sketch to go from \(-1\) to \(+1\) or from \(-3 \times 10^{3}\) to \(3 \times 10^{3}\) or from \(-10^{6}\) to \(10^{6}\) or from 0 to \(10^{12}\), whichever you think will best describe this distribution function.
5. Now let \(n=10^{10}\). Give an exact expression for \(\operatorname{Pr}\left\{S_{n} \leq 10^{10}\right.\) and show that this can be approximated by \(e^{-1}\). Sketch the distribution function of \(S_{n}\) for \(n=10^{10}\), using a horizontal axis going from slightly below 0 to slightly more than \(2 \times 10^{12}\). Hint: First view \(S_{n}\) as conditioned on an appropriate rv.
6. Can you make a qualitative statement about how the distribution function of a rv \(X\) affects the required size of \(n\) before the WLLN and the CLT provide much of an indication about \(S_{n}\).

Answer