# 概率论与数理统计 (Spring 2023)/Problem Set 3

• 每道题目的解答都要有完整的解题过程，中英文不限。
• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

## Assumption throughout Problem Set 3

Without further notice, we are working on probability space $\displaystyle{ (\Omega,\mathcal{F},\mathbf{Pr}) }$.

Without further notice, we assume that the expectation of random variables are well-defined.

The term $\displaystyle{ \log }$ used in this context refers to the natural logarithm.

## Problem 1 (Warm-up Problems)

• [Variance (I)] Let $\displaystyle{ X_1,X_2,\cdots, X_n }$ be pairwise independent random variables. Show that $\displaystyle{ \textbf{Var}\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n \textbf{Var} [X_i] }$.
• [Variance (II)] Each member of a group of $\displaystyle{ n }$ players rolls a (fair) die. For any pair of players who throw the same number, the group scores $\displaystyle{ 1 }$ point. Find the mean and variance of the total score of the group.
• [Variance (III)] An urn contains $\displaystyle{ n }$ balls numbered $\displaystyle{ 1, 2, \ldots, n }$. We select $\displaystyle{ k }$ balls uniformly at random without replacement and add up their numbers. Find the mean and variance of the sum.
• [Variance (IV)] Let $\displaystyle{ N }$ be an integer-valued, positive random variable and let $\displaystyle{ \{X_i\}_{i=1}^{\infty} }$ be indepedently identically distributed random variables that are independent of $\displaystyle{ N }$, too. Precisely, for any finite subset $\displaystyle{ I \subseteq\mathbb{N}_+ }$, $\displaystyle{ \{X_i\}_{i \in I} }$ and $\displaystyle{ N }$ are mutually independent. Let $\displaystyle{ X = \sum_{i=1}^N X_i }$, show that $\displaystyle{ \textbf{Var}[X] = \textbf{Var}[X_1] \mathbb{E}[N] + \mathbb{E}[X_1]^2 \textbf{Var}[N] }$.
• [Moments (I)] Find an example of a random variable with finite $\displaystyle{ j }$-th moments for $\displaystyle{ 1 \leq j \leq k }$ but an unbounded $\displaystyle{ (k + 1) }$-th moment. Give a clear argument showing that your choice has these properties.
• [Moments (II)] Let $\displaystyle{ X\sim \text{Geo}(p) }$ for some $\displaystyle{ p \in (0,1) }$. Find $\displaystyle{ \mathbb{E}[X^3] }$ and $\displaystyle{ \mathbb{E}[X^4] }$.
• [Moments (III)] Let $\displaystyle{ X\sim \text{Pois}(\lambda) }$ for some $\displaystyle{ \lambda \gt 0 }$. Find $\displaystyle{ \mathbb{E}[X^3] }$ and $\displaystyle{ \mathbb{E}[X^4] }$.
• [Covariance and correlation (I)] Let $\displaystyle{ X }$ and $\displaystyle{ Y }$ be discrete random variables with correlation $\displaystyle{ \rho }$. Show that $\displaystyle{ |\rho|\leq 1 }$.
• [Covariance and correlation (II)] Let $X$ and $Y$ be discrete random variables with mean $\displaystyle{ 0 }$, variance $\displaystyle{ 1 }$, and correlation $\rho$. Show that $\mathbb{E}(\max\{X^2,Y^2\})\leq 1+\sqrt{1-\rho^2}$. (Hint: use the identity $\max\{a,b\} = \frac{1}{2}(a+b+|a-b|)$.)
• [Covariance and correlation (III)] Construct two random variables $X$ and $Y$ such that their covariance $\textbf{Cov}(X,Y) = 0$ but $X$ and $Y$ are not independent. You should prove your construction is true.

## Problem 2 (Inequalities)

