3
$\begingroup$

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 \begin{equation} \mathbb{E}[M_n] \le \frac{(\lambda+1) \log n}{\log \log n} + O \left( \frac{1}{\log \log n} \right) \end{equation} 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.

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$ – zoidberg Dec 7 '18 at 2:24
  • $\begingroup$ Just the constant $\lambda + 1$. I do think its $O(\log n / \log \log n)$. $\endgroup$ – Sandeep Silwal Dec 7 '18 at 2:27
  • $\begingroup$ Does the constant 1 match better? You're clearly losing something by going from max to sum. $\endgroup$ – zoidberg Dec 7 '18 at 2:35
  • $\begingroup$ 1 is definitely too small. Also the constant should depend on $\lambda$. $\endgroup$ – Sandeep Silwal Dec 7 '18 at 2:37
  • $\begingroup$ 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$. $\endgroup$ – zoidberg Dec 7 '18 at 2:48
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Hmm interesting, can you clarify how tight the bounds are exactly? The paper does not give much detail on the rate of convergence $\endgroup$ – Sandeep Silwal Dec 7 '18 at 2:57
  • $\begingroup$ 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. $\endgroup$ – zoidberg Dec 7 '18 at 2:59
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.