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

From TCS Wiki
Jump to navigation Jump to search
Zhangxy (talk | contribs)
Zhangxy (talk | contribs)
 
(47 intermediate revisions by 2 users not shown)
Line 10: Line 10:
<p>The term <math>\log</math> used in this context refers to the natural logarithm.</p>
<p>The term <math>\log</math> used in this context refers to the natural logarithm.</p>


== Problem 1 ==
== Problem 1 (Warm-up Problems) ==
<ul>
<ul>
     <li>[<strong>Variance (I)</strong>]
     <li>[<strong>Variance (I)</strong>]
         For pairwise independent random variables <math>X_1,X_2,\cdots, X_n</math>, show that <math>\textbf{Var}\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n \textbf{Var} (X_i)</math>.
         Let <math>X_1,X_2,\cdots, X_n</math> be pairwise independent random variables. Show that <math>\textbf{Var}\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n \textbf{Var} [X_i]</math>.
     </li>
     </li>
     <li>[<strong>Variance (II)</strong>]
     <li>[<strong>Variance (II)</strong>]
         Let <math>X = \sum_{i=1}^N X_i</math>, where <math>X_i (i\geq 1)</math> are independent, identically distributed random variables with mean <math>\mu</math> and variance <math>\sigma^2</math>, and <math>N</math> is positive, integer-valued random variable, and is independent of the <math>X_i</math> for all <math>i\geq 1</math>. Show that <math>\textbf{Var}(X) = \sigma^2\mathbb{E}[N] + \mu^2 \textbf{Var}(N)</math>.
         Each member of a group of <math>n</math> players rolls a (fair) die. For any pair of players who throw the same number, the group scores <math>1</math> point. Find the mean and variance of the total score of the group.
     </li>
     </li>
     <li>[<strong>Variance (III)</strong>]
     <li>[<strong>Variance (III)</strong>]
         Each member of a group of <math>n</math> players rolls a dice (with six faces). For any pair of players who throw the same number, the group scores 1 point. Find the mean and variance of the total score of the group. (Hint: use the property of pairwise independent.)
         An urn contains <math>n</math> balls numbered <math>1, 2, \ldots, n</math>. We select <math>k</math> balls uniformly at random <strong>without replacement</strong> and add up their numbers. Find the mean and variance of the sum.
     </li>
     </li>
     <li>[<strong>Variance (IV)</strong>]
     <li>[<strong>Variance (IV)</strong>]
        An urn contains <math>n</math> balls numbered 1, 2, ..., <math>n</math>. We remove <math>k</math> balls at random (without replacement) and add up their numbers. Find the mean and variance of the sum.
      Let <math>N</math> be an integer-valued, positive random variable and let <math>\{X_i\}_{i=1}^{\infty}</math> be indepedently identically distributed random variables that are independent of <math>N</math>, too.  
Precisely, for any finite subset <math>I \subseteq\mathbb{N}_+</math>, <math>\{X_i\}_{i \in I}</math> and <math>N</math> are mutually independent. Let <math>X = \sum_{i=1}^N X_i</math>, show that <math>\textbf{Var}[X] = \textbf{Var}[X_1] \mathbb{E}[N] + \mathbb{E}[X_1]^2 \textbf{Var}[N]</math>.
     </li>
     </li>
     <li> [<strong>Moments (I)</strong>]
     <li> [<strong>Moments (I)</strong>]
Line 28: Line 29:
     </li>
     </li>
     <li>[<strong>Moments (II)</strong>]
     <li>[<strong>Moments (II)</strong>]
         Let <math>X\sim \text{Geo}(p)</math> for some <math>p \in (0,1)</math>. Find <math>\mathbb{E}[X^3]</math> and <math>\mathbb{E}[X^4]</math>. (Hint: find a recursive expression from <math>\mathbb{E}[X^{n-1}]</math> to <math>\mathbb{E}[X^{n}]</math> may be useful.)
         Let <math>X\sim \text{Geo}(p)</math> for some <math>p \in (0,1)</math>. Find <math>\mathbb{E}[X^3]</math> and <math>\mathbb{E}[X^4]</math>.  
    </li>
    <li>[<strong>Moments (III)</strong>]
        Let <math>X\sim \text{Pois}(\lambda)</math> for some <math>\lambda >0 </math>. Find <math>\mathbb{E}[X^3]</math> and <math>\mathbb{E}[X^4]</math>.  
     </li>
     </li>
     <li>[<strong>Covariance and correlation (I)</strong>]
     <li>[<strong>Covariance and correlation (I)</strong>]
         Let <math>X</math> and <math>Y</math> be discrete random variables with correlation <math>\rho</math>. Show that <math>|\rho|\leq 1</math>.
         Let <math>X</math> and <math>Y</math> be discrete random variables with correlation <math>\rho</math>. Show that <math>|\rho|\leq 1</math>.
    </li>
    <li>[<strong>Covariance and correlation (II)</strong>]
    Let [math]X[/math] and [math]Y[/math] be discrete random variables with mean <math>0</math>, variance <math>1</math>, and correlation [math]\rho[/math]. Show that [math]\mathbb{E}(\max\{X^2,Y^2\})\leq 1+\sqrt{1-\rho^2}[/math]. (Hint: use the identity [math]\max\{a,b\} = \frac{1}{2}(a+b+|a-b|)[/math].)
