概率论与数理统计 (Spring 2023)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
Zhangxy (talk | contribs)
 
(79 intermediate revisions by 3 users not shown)
Line 1: Line 1:
*目前作业非最终版本。
*每道题目的解答都要有完整的解题过程,中英文不限。
 
*我们推荐大家使用LaTeX, markdown等对作业进行排版。


*每道题目的解答都要有完整的解题过程,中英文不限。
*每道题目的解答都要有完整的解题过程,中英文不限。
Line 7: Line 9:
== Assumption throughout Problem Set 1==
== Assumption throughout Problem Set 1==
<p>Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.</p>
<p>Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.</p>
<h2 id="problem-1-classic-examples">Problem 1 (Classic examples: symmetric 1D random walk)</h2>
<h2 id="problem-2-principle-of-inclusion-and-exclusion">Problem 1 (Principle of Inclusion and Exclusion)</h2>
<p>Let <math>n\ge 1</math> be a positive integer and <math>A_1,A_2,\ldots,A_n</math> be <math>n</math> events.</p>
<ul>
<li>[<strong>Union bound</strong>] Prove <math>\mathbf{Pr}\left( \bigcup_{i=1}^{n} A_i \right) \le \sum_{i=1}^{n} \mathbf{Pr}\left(A_i\right)</math><strong> using the definition of probability space</strong>.</li>
<li>[<strong>Principle of Inclusion and Exclusion (PIE)</strong>] Prove that <math>\mathbf{Pr}\left( \bigcup_{i=1}^n A_i\right) = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \mathbf{Pr}\left( \bigcap_{i \in S} A_i \right)</math>, where <math>[n]=\{1,2,\ldots,n\}</math>.</li>
<li>[<strong>Surjection</strong>] For positive integers <math>m\ge n</math>, prove that the probability of a uniform random function <math>f:[m]\to[n]</math> to be surjective (满射) is <math>\sum_{k=1}^n(-1)^{n-k}{n\choose k}\left(\frac{k}{n}\right)^m</math>. </li>
<li>[<strong>Proper <math>q</math>-coloring of <math>n</math>-cycle</strong>] Given an arbitrary integer <math>q\ge 2</math>, calculate the probability of a uniform random <math>n</math>-tuples <math>p = (p_1,p_2,\ldots,p_n)\in[q]^n</math> satisfying the following property: <math>p_{n} \neq p_1</math> and <math>p_i \neq p_{i+1}</math> for all <math>1 \le i \le n-1</math>. You are required to apply PIE to calculate this probability. Note that this is the probability of a uniform random <math>q</math>-coloring of an <math>n</math>-cycle to be proper.</li>
<li>[<strong>Bonferroni&#39;s inequality and Kounias&#39; inequality</strong>] Prove that
<math>
\sum_{i=1}^n \mathbf{Pr}(A_i) - \sum_{1 \le i< j \le n} \mathbf{Pr}(A_i \cap A_j)\le \mathbf{Pr}\left(\bigcup_{i=1}^n A_i\right) \le \sum_{i=1}^n \mathbf{Pr} \left( A_i\right) - \sum_{i=2}^n \mathbf{Pr}(A_1 \cap A_i).
</math>
(Hint: This is sometimes called Kounias' inequality which is weaker than the Bonferroni's inequality. You can try using Venn diagram to understand these inequalities.)</li>
</ul>
 
<h2 id="problem-1-classic-examples">Problem 2 (Symmetric 1D random walk)</h2>
A gambler plays a fair gambling game: At each round, he flips a fair coin, earns <math>1</math> point if it's HEADs, and loses <math>1</math> point if otherwise.
<ul>
<ul>
<li><p>[<strong>Symmetric 1D random walk (I)</strong>] Let <math>(X_i)_{i \in \mathbb{N}}</math> be i.i.d. random variables, where <math>X_i</math> is uniformly chosen from <math>\{-1,1\}</math>. Let <math>S_n = \sum_{i=1}^{n} X_i</math>. Find out <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(S_i = 0)</math>.</p>
<li><p>[<strong>Symmetric 1D random walk (I)</strong>] Let <math>A_i</math> be the event that the gambler earns <math>0</math> points after playing <math>i</math> rounds of the game, that is, the number of times the coin lands on heads is equal to the number of times it lands on tails. Compute <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(A_i)</math>. (Hint: You may use Stirling's approximation to estimate [math]\mathbf{Pr}(A_i)[/math] and derive that <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(A_i) = +\infty</math>.)</p>
</li>
</li>
<li><p>[<strong>Symmetric 1D random walk (II)</strong>] Let <math>(X_i)_{i \in \mathbb{N}}</math> be i.i.d. random variables, where <math>X_i</math> is uniformly chosen from <math>\{-1,1\}</math>. Let <math>S_n = \sum_{i=1}^{n} X_i</math> and <math>U = \min \{n \in \mathbb{N}_+ \mid S_n = 0\}</math> (<math>U = +\infty</math> if the set is empty). Find out <math>\mathbb{E}(U) = \sum_{k=1}^{+\infty} \mathbf{Pr}(U \ge k)</math>.</p>
<li><p>[<strong>Symmetric 1D random walk (II)</strong>] Suppose that the game ends upon that the gambler loses all his <math>m</math> points. Let <math>B_i</math> be the event that the game ends within <math>i</math> rounds. Compute <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i})</math>. (Hint: You may first consider [math] \displaystyle{m = 1}[/math] case. Let [math]\displaystyle{C_i}[/math] be the event that the game ends at the [math]\displaystyle{i}[/math]-th round. (i) Prove that <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i}) = \sum_{i=1}^{+\infty} (i-1) \mathbf{Pr}(C_i)</math>. (ii) Compute <math>\mathbf{Pr}(C_i)</math>, which is a special case of the ballot problem.  (iii) Finally, use Stirling's approximation to derive that <math>\sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i}) = +\infty</math>.)</p>
</li>
</li>
<li><p>[<strong>Symmetric 1D random walk (III)</strong>] Let <math>(X_i)_{i \in \mathbb{N}}</math> be i.i.d. random variables, where <math>X_i</math> is uniformly chosen from <math>\{-1,1\}</math>. Let <math>S_n = \sum_{i=1}^{n} X_i</math>. Find out the probability <math>\mathbf{Pr}\left(\forall 1 \le i \le n, |S_i| \le m \right)</math>. (Hint: André's reflection principle)</p>
<li><p>[<strong>Symmetric 1D random walk (III)</strong>] Suppose that the game ends upon that the gambler loses all his <math>m</math> points or earns another <math>m</math> points (i.e., the number of points he possesses reaches <math>2m</math>). Let <math>C</math> be the event that the game ends within <math>n</math> rounds. Compute <math>\mathbf{Pr}(C)</math>. (Hint: A variant of the problem is sometimes called the ballot problem, and there is a famous trick known as André's reflection principle.)</p>
</li>
</li>
</ul>
<h2 id="problem-2-principle-of-inclusion-and-exclusion">Problem 2 (Principle of Inclusion and Exclusion)</h2>
<p>In the following tasks, for all <math>i \in \mathbb{N}</math>, <math>A_i</math> is an event.</p>
<ul>
<li>[<strong>Union bound</strong>] Prove that <math>\mathbf{Pr}\left( \bigcup_{i=1}^{+\infty} A_i \right) \le \sum_{i=1}^{+\infty} \mathbf{Pr}\left(A_i\right)</math>.</li>
<li>[<strong>Principle of Inclusion and Exclusion (PIE)</strong>] Prove that <math>\mathbf{Pr}\left( \bigcup_{i=1}^n A_i\right) = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \mathbf{Pr}\left( \bigcap_{i \in S} A_i \right)</math>, where <math>[n]=\{1,2,\ldots,n\}</math>.</li>
<li>[<strong>Derangements</strong>] Find the number of permutation <math>p = (p_1,p_2,\ldots,p_n)</math> satisfying that <math>p_i \neq i</math> for all <math>1 \le i \le n</math> using PIE. Sequence <math>p=(p_1,p_2,\ldots,p_n)</math> is a permutation if each integer from <math>1</math> to <math>n</math> appears exactly once in <math>p_1, p_2,\ldots, p_n</math>.</li>
<li>[<strong>Bonferroni&#39;s inequality and Kounias&#39;s inequality</strong>] Prove that
<math>
\sum_{i=1}^n \mathbf{Pr}(A_i) - \sum_{1 \le i< j \le n} \mathbf{Pr}(A_i \cap A_j)\le \mathbf{Pr}\left(\bigcup_{i=1}^n A_i\right) \le \sum_{i=1}^n \mathbf{Pr} \left( A_i\right) - \sum_{i=2}^n \mathbf{Pr}(A_1 \cap A_i).
</math>
(Hint: try using Venn diagram to understand these inequalites)</li>
</ul>
</ul>
<h2 id="problem-3-probability-space">Problem 3 (Probability space)</h2>
<h2 id="problem-3-probability-space">Problem 3 (Probability space)</h2>
<ul>
<ul>
<li><p>[<strong>Nonexistence of probability space</strong>] Prove that it is impossible to uniformly sample from the set of natural numbers <math>\mathbb{N}</math>, i.e., there exists no probability space <math>(\mathbb{N},2^{\mathbb{N}},\mathbf{Pr})</math> such that <math>\mathbf{Pr}(X = i) = \mathbf{Pr}(X = j)</math> for all <math>i, j \in \mathbb{N}</math>. Please clarify why your argument fails on proving that it is impossible to uniformly sample from interval <math>[0,1]</math>, i.e., there exists no probability space <math>([0,1],\mathcal{F},\mathbf{Pr})</math> such that for any interval <math>(l,r] \subseteq [0,1]</math>, <math>(l,r] \in \mathcal{F}</math> and <math>\mathbf{Pr}(X \in (l,r]) = r-l</math>. (Actually, such probability measure exists and is called the Lebesgue measure). </p>
<li><p>[<strong>Nonexistence of probability space</strong>] Prove that it is impossible to define a uniform probability law on natural numbers <math>\mathbb{N}</math>. More precisely, prove that there does not exist a probability space <math>(\mathbb{N},2^{\mathbb{N}},\mathbf{Pr})</math> such that <math>\mathbf{Pr}(\{i\}) = \mathbf{Pr}(\{j\})</math> for all <math>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>[0,1]</math>, that is, there is no such probability space <math>([0,1],\mathcal{F},\mathbf{Pr})</math> that for any interval <math>(l,r] \subseteq [0,1]</math>, it holds that <math>(l,r] \in \mathcal{F}</math> and <math>\mathbf{Pr}( (l,r] ) = r-l</math>. (Actually, such probability measure does exist and is called the Lebesgue measure on <math>[0,1]</math>). </p>
</li>
<li><p>[<strong>Smallest <math>\sigma</math>-field</strong>] For any subset <math>S \subseteq 2^\Omega</math>, prove that the smallest <math>\sigma</math>-field containing <math>S</math> is given by <math>\bigcap_{\substack{S \subseteq \mathcal{F} \subseteq 2^\Omega\\ \mathcal{F} \text{ is a } \sigma\text{-field }} } \mathcal{F}</math>. (Hint: You should show that it is indeed a <math>\sigma</math>-field and also it is the smallest one containing <math>S</math>.)</p>
</li>
</li>
<li><p>[<strong>Limit of events</strong>] Let <math>(A_i)_{i \in \mathbb{N}}</math> be a sequence of events.
<li><p>[<strong>Limit of events</strong>] Let <math>(A_i)_{i \in \mathbb{N}}</math> be a sequence of events.
Line 38: Line 46:
<li><math>\liminf A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for all but finitely many values of } n\}</math>;</li>
<li><math>\liminf A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for all but finitely many values of } n\}</math>;</li>
<li><math>\limsup A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for infinite many values of } n\}</math>;</li>
<li><math>\limsup A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for infinite many values of } n\}</math>;</li>
<li>If <math>A = \liminf A_n = \limsup A_n</math>, then <math>\mathbf{Pr}(A_n) \rightarrow \mathbf{Pr}(A)</math> when <math>n</math> tends to infinity;</li>
<li>If <math>A = \liminf A_n = \limsup A_n</math>, then <math>\mathbf{Pr}(A_n) \rightarrow \mathbf{Pr}(A)</math> as <math>n\to\infty</math>;</li>
<li>Furthermore, if <math>\bigcup_{k=n}^{+\infty} A_k</math> and <math>\bigcap_{k=n}^{+\infty} A_k</math> is independent for all <math>n</math> and <math>A = \liminf A_n = \limsup A_n</math>, then <math>\mathbf{Pr}(A)</math> is either <math>0</math> or <math>1</math>.</li>
<li>Furthermore, if the limit <math>A = \liminf A_n = \limsup A_n</math> exists and for every <math>n</math>, the two events <math>\bigcup_{k=n}^{+\infty} A_k</math> and <math>\bigcap_{k=n}^{+\infty} A_k</math> are independent, then <math>\mathbf{Pr}(A)</math> is either <math>0</math> or <math>1</math>.</li>
</ul>
</ul>
</li>
</li>
Line 45: Line 53:
<h2 id="problem-4-conditional-probability">Problem 4 (Conditional probability)</h2>
<h2 id="problem-4-conditional-probability">Problem 4 (Conditional probability)</h2>
<ul>
<ul>
<li><p>[<strong>Symmetric 1D random walk (IV)</strong>] Let <math>(X_i)_{i \in \mathbb{N}_+}</math> be i.i.d. random variables, where <math>X_i</math> is uniformly chosen from <math>\{-1,1\}</math>. Let <math>S_n = \sum_{i=1}^{n} X_i</math>. Compute <math>\textbf{Pr}(S_4 = 4|S_8 = 6)</math>.</p>
<li><p>[<strong>Conditional version of the total probability</strong>] Let <math>C_1,\cdots, C_n</math> be disjoint events that form a partition of the sample space. Let <math>A</math> and <math>B</math> be events such that <math>\textbf{Pr}(B\cap C_i)>0</math> for all <math>i</math>. Show that  
</li>
<li><p>[<strong>Conditional version of the total probability</strong>] Let <math>C_1,\cdots, C_n</math> be disjoint events that form a partition of the state space. Let <math>A</math> and <math>B</math> be events such that <math>\textbf{Pr}(B\cap C_i)>0</math> for all <math>i</math>. Show that  
<math>\textbf{Pr}(A|B) = \sum_{i = 1}^n \textbf{Pr}(C_i|B)\cdot \textbf{Pr}(A|B\cap C_i)</math></p>
<math>\textbf{Pr}(A|B) = \sum_{i = 1}^n \textbf{Pr}(C_i|B)\cdot \textbf{Pr}(A|B\cap C_i)</math></p>
</li>
</li>
<li><p>[<strong>Bayes&#39; Law</strong>] There are <math>n</math> urns filled with black and white balls. Let <math>f_i</math> be the fraction of white balls in urn <math>i</math>. In stage 1 an urn is chosen uniformly at random (i.e., each urn has probability <math>1/n</math> of being chosen). In stage 2 a ball is drawn uniformly at random from the urn. Let <math>U_i</math> be the event that urn <math>i</math> was selected at stage 1. Let <math>W</math> denote the event that a white ball is drawn at stage 2, and <math>B</math> denote the event that a black ball is drawn at stage 2. </p>
<li><p>[<strong>Balls in urns (I)</strong>] There are <math>n</math> urns of which the <math>r</math>-th contains <math>r-1</math> white balls and <math>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>{n-1\choose 2}</math> pairs of balls are chosen to be removed with equal probability). Find the following probabilities:
<ul>
# the second ball is black;
<li>Use Bayes&#39;s Law to express <math>\textbf{Pr}(U_i|W)</math> in terms of <math>f_1,\cdots, f_n</math>.</li>
# the second ball is black, given that the first is black.
<li>Let&#39;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>\textbf{Pr}(U_1|B)</math>, <math>\textbf{Pr}(U_2|B)</math> and <math>\textbf{Pr}(U_3|B)</math>.</li>
</p></li>
</ul>
<li><p>[<strong>Balls in urns (II)</strong>] Suppose that an urn contains <math>w</math> white balls and <math>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:
# the first white ball drawn is the <math>(k+1)</math>th ball;
# the last ball drawn is white.
</p></li>
<li>[<strong>Balls in urns (III)</strong>] There are <math>n</math> urns filled with black and white balls. Let <math>f_i</math> be the fraction of white balls in the <math>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>U_i</math> be the event that the <math>i</math>-th urn was chosen at stage 1. Let <math>W</math> be the event that a white ball is drawn at stage 2, and <math>B</math> be the event that a black ball is drawn at stage 2.
# Use Bayes&#39;s Law to express <math>\textbf{Pr}(U_i|W)</math> in terms of <math>f_1,\cdots, f_n</math>.
# Let&#39;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>\textbf{Pr}(U_1|B)</math>, <math>\textbf{Pr}(U_2|B)</math> and <math>\textbf{Pr}(U_3|B)</math>.
</li>
</li>
</ul>
</ul>
<h2 id="problem-5-independence">Problem 5 (Independence)</h2>
<h2 id="problem-5-independence">Problem 5 (Independence)</h2>
<p>Let&#39;s consider <math>n</math> independent and identically distributed Bernoulli random variables <math>(X_1, X_2, \cdots, X_n)</math> related to <math>n</math> same Bernoulli trials, where each trail succeeds with probability <math>p</math> for <math>0 < p < 1</math>.</p>
<p>Let&#39;s consider a series of <math>n</math> outputs <math>(X_1, X_2, \cdots, X_n) \in \{0,1\}^n</math> of <math>n</math> independent Bernoulli trials, where each trial succeeds with the same probability <math>0 < p < 1</math>.</p>
<ul>
<ul>
<li><p>[<strong>Limited independence</strong>] Let <math>n = 2</math>. Construct three events <math>A,B</math> and <math>C</math> in <math>\mathcal{F}</math> such that <math>A, B</math> and <math>C</math> are pairwise independent but are not (mutually) independent. You also need to explain your choices.</p>
<li><p>[<strong>Limited independence</strong>] Construct three events <math>A,B</math> and <math>C</math> out of <math>n</math> Bernoulli trials such that <math>A, B</math> and <math>C</math> are pairwise independent but are not (mutually) independent. You need to prove that the constructed events <math>A, B</math> and <math>C</math> satisfy this. (Hint: Consider the case where <math>n = 2</math> and <math>p = 1/2</math>.)</p>
</li>
</li>
<li><p>[<strong>Product distribution</strong>] Suppose someone has observed the output of <math>n</math> trials, and she told you that the trail succeeded in precisely <math>k</math> rounds for <math>0< k< n</math>. Now you want to predict the output of <math>(n-1)</math>-th trail while <math>p</math> is unknown. One way to estimate <math>p</math> is to find a <math>\hat{p}</math> which makes the observed result most probable, namely you need to solve  
<li><p>[<strong>Product distribution</strong>] Suppose someone has observed the output of the <math>n</math> trials, and she told you that precisely <math>k</math> out of <math>n</math> trials succeeded for some <math>0< k< n</math>. Now you want to predict the output of the <math>(n+1)</math>-th trial while the parameter <math>p</math> of the Bernoulli trial is unknown. One way to estimate <math>p</math> is to find such <math>\hat{p}</math> that makes the observed outcomes most probable, namely you need to solve  
   <math>\arg \max_{p\in(0,1)} \mathbf{Pr}_p [\text{the trail succeeded } k \text{ times}].</math></p>
   <math>\arg \max_{\hat{p}\in(0,1)} \mathbf{Pr}_{\hat{p}} [k \text{ out of } n\text{ trials succeed}].</math></p>
