Classical Probability and Inclusion-Exclusion

Let \(A_{n}\) be a sequence of independent events with \(P(A_{n}) < 1\) for all \(n\). Show that \[ P\left (\bigcup _{n} A_{n}\right ) = 1 \quad \text {implies} \quad \sum _{n} P(A_{n}) = \infty . \]

Let \(X_{1}, X_{2}, \ldots \) be i.i.d. with characteristic function \(\phi \).

1. Show that if \(\phi '(0) = ia\) and \(S_{n} = X_{1} + \cdots + X_{n}\), then \(S_{n}/n \to a\) in probability. (Hint: first show that if \(c_{n} \to c \in \mathbb {C}\), then \((1 + c_{n}/n)^{n} \to e^{c}\).)
2. Show that if \(S_{n}/n \to a\) in probability, then \(\phi (t/n)^{n} \to e^{iat}\) as \(n \to \infty \) through the integers.

Let \(\{A_{i}\}_{i=1}^{\infty }\) be a sequence of independent events such that \(\sum _{i=1}^{\infty } P(A_{i}) = \infty \). Prove that the \(A_{n}\) occur infinitely often with probability 1 (the converse of the Borel-Cantelli Lemma), i.e. that \(\sum _{i=1}^{\infty }\mathbf {1}_{A_{i}} = \infty \) almost surely.

Show that if \(X_{n} \to X\) in probability, then \(X_{n} \Rightarrow X,\) i.e. \(X_{n}\) converges weakly to \(X\).

Recall the inversion formula: if \(\mu \) is a probability measure and \(\widehat {\mu }\) is its characteristic function, then for all \(a < b\):

1. Prove that if \(\widehat {\mu } \in L^{1}\), then \(\mu (\{a\}) = 0\) for all \(a \in \mathbb {R}\) and \(\mu \) has a probability density function given by

   \[ f(y) = \frac {1}{2\pi }\int _{-\infty }^{\infty } e^{-ity}\widehat {\mu }(t)\,dt. \]

2. Show that if \(X_{1}, \ldots , X_{n}\) are independent and uniformly distributed on \((-1, 1)\), then for \(n \ge 2\), \(X_{1} + \cdots + X_{n}\) has density

   \[ f(y) = \frac {1}{\pi }\int _{0}^{\infty } \left (\frac {\sin t}{t}\right )^{n}\cos (ty)\,dt. \]

Answer the following questions.

1. State the definition of convergence in probability. Using only this definition, show that \(X_{n} \to X\) in probability if and only if \(\mathbb {E}[1 \wedge |X_{n} - X|] \to 0\). Do not appeal to any theorems that trivialize the problem.
2. State the definition of almost sure convergence. Prove that if \(X_{n} \to X\) almost surely, then \(X_{n} \to X\) in probability. Again, do not appeal to any theorems that trivialize the problem.

Suppose a box contains 6 marbles in total. Suppose \(\theta \) of them are white and \(6-\theta \) of them are black. Test \(H_0:\theta =2\) against \(H_a:\theta \ne 2\) as follows: draw two marbles without replacement and reject \(H_0\) if both marbles are the same color, otherwise do not reject. What is the probability of Type II error for each of the alternatives \(\theta =1\) and \(\theta =3\)?

Let \(\{X_n:n\in \mathbb {N}\}\) be a sequence of i.i.d. positive integrable random variables. Define \(T_n=X_1+\cdots +X_n\), \(n\in \mathbb {N}\), and \[ N(t)=\max \{n\in \mathbb {N}:T_n\leq t\}, \qquad t\geq 0. \] Show that with probability one, \[ \frac {N(t)}{t}\to \frac {1}{\mathbb {E}[X_1]} \qquad \text {as } t\to \infty . \] (Hint: Sketch what the process \(t\mapsto N(t)\) looks like for a fixed realization of the \(X_n\). What do you know about the asymptotic behavior of the jump times?)

Assume the same setting as in the previous problem. You can assume that the claim in that problem is true and solve this problem independently.

a) For an integer \(a\geq 0\) let \(T_a=\inf \{n\geq 0:X_n=a\}\). Fix \(a\geq 2\) and prove that \[ \mathbb {P}(T_0<\infty \text { or }T_a<\infty )=1. \] (Hint: As long as the process is not at 0 it has a positive probability to go up \(a\) times in a row. How do you turn this observation into a proof?)

