Introduction and review of probability

For two arbitrary events $A_{1}$ and $A_{2}$, show that

Show that $A_{1}$ and $A_{2}-A_{1}$ are disjoint.

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_{m=1}^{n-1}A_{m}$. Show that $B_{1}, B_{2}, \ldots$, are disjoint events and show that for each $n \geq 2$, $\bigcup_{m=1}^{n}A_{m} = \bigcup_{m=1}^{n}B_{m}$.

Show that

Show that for each $n$, $\mathbb {P}\left(B_{n}\right) \leq \mathbb {P}\left(A_{n}\right)$. Use this to show that

Show that $\mathbb {P}\left(\bigcup_{n=1}^{\infty }A_{n}\right) = \lim_{m \rightarrow \infty }\mathbb {P}\left(\bigcup_{n=1}^{m}A_{n}\right)$. 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.

Show that $\mathbb {P}\left(\bigcap_{n=1}^{\infty }A_{n}\right) = \lim_{n \rightarrow \infty }\mathbb {P}\left(\bigcap_{i=1}^{n}A_{i}\right)$.

Create an example where $\mathbb {P}\left(A_{1}A_{2}\right) = \mathbb {P}\left(A_{1}A_{3}\right) = \frac{1}{4}$ but $\mathbb {P}\left(A_{2}A_{3}\right) = \frac{1}{8}$.

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 the joint factorization condition on all subsets of events, rather than just pairwise factorization of every pair of events.

For any given rv $X$, any real number $x$, and each integer $n \geq 1$, let $A_{n} = \left\{ \omega : X > x+1/n\right\}$, and show that $A_{1} \subseteq A_{2} \subseteq \cdots$. Use this and the corollaries to the axioms of probability to show that $\mathbb {P}\left(\bigcup_{n \geq 1}A_{n}\right) = \lim_{n \rightarrow \infty }\mathbb {P}\left(A_{n}\right)$.

Show that $\mathbb {P}\left(\bigcup_{n \geq 1}A_{n}\right) = \mathbb {P}\left(X>x\right)$ and that $\mathbb {P}\left(X>x\right) = \lim_{n \rightarrow \infty }\mathbb {P}\left(X>x+1/n\right)$.

Show that for $\epsilon >0$, $\lim_{\epsilon \rightarrow 0}\mathbb {P}\left(X \leq x+\epsilon \right) = \mathbb {P}\left(X \leq x\right)$.

Define $\widetilde{F}_{X}(x) = \mathbb {P}\left(X<x\right)$. Show that $\widetilde{F}_{X}(x)$ is continuous from the left. In other words, the continuity from the right for the CDF arises from the almost arbitrary (but universally accepted) choice in defining the CDF as $\mathbb {P}\left(X \leq x\right)$ rather than $\mathbb {P}\left(X<x\right)$.

Show that $\sum_{m \geq 0}m\mathsf{p}_{M}(m) = \infty$ and $\sum_{m<0}m\mathsf{p}_{M}(m) = -\infty$. (Thus show that the expectation of $M$ not only does not exist but is undefined even as an extended real number.)

Suppose that the terms in $\sum_{m=-\infty }^{\infty }m\mathsf{p}_{M}(m)$ are summed in the order of two positive terms for each negative term (i.e., in the order $1, 2, -1, 3, 4, -2, 5, \cdots$). Find the limiting value of the partial sums in this series.

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

Show from the Stirling bounds above and from the monotone property that

Use the result of (a) to upper bound $\mathsf{p}_{S_{n}}(k)$ by

Show that this is equivalent to the upper bound in Theorem 1.4.1.

Show that

Derive the lower bound in Theorem 1.4.1.

Show that $D(\widetilde{p}\| p) = \widetilde{p}\ln (\widetilde{p}/p)+(1-\widetilde{p})\ln [(1-\widetilde{p})/(1-p)]$ is 0 at $\widetilde{p} = p$ and non-negative elsewhere.

$p_{0} = 0.2$, $p_{1} = 0.4$, $p_{2} = 0.4$.

$p_{0} = 0.2$, $p_{1} = 0.2$, $p_{2} = 0.6$.

