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

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

• 为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

• 若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

Assumption throughout Problem Set 3

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

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

The term [math]\displaystyle{ \log }[/math] used in this context refers to the natural logarithm.

Problem 1 (Warm-up Problems)

• [Variance (I)] Let [math]\displaystyle{ X_1,X_2,...,X_n }[/math] be independent random variables, and suppose that [math]\displaystyle{ X_k }[/math] is Bernoulli with parameter [math]\displaystyle{ p_k }[/math]. Let [math]\displaystyle{ Y= X_1 + X_2 + \dots + X_n }[/math]. Show that, for [math]\displaystyle{ \mathbb E[Y] }[/math] fixed, [math]\displaystyle{ \mathrm{Var}(Y ) }[/math] is a maximized when [math]\displaystyle{ p_1 = p_2 = \dots = p_n }[/math]. That is to say, the variation in the sum is greatest when individuals are most alike.
• [Variance (II)] Each member of a group of [math]\displaystyle{ n }[/math] players rolls a (fair) 6-sided die. For any pair of players who throw the same number, the group scores [math]\displaystyle{ 1 }[/math] point. Find the mean and variance of the total score of the group.
• [Variance (III)] An urn contains [math]\displaystyle{ n }[/math] balls numbered [math]\displaystyle{ 1, 2, \ldots, n }[/math]. We select [math]\displaystyle{ k }[/math] balls uniformly at random without replacement and add up their numbers. Find the mean and variance of the sum.
• [Variance (IV)] Let [math]\displaystyle{ N }[/math] be an integer-valued, positive random variable and let [math]\displaystyle{ \{X_i\}_{i=1}^{\infty} }[/math] be indepedently identically distributed random variables that are independent of [math]\displaystyle{ N }[/math], too. Precisely, for any finite subset [math]\displaystyle{ I \subseteq\mathbb{N}_+ }[/math], [math]\displaystyle{ \{X_i\}_{i \in I} }[/math] and [math]\displaystyle{ N }[/math] are mutually independent. Let [math]\displaystyle{ X = \sum_{i=1}^N X_i }[/math], show that [math]\displaystyle{ \textbf{Var}[X] = \textbf{Var}[X_1] \mathbb{E}[N] + \mathbb{E}[X_1]^2 \textbf{Var}[N] }[/math].
• [Moments (I)] Show that [math]G(t) = \frac{e^t}{4} + \frac{e^{-t}}{2} + \frac{1}{4}[/math] is a moment-generating function of a random variable, and write the probability mass function of this random variable.
• [Moments (II)] Let [math]\displaystyle{ X\sim \text{Geo}(p) }[/math] for some [math]\displaystyle{ p \in (0,1) }[/math]. Find [math]\displaystyle{ \mathbb{E}[X^3] }[/math] and [math]\displaystyle{ \mathbb{E}[X^4] }[/math].
• [Moments (III)] Let [math]\displaystyle{ X\sim \text{Pois}(\lambda) }[/math] for some [math]\displaystyle{ \lambda \gt 0 }[/math]. Find [math]\displaystyle{ \mathbb{E}[X^3] }[/math] and [math]\displaystyle{ \mathbb{E}[X^4] }[/math].
• [Covariance and correlation (I)] Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be discrete random variables with correlation [math]\displaystyle{ \rho }[/math]. Show that [math]\displaystyle{ |\rho|= 1 }[/math] if and only if [math]\displaystyle{ X=aY+b }[/math] for some real numbers [math]\displaystyle{ a,b }[/math].
• [Covariance and correlation (II)] Let [math]X[/math] and [math]Y[/math] be discrete random variables with mean [math]\displaystyle{ 0 }[/math], variance [math]\displaystyle{ 1 }[/math], and correlation [math]\rho[/math]. Show that [math]\mathbb{E}(\max\{X^2,Y^2\})\leq 1+\sqrt{1-\rho^2}[/math]. (Hint: use the identity [math]\max\{a,b\} = \frac{1}{2}(a+b+|a-b|)[/math].)
• [Covariance and correlation (III)] Let [math]X[/math] and [math]Y[/math] be independent Bernoulli random variables with parameter [math]1/2[/math]. Show that [math]X+Y[/math] and [math]|X-Y|[/math] are dependent though uncorrelated.

Problem 2 (Inequalities)

