Question

5. Doing (much) Better by Taking the Min Let X be a random variable that takes on the values in the set {1,...,n} that satisfies the inequality Pr( x i) Sali for some value a>0 and all i € {1,...,n}. Recall that (or convince yourself that) E(X) = P(X= i) = Pr(x2i). 1. Given what little you know so far, give the best upper bound you can on E(X). 2. Let X1 and X2 be two independent copies of X and let Z= min{X1, X2}. What can you say about Pr(Z >i)? 3. Give the best upper bound you can on E(Z). 4. Use Euler's result on the Basel Problem to show that E(Z) has an upper bound that depends only on a (and not on n).

Answer 1

5. 1.To get an upper bound on the expectation, we send $n\to \infty$ :

$\mathbb{E}[X]\le \lim_{n\to\infty}\sum_{i=1}^{n}\mathbb{P}(X\ge i)\le\sum_{i=1}^{\infty}\frac{a}{i}=aH$

where by , we denote the Harmonic series $H=\sum_{i=1}^{\infty}\frac1i$ which is a diverging sequence, and so we can say at max that the expectation can be finite but we can't gurantee it.

2. We have:

$\mathbb{P}(Z\ge i)=\mathbb{P}(\min\{X_1,X_2\}\ge i)=\mathbb{P}(X_1\ge i)\mathbb{P}(X_2\ge i)\le \frac{a^2}{i^2}$

3. Similar to the first problem, to get a good upper bound, we send $n\to\infty$ and get:

$\mathbb{E}[Z]\le \lim_{n\to\infty}\sum_{i=1}^{n}\mathbb{P}(Z\ge i)\le\sum_{i=1}^{\infty}\frac{a^2}{i^2}$

4. Euler proved that:

$\sum_{i=1}^{\infty}\frac1{i^2}=\frac{\pi^2}{6}$

Putting this in the above, we get:

$\mathbb{E}[Z]\le \lim_{n\to\infty}\sum_{i=1}^{n}\mathbb{P}(Z\ge i)\le\sum_{i=1}^{\infty}\frac{a^2}{i^2}=\frac{a^2\pi^2}{6}$

which is independent of .