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

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

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

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

Assumption throughout Problem Set 5

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 (Random Graphs)

• [Triangle neighbors] Suppose that [math]\displaystyle{ p= O(1/n) }[/math]. Prove that the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G}(n,p) }[/math] does not contain vertex which belongs to more than one triangle.
• [Isolated vertices] An isolated vertex is of degree of 0. Let [math]\displaystyle{ X }[/math] be the random variable counting isolated vertices in the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G}(n,p) }[/math]. Assume [math]\displaystyle{ p=(\log n+c)/n }[/math] for some constant [math]\displaystyle{ c }[/math], show that [math]\displaystyle{ X }[/math] converges to Poisson distribution with parameter [math]\displaystyle{ e^{-c} }[/math] as [math]\displaystyle{ n\to\infty }[/math]. (hint: prove the binomial moments [math]\displaystyle{ \mathbb E\left[\binom X k\right],\forall k\in\mathbb N }[/math] are equal)

Problem 2 (Continuous Random Variables)

• [Jointly continuous]
  1. If [math]\displaystyle{ U }[/math] and [math]\displaystyle{ V }[/math] are jointly continuous, show that [math]\displaystyle{ \Pr(U = V) = 0 }[/math].
  2. Let [math]\displaystyle{ X }[/math] be uniformly distributed on [math]\displaystyle{ (0, 1) }[/math], and let [math]\displaystyle{ Y = X }[/math] . Then [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are continuous, and [math]\displaystyle{ \Pr(X = Y ) = 1 }[/math]. Is there a contradiction here?
• [Distribution function] Can an [math]\displaystyle{ F:\mathbb R\to [0,1] }[/math], which is (i) nondecreasing, (ii) [math]\displaystyle{ \lim_{x\to-\infty}F(x)=0,\lim_{x\to+\infty}F(x)=1 }[/math], (iii) continuous, (iv) not differentiable at some point, be a cumulative distribution function (CDF) for some random variable? Is [math]\displaystyle{ F }[/math] always a cumulative distribution function for some random variable? What random variable might it be? Justify your answer.
• [Density function] For what values of the [math]\displaystyle{ C }[/math], [math]\displaystyle{ f (x)= C\cdot\exp(−x− e^{−x} ), x \in \mathbb R }[/math], the density function of the ‘extreme-value distribution’, is a probability density function?
• [iid] Let [math]\displaystyle{ \{X_r : r \ge 1\} }[/math] be independent and identically distributed with distribution function [math]\displaystyle{ F }[/math] satisfying [math]\displaystyle{ F(y)\lt 1 }[/math] for all [math]\displaystyle{ y }[/math], and let [math]\displaystyle{ Y (y)= \min\{k : X_k \gt y\} }[/math]. Show that [math]\displaystyle{ \lim_{y\to\infty} \Pr( Y (y)\le \mathbb E[Y (y)])= 1− e−1 }[/math].
• [Tails and moments] If [math]\displaystyle{ X }[/math] is a continuous random variable and [math]\displaystyle{ \mathbb E(X^r ) }[/math] exists, where [math]\displaystyle{ r \ge 1 }[/math] is an integer, show that [math]\displaystyle{ \int_0^\infty x^{r−1}\Pr(|X| \gt x)dx \lt \infty }[/math], and [math]\displaystyle{ x^r\cdot\Pr(|X| \gt x)\to 0 }[/math] as [math]\displaystyle{ x \to\infty }[/math]. (Hint. You might need this: for non-negative [math]\displaystyle{ X }[/math], [math]\displaystyle{ \mathbb E(X^r )=\int_0^\infty rx^{r-1}\Pr(X\gt x)dx }[/math].)
• [Conditional expectation] Show that the conditional expectation [math]\displaystyle{ \psi(X)= \mathbb E(Y | X) }[/math] satisfies [math]\displaystyle{ \mathbb E(\psi(X)g(X))=\mathbb E(Y\cdot g(X)) }[/math], for any function [math]\displaystyle{ g }[/math] for which both expectations exist.
• [Correlated?Indepedent?] Let [math]\displaystyle{ X }[/math] be uniformly distributed on [math]\displaystyle{ [−1,1] }[/math]. Are the random variables [math]\displaystyle{ Z_n = \cos(n\pi X), n =1,2,\dots }[/math], correlated? Are they independent? Explain your answers.
• [Aliasing method] A finite real vector is called a probability vector if it has non-negative entries with sum [math]\displaystyle{ 1 }[/math]. Show that a probability vector [math]\displaystyle{ \mathbf p }[/math] of length [math]\displaystyle{ n }[/math] may be written in the form [math]\displaystyle{ \mathbf p=\frac 1{n− 1}\sum^n_{r=1}\mathbf v_r }[/math], where each [math]\displaystyle{ \mathbf v_r }[/math] is a probability vector with at most two non-zero entries. Describe a method, based on this observation, for sampling from [math]\displaystyle{ \mathbf p }[/math] viewed as a probability mass function.
• [Stochastic domination] Let [math]\displaystyle{ X, Y }[/math] be continuous random variables. Show that [math]\displaystyle{ X }[/math] dominates [math]\displaystyle{ Y }[/math] stochastically if and only if [math]\displaystyle{ \mathbb{E}[f(X)]\geq \mathbb{E}[f(Y)] }[/math] for any non-decreasing function [math]\displaystyle{ f }[/math] for which the expectations exist.

Problem 3 (Continuous Distributions)

• [Uniform Distribution (i)] Let [math]\displaystyle{ U }[/math] be uniform on [math]\displaystyle{ [0,1] }[/math] and [math]\displaystyle{ 0 \lt q \lt 1 }[/math]. Show that [math]\displaystyle{ X= 1 + \lfloor\ln U/\ln q\rfloor }[/math] has a geometric distribution.
• [Uniform Distribution (ii)] Show that it cannot be the case that [math]\displaystyle{ U= X + Y }[/math] where [math]\displaystyle{ U }[/math] is uniformly distributed on [math]\displaystyle{ [0,1] }[/math] and [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are independent and identically distributed. You should not assume that [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are continuous variables.
• [Uniform Distribution (iii)] Disprove the existence of uniform distribution over [math]\displaystyle{ [a,+\infty) }[/math] for any [math]\displaystyle{ a\in\mathbb R }[/math].
• [Exponential distribution (i)] Prove that exponential distribution is the only memoryless continuous random variable.
• [Exponential distribution (ii)] Let [math]\displaystyle{ X }[/math] be exponentially distributed with parameter [math]\displaystyle{ \lambda }[/math]. Let [math]\displaystyle{ N }[/math] be the greatest integer not greater than [math]\displaystyle{ X }[/math], and set [math]\displaystyle{ M= X− N }[/math]. Show that [math]\displaystyle{ M }[/math] and [math]\displaystyle{ N }[/math] are independent. Find the density function of [math]\displaystyle{ M }[/math] and the distribution of [math]\displaystyle{ N }[/math].
• [Waiting for offers] I am selling my house, and have decided to accept the first offer exceeding ￥[math]\displaystyle{ K }[/math]. Assuming that offers are independent random variables with common distribution function [math]\displaystyle{ F }[/math], find the expected number of offers received before I sell the house.
• [Geometric distribution] Prove that [math]\displaystyle{ \lfloor X\rfloor }[/math] is a geometric random variable, and find its probability mass function, where [math]\displaystyle{ X\sim\exp(\lambda) }[/math].
• [Poisson clocks] Prove that a Poisson point process with [math]\displaystyle{ k }[/math] Poisson clocks with rate [math]\displaystyle{ \lambda }[/math] is equivalent to the [math]\displaystyle{ 1 }[/math]-clock process with rate [math]\displaystyle{ \lambda k }[/math].
• [Poissonian bears] In a certain town at time [math]\displaystyle{ t = 0 }[/math] there are no bears. Brown bears and grizzly bears arrive as independent Poisson point processes [math]\displaystyle{ B }[/math] and [math]\displaystyle{ G }[/math] with respective intensities [math]\displaystyle{ \beta }[/math] and [math]\displaystyle{ \gamma }[/math].
  1. Show that the first bear is brown with probability [math]\displaystyle{ \beta/(\beta+ \gamma) }[/math].
  2. Find the probability that between two consecutive brown bears, there arrive exactly [math]\displaystyle{ r }[/math] grizzly bears.
• [Bivariate normal distributions (i)] Let [math]\displaystyle{ f_{X,Y}(x,y)=\frac{1}{2\pi\sigma_1\sigma_2\sqrt{1-\rho^2}}\exp(-\frac{1}{2}Q(x,y)) }[/math] with [math]\displaystyle{ Q(x,y)=\frac{1}{1-\rho^2}\left[\left(\frac{x-\mu_1}{\sigma_1}\right)^2-2\rho\left(\frac{x-\mu_1}{\sigma_1}\right)\left(\frac{y-\mu_2}{\sigma_2}\right)+\left(\frac{y-\mu_2}{\sigma_2}\right)^2\right] }[/math] be density function of random variable pair [math]\displaystyle{ (X, Y) }[/math]. Find the means, variances of [math]\displaystyle{ X, Y }[/math] and their covariance.
• [Bivariate normal distributions (ii)] Let [math]\displaystyle{ X }[/math] have the [math]\displaystyle{ N(0,1) }[/math] distribution and let [math]\displaystyle{ a \gt 0 }[/math]. Show that the random variable [math]\displaystyle{ Y }[/math] given by [math]\displaystyle{ Y= \begin{cases}X&\text{ if }|X| \lt a \\ −X &\text{ if } |X| \ge a \end{cases} }[/math] has the [math]\displaystyle{ N(0,1) }[/math] distribution, and find an expression for [math]\displaystyle{ \rho(a)= \mathrm{cov}(X,Y ) }[/math] in terms of the density function [math]\displaystyle{ \varphi }[/math] of [math]\displaystyle{ X }[/math]. Does the pair [math]\displaystyle{ (X,Y ) }[/math] have a bivariate normal distribution?