<ul>
<ol>
<li>Estimate <math>p</math> by the given objective function.</li>
<li>Estimate <math>p</math> by solving the above optimization problem.</li>
<li>If someone tells you exactly which <math>k</math> rounds in total <math>n</math> trails that are success, would it help you to estimate <math>p</math> more accurately? Why?</li>
<li>If someone tells you exactly which <math>k</math> trials succeed (in addition to just telling you the number of successful trials, which is <math>k</math>), would it help you to estimate <math>p</math> more accurately? Why?</li>
</ul>
</ol>
</li>
</li>
</ul>
</ul>
<h2 id="problem-6-probabilistic-method">Problem 6 (Probabilistic method)</h2>
<h2 id="problem-6-probabilistic-method">Problem 6 (Probabilistic method)</h2>
<p>A CNF formula over variables <math>x_1,\cdots, x_n</math> is a conjunction (AND) of clause, where each clause is an OR of literals. A literal is either a variable <math>x_1</math> or its negation <math>\bar{x}_i</math>. A CNF formula is satisfiable if there is an assignment to the variables that makes the formula true. A <math>k</math>-CNF formula is a CNF formula where each clause of it has exactly <math>k</math> literals (without repetition.)</p>
<p>A '''CNF formula''' ('''合取范式''') <math>\Phi</math> over <math>n</math> Boolean variables <math>x_1,\cdots, x_n</math> is a '''conjunction''' (<math>\land</math>) of '''clauses''' ('''子句''') <math>\Phi=C_1\land C_2\land\cdots\land C_m</math>, where each clause <math>C_j=\ell_{j_1}\lor\ell_{j_2}\cdots\lor\ell_{j_k}</math> is a '''disjunction''' (<math>\lor</math>) of '''literals''' ('''文字'''), where a literal <math>\ell_r</math> is either a variable <math>x_i</math> or the negation <math>\bar{x}_i</math> of a variable. A CNF formula is '''satisfiable''' ('''可满足''') if there is a truth assignment <math>x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n</math> to the variables such that <math>\Phi(x)=\mathtt{true}</math>. A <math>k</math>-CNF formula is a CNF formula in which each clause contains exactly <math>k</math> literals (without repetition).</p>
<ul>
<ul>
<li>[<strong>Satisfiability (I)</strong>] Let <math>F</math> be a <math>k</math>-CNF with less than <math>2^k</math> clauses. Use the probabilistic method to show that <math>F</math> must be satisfiable. </li>
<li>[<strong>Satisfiability (I)</strong>] Let <math>\Phi</math> be a <math>k</math>-CNF with less than <math>2^k</math> clauses. Use the probabilistic method to show that <math>\Phi</math> must be satisfiable. You should be explicit about the probability space that is used. </li>
<li>[<strong>Satisfiability (II)</strong>] Give a constructive proof of same problem above. That is, prove that <math>F</math> is satisfiable by showing how to construct an assignment that does satisfy <math>F</math>. Your construction doesn&#39;t have to be efficient. By doing this, You may better understand the probabilitic method.</li>
<li>[<strong>Satisfiability (II)</strong>] Give a constructive proof of the same problem above. That is, prove that <math>\Phi</math> is satisfiable by showing how to construct a truth assignment <math>x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n</math> such that <math>\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.</li>
<li>[<strong>Satisfiability (III)</strong>] Let <math>F</math> be a <math>k</math>-CNF with <math>m\geq 2^k</math> clauses. Show that there must exist an assignment satisfying at least <math>\lfloor m(1-1/2^k) \rfloor</math> clauses in <math>F</math>. (Hint: Consider overlaps of events in Venn diagram.)</li>
<li>[<strong>Satisfiability (III)</strong>] Let <math>\Phi</math> be a <math>k</math>-CNF with <math>m\geq 2^k</math> clauses. Use the probabilistic method to show that there exists a truth assignment <math>x=(x_1,\cdots, x_n)\in \{\mathtt{true},\mathtt{false}\}^n</math> satisfying at least <math>\lfloor m(1-1/2^k) \rfloor</math> clauses in <math>\Phi</math>. (Hint: Consider overlaps of events in Venn diagram.) You should be explicit about the probability space that is used.</li>
</ul>
</ul>