• [Reverse Markov's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable with bounded range [math]\displaystyle{ 0 \le X \le U }[/math] for some [math]\displaystyle{ U \gt 0 }[/math]. Show that [math]\displaystyle{ \mathbf{Pr}(X \le a) \le \frac{U-\mathbf{E}[X]}{U-a} }[/math] for any [math]\displaystyle{ 0 \lt a \lt U }[/math].
• [Markov's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable. Show that for all [math]\displaystyle{ \beta \geq 0 }[/math] and all [math]\displaystyle{ x \gt 0 }[/math], [math]\displaystyle{ \mathbf{Pr}(X\geq x)\leq \mathbb{E}(e^{\beta X})e^{-\beta x} }[/math].
• [Cantelli's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable with mean [math]\displaystyle{ 0 }[/math] and variance [math]\displaystyle{ \sigma^2 }[/math]. Prove that for any [math]\displaystyle{ \lambda \gt 0 }[/math], [math]\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2}{\lambda^2+\sigma^2} }[/math]. (Hint: You may first show that [math]\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2 + u^2}{(\lambda + u)^2} }[/math] for all [math]\displaystyle{ u \gt 0 }[/math].)
• [Chebyshev's inequality] Fix [math]\displaystyle{ 0 \lt b \le a }[/math]. Construct a random variable [math]\displaystyle{ X }[/math] with [math]\displaystyle{ \mathbb{E}[X^2] = b^2 }[/math] for which [math]\displaystyle{ \mathbf{Pr}(|X| \ge a) = b^2/a^2 }[/math].
• [Chernoff bound] Let [math]\displaystyle{ X_1,...,X_n }[/math] be independent Poisson trials. Let [math]\displaystyle{ X=\sum \limits_{i=1}^n X_i }[/math] and [math]\displaystyle{ \mu=\mathbb{E}[X] }[/math]. Prove that for any [math]\displaystyle{ \delta\gt 0 }[/math],

  [math]\displaystyle{ \mathbf{Pr}[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}. }[/math]

Problem 3 (Probability meets distinct sums)

Let [math]\displaystyle{ f(n) }[/math] denote the maximal [math]\displaystyle{ m }[/math] such that there exists a set of [math]\displaystyle{ m }[/math] distinct numbers [math]\displaystyle{ \{x_1,x_2,\ldots,x_m\} }[/math] in [math]\displaystyle{ [n] = \{1,2,\ldots,n\} }[/math] all of whose sums are distinct. Namely, [math]\displaystyle{ \sum_{i \in S} x_i }[/math] are distinct for all [math]\displaystyle{ S \subseteq \{1,2,\ldots,m\} }[/math]. Use the second moment method (i.e., Chebyshev's inequality) to show that [math]\displaystyle{ f(n) \le \log_2 n + \frac{1}{2} \log_2 \log_2 n + O(1) }[/math]. (Remark: Erdös' first open problem asks if [math]\displaystyle{ f(n) \le \log_2 n + C }[/math] for some universal constant [math]\displaystyle{ C }[/math].)

Problem 4 (Chernoff bound vs k-th moment method)

Let [math]\displaystyle{ X }[/math] be a random variable such that the moment generating function [math]\displaystyle{ \mathbf{E}[e^{t|X|}] }[/math] is finite for some [math]\displaystyle{ t \gt 0 }[/math]. We can use the following two kinds of tail inequalities for [math]\displaystyle{ X }[/math].

Chernoff Bound: [math]\displaystyle{ \mathbf{Pr}[|X| \ge \delta] \le \min_{t \ge 0} \frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}}. }[/math]


kth-Moment Bound:

[math]\displaystyle{ \mathbf{Pr}[|X| \ge \delta] \le \frac{\mathbf{E}[|X|^k]}{\delta^k}. }[/math]


(a) Prove that for each [math]\displaystyle{ \delta\gt 0 }[/math], there is a choice of [math]\displaystyle{ k \in \mathbb{Z}_{\ge 0} }[/math] such that the [math]\displaystyle{ k }[/math]-th moment bound is at least as strong as the Chernoff bound.

(Hint: Consider the Taylor expansion of the moment generating function.)

(b) Why do we still prefer to use the Chernoff bound rather than the [math]\displaystyle{ k }[/math]-th moment bound in algorithmic analysis?