0

for two integers $1 \le \mu \le m$, $$ e^{-\mu } \sum_{k=m }^{\infty} \frac{\mu^k}{k!} \le (\frac{\mu}{m})^m e^{m-\mu}. $$ When I try to prove Chernoff bound, I met this inequality as the last step. But I can't prove. WolframAlpha tells me it is true. Can someone help me prove it?

log2
  • 399
  • 5
    I vote for this question and Fedor's answer to be removed. Should be on MSE. Nothing original at all in the answer. – mathworker21 Oct 29 '23 at 16:59
  • 1
    I'm sorry to bother you, but I evaluated the asymptotics of your last problem (the problem disappeared from the site): $$S(a)=\left(\frac14\right)^{2n}\sum_{i=1}^n\binom{2n}{i}a^i\sim\left(\frac a4\right)^n\frac1{\sqrt{\pi n}}\frac a{a-1}$$ Take $a=3$ – Svyatoslav Nov 09 '23 at 15:09
  • 1
    @Svyatoslav Too much thanks! It helps me a lot!❤️ – log2 Nov 09 '23 at 15:26
  • @Svyatoslav Recently I am learning about randomized algorithms. I often come across summation formulas like this. Can you recommend some relevant study materials to me? – log2 Nov 09 '23 at 15:52
  • 1
    I'm a former physicist and studied long time ago :) I can only recommend some tools for physicists, like MATHEMATICAL METHODS FOR PHYSICISTS by George B. Arfken. BTW, if you need higher terms: $$S(a)=\left(\frac14\right)^{2n}\sum_{i=1}^n\binom{2n}{i}a^i\sim\left(\frac a4\right)^n\frac1{\sqrt{\pi n}}\frac a{a-1}\left(1-\frac{a+1}{(a-1)^2}\frac{\ln^2a}n\right)$$ In fact, this is an interesting problem; I think if you added your efforts and provide some rational - it would help to avoid downvoting... – Svyatoslav Nov 09 '23 at 16:17
  • @Svyatoslav Thank you again for these magical asymptotic terms! I will add my efforts and provide some rational in my subsequent posts. – log2 Nov 09 '23 at 16:44

1 Answers1

9

Divide by $e^{-\mu}$, and also divide by $\mu^m$, you get an equivalent inequality $$\sum_{k=m}^\infty \frac{\mu^{k-m}}{k!}\leqslant \left(\frac{e}m\right)^m.$$ LHS is obviously an increasing function in $\mu$, so it suffices to consider the case $\mu=m$. But then it reads (multiply both sides by $m^m$) as $$ \sum_{k=m}^\infty \frac{m^{k}}{k!}\leqslant e^m $$ which follows from $e^m=\sum_{k=0}^\infty \frac{m^{k}}{k!}$.

Fedor Petrov
  • 1,317