$p_{0} = 0.2$, $p_{1} = 0.3$, $p_{2} = 0.5$.

Now suppose that $X$ is non-negative and continuous with the density $\mathsf{f}_{X}(x) = 1$ for $0 \leq x \leq 0.5$ and $\mathsf{f}_{X}(x) = 0$ for $0.5<x \leq 1$. We know that $\mathsf{f}_{X}(x)$ is positive for all $x>1$, but it is otherwise unknown. Find the median or interval of medians.

For any given rv $Y$, express $\mathbb {E}\left[\left|Y\right|\right]$ in terms of $\int_{y<0}F_{Y}(y) \, dy$ and $\int_{y \geq 0}F_{Y}^{c}(y) \, dy$.

For some given rv $X$ with $\mathbb {E}\left[\left|X\right|\right]<\infty$, let $Y = X-\alpha$. Using (a), show that

Show that $\mathbb {E}\left[\left|X-\alpha \right|\right]$ is minimized over $\alpha$ by choosing $\alpha$ to be a median of $X$. Be careful to show that when the median is an interval, all points in this interval achieve the minimum.

The maximum of $n$ IID rv's, each with CDF $F_{X}(x)$.

The minimum of $n$ IID rv's, each with CDF $F_{X}(x)$.

The difference of the rv's defined in (a) and (b); assume $X$ has a density $\mathsf{f}_{X}(x)$.

Show that the set of $\omega$ for which $Z(\omega ) = \pm \infty$ has probability 0.

To show that $Z = X+Y$ is a rv, we must show that for each real number $\alpha$, the set $\left\{ \omega \in \Omega : X(\omega )+Y(\omega ) \leq \alpha \right\}$ is an event. We proceed indirectly. For an arbitrary positive integer $n$ and an arbitrary integer $k>0$, let $B(n, k) = \left\{ \omega : X(\omega ) \leq k/n\right\} \cap \left\{ \omega : Y(\omega ) \leq \alpha +(1-k)/n\right\}$. Let $D(n) = \bigcup_{k}B(n, k)$ and show that $D(n)$ is an event.

On a two-dimensional sketch for a given $\alpha$, show the values of $X(\omega )$ and $Y(\omega )$ for which $\omega \in D(n)$.

Show that

Explain why this shows that $Z = X+Y$ is a rv.

Explain why (d) implies that if $Y = X_{1}+X_{2}+\cdots +X_{n}$ and if $X_{1}, X_{2}, \ldots , X_{n}$ are rv's, then $Y$ is a rv.

Let $X_{1}, X_{2}, \ldots , X_{n}$ be rv's with expected values $\overline{X}_{1}, \ldots , \overline{X}_{n}$. Show that $\mathbb {E}\left[X_{1}+\cdots +X_{n}\right] = \overline{X}_{1}+\cdots +\overline{X}_{n}$. You may assume that the rv's have a joint density function, but do not assume that the rv's are independent.

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.

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.

Let $h(x) = u(x)$ and $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 as the limit of Riemann sums $\sum_{n}h(x_{n})[F(y_{n})-F(y_{n-1})]$ over partitions $\left\{ y_{n}; n \geq 1\right\}$ with $y_{n-1}<x_{n} \leq y_{n}$, refined as the partition mesh $\delta \rightarrow 0$, show that $\int_{-1}^{1}h(x) \, dF_{X}(x)$ does not exist.

Let $h(x) = u(x-a)$ and $F_{X}(x) = u(x-b)$, where $a$ and $b$ are in $(-1, +1)$. Show that $\int_{-1}^{1}h(x) \, dF_{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 )$.

Let $X$ and $Y$ be independent discrete rv's, each with a finite set of possible values. Show that $\int_{-\infty }^{\infty }F_{X}(z-y) \, dF_{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$.

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.

Find the probability that $X_{n}$ is a record-to-date, as a function of $n \geq 1$. Again use symmetry.

Find a simple expression for the expected number of records-to-date that occur over the first $m$ trials for any given integer $m$. Show that this expected number is infinite in the limit $m \rightarrow \infty$.

Let $N_{1}$ be the index of the first record-to-date in the sequence. Find $\mathbb {P}\left(N_{1}>n\right)$ for each $n \geq 2$.

