$\sum_{m=1}^n 1/m \sim log(n)$

Question

Let $Y_1,Y_2,...$ be independent with $$P(Y_m=1)=\frac{1}{m}$$ and $$P(Y_m=0)=1-\frac{1}{m}$$ $$E[Y_m]=\frac{1}{m} $$ and $$ Var[Y_m]=\frac{1}{m}-\frac{1}{m^2}$$

We want to prove:

If $S_n=Y_1+...+Y_n$ then $E[S_n] \sim log(n)$

Answer 1

Use linearity of expectation to get $$\sum_{m=1}^n \mathbb{E}[Y_m]=\mathbb{E}[S_n]$$ One intuitive way to see why $$\sum_{m=1}^n \frac 1m \sim \ln n $$ Is to compute approximate the area under $$\frac {1}{x}$$ through the use of Riemann Sums and connecting that with the fact that $$\int \frac 1x \mathrm{d}x=\ln x$$