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

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

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

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

Assumption throughout Problem Set 1

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

The Problems

• [[math]\displaystyle{ \sigma }[/math]-algebra] Let [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] belong to some [math]\displaystyle{ \sigma }[/math]-algebra [math]\displaystyle{ \mathcal F }[/math]. Show that [math]\displaystyle{ \mathcal F }[/math] contains the sets [math]\displaystyle{ A\cap B }[/math], [math]\displaystyle{ A\setminus B }[/math], and [math]\displaystyle{ A\oplus B }[/math]. Let [math]\displaystyle{ \mathcal{F} }[/math] and [math]\displaystyle{ \mathcal{G} }[/math] be [math]\displaystyle{ \sigma }[/math]-algebras of subsets of [math]\displaystyle{ \Omega }[/math]. Show that [math]\displaystyle{ \mathcal{F} \cup \mathcal{G} }[/math] is not necessarily a [math]\displaystyle{ \sigma }[/math]-algebra
• [Probability law] Let [math]\displaystyle{ \mathcal F }[/math] be a [math]\displaystyle{ \sigma }[/math]-algebra of subsets of [math]\displaystyle{ \Omega }[/math], and suppose [math]\displaystyle{ \Pr : \mathcal F → [0,1] }[/math] satisfies: (i) [math]\displaystyle{ \Pr(\Omega)=1 }[/math], and (ii) [math]\displaystyle{ \Pr }[/math] is additive, in that [math]\displaystyle{ \Pr(A \cup B)= \Pr(A)+ \Pr(B) }[/math] whenever [math]\displaystyle{ A \cap B= \emptyset }[/math]. Show that [math]\displaystyle{ \Pr(\emptyset)= 0 }[/math].
• [Nonexistence of probability space] Prove that it is impossible to define a uniform probability law on natural numbers [math]\displaystyle{ \mathbb{N} }[/math]. More precisely, prove that there does not exist a probability space [math]\displaystyle{ (\mathbb{N},2^{\mathbb{N}},\Pr) }[/math] such that [math]\displaystyle{ \Pr(\{i\}) = \Pr(\{j\}) }[/math] for all [math]\displaystyle{ i, j \in \mathbb{N} }[/math].
  Please explain why the same argument fails to prove that there is no uniform probability law on the real interval [math]\displaystyle{ [0,1] }[/math], that is, there is no such probability space [math]\displaystyle{ ([0,1],\mathcal{F},\Pr) }[/math] that for any interval [math]\displaystyle{ (l,r] \subseteq [0,1] }[/math], it holds that [math]\displaystyle{ (l,r] \in \mathcal{F} }[/math] and [math]\displaystyle{ \Pr( (l,r] ) = r-l }[/math]. (Actually, such probability measure does exist and is called the Lebesgue measure on [math]\displaystyle{ [0,1] }[/math]).
• [Euler's totient function] For any positive integer [math]\displaystyle{ n }[/math], let [math]\displaystyle{ \varphi(n) }[/math] be the number of positive integers [math]\displaystyle{ x\le n }[/math] such that [math]\displaystyle{ \mathrm{gcd}(x,n)=1 }[/math]. Prove that [math]\displaystyle{ \varphi(n)=n\prod_{i=1}^k(1-1/p_i) }[/math] using the principle of inclusion and exclusion, where [math]\displaystyle{ p_i }[/math]’s are primes and [math]\displaystyle{ n=\prod_{i=1}^k p_i^{c_i} }[/math] is the prime factorization of [math]\displaystyle{ n }[/math] for some positive integers [math]\displaystyle{ \{c_i\}_{i\le k} }[/math].
• [Ménages] Men and women alternate when seated at a circular table. If [math]\displaystyle{ n }[/math] heterosexual couples are seated randomly according to this rule, calculate the probability that nobody sits next to his or her partner. (hint: enumerate forbidden adjacent seats instead of forbidden couples.)
• [The problem of points] Telis and Wendy play a round of golf (18 holes) for a $10 stake, and their probabilities of winning on any one hole are [math]\displaystyle{ p }[/math] and [math]\displaystyle{ 1 - p }[/math], respectively, independent of their results in other holes. At the end of 10 holes, with the score 4:6 in favor of Wendy, Telis receives an urgent call and has to report back to work. They decide to split the stake in proportion to their probabilities of winning had they completed the round, as follows. If [math]\displaystyle{ p_T }[/math] and [math]\displaystyle{ p_W }[/math] are the conditional probabilities that Telis and Wendy, respectively, are ahead in the score after 18 holes given the 4:6 score after 10 holes, then Telis should get a fraction [math]\displaystyle{ p_T / (p_T + p_W) }[/math] of the stake, and Wendy should get the remaining [math]\displaystyle{ p_W /(p_T + p_W }[/math] ). How much money should Telis get? Explain the reasoning.
• [Certainly occur] You are given that at least one of the events [math]\displaystyle{ A_r }[/math] , [math]\displaystyle{ 1 \le r \le n }[/math], is certain to occur, but certainly no more than two occur. If [math]\displaystyle{ \Pr(A_r )= p }[/math], and [math]\displaystyle{ \Pr(A_r \cap A_s )= q, r \ne s }[/math], show that [math]\displaystyle{ p \ge 1/n }[/math] and [math]\displaystyle{ q \le 2/n }[/math].