Show that $N_{1}$ is a rv.

Show that $\mathbb {E}\left[N_{1}\right] = \infty$.

Let $N_{2}$ be the index of the second record-to-date in the sequence. Show that $N_{2}$ is a rv. You need not find the CDF of $N_{2}$ here.

Contrast your result in (c) to the result from Exercise 1.16(c) saying that the expected number of records-to-date is infinite over an infinite number of trials. Note: this might 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.

For any given $n \geq 2$, find the probability that $X_{n}$ and $X_{n+1}$ are both records-to-date.

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?

Find the expected number of adjacent pairs of records-to-date over the sequence $X_{1}, X_{2}, \ldots$.

Assume that $X$ is a non-negative discrete rv taking on values $a_{1}, a_{2}, \ldots$, and let $Y = h(X)$ for some non-negative function $h$. Let $b_{i} = h(a_{i})$, $i \geq 1$, be the $i$th value taken on by $Y$. Show that $\mathbb {E}\left[Y\right] = \sum_{i}b_{i}\mathsf{p}_{Y}(b_{i}) = \sum_{i}h(a_{i})\mathsf{p}_{X}(a_{i})$. Find an example where $\mathbb {E}\left[X\right]$ exists but $\mathbb {E}\left[Y\right] = \infty$.

Let $X$ be a non-negative continuous rv with density $\mathsf{f}_{X}(x)$ and let $h(x)$ be differentiable, non-negative, and strictly increasing in $x$. Let $A(\delta ) = \sum_{n \geq 1}h(n\delta )[F(n\delta )-F(n\delta -\delta )]$, i.e., $A(\delta )$ is a $\delta$th-order approximation to the Stieltjes integral $\int h(x) \, dF(x)$. Show that if $A(1)<\infty$, then $A(2^{-k}) \leq A(2^{-(k-1)})<\infty$. Show from this that $\int h(x) \, dF(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 to consider them in general.

Consider a positive, integer-valued rv whose CDF is given at integer values by

Use $\mathbb {E}\left[Y\right] = \int_{0}^{\infty }F_{Y}^{c}(y) \, dy$ (equation (1.30)) to show that $\mathbb {E}\left[Y\right] = 2$.

Find the PMF of $Y$ and use it to check the value of $\mathbb {E}\left[Y\right]$.

Let $X$ be another positive, integer-valued rv. Assume its conditional PMF is given by

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

Let $Z$ be another integer-valued rv with the conditional PMF

Find $\mathbb {E}\left[Z \mid Y=y\right]$ for each integer $y \geq 1$ and find $\mathbb {E}\left[Z\right]$.

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 $\mathbb {E}\left[(X-\overline{X})(Y-\overline{Y})\right] = 0$).

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$.

Show that if $X_{1}, \ldots , X_{n}$ are uncorrelated, then the variance of the sum is equal to the sum of the variances.

Show that independent rv's are uncorrelated.

Let $X, Y$ be identically distributed ternary valued rv's with the PMF $\mathsf{p}_{X}(-1) = \mathsf{p}_{X}(1) = 1/4$; $\mathsf{p}_{X}(0) = 1/2$. Find a simple joint probability assignment such that $X$ and $Y$ are uncorrelated but dependent.

You have seen that the MGF of a sum of independent rv's is equal to the product of the individual MGFs. Give an example where this is false if the variables are uncorrelated but dependent.

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 $\mathsf{p}_{XYZ}(x, y, z)$ for your example.

Is pairwise statistical independence enough to ensure that

for a set of rv's $X_{1}, \ldots , X_{n}$?

Let $\lambda , \theta$, be positive numbers and let $X$ have the density

Let $Y$ be a Gaussian rv with mean $m$ and variance $\sigma^{2}$.

Let $Z$ be a non-negative rv with density

where $\lambda >0$ and $k = \left[\int_{z \geq 0}(1+z)^{-2}\exp (-\lambda z) \, dz\right]^{-1}$.

For the $Z$ of (c), find the limit of $\gamma '(r)$ as $r$ approaches $\lambda$ from below. Then replace $(1+z)^{2}$ with $\left|1+z\right|^{3}$ in the definition of $\mathsf{f}_{Z}(z)$ and $k$ and show whether the above limit is then finite or not.