Latest revision as of 08:45, 19 March 2024

  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。
  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用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 1 (Principle of Inclusion and Exclusion)

Let [math]\displaystyle{ n\ge 1 }[/math] be a positive integer and [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be [math]\displaystyle{ n }[/math] events.

  • [Union bound] Prove [math]\displaystyle{ \mathbf{Pr}\left( \bigcup_{i=1}^{n} A_i \right) \le \sum_{i=1}^{n} \mathbf{Pr}\left(A_i\right) }[/math] using the definition of probability space.
  • [Principle of Inclusion and Exclusion (PIE)] Prove that [math]\displaystyle{ \mathbf{Pr}\left( \bigcup_{i=1}^n A_i\right) = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \mathbf{Pr}\left( \bigcap_{i \in S} A_i \right) }[/math], where [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math].
  • [Surjection] For positive integers [math]\displaystyle{ m\ge n }[/math], prove that the probability of a uniform random function [math]\displaystyle{ f:[m]\to[n] }[/math] to be surjective (满射) is [math]\displaystyle{ \sum_{k=1}^n(-1)^{n-k}{n\choose k}\left(\frac{k}{n}\right)^m }[/math].
  • [Proper [math]\displaystyle{ q }[/math]-coloring of [math]\displaystyle{ n }[/math]-cycle] Given an arbitrary integer [math]\displaystyle{ q\ge 2 }[/math], calculate the probability of a uniform random [math]\displaystyle{ n }[/math]-tuples [math]\displaystyle{ p = (p_1,p_2,\ldots,p_n)\in[q]^n }[/math] satisfying the following property: [math]\displaystyle{ p_{n} \neq p_1 }[/math] and [math]\displaystyle{ p_i \neq p_{i+1} }[/math] for all [math]\displaystyle{ 1 \le i \le n-1 }[/math]. You are required to apply PIE to calculate this probability. Note that this is the probability of a uniform random [math]\displaystyle{ q }[/math]-coloring of an [math]\displaystyle{ n }[/math]-cycle to be proper.
  • [Bonferroni's inequality and Kounias' inequality] Prove that [math]\displaystyle{ \sum_{i=1}^n \mathbf{Pr}(A_i) - \sum_{1 \le i\lt j \le n} \mathbf{Pr}(A_i \cap A_j)\le \mathbf{Pr}\left(\bigcup_{i=1}^n A_i\right) \le \sum_{i=1}^n \mathbf{Pr} \left( A_i\right) - \sum_{i=2}^n \mathbf{Pr}(A_1 \cap A_i). }[/math] (Hint: This is sometimes called Kounias' inequality which is weaker than the Bonferroni's inequality. You can try using Venn diagram to understand these inequalities.)

Problem 2 (Symmetric 1D random walk)

A gambler plays a fair gambling game: At each round, he flips a fair coin, earns [math]\displaystyle{ 1 }[/math] point if it's HEADs, and loses [math]\displaystyle{ 1 }[/math] point if otherwise.

  • [Symmetric 1D random walk (I)] Let [math]\displaystyle{ A_i }[/math] be the event that the gambler earns [math]\displaystyle{ 0 }[/math] points after playing [math]\displaystyle{ i }[/math] rounds of the game, that is, the number of times the coin lands on heads is equal to the number of times it lands on tails. Compute [math]\displaystyle{ \sum_{i=1}^{+\infty} \mathbf{Pr}(A_i) }[/math]. (Hint: You may use Stirling's approximation to estimate [math]\mathbf{Pr}(A_i)[/math] and derive that [math]\displaystyle{ \sum_{i=1}^{+\infty} \mathbf{Pr}(A_i) = +\infty }[/math].)

  • [Symmetric 1D random walk (II)] Suppose that the game ends upon that the gambler loses all his [math]\displaystyle{ m }[/math] points. Let [math]\displaystyle{ B_i }[/math] be the event that the game ends within [math]\displaystyle{ i }[/math] rounds. Compute [math]\displaystyle{ \sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i}) }[/math]. (Hint: You may first consider [math] \displaystyle{m = 1}[/math] case. Let [math]\displaystyle{C_i}[/math] be the event that the game ends at the [math]\displaystyle{i}[/math]-th round. (i) Prove that [math]\displaystyle{ \sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i}) = \sum_{i=1}^{+\infty} (i-1) \mathbf{Pr}(C_i) }[/math]. (ii) Compute [math]\displaystyle{ \mathbf{Pr}(C_i) }[/math], which is a special case of the ballot problem. (iii) Finally, use Stirling's approximation to derive that [math]\displaystyle{ \sum_{i=1}^{+\infty} \mathbf{Pr}(\overline{B_i}) = +\infty }[/math].)

  • [Symmetric 1D random walk (III)] Suppose that the game ends upon that the gambler loses all his [math]\displaystyle{ m }[/math] points or earns another [math]\displaystyle{ m }[/math] points (i.e., the number of points he possesses reaches [math]\displaystyle{ 2m }[/math]). Let [math]\displaystyle{ C }[/math] be the event that the game ends within [math]\displaystyle{ n }[/math] rounds. Compute [math]\displaystyle{ \mathbf{Pr}(C) }[/math]. (Hint: A variant of the problem is sometimes called the ballot problem, and there is a famous trick known as André's reflection principle.)

Problem 3 (Probability space)

  • [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}},\mathbf{Pr}) }[/math] such that [math]\displaystyle{ \mathbf{Pr}(\{i\}) = \mathbf{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},\mathbf{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{ \mathbf{Pr}( (l,r] ) = r-l }[/math]. (Actually, such probability measure does exist and is called the Lebesgue measure on [math]\displaystyle{ [0,1] }[/math]).

  • [Smallest [math]\displaystyle{ \sigma }[/math]-field] For any subset [math]\displaystyle{ S \subseteq 2^\Omega }[/math], prove that the smallest [math]\displaystyle{ \sigma }[/math]-field containing [math]\displaystyle{ S }[/math] is given by [math]\displaystyle{ \bigcap_{\substack{S \subseteq \mathcal{F} \subseteq 2^\Omega\\ \mathcal{F} \text{ is a } \sigma\text{-field }} } \mathcal{F} }[/math]. (Hint: You should show that it is indeed a [math]\displaystyle{ \sigma }[/math]-field and also it is the smallest one containing [math]\displaystyle{ S }[/math].)

  • [Limit of events] Let [math]\displaystyle{ (A_i)_{i \in \mathbb{N}} }[/math] be a sequence of events. Define [math]\displaystyle{ \limsup A_n = \bigcap_{n=1}^{+\infty} \bigcup_{k=n}^{+\infty} A_k }[/math] and [math]\displaystyle{ \liminf A_n = \bigcup_{n=1}^{+\infty} \bigcap_{k=n}^{+\infty} A_k }[/math]. Prove that

    • [math]\displaystyle{ \liminf A_n, \limsup A_n \in \mathcal{F} }[/math] and [math]\displaystyle{ \liminf A_n \subseteq \limsup A_n }[/math];
    • [math]\displaystyle{ \liminf A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for all but finitely many values of } n\} }[/math];
    • [math]\displaystyle{ \limsup A_n = \{\omega \in \Omega \mid \omega \in A_n \text{ for infinite many values of } n\} }[/math];
    • If [math]\displaystyle{ A = \liminf A_n = \limsup A_n }[/math], then [math]\displaystyle{ \mathbf{Pr}(A_n) \rightarrow \mathbf{Pr}(A) }[/math] as [math]\displaystyle{ n\to\infty }[/math];
    • Furthermore, if the limit [math]\displaystyle{ A = \liminf A_n = \limsup A_n }[/math] exists and for every [math]\displaystyle{ n }[/math], the two events [math]\displaystyle{ \bigcup_{k=n}^{+\infty} A_k }[/math] and [math]\displaystyle{ \bigcap_{k=n}^{+\infty} A_k }[/math] are independent, then [math]\displaystyle{ \mathbf{Pr}(A) }[/math] is either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math].

Problem 4 (Conditional probability)

  • [Conditional version of the total probability] Let [math]\displaystyle{ C_1,\cdots, C_n }[/math] be disjoint events that form a partition of the sample space. Let [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] be events such that [math]\displaystyle{ \textbf{Pr}(B\cap C_i)\gt 0 }[/math] for all [math]\displaystyle{ i }[/math]. Show that [math]\displaystyle{ \textbf{Pr}(A|B) = \sum_{i = 1}^n \textbf{Pr}(C_i|B)\cdot \textbf{Pr}(A|B\cap C_i) }[/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.