b) Calculate \(\mathbb {P}(T_a<T_0\mid X_0=1)\). (Carefully explain why the conditions of the theorems you use are satisfied.)

Assume that \(A_i\), \(i=1,2,\ldots \), are independent events. Prove that \[ \frac {1}{n}\sum _{i=1}^{n}\left (\mathbf {1}_{A_i}-\mathbb {P}(A_i)\right ) \] converges to zero in probability as \(n\to \infty \), where where \(\mathbf {1}_{A_i}\) is the indicator function of the event \(A_i\).

Let \(X\) and \(Y\) be two integer-valued random variables defined on the same probability space. The total variation distance between \(X\) and \(Y\) is defined as \[ d_{TV}(X,Y)=2\sup _{A\subseteq \mathbb {Z}} |\mathbb {P}(X\in A)-\mathbb {P}(Y\in A)|. \] Prove that \(\mathbb {P}(X=Y)\leq 1-\frac {1}{2}d_{TV}(X,Y)\).

A particular gene occurs as one of two alleles (\(A\) and \(a\)), with allele \(A\) having frequency \(\theta \) in the population. In other words, a random copy of the gene is \(A\) with probability \(\theta \) and \(a\) with probability \(1-\theta \). A diploid genotype is just two genes put together (in any particular order) so the probability of each diploid genotype is \(\theta ^2\) for \(AA\), \(2\theta (1-\theta )\) for \(Aa\), and \((1-\theta )^2\) for \(aa\). Suppose we test a random sample of people and find that \(k_1\) of them are \(AA\), \(k_2\) of them are \(Aa\), and \(k_3\) of them are \(aa\). Find the MLE of \(\theta \).

Let \(\mu \) and \(\nu \) be probability measures on \((\mathbb {R},\mathcal {B}(\mathbb {R}))\). Let \(\lambda =\frac {1}{2}\mu +\frac {1}{2}\nu \). Let \(\mathcal {F}\) be a \(\sigma \)-algebra contained in \(\mathcal {B}(\mathbb {R})\). Let \(\mu _{\mathcal {F}}\), \(\nu _{\mathcal {F}}\), and \(\lambda _{\mathcal {F}}\) be the restrictions of \(\mu \), \(\nu \), and \(\lambda \) to \(\mathcal {F}\), respectively.

1. Prove that \(\mu _{\mathcal {F}}\ll \lambda _{\mathcal {F}}\) and \(\nu _{\mathcal {F}}\ll \lambda _{\mathcal {F}}\).
2. What is \(f_\mu =\frac {d\mu _{\mathcal {F}}}{d\lambda _{\mathcal {F}}}\) in terms of \(\frac {d\mu }{d\lambda }\)? Of course, a similar relationship holds for \(f_\nu =\frac {d\nu _{\mathcal {F}}}{d\lambda _{\mathcal {F}}}\).
3. For a bounded \(\mathcal {B}(\mathbb {R})\)-measurable function \(g\), compute \(\mathbb {E}^\lambda [g\mid \mathcal {F}]\) in terms of \(\mathbb {E}^\mu [g\mid \mathcal {F}]\), \(\mathbb {E}^\nu [g\mid \mathcal {F}]\), \(f_\mu \), and \(f_\nu \)?

