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

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

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

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

Assumption throughout Problem Set 3

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.

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

Problem 1 (Warm-up problems)

• [Cumulative distribution function (CDF)] Let [math]\displaystyle{ F }[/math] be a distribution function and [math]\displaystyle{ r }[/math] a positive integer. Show that the following are distribution functions:
  1. [math]\displaystyle{ F(x)^r }[/math],
  2. [math]\displaystyle{ 1 − (1− F(x))^r }[/math],
  3. [math]\displaystyle{ F(x)+ (1− F(x))\cdot\log(1− F(x)) }[/math],
  4. [math]\displaystyle{ (F(x)− 1)\cdot e + \exp(1− F(x)) }[/math].
• [Probability mass function (PMF)] Let [math]\displaystyle{ S_k }[/math] be the set of positive integers whose base-10 expansion contains exactly [math]\displaystyle{ k }[/math] elements (so that, for example, [math]\displaystyle{ 1024 \in S_4 }[/math]). A fair coin is tossed until the first head appears, and we write [math]\displaystyle{ T }[/math] for the number of tosses required. We pick a random element, [math]\displaystyle{ N }[/math] say, from [math]\displaystyle{ S_T }[/math] , each such element having equal probability. What is the mass function of [math]\displaystyle{ N }[/math]?
• [Transitive coins] Three coins each show heads with probability [math]\displaystyle{ 3/5 }[/math] and tails otherwise. The first counts 10 points for a head and 2 for a tail, the second counts 4 points for both head and tail, and the third counts 3 points for a head and 20 for a tail. You and your opponent each choose a coin; you cannot choose the same coin. Each of you tosses your coin and the person with the larger score wins £[math]\displaystyle{ 10^{10} }[/math]. Would you prefer to be the first to pick a coin or the second?
• [Estimator] Let [math]\{X_r : r \ge 1\}[/math] be observations which are independent and identically distributed with unknown distribution function [math]F[/math]. Describe and justify a method for estimating [math]F(x)[/math].
• [Independence] Three players, A, B, and C, take turns to roll a die; they do this in the order ABCABCA....
  1. Show that the probability that, of the three players, A is the first to throw a 6, B the second, and C the third, is 216/1001.
  2. Show that the probability that the first 6 to appear is thrown by A, the second 6 to appear is thrown by B, and the third 6 to appear is thrown by C, is 46656/753571.
• [Joint distribution] Is the function [math]\displaystyle{ F(x,y)= 1− e^{−xy}, 0 \le x,y \lt \infty }[/math], the joint distribution function of some pair of random variables?
• [Jensen's entropy] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.
• [Law of total expectation] Let [math]\displaystyle{ \{X_n\}_{n \ge 1} }[/math] be identically distributed random variable and [math]\displaystyle{ N }[/math] be a random variable taking values in the non-negative integers and independent of the [math]\displaystyle{ X_n }[/math] for all [math]\displaystyle{ n \ge 1 }[/math]. Prove that [math]\displaystyle{ \mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1] }[/math].
• [Composing random variables] Show that any discrete random variable may be written as a linear combination of indicator variables.

Problem 2 (Discrete random variable)

• [Geometric distribution] Prove that geometric distribution is the only discrete memoryless distribution with range values [math]\displaystyle{ \mathbb{N}_+ }[/math].
• [Binomial distribution] Consider a binomial random variable [math]\displaystyle{ X }[/math] with parameters [math]\displaystyle{ n }[/math] and [math]\displaystyle{ p }[/math]. Let [math]\displaystyle{ k^* }[/math] be the largest integer that is less than or equal to [math]\displaystyle{ (n + 1)p }[/math]. Show that the PMF [math]\displaystyle{ p_x (k) }[/math] is monotonically nondecreasing with [math]\displaystyle{ k }[/math] in the range from [math]\displaystyle{ 0 }[/math] to [math]\displaystyle{ k^* }[/math] . and is monotonically decreasing with [math]\displaystyle{ k }[/math] for [math]\displaystyle{ k \ge k^* }[/math] .
• [Negative binomial distribution] Let [math]\displaystyle{ X }[/math] follows the negative binomial distribution with parameter [math]\displaystyle{ r \in \mathbb{N}_+ }[/math] and [math]\displaystyle{ p \in (0,1) }[/math]. Calculate [math]\displaystyle{ \mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2 }[/math].
• [Hypergeometric distribution (i)] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\Pr(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].
• [Hypergeometric distribution (ii)] Let [math]X[/math] and [math]Y[/math] be independent [math]\mathrm{Bin}(n,p)[/math] variables, and let [math]Z= X + Y[/math] . Show that the conditional distribution of [math]X[/math] given [math]Z= N[/math] is the hypergeometric distribution.
• [Multinomial distribution] Prove by calculating that the marginal distribution of multinomial distribution is binomial distribution.
• [Poisson distribution] In your pocket is a random number [math]\displaystyle{ N }[/math] of coins, where [math]\displaystyle{ N }[/math] has the Poisson distribution with parameter [math]\displaystyle{ \lambda }[/math]. You toss each coin once, with heads showing with probability [math]\displaystyle{ p }[/math] each time. Let [math]\displaystyle{ X }[/math] be the (random) number of heads outcomes and [math]\displaystyle{ Y }[/math] be the (also random) number of tails.
  1. Find the joint mass function of [math]\displaystyle{ (X,Y) }[/math].
  2. Find PMF of the marginal distribution of [math]\displaystyle{ X }[/math] in [math]\displaystyle{ (X,Y) }[/math]. Are [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] independent?

