Suppose that we have $X_1,\ldots,X_n$ iid geometric random variables with parameter $\frac{1}{2}$ satisfying $P(X_i=k)=\frac{1}{2^{k+1}}$ ($k$ can also be zero) and let $R=max{X_i}$
Prove: 1. $P(R>log(n)+c)\le\frac{1}{2^c}$ for $c>0$ and $log$ is in base $2$
- $E[R]\le \lceil{log(n)}\rceil+\sum_{i=1}^\infty\frac{i}{2^i}$ and $log$ is in base $2$
The first part is easily seen using union bound.
Any help for the second part would be appreciated!
Best Answer
You can make use of the fact that the expectation of a nonnegative discrete random variable $X$ can be written as $\mathbb{E}(X) = \sum_{i=0}^{\infty} \mathbb{P}(X > i)$. Can you combine this with the first part of the question to finish the proof for part $2$?