A particular gene occurs as one of two alleles (\(A\) and \(a\)), with allele \(A\) having frequency \(\theta \) in the population. In other words, a random copy of the gene is \(A\) with probability \(\theta \) and \(a\) with probability \(1-\theta \). A diploid genotype is just two genes put together (in any particular order) so the probability of each diploid genotype is \(\theta ^2\) for \(AA\), \(2\theta (1-\theta )\) for \(Aa\), and \((1-\theta )^2\) for \(aa\). Suppose we test a random sample of people and find that \(k_1\) of them are \(AA\), \(k_2\) of them are \(Aa\), and \(k_3\) of them are \(aa\). Find the MLE of \(\theta \).

Let \(X_1,X_2,\ldots \) be independent random variables, and suppose that \(p_i:=\mathbb {P}\{X_i=0\}\) satisfies \(0<p_i<1\) for every \(i=1,2,\ldots \). For every \(n\geq 1\) let \[ N_n:=\sum _{i=1}^{n}\mathbf {1}_{\{X_i=0\}} \] denote the number of times the finite random sequence \(X_1,\ldots ,X_n\) enters zero. Prove that \[ \frac {N_n}{\sum _{i=1}^{n}p_i}\to 1 \qquad \text {in probability as }n\to \infty . \]

Let \(X_1,X_2,\ldots \) be a collection of i.i.d. random variables, taking values \(\pm 1\) with probability \(1/2\) each. Define \(S_n:=X_1+\cdots +X_n\) for all \(n\geq 1\), \(T_0:=0\), and then iteratively define \[ T_{k+1}:=\inf \{n>T_k:S_n=0\} \qquad [\inf \emptyset :=\infty ]\quad \text {for all }k\geq 0. \] That is, \(T_k\) denotes the \(k\)th return time to zero. Prove that \(\lim _{k\to \infty }(T_k/k)=\infty \) a.s.

Let \(n\geq 1\) be a fixed integer and recall that there are \(n!\) permutations of \([n]:=\{1,\ldots ,n\}\). Let \(\sigma :=\{\sigma (1),\ldots ,\sigma (n)\}\) denote an arbitrary permutation of \([n]\), and choose and fix some integer \(j\in [n]\). We say that \(\sigma \) fixes \(j\) if \(\sigma (j)=j\). Now suppose that \(\sigma \) is selected at random, all permutations of \([n]\) equally likely.

(a) What is the probability that \(\sigma \) fixed \(j\)?

(b) What is the expectation of the number of integers in \([n]\) that are fixed by \(\sigma \)?

Let \(X_1,\ldots ,X_n\) be iid Uniform\((0,\theta )\) with \(\theta >0\), and \(X_{(n)}\) be the largest order statistic.

(a) Find the probability that the random interval \((X_{(n)},2X_{(n)})\) contains \(\theta \).

(b) Find the constant \(c\) such that \((X_{(n)},cX_{(n)})\) is a \(100(1-\alpha )\%\) confidence interval for \(\theta \).

Let \(\{e_i,-\infty <i<\infty \}\) be independent and identically distributed random variables with \(\mathbb {E}[e_1]=0\) and \(\mathbb {E}[e_1^2]=\sigma ^2\) and \(\rho \) be a real number satisfying \(|\rho |<1\). Show that \[ Y=\sum _{i=0}^{\infty }\rho ^i e_i \] is finite with probability one. Compute \(\mathbb {E}[Y]\) and \(\mathbb {E}[Y^2]\). (You need to justify your steps when you compute these two expected values.)

Let \(X_1,X_2,\ldots \) be independent and identically distributed random variables with \(\mathbb {E}\log (1+|X_1|)<\infty \). Show that \[ \sum _{i=1}^{\infty }\prod _{j=1}^{i}X_j \] is finite with probability one if and only if \(\mathbb {E}\log |X_1|<0\).

Let \(f\) be a continuous element of \(L^1(\mathbb {R})\), and recall that its Fourier transform is \[ \hat {f}(t):=\int _{-\infty }^{\infty }\exp (itx)f(x)\,dx. \]