• [Reverse Markov's inequality] Let $\displaystyle{ X }$ be a discrete random variable with bounded range $\displaystyle{ 0 \le X \le U }$ for some $\displaystyle{ U \gt 0 }$. Show that $\displaystyle{ \mathbf{Pr}(X \le a) \le \frac{U-\mathbf{E}[X]}{U-a} }$ for any $\displaystyle{ 0 \lt a \lt U }$.
• [Markov's inequality] Let $\displaystyle{ X }$ be a discrete random variable. Show that for all $\displaystyle{ \beta \geq 0 }$ and all $\displaystyle{ x \gt 0 }$, $\displaystyle{ \mathbf{Pr}(X\geq x)\leq \mathbb{E}(e^{\beta X})e^{-\beta x} }$.
• [Cantelli's inequality] Let $\displaystyle{ X }$ be a discrete random variable with mean $\displaystyle{ 0 }$ and variance $\displaystyle{ \sigma^2 }$. Prove that for any $\displaystyle{ \lambda \gt 0 }$, $\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2}{\lambda^2+\sigma^2} }$. (Hint: You may first show that $\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2 + u^2}{(\lambda + u)^2} }$ for all $\displaystyle{ u \gt 0 }$.)
• [The weak law of large numbers] Let $\displaystyle{ X_1,X_2,\cdots, X_n }$ be independent and identically distributed random variables with mean $\displaystyle{ \mu }$ and finite variance, use Chebyshev's inequality to show that for any constant $\displaystyle{ \epsilon\gt 0 }$ we have $\displaystyle{ \lim_{n\rightarrow \infty} \mathbf{Pr}\left( \left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu\right| \gt \epsilon\right) = 0 }$.
• [Median trick] Suppose we want to estimate the value of $\displaystyle{ Z }$. Let $\displaystyle{ \mathcal{A} }$ be a randomized algorithm that outputs $\displaystyle{ \widehat{Z} }$ satisfying $\displaystyle{ \mathbf{Pr}[(1-\epsilon) Z \leq \widehat{Z} \leq (1+\epsilon)Z]\geq \frac{3}{4} }$ for some fixed parameter $\displaystyle{ \epsilon \gt 0 }$. We run $\displaystyle{ \mathcal{A} }$ independently for $\displaystyle{ 2n-1 }$ times, and obtain the outputs $\displaystyle{ \widehat{Z}_1, \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1} }$. Let $\displaystyle{ X }$ be the median (中位数) of $\displaystyle{ \widehat{Z}_1, \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1} }$. Use Chebyshev's inequality to show that $\displaystyle{ \mathbf{Pr}[(1-\epsilon) Z \leq X \leq (1+\epsilon)Z] = 1 - O(1/n) }$. (Remark: The bound can be drastically improved with Chernoff bound).

## Problem 3 (Probability meets graph theory)

• [Common neighbor] Let $\displaystyle{ p \in (0,1) }$ be a constant. Show that with a probability approaching to $\displaystyle{ 1 }$ (as $\displaystyle{ n }$ tends to infinity) the Erdős–Rényi random graph $\displaystyle{ \mathbf{G}(n,p) }$ has the property that every pair of its vertices has a common neighbor. (Hint: You may use Markov's inequality.)
• [Isolated vertices] Prove that $\displaystyle{ p = \log n/n }$ is the threshold probability for the disappearance of isolated vertices. Formally, you are required to show that
1. with a probability approaching to $\displaystyle{ 1 }$ (as $\displaystyle{ n }$ tends to infinity) the Erdős–Rényi random graph $\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }$ has the property that $\displaystyle{ \mathbf{G} }$ has no isolated vertices when $\displaystyle{ p = \omega(\log n/n) }$;
2. with a probability approaching to $\displaystyle{ 0 }$ (as $\displaystyle{ n }$ tends to infinity) the Erdős–Rényi random graph $\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }$ has the property that $\displaystyle{ \mathbf{G} }$ has no isolated vertices when $\displaystyle{ p = o(\log n/n) }$.