数据科学基础 (Fall 2025)/Problem Set 4

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

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

• 没有条件的同学可以用纸笔完成作业之后拍照。

Assumption throughout Problem Set 4

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

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

Problem 1 (Moments and (co)variances)

• [Run] A biased coin is tossed [math]\displaystyle{ n }[/math] times, and heads shows with probability [math]\displaystyle{ p }[/math] on each toss. A run is a sequence of throws which result in the same outcome, so that, for example, the sequence HHTHTTH contains five runs.
  1. Find the expectation and the variance of the number of runs.
  2. Let [math]\displaystyle{ h }[/math] heads and [math]\displaystyle{ t }[/math] tails be arranged randomly in a line. Find the mean and variance of the number of runs of heads.
• [Gambler Lester Savage] The gambler Lester Savage makes up to three successive bets that a fair coin flip will show heads. He places a stake on each bet, which, if a head is shown, pays him back twice the stake. If a tail is shown, he loses his stake. His stakes are determined as follows. Let [math]\displaystyle{ x \gt y \gt z \gt 0 }[/math]. He bets x on the first flip; if it shows heads he quits, otherwise he continues. If he continues, he bets [math]\displaystyle{ y }[/math] on the second flip; if it shows heads he quits, otherwise he continues. If he continues, he bets [math]\displaystyle{ z }[/math] on the third flip. Let [math]\displaystyle{ G }[/math] be his accumulated gain (positive or negative).
  1. List the possible values of [math]\displaystyle{ G }[/math] and their probabilities. Show that [math]\displaystyle{ \mathbb E(G)= 0 }[/math], and find [math]\displaystyle{ \mathrm{Var}(G) }[/math]and [math]\displaystyle{ \Pr(G \lt 0) }[/math].
  2. Lester decides to stick with the three numbers [math]\displaystyle{ x, y, z }[/math] but to vary their order. How should he place his bets in order to simultaneously minimize both [math]\displaystyle{ \Pr(G \lt 0) }[/math] and [math]\displaystyle{ \mathrm{Var}(G) }[/math]? Explain.
• [Moments] Let [math]\displaystyle{ X }[/math] have mass function

[math]\displaystyle{ f(x)=\begin{cases}1/(x(x+1)) & \text{if }x=1,2,\dots,\\ 0 &\text{otherwise,}\end{cases} }[/math]

