Lesson 2

Advanced Problems.

1. (20 points) Let \(X\) be a random variable with expected value \(E[X] = 0\) and variance \(\operatorname{Var}[X] = \sigma^{2}\). Prove that for any \(\lambda > 0\): \[\Pr[X \ge \lambda] \le \frac{\sigma^2}{\sigma^2 + \lambda^2}.\]
   Hint:

   Consider introducing a constant \(b > 0\) and observing that the event \(X \ge \lambda\) is equivalent to \(X + b \ge \lambda + b\).
2. (20 points) Let \(\operatorname{Cov}(X, Y) = E[XY] - E[X]E[Y]\) denote the covariance between two random variables \(X\) and \(Y\). Show that the variance of the sum of \(n\) random variables is given by \[\operatorname{Var}\left[\sum_{i=1}^{n} X_{i}\right] = \sum_{i=1}^{n} \operatorname{Var}[X_{i}] + 2 \sum_{1 \le i < j \le n}\operatorname{Cov}(X_{i}, X_{j}).\]
   Hint:

   It may be helpful to first prove the bilinearity of covariance using the definition of expectation. Specifically, show that \(\operatorname{Cov}\left(\sum_{i} X_{i}, \sum_{j} Y_{j}\right) = \sum_{i} \sum_{j} \operatorname{Cov}(X_{i}, Y_{j})\).
3. (20 points) Let \(X\) be a non-negative random variable with finite variance such that \(\Pr[X>0]>0\). Prove that for any \(0 \le \theta \le 1\): \[\Pr[X > \theta E[X]] \ge (1-\theta)^{2} \frac{E[X]^2}{E[X^2]}.\]
   Hint:

   Express \(E[X]\) using the sum of expectations over two regions: where \(X \le \theta E[X]\) and where \(X > \theta E[X]\).
4. (20 points) Let \(X_{i}\) be independent Bernoulli random variables with \(\Pr[X_{i}=1]=p_{i}\). Let \(X = X_{1} + \cdots + X_{n}\) and \(p = p_{1} + \cdots + p_{n}\).
   • For any \(t>0\) and \(\delta>0\), prove: \[\Pr[X \ge (1+\delta)p] \le \frac{E[e^{tX}]}{e^{t(1+\delta)p}}.\]
   
   
   • Prove that: \[E[e^{tX}] = \prod_{i=1}^{n} (p_{i} e^{t} + 1 - p_{i}).\]
   
   
   • Prove that: \[\Pr[X \ge (1+\delta)p] \le \frac{e^{(e^t-1)p}}{e^{t(1+\delta)p}}.\]
   
   
   • Substitute \(t = \ln(1+\delta)\) and write the resulting upper bound.
   
   
   • Show that if \(\delta > 2e-1\), then \(\Pr[X \ge (1+\delta)p] < 2^{-(1+\delta)p}\).
   
   

   Hint:

   For (c), recall that \(1 + x \le e^{x}\).
5. (20 points) Consider a random graph \(G(n, p)\) where every edge exists independently with probability \(p\). Let \(T\) be the number of triangles (sets of 3 vertices \(\{u,v,w\}\) where all edges \((u,v), (v,w), (u,w)\) exist). Compute \(\operatorname{Var}[T]\).