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

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

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

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

Assumption throughout Problem Set 2

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

Problem 1 (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 2 (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 3 (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 4 (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.