概率论与数理统计 (Spring 2024)/Problem Set 1

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

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

Assumption throughout Problem Set 1

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

Problem 4 (Conditional probability)

• [Positive correlation] We say that events [math]\displaystyle{ B }[/math] gives positive information about event [math]\displaystyle{ A }[/math] if [math]\displaystyle{ \mathbf{Pr}(A|B) \gt \mathbf{Pr}(A) }[/math], that is, the occurrence of [math]\displaystyle{ B }[/math] makes the occurrence of [math]\displaystyle{ A }[/math] more likely. Now suppose that [math]\displaystyle{ B }[/math] gives positive information about [math]\displaystyle{ A }[/math].
• Does [math]\displaystyle{ A }[/math] give positive information about [math]\displaystyle{ B }[/math]?
• Does [math]\displaystyle{ \overline{B} }[/math] give negative information about [math]\displaystyle{ A }[/math], that is, is it true that [math]\displaystyle{ \mathbf{Pr}(A|\overline{B}) \gt \mathbf{Pr}(A) }[/math]?
• Does [math]\displaystyle{ \overline{B} }[/math] give positive information or negative information about [math]\displaystyle{ \overline{A} }[/math]?

• [Balls in urns (I)] There are [math]\displaystyle{ n }[/math] urns of which the [math]\displaystyle{ r }[/math]-th contains [math]\displaystyle{ r-1 }[/math] white balls and [math]\displaystyle{ n-r }[/math] black balls. You pick an urn uniformly at random (here, "uniformly" means that each urn has equal probability of being chosen) and remove two balls from that urn, uniformly at random without replacement (which means that each of the [math]\displaystyle{ {n-1\choose 2} }[/math] pairs of balls are chosen to be removed with equal probability). Find the following probabilities:

  1. the second ball is black;
  2. the second ball is black, given that the first is black.

• [Balls in urns (II)] Suppose that an urn contains [math]\displaystyle{ w }[/math] white balls and [math]\displaystyle{ b }[/math] black balls. The balls are drawn from the urn one by one, each time uniformly and independently at random, without replacement (which means we do not put the chosen ball back after each drawing). Find the probabilities of the events:

  1. the first white ball drawn is the [math]\displaystyle{ (k+1) }[/math]th ball;
  2. the last ball drawn is white.

• [Balls in urns (III)] There are [math]\displaystyle{ n }[/math] urns filled with black and white balls. Let [math]\displaystyle{ f_i }[/math] be the fraction of white balls in the [math]\displaystyle{ i }[/math]-th urn. In stage 1 an urn is chosen uniformly at random. In stage 2 a ball is drawn uniformly at random from the urn chosen in stage 1. Let [math]\displaystyle{ U_i }[/math] be the event that the [math]\displaystyle{ i }[/math]-th urn was chosen at stage 1. Let [math]\displaystyle{ W }[/math] be the event that a white ball is drawn at stage 2, and [math]\displaystyle{ B }[/math] be the event that a black ball is drawn at stage 2.
  1. Use Bayes's Law to express [math]\displaystyle{ \textbf{Pr}(U_i|W) }[/math] in terms of [math]\displaystyle{ f_1,\cdots, f_n }[/math].
  2. Let's say there are three urns and urn 1 has 30 white and 10 black balls, urn 2 has 20 white and 20 black balls, and urn 3 has 10 white balls and 30 black balls. Compute [math]\displaystyle{ \textbf{Pr}(U_1|B) }[/math], [math]\displaystyle{ \textbf{Pr}(U_2|B) }[/math] and [math]\displaystyle{ \textbf{Pr}(U_3|B) }[/math].

Problem 5 (Independence)

Let's consider a series of [math]\displaystyle{ n }[/math] outputs [math]\displaystyle{ (X_1, X_2, \cdots, X_n) \in \{0,1\}^n }[/math] of [math]\displaystyle{ n }[/math] independent Bernoulli trials, where each trial succeeds with the same probability [math]\displaystyle{ 0 \lt p \lt 1 }[/math].

