CSE 525: Randomized Algorithms and Probability Spring 2026 HW5 Submit to gradescope

Instructions

• You should think about each problem by yourself for at least an hour before choosing to collaborate with others.

• You are allowed to collaborate with fellow students taking the class in solving the problems. But you must write your solution on your own.

• You are not allowed to search for answers or hints on the web. You are encouraged to contact the instructor or the TAs for a possible hint.

• You cannot collaborate on Extra credit problems

• Solutions typeset in LATEX are preferred.

• Feel free to use the Discussion Board or email the instructor or the TAs if you have any questions or would like any clarifications about the problems.

• Please upload your solutions to Gradescope.

 

In solving these assignments, feel free to use these approximations:

$$1-x\approx e^{-x},\sqrt{1-x}\approx 1-x/2,n!\approx {(n/e)}^n,{\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {\left(\frac{en}{k}\right)}^k$$

1. Let $G\sim G_{n,p}$ with $p=D/n$ and $D>0$ is some fixed number. Let $X$ be the number of isolated vertices in $G$ (i.e., the number of vertices that have no neighbors). Determine $𝔼\left[X\right]$ and then show that for any $\lambda >0$,

   $$\mathbb{P}\left[|X-𝔼\left[X\right]|\ge 4\lambda \sqrt{Dn}\right]\le e^{-c{\lambda }^2},$$

   for some universal constant $c$.

2. Prove the following theorem that we discussed in class: Let . Suppose $y_0,\mathrm{\dots },$ is a sequence of random variables such that for all $i>1$, $y_i-y_{i-1}\mid y_1,\mathrm{\dots },y_{i-1}\sim 𝒩(0,{\sigma }_i^2)$ where . Then:

   $$\mathbb{P}\left[|y_{\mathrm{\ell }}|>\lambda \cdot \tau \cdot \sqrt{\mathrm{\ell }}\right]\le 2\exp (-c{\lambda }^2)$$

   for some constant $c>0$.