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

Problem 1 (Probability space)

• [[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].

Problem 2 (Conditional probability)

• [The prosecutor’s fallacy] Let [math]\displaystyle{ G }[/math] be the event that an accused is guilty, and [math]\displaystyle{ T }[/math] the event that some testimony is true. Some lawyers have argued on the assumption that [math]\displaystyle{ \Pr(G | T )= \Pr(T | G) }[/math]. Show that this holds if and only if [math]\displaystyle{ \Pr(G)= \Pr(T ) }[/math].
• [Sure thing principle] If you prefer [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] given [math]\displaystyle{ C }[/math], and also prefer [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] given [math]\displaystyle{ C^c }[/math], then you surely prefer [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math]. Agreed? Explain the reasoning.
• [The prisoner's dilemma] The release of two out of three prisoners has been announced. but their identity is kept secret. One of the prisoners considers asking a friendly guard to tell him who is the prisoner other than himself that will be released, but hesitates based on the following rationale: at the prisoner's present state of knowledge, the probability of being released is [math]\displaystyle{ 2/3 }[/math], but after he knows the answer, the probability of being released will become [math]\displaystyle{ 1/2 }[/math], since there will be two prisoners (including himself) whose fate is unknown and exactly one of the two will be released. What is wrong with this line of reasoning?
• [The Monty Hall problem] In a game show; you have to choose one of three doors. One conceals a new car, two conceal old goats. You choose, but your chosen door is not opened immediately. Instead the presenter opens another door, which reveals a goat. He offers you the opportunity to change your choice to the third door (unopened and so far unchosen). Let [math]\displaystyle{ p }[/math] be the (conditional) probability that the third door conceals the car. The presenter’s protocol is:
  1. 1. he is determined to show you a goat; with a choice of two, he picks one at random. Show [math]\displaystyle{ p=2/3 }[/math].
     2. he is determined to show you a goat; with a choice of two goats (Bill and Nan, say) he shows you Bill with probability [math]\displaystyle{ b }[/math]. Show that, given you see Bill, the probability is [math]\displaystyle{ 1/(1 + b) }[/math].
     3. he opens a door chosen at random irrespective of what lies behind. Show [math]\displaystyle{ p=1/2 }[/math].
  2. Show that, for [math]\displaystyle{ \alpha\in [ 1/2, 2/3 ] }[/math], there exists a protocol such that [math]\displaystyle{ p= \alpha }[/math]. Are you well advised to change your choice to the third door?
  3. In a variant of this question, the presenter is permitted to open the first door chosen, and to reward you with whatever lies behind. If he chooses to open another door, then this door invariably conceals a goat. Let [math]\displaystyle{ p }[/math] be the probability that the unopened door conceals the car, conditional on the presenter having chosen to open a second door. Devise protocols to yield the values [math]\displaystyle{ p= 0, p= 1 }[/math], and deduce that, for any [math]\displaystyle{ \alpha\in [0,1] }[/math], there exists a protocol with [math]\displaystyle{ p= \alpha }[/math].

Problem 3 (1D random walk)

• [Gambler's ruin] A gambler makes a sequence of independent bets. In each bet, he wins $1 with probability [math]\displaystyle{ p }[/math], and loses $1 with probability [math]\displaystyle{ 1 - p }[/math]. Initially, the gambler has $[math]\displaystyle{ k }[/math], and plays until he either accumulates $[math]\displaystyle{ n }[/math] or has no money left. What is the probability that the gambler will end up with $[math]\displaystyle{ n }[/math]?

Problem 4 (Independence)

• [Certainty and independency]
  1. If [math]\displaystyle{ A }[/math] is independent of itself, show that [math]\displaystyle{ \Pr(A) }[/math] is [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math].
  2. If [math]\displaystyle{ \Pr(A) }[/math] is [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math], show that [math]\displaystyle{ A }[/math] is independent of all events [math]\displaystyle{ B }[/math].
• [Out of service] A cellular phone system services a population of [math]\displaystyle{ n_1 }[/math] "voice users" (those who occasionally need a voice connection) and [math]\displaystyle{ n_2 }[/math] "data users" (those who occasionally need a data connection). We estimate that at a given time, each user will need to be connected to the system with probability [math]\displaystyle{ p_1 }[/math] (for voice users) or [math]\displaystyle{ p_2 }[/math] (for data users), independent of other users. The data rate for a voice user is [math]\displaystyle{ r_1 }[/math] bits/sec and for a data user is [math]\displaystyle{ r_2 }[/math] bits/sec. The cellular system has a total capacity of [math]\displaystyle{ c }[/math] bits/sec. What is the probability that more users want to use the system than the system can accommodate?
• [Pairwise independences] Prove that the following statements are equivalent:
  1. [math]\displaystyle{ \mathbf{Pr}(A|B)=\mathbf{Pr}(A) }[/math]
  2. [math]\displaystyle{ \mathbf{Pr}(A\cap B)=\mathbf{Pr}(A)\cdot P(B) }[/math]
  3. [math]\displaystyle{ \mathbf{Pr}(A|B^C)=\mathbf{Pr}(A) }[/math]
• [Limited independence] Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be the scores on two fair dice taking values in the set [math]\displaystyle{ \{1,2,...,6\} }[/math]. Let [math]\displaystyle{ A_1 =\{X + Y= 9\} }[/math], [math]\displaystyle{ A_2 = \{X \in \{1,2,3\}\} }[/math], and [math]\displaystyle{ A_3 = \{X \in \{3,4,5\}\} }[/math]. Show that [math]\displaystyle{ \Pr(A_1 \cap A_2 \cap A_3)= \Pr(A_1)\Pr(A_2)\Pr(A_3) }[/math]. Are these three events mutually independent?
• [Galton’s paradox] You flip three fair coins. At least two are alike, and it is an evens chance that the third is a head or a tail. Therefore [math]\displaystyle{ \Pr( }[/math]all alike[math]\displaystyle{ )=1/2 }[/math] . Do you agree? Explain the reasoning.
• [Conditional independence] Show that the conditional independence of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] given [math]\displaystyle{ C }[/math] neither implies, nor is implied by, the independence of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]. For which events [math]\displaystyle{ C }[/math] is it the case that, for all [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], the events [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are independent if and only if they are conditionally independent given [math]\displaystyle{ C }[/math]?

Problem 5 (Probabilistic method)

• [Independent Sets] Let [math]\displaystyle{ G(V,E) }[/math] be a graph with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges. Prove that [math]\displaystyle{ G }[/math] has an independent set with at least [math]\displaystyle{ n^2/(4m) }[/math] vertices.