0
$\begingroup$

I can't seem to understand how (5.3.23) was reached (below). In particular, how is the fact that $\lambda \mapsto \lambda e^{-\lambda/2}$ is decreasing being used?

Here is the passage in question:

For all $k \le n/2$ with $k \ge 5$, we bound $k(n-k) \ge kn/2$, so that $$\mathbb E_\lambda[X_k] \le n(e \lambda e^{-\lambda/2})^k. \tag{5.3.22}$$ As a result, for $\lambda = a \log n$ with $a > 1/2$, and all $k \ge 5$, and using that $\lambda \mapsto \lambda e^{-\lambda/2}$ is decreasing for $\lambda \ge 2$, $$\mathbb E_\lambda[X_k] \le n^{1-k/4}. \tag{5.3.23}$$

$\endgroup$
0
$\begingroup$

If $\lambda = a \log n$, then $e^{-\lambda/2} = n^{-a/2} = \frac{n^{-1/4}}{n^{a/2 - 1/4}},$ and we can write $$e\lambda e^{-\lambda/2} = \frac{a e \log n}{n^{a/2 - 1/4}} \cdot n^{-1/4}.$$ There's that messy factor out front that we want to ignore, but the numerator in it is $O(\log n)$ and the denominator is $n$ raised to a positive power, so when $n$ is large enough the messy factor is less than $1.$

So we know that if $\lambda$ actually is $a \log n$ from some constant $a>\frac12$, then (ignoring the messy factor, as we've earned the right to do) $$\mathbb E_\lambda[X_k] \le n\left(n^{-1/4}\right)^k \le n^{1 - k/4}.$$ As far as I can tell, the point of saying that $\lambda \mapsto \lambda e^{-\lambda/2}$ is decreasing is that Proposition 5.10 wants to be true for all $\lambda \ge a \log n$ for some $a > \frac12$. So if it were true for $\lambda = \frac23 \log n$, but then stopped being true for $\lambda = (\log n)^2$, that would be a problem. It's a problem we don't have here, because making $\lambda$ bigger only makes the term raised to the $k$-th power smaller.

$\endgroup$
1
  • $\begingroup$ I've thought about this some more. I'm not entirely sure that you're explanation for the use of decreasing is right. A few lines above, an argument is made about $f(\lambda)$ being decreasing. I believe that is the reason we can restrict ourselves to the case $\lambda = a \log(n)$ (rather than $\lambda > a \log(n))$. So I'm still a bit puzzled by why we need the fact that $\lambda \to \lambda e^{-\lambda/2}$ is decreasing. $\endgroup$
    – theQman
    Mar 28 '17 at 16:36

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.