Assume that the MGF of the rv $X$ exists (i.e., is finite) in the interval $(r_{-}, r_{+})$, $r_{-}<0<r_{+}$, and assume $r_{-}<r<r_{+}$ throughout. For any finite constant $c$, express the MGF of $X-c$, i.e., $\mathsf{g}_{(X-c)}(r)$, in terms of the MGF of $X$ and show that $\mathsf{g}_{(X-c)}''(r) \geq 0$. Explain why $\mathsf{g}_{(X-c)}''(r) \geq 0$.

Show that $\mathsf{g}_{(X-c)}''(r) = [\mathsf{g}_{X}''(r)-2c\mathsf{g}_{X}'(r)+c^{2}\mathsf{g}_{X}(r)]e^{-rc}$.

Use (a) and (b) to show that $\mathsf{g}_{X}''(r)\mathsf{g}_{X}(r)-[\mathsf{g}_{X}'(r)]^{2} \geq 0$. Let $\gamma_{X}(r) = \ln \mathsf{g}_{X}(r)$ and show that $\gamma_{X}''(r) \geq 0$.

Assume that $X$ is non-deterministic, i.e., there is no value of $\alpha$ such that $\mathbb {P}\left(X=\alpha \right) = 1$. Show that the inequality sign $\geq$' may be replaced by $>$' everywhere in (a), (b) and (c).

What is the probability that a particular user, say user 1, is able to continue using the system?

What is the expected number of users able to continue using the system?

Let $Y$ be a non-negative 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$).

Use your result in (a) to prove the Markov inequality.

Minimize $\mathbb {E}\left[Y\right]$ over all non-negative rv's such that $\mathbb {P}\left(Y \geq b\right) = \beta$ for some given $b>0$ and $0<\beta <1$. What is the rv that achieves the minimum?

Use (a) to prove the Markov inequality and also point out the distribution that meets the inequality with equality.

Show that the second integral above satisfies $\int_{b}^{\infty }x^{2}\mathsf{f}_{X}(x) \, dx \geq b^{2}\beta$.

Show that the first integral above is constrained by

Minimize the first integral subject to the constraints in (b).

Combine the results in (a) and (c) to show that $\sigma^{2} \geq b^{2}\beta /(1-\beta )$. Find the minimizing distribution.

Use (d) to establish the one-sided Chebyshev inequality above. Also show (trivially) that if $Y$ has a mean $\overline{Y}$ and variance $\sigma^{2}$, then $\mathbb {P}\left(Y-\overline{Y} \geq b\right) \leq \sigma^{2}/(\sigma^{2}+b^{2})$.

First show that $\left|\alpha \right| \leq \sigma$ for the special case where $X$ is binary with equiprobable values at $\pm \sigma$.

For all zero-mean rv's $X$ with variance $\sigma^{2}$ other than the special case in (a), show that

Show that $\mathbb {P}\left(X \geq \alpha \right) \geq 0.5$. Other than the special case in (a), show that this implies that $\alpha <\sigma$.

Other than the special case in (a), show that $\left|\alpha \right|<\sigma$. You have then shown that $\left|\alpha \right| \leq \sigma$ with equality only for the binary case with values $\pm \sigma$. For rv's $Y$ with a non-zero mean, this shows that $\left|\alpha -\overline{Y}\right| \leq \sigma$.

For any given $x$, let $\mathbb {I}_{j}(x)$ be the indicator function of the event $\left\{ X_{j} \leq x\right\}$ where $X_{1}, X_{2}, \ldots , X_{j}, \ldots$ are IID rv's with the CDF $F_{X}(x)$. State the WLLN for the IID rv's $\left\{ \mathbb {I}_{1}(x), \mathbb {I}_{2}(x), \ldots \right\}$.

Does the answer to (a) require $X$ to have a mean or variance?

Suggest a procedure for evaluating the median of $X$ from the sample values of $X_{1}, X_{2}, \ldots$. Assume that $X$ is a continuous rv and that its PDF is positive in an open interval around the median. You need not be precise, but try to think the issue through carefully.

Show that for any integers $0<k<n$,