and let [math]\displaystyle{ \alpha\in\mathbb R }[/math]. For what values of [math]\displaystyle{ \alpha }[/math] is it the case that [math]\displaystyle{ \mathbb E[X^\alpha]\lt \infty }[/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]\displaystyle{ X, Y , Z }[/math] be non-degenerate and independent random variables. By considering [math]\displaystyle{ U= X + Y , V= Y + Z, W= Z− X }[/math], or otherwise, show that having positive correlation is not a transitive relation.
• [Uncorrelation versus Independence] Suppose [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] take values in [math]\displaystyle{ \{0,1\} }[/math], with joint mass function [math]\displaystyle{ f (x,y) }[/math]. Write [math]\displaystyle{ f (0,0)= a, f (0,1)= b, f (1,0)= c, f (1,1)= d }[/math], and find necessary and sufficient conditions for [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] to be: (a) uncorrelated, (b) independent.
• [Covariance Matrix] Let [math]\displaystyle{ \mathbf X= (X_1,X_2,...,X_n) }[/math] be a vector of random variables. The covariance matrix [math]\displaystyle{ \mathbf V(\mathbf X) }[/math] of [math]\displaystyle{ \mathbf X }[/math] is defined to be the symmetric [math]\displaystyle{ n }[/math] by [math]\displaystyle{ n }[/math] matrix with entries [math]\displaystyle{ (v_{i j} : 1 \le i,j \le n) }[/math] given by [math]\displaystyle{ v_{ij}= \mathrm{cov}(X_i ,X_j ) }[/math]. Show that [math]\displaystyle{ |\mathbf V(\mathbf X)| = 0 }[/math] if and only if the [math]\displaystyle{ X_i }[/math] are linearly dependent with probability one, in that [math]\displaystyle{ \Pr(a_1 X_1 + a_2 X_2 + \dots + a_n X_n = b)= 1 }[/math] for some [math]\displaystyle{ \mathbf a }[/math] and [math]\displaystyle{ b }[/math]. ([math]\displaystyle{ |\mathbf V| }[/math] denotes the determinant of [math]\displaystyle{ \mathbf V }[/math].)
• [Conditional variance formula]
  1. How should we define [math]\displaystyle{ \mathrm{Var}(Y | X) }[/math], the conditional variance of [math]\displaystyle{ Y }[/math] given [math]\displaystyle{ X }[/math]? Show that [math]\displaystyle{ \mathrm{Var}(Y )= \mathbb E[\mathrm{Var}(Y | X)]+ \mathrm{Var}(\mathbb E[Y | X]) }[/math].
  2. Let [math]\displaystyle{ X_1,X_2,\dots }[/math] be identically distributed random variables with mean [math]\displaystyle{ \mu }[/math] and variance [math]\displaystyle{ \sigma^2 }[/math], and let [math]\displaystyle{ N }[/math] be a random variable taking values in the non-negative integers and independent of the [math]\displaystyle{ X_i }[/math] . Let [math]\displaystyle{ S= X_1 + X_2 + \dots + X_N }[/math] . Show that [math]\displaystyle{ \mathbb E(S | N)= \mu N }[/math], and deduce that [math]\displaystyle{ \mathbb E(S)= \mu \mathbb E(N) }[/math]. Find [math]\displaystyle{ \mathrm{Var}(S) }[/math] in terms of the first two moments of [math]\displaystyle{ N }[/math], using the conditional variance formula.

Problem 2 (Markov and Chebyshev)

• [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{ \Pr[X\geq x]\leq \mathbb{E}[e^{\beta X}]e^{-\beta x} }[/math].
• [Chebyshev's inequality (i) (Cantelli's inequality)] Show that [math]\displaystyle{ \Pr[X-\mathbb E[X]\gt t]\le\frac{\mathrm{Var}(X)}{t^2+\mathrm{Var}(X)}, \forall t\gt 0. }[/math]
• [Chebyshev's inequality (ii) (Paley–Zygmund inequality)]

1. Let [math]\displaystyle{ X }[/math] be a random variable with [math]\displaystyle{ \mathbb E[X]\gt 0 }[/math] and [math]\displaystyle{ 0 \lt \mathbb E[X^2]\lt \infty }[/math]. Show that [math]\displaystyle{ \Pr[X \gt a\cdot\mathbb E[X]]\ge \frac{(1− a)^2\cdot \mathbb E[X]^2}{ \mathbb E[X^2]} }[/math] for [math]\displaystyle{ 0 \le a \le 1 }[/math].
2. Deduce that, if [math]\displaystyle{ \Pr[X \ge 0]= 1 }[/math], then [math]\displaystyle{ \Pr[X= 0]\le\frac{\mathrm{Var}(X)}{\mathbb E[X^2]} \le \frac{\mathrm{Var}(X)}{\mathbb E[X]^2} }[/math].
3. Let [math]\displaystyle{ A_1,A_2,\dots,A_n }[/math] be events, and let [math]\displaystyle{ X= \sum^n_{r=1} I_{A_r} }[/math] be the sum of their indicator functions. Show that [math]\displaystyle{ \Pr[X= 0]\le \frac 1{\mathbb E[X]} + \frac 1 {\mathbb E[X]^2}\sum^∗ \Pr[A_r \cap A_s ] }[/math], where the summation [math]\displaystyle{ \sum^∗ }[/math] is over all distinct unordered pairs [math]\displaystyle{ r, s }[/math] such that [math]\displaystyle{ A_r }[/math] and [math]\displaystyle{ A_s }[/math] are not independent.