let us look at the function $N^d e^{-N}$, for each $d\in \mathbb{N}$. The graphs of the function for various values of $d$ show a striking phenomenon: the graph look parallel, and with a near-constant distance between each consecutive graphs.

enter image description here

Put in other words, Let $p<1$, and for each $d\in \mathbb{N}$ look at the $N$ that satisfies $N^de^{-N}=p$. Then it seems that the resulting function $N(d)$ is $o(n^2)$ or even $\Theta(n)$, and furthermore that for all $d$, $N(d+1)-N(d)$ is approximately uniform in $p$.

This phenomenon is observed here without explaining the exact argument. This also gives a good statistical motivation for asking the question.

What will be a rigorous statement of this phenomenon, and why is it true?

  • 1
    $\begingroup$ Note that the vertical axis has a log scale. He is effectively plotting $\ln(x^ne^{-x})$ for multiple values of $n$. Once $x$ is significantly bigger than $n$, the exponential decay dominates over the power term and since $\ln(e^{-x})$ is just $-x$ we get an apparently straight line. $\endgroup$ – almagest Apr 23 '16 at 20:01
  • $\begingroup$ @almagest Thanks for the nice observation. Does the supposed-linearity of $N(d)$ follow from it? (It is unaffected by whether we use a log-scale or not.) $\endgroup$ – Emolga Apr 24 '16 at 11:43

For all $d \geq e$ and $0 < p < 1$ the equation

$$ N^d = pe^N $$

has two positive solutions $N$, call them $N_1$ and $N_2$. Since the maximum of $x \mapsto x^d e^{-x}$ occurs at $x=d$ and $x^d e^{-x} \to 0$ as $x \to \infty$ we know that $N_1 < d < N_2$.

We'll first investigate the behavior of $N_1$, then $N_2$ afterwards.

Because the maximum of $x \mapsto x^d e^{-x}$ is located at $x=d$, if $1 + \epsilon < x \leq d$ for some $\epsilon > 0$ then

$$ x^d e^{-x} > (1+\epsilon)^d e^{-1-\epsilon} \to \infty $$

as $d \to \infty$. In this case the equation $x^d e^{-x} = p$ will not hold for $d$ large enough. Consequently we may conclude that

$$ \limsup_{d \to \infty} N_1 \leq 1. $$

This is clearly not the solution we're looking for, so let's move on to $N_2$.

We know that $N_2 > d$. Taking logarithms of the original equation we have

$$ d \log N_2 = N_2 + \log p, \tag{$*$} $$

and so

$$ N_2 > d \log d - \log p. $$

In fact this captures the asymptotic behavior of $N_2$. Indeed, as $d \to \infty$ we know that $N_2 \to \infty$, so

$$ N_2 + \log p \sim N_2 $$

as $d \to \infty$, and thus equation $(*)$ implies

$$ d\log N_2 \sim N_2 $$

as $d \to \infty$. Taking logarithms again we see that

$$ \log d = \log N_2 - \log\log N_2 + o(1) $$

as $d \to \infty$. Dividing both sides by $\log N_2$ yields

$$ \frac{\log d}{\log N_2} = 1 - \frac{\log\log N_2}{\log N_2} + o(1) = 1 + o(1) $$

and thus $\log N_2 \sim \log d$. Plugging this back into $(*)$ allows us to conclude that

$$ N_2 \sim d\log d. $$


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.