Problem 3 (Expectation)

• [Expectation] Is it generally true that [math]\mathbb{E}[1/X] = 1/\mathbb{E}[X][/math]? Is it ever true that [math]\mathbb{E}[1/X] = 1/\mathbb{E}[X][/math]?
• [Error] Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be independent with mean [math]\displaystyle{ \mu }[/math]. Explain the error in the following equation: [math]\displaystyle{ \mathbb E[X|X+Y=z]=\mathbb E[X|X=z-Y]=\mathbb E[z-Y]=z-\mu }[/math].
• [Optimal stopping time] You roll a conventional fair die repeatedly. If it shows 1, you must stop, but you may choose to stop at any prior time. Your score is the number shown by the die on the final roll. What stopping strategy yields the greatest expected score? What strategy would you use if your score were the square of the final roll?
• [Streak] Suppose we flip a fair coin [math]\displaystyle{ n }[/math] times independently to obtain a sequence of flips [math]\displaystyle{ X_1, X_2, \ldots , X_n }[/math]. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if [math]\displaystyle{ X_3 }[/math], [math]\displaystyle{ X_4 }[/math], and [math]\displaystyle{ X_5 }[/math] are all heads, there is a streak of length [math]\displaystyle{ 3 }[/math] starting at the third lip. (If [math]\displaystyle{ X_6 }[/math] is also heads, then there is also a streak of length [math]\displaystyle{ 4 }[/math] starting at the third lip.) Find the expected number of streaks of length [math]\displaystyle{ k }[/math] for some integer [math]\displaystyle{ k \ge 1 }[/math].
• [Tail sum for expectation (double counting)]
  1. If [math]\displaystyle{ X }[/math] takes non-negative integer values show that [math]\displaystyle{ \mathbb E[X]=\sum_{n=0}^\infty \Pr[X\gt n] }[/math].
  2. An urn contains [math]\displaystyle{ b }[/math] blue and [math]\displaystyle{ r }[/math] red balls. Balls are removed at random until the first blue ball is drawn. Show that the expected number drawn is [math]\displaystyle{ (b + r + 1)/(b + 1) }[/math].
  3. The balls are replaced and then removed at random until all the remaining balls are of the same colour. （现在我们把所有球都放回去，然后再次随机地把球无放回地取出来，直到剩下的小球都是同色的。） Find the expected number remaining in the urn.
  4. Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be independent random variables taking values in the non-negative integers, with finite means. Let [math]\displaystyle{ U= \min\{X,Y \} }[/math] and [math]\displaystyle{ V= \max\{X,Y \} }[/math]. Show that
     [math]\displaystyle{ \begin{align*} \mathbb E[U]&=\sum_{r=1}^\infty \Pr[X\ge r]\Pr[Y\ge r]\\ \mathbb E[V]&=\sum_{r=1}^\infty \bigg(\Pr[X\ge r]+\Pr[Y\ge r]-\Pr[X\ge r]\Pr[Y\ge r]\bigg)\\ \mathbb E[UV]&=\sum_{r,s=1}^\infty \Pr[X\ge r]\Pr[Y\ge s]. \end{align*} }[/math]
  5. Let [math]\displaystyle{ X }[/math] take values in the non-negative integers. Show that [math]\displaystyle{ \mathbb E[X^2]=\mathbb E[X]+2\sum_{r=0}^\infty r\Pr[X\gt r]=\sum_{r=0}^\infty (2r+1)\Pr[X\gt r] }[/math], and find a similar formula for [math]\displaystyle{ \mathbb E[X^3] }[/math].

Problem 4 (Random graph)

• [Turán's Theorem] Let [math]\displaystyle{ G=(V,E) }[/math] be a fixed undirected graph, and write [math]\displaystyle{ d_v }[/math] for the degree of the vertex [math]\displaystyle{ v }[/math]. Use probablistic method to prove that [math]\displaystyle{ \alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1} }[/math]. (Hint: Consider the following random procedure for generating an independent set [math]\displaystyle{ I }[/math] from a graph with vertex set [math]\displaystyle{ V }[/math]: First, generate a random permutation of the vertices, denoted as [math]\displaystyle{ v_1,v_2,\ldots,v_n }[/math]. Then, construct the independent set [math]\displaystyle{ I }[/math] as follows: For each vertex [math]\displaystyle{ v_i \in V }[/math], add [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ I }[/math] if and only if none of its predecessors in the permutation, i.e., [math]\displaystyle{ v_1,\ldots,v_{i-1} }[/math], are neighbors of [math]\displaystyle{ v_i }[/math].)
• [Dominating set] A dominating set of vertices in an undirected graph [math]\displaystyle{ G = (V, E) }[/math] is a set [math]\displaystyle{ S \subseteq V }[/math] such that every vertex of [math]\displaystyle{ G }[/math] belongs to [math]\displaystyle{ S }[/math] or has a neighbor in [math]\displaystyle{ S }[/math]. Let [math]\displaystyle{ G = (V, E) }[/math] be an [math]\displaystyle{ n }[/math]-vertex graph with minimum degree [math]\displaystyle{ d \gt 1 }[/math]. Prove that [math]\displaystyle{ G }[/math] has a dominating set with at most [math]\displaystyle{ \frac{n\left(1+\log(d+1)\right)}{d+1} }[/math] vertices. (Hint: Consider a random vertex subset [math]\displaystyle{ S \subseteq V }[/math] by including each vertex independently with probability [math]\displaystyle{ p \triangleq \log(d + 1)/(d + 1) }[/math].)