数据科学基础 (Fall 2024)/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 (ii)] 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 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.

• [Random sum (ii)] Let [math]\displaystyle{ S= \sum^N_{i=1} X_i }[/math] , where the [math]\displaystyle{ X_i, i \ge 1, }[/math] are independent, identically distributed random variables with mean [math]\displaystyle{ \mu }[/math] and variance [math]\displaystyle{ \sigma^2 }[/math], and [math]\displaystyle{ N }[/math] is positive, integer-valued, and independent of the [math]\displaystyle{ X_i }[/math] . Show that [math]\displaystyle{ \mathrm{Var}(S)= \sigma^2\cdot\mathbb E[N]+ \mu^2\cdot\mathrm{Var}(N) }[/math].
• [Maximum variance] 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] . Show that [math]\displaystyle{ Y= X_1 + X_2 + \dots + X_n }[/math] has mean and variance given by [math]\displaystyle{ \mathbb E[Y ]= \sum^n_1 p_k , \mathrm{Var}(Y )= \sum^n_1 p_k (1− p_k ) }[/math]. Show that, for [math]\displaystyle{ \mathbb E[Y] }[/math] fixed, [math]\displaystyle{ \mathrm{Var}(Y ) }[/math] is a maximum 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. Is this contrary to intuition?
• [Moments (i)] 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\ge\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]?

• [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].
• [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.
• [Berkson’s fallacy] Any individual in a group [math]\displaystyle{ G }[/math] contracts a certain disease [math]\displaystyle{ C }[/math] with probability [math]\displaystyle{ \gamma }[/math]; such individuals are hospitalized with probability [math]\displaystyle{ c }[/math]. Independently of this, anyone in [math]\displaystyle{ G }[/math] may be in hospital with probability [math]\displaystyle{ a }[/math], for some other reason. Let [math]\displaystyle{ X }[/math] be the number in hospital, and [math]\displaystyle{ Y }[/math] the number in hospital who have [math]\displaystyle{ C }[/math] (including those with [math]\displaystyle{ C }[/math] admitted for any other reason). Show that the correlation between [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] is [math]\displaystyle{ \rho(X,Y )=\sqrt{\frac{\gamma p}{1-\gamma p}\cdot\frac{(1-a)(1-\gamma c)}{a+\gamma c-a\gamma c}} }[/math], where [math]\displaystyle{ p= a + c− ac }[/math]. It has been stated erroneously that, when [math]\displaystyle{ \rho(X,Y ) }[/math] is near unity, this is evidence for a causal relation between being in [math]\displaystyle{ G }[/math] and contracting [math]\displaystyle{ C }[/math].
• [Correlation and independence] Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be independent Bernoulli random variables with parameter [math]\displaystyle{ 1/2 }[/math] . Show that [math]\displaystyle{ X + Y }[/math] and [math]\displaystyle{ |X− Y | }[/math] are dependent though uncorrelated.
• [Conditional variance formula] 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].
• [Conditional covariance] Give a definition of the conditional covariance [math]\displaystyle{ \mathrm{Cov}(X,Y | Z) }[/math]. Show that [math]\displaystyle{ \mathrm{Cov}(X,Y )= \mathbb E[ \mathrm{Cov}(X,Y | Z)] + \mathrm{Cov} (\mathbb E[X | Z], \mathbb E[Y | Z]) }[/math] .

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.

Problem 3 (Random graphs)

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

1. with a probability approaching to [math]\displaystyle{ 1 }[/math] (as [math]\displaystyle{ n }[/math] tends to infinity) the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }[/math] has the property that [math]\displaystyle{ \mathbf{G} }[/math] has no isolated vertices when [math]\displaystyle{ p = \omega(\log n/n) }[/math];
2. with a probability approaching to [math]\displaystyle{ 0 }[/math] (as [math]\displaystyle{ n }[/math] tends to infinity) the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }[/math] has the property that [math]\displaystyle{ \mathbf{G} }[/math] has no isolated vertices when [math]\displaystyle{ p = o(\log n/n) }[/math].