# Upper Bound on Expected Value of $n$ i.i.d. Poisson random variables.

Let $$\{X_i \}_{i=1}^n$$ be i.i.d. from a Poisson random variable with mean $$\lambda$$ and let $$M_n = \max_{1 \le i \le n} X_i.$$ What is a tight upper bound on $$\mathbb{E}[M_n]$$? I can prove that $$$$\mathbb{E}[M_n] \le \frac{(\lambda+1) \log n}{\log \log n} + O \left( \frac{1}{\log \log n} \right)$$$$ but numerically this bound is not tight. Can someone give a tighter analysis or point to a reference with one?

Proof of my bound:

Let $$s > 0$$. Then by Jensen's inequality, $$e^{s \mathbb{E}[M_n]} \le \mathbb{E}[e^{sM_n}] \le \sum_{i-1}^n \mathbb{E}[e^{sX_i}] = ne^{\lambda(e^s-1)}$$ from the moment generating function. Then taking the logarithm of both sides gives $$\mathbb{E}[M_n] \le \frac{\log n}s + \frac{\lambda(e^s-1)}{s}.$$ Finally, the minimum of the function on the right hand side should be around $$s = \log \log n$$ which gives the bound above.

• Some back of the envelope calculations lead me to believe that is the right asymptotic growth. What numerics do you have to show it's not tight? Is it the $\log n/ \log \log n$ asymptotic or just the constant $\lambda+1$? – zoidberg Dec 7 '18 at 2:24
• Just the constant $\lambda + 1$. I do think its $O(\log n / \log \log n)$. – Sandeep Silwal Dec 7 '18 at 2:27
• Does the constant 1 match better? You're clearly losing something by going from max to sum. – zoidberg Dec 7 '18 at 2:35
• 1 is definitely too small. Also the constant should depend on $\lambda$. – Sandeep Silwal Dec 7 '18 at 2:37
• Are you sure? Take a look at this paper: arxiv.org/pdf/0903.4373.pdf Apparently $M_n$ becomes super concentrated as $n \to \infty$ and with high probability lies in an interval of length 1 located $~ \log n /\log \log n$ independent of $\lambda$. – zoidberg Dec 7 '18 at 2:48

The paper https://arxiv.org/pdf/0903.4373.pdf mentions that as $$n \to \infty$$, $$M_n$$ becomes concentrated at two adjacent values located asymptotically at $$\sim \log n/ \log \log n$$ independent of $$\lambda$$ with probability approaching 1. Even tighter estimates are given there.
• You can see from the Figure 3. It's really tight apparently. They claim the formula they give has error less than 1 (at least over the values of $n$ and $\lambda$ in that figure). They don't seem to offer much in the way of proofs. – zoidberg Dec 7 '18 at 2:59
After the fact, but a quick observation: in your proof, set instead $$s \stackrel{\rm def}{=} \log\left(\frac{\log n}{\lambda}+1\right)$$ Then $$\mathbb{E}[M_n] \leq \frac{\log n}{s} + \frac{\lambda(e^s-1)}{s} = \frac{2\log n}{s} \operatorname*{\sim}_{n\to\infty} 2\frac{\log n}{\log\log n}$$ which is better than your bound for $$\lambda >1$$.