(a) Suppose also that \(\hat {f}\in L^1(\mathbb {R})\). Prove the following [inversion formula]: \[ f(x)=\frac {1}{2\pi }\int _{-\infty }^{\infty }e^{-ixt}\hat {f}(t)\,dt \qquad \text {for all }x\in \mathbb {R}. \] In other words, \(\widehat {\widehat {f}}(-x)=2\pi f(x)\) for all \(x\in \mathbb {R}\).

(b) Choose and fix some \(\theta >0\). Use the preceding to prove that the Fourier transform of the probability density function \[ f(x):=\frac {\theta }{\pi (\theta ^2+x^2)} \qquad [-\infty <x<\infty ] \] is \(\hat {f}(t)=\exp (-\theta |t|)\).

Suppose \(\mu \) is a probability measure on the Borel subsets of \((0,1)\) such that \[ \int |\ln (x)|\,\mu (dx)<\infty . \] Prove that \[ I(n):=\left (\int x^{1/n}\,\mu (dx)\right )^n \to \exp \left (\int \ln (x)\,\mu (dx)\right ) \qquad \text {as } n\to \infty . \]

[Hint: \(I(n)=\mathbb {E}\left (\prod _{j=1}^{n}X_j^{1/n}\right )\), where \(X_1,\ldots ,X_n\) are i.i.d.]

Let \(X_1,X_2,\ldots \) be i.i.d. with mean \(\mu \) and finite variance. Show that \[ U_n:=\binom {n}{2}^{-1}\sum _{1\leq i<j\leq n}X_iX_j \] converges in probability to \(\mu ^2\) as \(n\to \infty \).

Consider a deck of \(n\) cards labeled \(1,2,\ldots ,n\). Assume it is well shuffled with every possible arrangement equally likely. Let \(E_n\) be the event that card \(j\) is in position \(j\) in the shuffled deck for some \(j\in \{1,2,\ldots ,n\}\). Evaluate \(\mathbb {P}(E_n)\) using inclusion-exclusion and show that \(\lim _{n\to \infty }\mathbb {P}(E_n)=1-e^{-1}\).

Let \(X_1\) and \(X_2\) be independent, each with probability density function \(f(x)=1/x^2\), \(x>1\). Find the joint probability density function of \(Y_1=X_1X_2\) and \(Y_2=X_1/X_2\). It is important to state where your formula is valid. (If you have time, check that your joint pdf integrates to 1; if it doesn’t, find the error.)

Let \(X_1,X_2,X_3,Y_1,Y_2,Y_3\) be independent \(N(0,1)\) random variables. Let \(P_1\), \(P_2\), and \(P_3\) be the points in the plane with coordinates \((X_1,Y_1)\), \((X_2,Y_2)\), and \((X_3,Y_3)\). Let \(M\) be the midpoint of the segment \(P_1P_2\) and let \(r\) be half its length. Show that the probability that the point \(P_3\) lies within the circle of radius \(r\) centered at \(M\) is equal to \(1/4\).

Suppose \(f\) is a probability density function on \(\mathbf {R}\), and define for all \(x,y\in \mathbf {R}\), \[ g(x,y):= \begin {cases} 2f(x)f(y), & \text {if } x\leq y,\\ 0, & \text {otherwise.} \end {cases} \] (a) Prove that \(g\) is the probability density function of some random variable \((X,Y)\) which takes values in \(\mathbf {R}^2\).

(b) Are \(X\) and \(Y\) independent? Prove or disprove.

A die is thrown 10 times. What is the probability that the sum of the scores in 27?

Hint: Use probability generating functions.

Let \(X_1,X_2,\ldots \) and \(Y_1,Y_2,\ldots \) denote random variables on a common probability space. Suppose \(X_n\) converges to 0 in probability as \(n\to \infty \), and \(Y_n\) converges to \(Y\) weakly. Prove that \((X_n,Y_n)\) converges weakly to \((0,Y)\).

Construct three random variables \(X,Y,Z\) such that \[ \mathbb {E}[\mathbb {E}[X\mid Y]\mid Z]\neq \mathbb {E}[\mathbb {E}[X\mid Z]\mid Y] \] with positive probability.