• [Limited independence] Construct three events [math]\displaystyle{ A,B }[/math] and [math]\displaystyle{ C }[/math] out of [math]\displaystyle{ n }[/math] Bernoulli trials such that [math]\displaystyle{ A, B }[/math] and [math]\displaystyle{ C }[/math] are pairwise independent but are not (mutually) independent. You need to prove that the constructed events [math]\displaystyle{ A, B }[/math] and [math]\displaystyle{ C }[/math] satisfy this. (Hint: Consider the case where [math]\displaystyle{ n = 2 }[/math] and [math]\displaystyle{ p = 1/2 }[/math].)

• [Product distribution] Suppose someone has observed the output of the [math]\displaystyle{ n }[/math] trials, and she told you that precisely [math]\displaystyle{ k }[/math] out of [math]\displaystyle{ n }[/math] trials succeeded for some [math]\displaystyle{ 0\lt k\lt n }[/math]. Now you want to predict the output of the [math]\displaystyle{ (n+1) }[/math]-th trial while the parameter [math]\displaystyle{ p }[/math] of the Bernoulli trial is unknown. One way to estimate [math]\displaystyle{ p }[/math] is to find such [math]\displaystyle{ \hat{p} }[/math] that makes the observed outcomes most probable, namely you need to solve [math]\displaystyle{ \arg \max_{\hat{p}\in(0,1)} \mathbf{Pr}_{\hat{p}} [k \text{ out of } n\text{ trials succeed}]. }[/math]

  1. Estimate [math]\displaystyle{ p }[/math] by solving the above optimization problem.
  2. If someone tells you exactly which [math]\displaystyle{ k }[/math] trials succeed (in addition to just telling you the number of successful trials, which is [math]\displaystyle{ k }[/math]), would it help you to estimate [math]\displaystyle{ p }[/math] more accurately? Why?

Problem 6 (Probabilistic method)

A CNF formula （合取范式） [math]\displaystyle{ \Phi }[/math] over [math]\displaystyle{ n }[/math] Boolean variables [math]\displaystyle{ x_1,\cdots, x_n }[/math] is a conjunction ([math]\displaystyle{ \land }[/math]) of clauses (子句) [math]\displaystyle{ \Phi=C_1\land C_2\land\cdots\land C_m }[/math], where each clause [math]\displaystyle{ C_j=\ell_{j_1}\lor\ell_{j_2}\cdots\lor\ell_{j_k} }[/math] is a disjunction ([math]\displaystyle{ \lor }[/math]) of literals (文字), where a literal [math]\displaystyle{ \ell_r }[/math] is either a variable [math]\displaystyle{ x_i }[/math] or the negation [math]\displaystyle{ \bar{x}_i }[/math] of a variable. A CNF formula is satisfiable (可满足) if there is a truth assignment [math]\displaystyle{ x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n }[/math] to the variables such that [math]\displaystyle{ \Phi(x)=\mathtt{true} }[/math]. A [math]\displaystyle{ k }[/math]-CNF formula is a CNF formula in which each clause contains exactly [math]\displaystyle{ k }[/math] literals (without repetition).

• [Satisfiability (I)] Let [math]\displaystyle{ \Phi }[/math] be a [math]\displaystyle{ k }[/math]-CNF with less than [math]\displaystyle{ 2^k }[/math] clauses. Use the probabilistic method to show that [math]\displaystyle{ \Phi }[/math] must be satisfiable. You should be explicit about the probability space that is used.
• [Satisfiability (II)] Give a constructive proof of the same problem above. That is, prove that [math]\displaystyle{ \Phi }[/math] is satisfiable by showing how to construct a truth assignment [math]\displaystyle{ x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n }[/math] such that [math]\displaystyle{ \Phi(x)=\mathtt{true} }[/math]. Your construction does NOT have to be efficient. Please explain the difference between this constructive proof and the proof by the probabilistic method.
• [Satisfiability (III)] Let [math]\displaystyle{ \Phi }[/math] be a [math]\displaystyle{ k }[/math]-CNF with [math]\displaystyle{ m\geq 2^k }[/math] clauses. Use the probabilistic method to show that there exists a truth assignment [math]\displaystyle{ x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n }[/math] satisfying at least [math]\displaystyle{ \lfloor m(1-1/2^k) \rfloor }[/math] clauses in [math]\displaystyle{ \Phi }[/math]. (Hint: Consider overlaps of events in Venn diagram.) You should be explicit about the probability space that is used.