</li>
<li>[<strong>Covariance and correlation (III)</strong>]
    Construct two random variables [math]X[/math] and [math]Y[/math] such that their covariance [math]\textbf{Cov}(X,Y) = 0[/math] but [math]X[/math] and [math]Y[/math] are not independent. You should prove your construction is true.
</li>
</ul>
== Problem 2 (Inequalities) ==
<ul>
<li>
    <strong>[Reverse Markov's inequality]</strong> Let <math>X</math> be a discrete random variable with bounded range <math>0 \le X \le U</math> for some <math>U > 0</math>. Show that <math>\mathbf{Pr}(X \le a) \le \frac{U-\mathbf{E}[X]}{U-a}</math> for any <math>0 < a < U</math>.
</li>
<li>
    <strong>[Markov's inequality]</strong> Let <math>X</math> be a discrete random variable. Show that for all <math>\beta \geq 0</math> and all <math>x > 0</math>, <math>\mathbf{Pr}(X\geq x)\leq \mathbb{E}(e^{\beta X})e^{-\beta x}</math>.
</li>
<li>
    <strong>[Cantelli's inequality]</strong> Let <math>X</math> be a discrete random variable with mean <math>0</math> and variance <math>\sigma^2</math>. Prove that for any <math>\lambda > 0</math>, <math>\mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2}{\lambda^2+\sigma^2}</math>. (Hint: You may first show that <math>\mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2 + u^2}{(\lambda + u)^2}</math> for all <math>u > 0</math>.)
</li>
<li>
    <strong>[The weak law of large numbers]</strong> Let <math>X_1,X_2,\cdots, X_n</math> be independent and identically distributed random variables with mean <math>\mu</math> and finite variance, use Chebyshev's inequality to show that for any constant <math>\epsilon>0</math> we have
    <math>\lim_{n\rightarrow \infty} \mathbf{Pr}\left( \left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu\right| > \epsilon\right) = 0</math>.
</li>
<li>
    <strong>[Median trick]</strong> Suppose we want to estimate the value of <math>Z</math>. Let <math>\mathcal{A}</math> be a randomized algorithm that outputs <math>\widehat{Z}</math> satisfying <math>\mathbf{Pr}[(1-\epsilon) Z \leq \widehat{Z} \leq (1+\epsilon)Z]\geq \frac{3}{4}</math> for some fixed parameter <math>\epsilon > 0</math>. We run <math>\mathcal{A}</math> independently for <math>2n-1</math> times, and obtain the outputs <math>\widehat{Z}_1,  \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1}</math>. Let <math>X</math> be the median (中位数) of <math>\widehat{Z}_1,  \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1}</math>. Use Chebyshev's inequality to show that <math>\mathbf{Pr}[(1-\epsilon) Z \leq X \leq (1+\epsilon)Z] = 1 - O(1/n)</math>. (Remark: The bound can be drastically improved with [https://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound]).
</li>
</ul>
== Problem 3 (Probability meets graph theory) ==
<ul>   
<li>[<strong>Common neighbor</strong>]
        Let <math>p \in (0,1)</math> be a constant.
        Show that with a probability approaching to <math>1</math> (as <math>n</math> tends to infinity) the Erdős–Rényi random graph <math>\mathbf{G}(n,p)</math> has the property that every pair of its vertices has a common neighbor. (Hint: You may use Markov's inequality.)
    </li>
    <li>[<strong>Isolated vertices</strong>]
        Prove that <math>p = \log n/n</math> is the threshold probability for the disappearance of isolated vertices.
        Formally, you are required to show that
        <ol type="a">
            <li>
                with a probability approaching to <math>1</math> (as <math>n</math> tends to infinity) the Erdős–Rényi random graph <math>\mathbf{G} = \mathbf{G}(n,p)</math> has the property that <math>\mathbf{G}</math> has no isolated vertices when <math>p = \omega(\log n/n)</math>;
            </li>
            <li>
                with a probability approaching to <math>0</math> (as <math>n</math> tends to infinity) the Erdős–Rényi random graph <math>\mathbf{G} = \mathbf{G}(n,p)</math> has the property that <math>\mathbf{G}</math> has no isolated vertices when <math>p = o(\log n/n)</math>.
            </li>
        </ol>
     </li>
     </li>
</ul>
</ul>

Latest revision as of 07:46, 25 April 2023

  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Assumption throughout Problem Set 3

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

Without further notice, we assume that the expectation of random variables are well-defined.

The term [math]\displaystyle{ \log }[/math] used in this context refers to the natural logarithm.

Problem 1 (Warm-up Problems)

  • [Variance (I)] Let [math]\displaystyle{ X_1,X_2,\cdots, X_n }[/math] be pairwise independent random variables. Show that [math]\displaystyle{ \textbf{Var}\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n \textbf{Var} [X_i] }[/math].
  • [Variance (II)] Each member of a group of [math]\displaystyle{ n }[/math] players rolls a (fair) die. For any pair of players who throw the same number, the group scores [math]\displaystyle{ 1 }[/math] point. Find the mean and variance of the total score of the group.
  • [Variance (III)] An urn contains [math]\displaystyle{ n }[/math] balls numbered [math]\displaystyle{ 1, 2, \ldots, n }[/math]. We select [math]\displaystyle{ k }[/math] balls uniformly at random without replacement and add up their numbers. Find the mean and variance of the sum.
  • [Variance (IV)] Let [math]\displaystyle{ N }[/math] be an integer-valued, positive random variable and let [math]\displaystyle{ \{X_i\}_{i=1}^{\infty} }[/math] be indepedently identically distributed random variables that are independent of [math]\displaystyle{ N }[/math], too. Precisely, for any finite subset [math]\displaystyle{ I \subseteq\mathbb{N}_+ }[/math], [math]\displaystyle{ \{X_i\}_{i \in I} }[/math] and [math]\displaystyle{ N }[/math] are mutually independent. Let [math]\displaystyle{ X = \sum_{i=1}^N X_i }[/math], show that [math]\displaystyle{ \textbf{Var}[X] = \textbf{Var}[X_1] \mathbb{E}[N] + \mathbb{E}[X_1]^2 \textbf{Var}[N] }[/math].
  • [Moments (I)] Find an example of a random variable with finite [math]\displaystyle{ j }[/math]-th moments for [math]\displaystyle{ 1 \leq j \leq k }[/math] but an unbounded [math]\displaystyle{ (k + 1) }[/math]-th moment. Give a clear argument showing that your choice has these properties.
  • [Moments (II)] Let [math]\displaystyle{ X\sim \text{Geo}(p) }[/math] for some [math]\displaystyle{ p \in (0,1) }[/math]. Find [math]\displaystyle{ \mathbb{E}[X^3] }[/math] and [math]\displaystyle{ \mathbb{E}[X^4] }[/math].
  • [Moments (III)] Let [math]\displaystyle{ X\sim \text{Pois}(\lambda) }[/math] for some [math]\displaystyle{ \lambda \gt 0 }[/math]. Find [math]\displaystyle{ \mathbb{E}[X^3] }[/math] and [math]\displaystyle{ \mathbb{E}[X^4] }[/math].
  • [Covariance and correlation (I)] Let [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] be discrete random variables with correlation [math]\displaystyle{ \rho }[/math]. Show that [math]\displaystyle{ |\rho|\leq 1 }[/math].
  • [Covariance and correlation (II)] Let [math]X[/math] and [math]Y[/math] be discrete random variables with mean [math]\displaystyle{ 0 }[/math], variance [math]\displaystyle{ 1 }[/math], and correlation [math]\rho[/math]. Show that [math]\mathbb{E}(\max\{X^2,Y^2\})\leq 1+\sqrt{1-\rho^2}[/math]. (Hint: use the identity [math]\max\{a,b\} = \frac{1}{2}(a+b+|a-b|)[/math].)
  • [Covariance and correlation (III)] Construct two random variables [math]X[/math] and [math]Y[/math] such that their covariance [math]\textbf{Cov}(X,Y) = 0[/math] but [math]X[/math] and [math]Y[/math] are not independent. You should prove your construction is true.

Problem 2 (Inequalities)

  • [Reverse Markov's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable with bounded range [math]\displaystyle{ 0 \le X \le U }[/math] for some [math]\displaystyle{ U \gt 0 }[/math]. Show that [math]\displaystyle{ \mathbf{Pr}(X \le a) \le \frac{U-\mathbf{E}[X]}{U-a} }[/math] for any [math]\displaystyle{ 0 \lt a \lt U }[/math].
  • [Markov's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable. Show that for all [math]\displaystyle{ \beta \geq 0 }[/math] and all [math]\displaystyle{ x \gt 0 }[/math], [math]\displaystyle{ \mathbf{Pr}(X\geq x)\leq \mathbb{E}(e^{\beta X})e^{-\beta x} }[/math].
  • [Cantelli's inequality] Let [math]\displaystyle{ X }[/math] be a discrete random variable with mean [math]\displaystyle{ 0 }[/math] and variance [math]\displaystyle{ \sigma^2 }[/math]. Prove that for any [math]\displaystyle{ \lambda \gt 0 }[/math], [math]\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2}{\lambda^2+\sigma^2} }[/math]. (Hint: You may first show that [math]\displaystyle{ \mathbf{Pr}[X \ge \lambda] \le \frac{\sigma^2 + u^2}{(\lambda + u)^2} }[/math] for all [math]\displaystyle{ u \gt 0 }[/math].)
  • [The weak law of large numbers] Let [math]\displaystyle{ X_1,X_2,\cdots, X_n }[/math] be independent and identically distributed random variables with mean [math]\displaystyle{ \mu }[/math] and finite variance, use Chebyshev's inequality to show that for any constant [math]\displaystyle{ \epsilon\gt 0 }[/math] we have [math]\displaystyle{ \lim_{n\rightarrow \infty} \mathbf{Pr}\left( \left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu\right| \gt \epsilon\right) = 0 }[/math].
  • [Median trick] Suppose we want to estimate the value of [math]\displaystyle{ Z }[/math]. Let [math]\displaystyle{ \mathcal{A} }[/math] be a randomized algorithm that outputs [math]\displaystyle{ \widehat{Z} }[/math] satisfying [math]\displaystyle{ \mathbf{Pr}[(1-\epsilon) Z \leq \widehat{Z} \leq (1+\epsilon)Z]\geq \frac{3}{4} }[/math] for some fixed parameter [math]\displaystyle{ \epsilon \gt 0 }[/math]. We run [math]\displaystyle{ \mathcal{A} }[/math] independently for [math]\displaystyle{ 2n-1 }[/math] times, and obtain the outputs [math]\displaystyle{ \widehat{Z}_1, \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1} }[/math]. Let [math]\displaystyle{ X }[/math] be the median (中位数) of [math]\displaystyle{ \widehat{Z}_1, \widehat{Z}_2, \cdots, \widehat{Z}_{2n-1} }[/math]. Use Chebyshev's inequality to show that [math]\displaystyle{ \mathbf{Pr}[(1-\epsilon) Z \leq X \leq (1+\epsilon)Z] = 1 - O(1/n) }[/math]. (Remark: The bound can be drastically improved with Chernoff bound).

Problem 3 (Probability meets graph theory)

  • [Common neighbor] Let [math]\displaystyle{ p \in (0,1) }[/math] be a constant. Show that with a probability approaching to [math]\displaystyle{ 1 }[/math] (as [math]\displaystyle{ n }[/math] tends to infinity) the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G}(n,p) }[/math] has the property that every pair of its vertices has a common neighbor. (Hint: You may use Markov's inequality.)
  • [Isolated vertices] Prove that [math]\displaystyle{ p = \log n/n }[/math] is the threshold probability for the disappearance of isolated vertices. Formally, you are required to show that
    1. with a probability approaching to [math]\displaystyle{ 1 }[/math] (as [math]\displaystyle{ n }[/math] tends to infinity) the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }[/math] has the property that [math]\displaystyle{ \mathbf{G} }[/math] has no isolated vertices when [math]\displaystyle{ p = \omega(\log n/n) }[/math];
    2. with a probability approaching to [math]\displaystyle{ 0 }[/math] (as [math]\displaystyle{ n }[/math] tends to infinity) the Erdős–Rényi random graph [math]\displaystyle{ \mathbf{G} = \mathbf{G}(n,p) }[/math] has the property that [math]\displaystyle{ \mathbf{G} }[/math] has no isolated vertices when [math]\displaystyle{ p = o(\log n/n) }[/math].