Construct an example of a sequence \(\{A_n\}_{n=1}^{\infty }\) such that:

(a) (i) \(\sum _n\mathbb {P}(A_n)=\infty \); and (ii) only finitely-many of the \(A_n\)’s occur with positive probability.

(b) (i) \(\sum _n\mathbb {P}(A_n)=\infty \); and (ii) infinitely-many of the \(A_n\)’s occur with positive probability.

Suppose \(X_1,X_2,\ldots \) have common mean \(\mu \) and variances \(\sigma _1^2,\sigma _2^2,\ldots \). Prove that if \(\sup _n\sigma _n^2<\infty \) and \(\lim _{|i-j|\to \infty }\mathbb {E}[X_iX_j]=0\), then \((X_1+\cdots +X_n)/n\) converges to \(\mu \) in probability.

Prove that whenever \(X_n\Rightarrow X\) and \(Y_n\to c\) in probability for a non-random \(c>0\), then \(X_n/Y_n\Rightarrow c^{-1}X\). Use this to prove the following: If \(\xi _1,\xi _2,\ldots \) are i.i.d. with \(\mathbb {E}[\xi _1]=\mu \) and \(\operatorname {Var}(\xi _1)=\sigma ^2\) then \[ \frac {S_n-n\mu }{\sqrt {\sum _{i=1}^{n}(\xi _i-\bar {\xi }_n)^2}} \Rightarrow N(0,1). \] where \(S_n=\xi _1+\cdots +\xi _n\), and \(\bar {\xi }_n=S_n/n\).

A sequence \(X_1,X_2,\ldots \) of random variables is said to be uniformly integrable if \[ \lim _{c\to \infty }\sup _{n\ge 1}\mathbb {E}\{|X_n|;\ |X_n|>c\}=0. \] Prove that \(X_n\to X\) in \(L^1(\mathbb {P})\) if and only if both of the following happen: (i) \(X_n\to X\) in probability; and (ii) \(\{X_n\}_{n=1}^{\infty }\) is uniformly integrable.

Choose and fix an integer \(n\ge 1\). For all continuous functions \(f:[0,1]\to \mathbb {R}\) define \[ B_nf(p)=\sum _{k=0}^{n}\binom {n}{k}p^k(1-p)^{n-k}f(k/n), \qquad \text {for all }p\in [0,1]. \] [ \(B_nf\) is the Bernstein polynomial of \(f\).] Prove that if \(f\) is increasing, then so is \(B_nf\).

Suppose \(\{X_n\}_{n=1}^{\infty }\) and \(\{Y_n\}_{n=1}^{\infty }\) are random variables on the same probability space \((\Omega ,\mathcal {F},\mathbb {P})\). Suppose also that \(X_n\Rightarrow X\) and \(Y_n\Rightarrow Y\). True or false: \((X_n,Y_n)\Rightarrow (X,Y)\). [If true, then prove it. If false, then construct a counter-example.]

A thinker who owns \(r\) umbrellas travels back and forth between home and office, taking along an umbrella (if there is one at hand) in rain (probability \(p\)) but not otherwise (probability \(q=1-p\)). Let the state be the number of umbrellas at hand, irrespective of whether the thinker is at home or at work. Set up the transition matrix, and show that the Markov chain approaches equilibrium (i.e., the ergodic theorem is applicable). Find the steady-state probability of his getting wet, and show that five umbrellas will protect him at the \(5\%\) level against any climate (any \(p\)).

A thinker who owns \(r\) umbrellas travels back and forth between home and office, taking along an umbrella (if there is one at hand) in rain (probability \(p\)) but not otherwise (probability \(q=1-p\)). Let the state be the number of umbrellas at hand, irrespective of whether the thinker is at home or at work. Set up the transition matrix, and show that the Markov chain approaches equilibrium (i.e., the ergodic theorem is applicable). Find the steady-state probability of his getting wet, and show that five umbrellas will protect him at the \(5\%\) level against any climate (any \(p\)).