Asymptotics de $e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot\frac1{n-k}$

Question

Dejar $$ a_n = \sqrt{2\pi n}\cdot e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot{\frac1{n-k}}, $$ ¿alguien sabe de un simple asintótica equivalente para $a_n$? Numérico experimentación sugiere que $$ a_n \stackrel{?}\sim \tfrac12\log n. $$ Si nos deshacemos de la $\frac1{n-k}$, no hay una respuesta simple, porque $$ \lim_{n\to\infty} e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}=\frac12. $$ como se muestra aquí. Lanzando en el factor de $\frac1{n-k}$ parece cambiar el asymptotics completamente.

El contexto es que el $a_n$ es resultado de la aplicación de Stirling aproximación a $\sum_{k=1}^n \frac{n_{(k)}}{kn^k},$ que es el número esperado de "ciclos" que una función aleatoria en un conjunto de $n$ elementos que en sí tiene, donde un ciclo es un conjunto de distintos números de $\{x_1,x_2,\dots,x_k\}$ que $f(x_i)=x_{i+1}$. Si se reemplaza "función random" con "random bijection," el número esperado de ciclos es acerca de $\log n$, por lo que si mi suposición es correcta, entonces funciones aleatorias tienden a tener la mitad de los ciclos de permutaciones.

Answer 1

Aquí seguimos ejercicio 5.2 de Asymptopia por Joel Spencer y mostrar OP suposición es correcta.

El siguiente es válido \begin{align*} \color{blue}{\sum_{k=1}^n\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}\sim \frac{1}{2}\ln n} \end{align*}

donde $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ denota la caída de factorial.

Un enfoque práctico es dividir el rango del índice de $k$ en tres partes:

• un pequeño rango: $\qquad\quad k<\frac{\sqrt{n}}{\ln n}$

• un gama media: $\quad\quad \frac{\sqrt{n}}{\ln n} < k < \sqrt{n}\ln n$

• y una amplia gama: $\ \quad k>\sqrt{n}\ln n$.

Pequeño rango: $k<\frac{\sqrt{n}}{\ln n}$

Escribimos \begin{align*} \frac{n^{\underline{k}}}{n^k}=\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right) \end{align*} y considerar el logaritmo del producto. Desde $$\ln(1-x)=-x+O(x^2)$$ when $x\rightarrow 0$ obtenemos \begin{align*} \ln\left(\frac{n^{\underline{k}}}{n^k}\right)&=\sum_{j=1}^{k-1}\ln\left(1-\frac{j}{n}\right)\\ &\sim\sum_{j=1}^{k-1}-\frac{j}{n}\sim -\frac{k^2}{2n}=o(1) \end{align*} Así tenemos \begin{align*} \frac{n^{\underline{k}}}{n^k}\sim 1\tag{1} \end{align*} Podemos obtener a partir de (1) \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\sim\sum_{k}\frac{1}{k}\sim\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim\ln\sqrt{n}-\ln\ln n\\ &\,\,\color{blue}{\sim\frac{1}{2}\ln n}\tag{2} \end{align*}

Gama media: $\frac{\sqrt{n}}{\ln n}<k<\sqrt{n}\ln n$

Desde $\frac{n^{\underline{k}}}{n^k}\leq 1$ obtenemos \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\leq \sum_{k}\frac{1}{k}\\ &\sim\ln\left(\sqrt{n}\ln n\right)-\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim \ln \sqrt{n}+\ln\ln n-\ln \sqrt{n}+\ln \ln n\\ &\,\,\color{blue}{\sim{2\ln \ln n}}\tag{3} \end{align*}

Amplia gama: $k>\sqrt{n}\ln n$

Aquí tenemos a $\frac{n^{\underline{k}}}{n^k}=o(1)$ y obtenemos \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&=o(1)\sum_{k}\frac{1}{k}\\ &= o(1)\left(\ln n-\ln \left(\sqrt{n}\ln n\right)\right)\\ &\,\,\color{blue}{=o(\ln n)}\tag{4} \end{align*}

Vemos que (2) constituye la principal contribución en comparación con (3) y (4) y la demanda de la siguiente manera.

Answer 2

Bueno, por lo de la onu-la aplicación de la aproximación de Stirling, queremos encontrar $$ \sum_{k=1}^n\frac{n_{(k)}}{n^k}\cdot \frac1k $$ donde $n_{(k)}=\frac{n!}{(n-k)!}$. La idea general es que para lo suficientemente pequeño $k$,$\frac{n_{(k)}}{n^k}\approx 1$, mientras que al $k$ es grande, $\frac{n_{(k)}}{n^k}\approx 0$. Tenemos que encontrar el punto de corte donde $\frac{n_{(k)}}{n^k}$ es moderado; entonces la suma es, efectivamente, la suma de $1/k$ hasta el punto de corte.

Usando la aproximación de Stirling, $$ \log \frac{n_{(k)}}{n^k} =n\log n-n-[(n-k)\log (n-k)-(n-k)]-k\log n+\dots\aprox -\frac{k^2}{2n}-\frac{k^3}{6n^2}-\dots $$ Por lo tanto, cuando $k\sim \sqrt{n}$, $ \frac{n_{(k)}}{n^k}\approx e^{-1/2}$, y que se cae exponencialmente rápidamente antes y después. Por lo tanto, agitar las manos, $$ \sum_{k=1}^n\frac{n_{(k)}}{n^k}\cdot \frac1k\approx \sum_{k=1}^{\sqrt{n}}\frac1k\sim \tfrac12\log n. $$

Answer 3

En primer lugar, hemos de invertir el orden de la suma, entonces obtenemos ($k\to n-k)$: $$\sqrt{2\pi n}e^{-n}\sum^n_{k=1}\frac{n^n}{(n-k)!n^k}\frac1k$$ $$=\sqrt{2\pi n}e^{-n}n^n\frac1{n!}\sum^n_{k=1} \frac{n!}{(n-k)!n^k}\frac1k$$ $$=(1+o(?))\sum^n_{k=1} (1+o(?))\frac1k\sim H_n\sim \gamma +\ln n$$

No puedo obtener el $\frac12$ factor. Por el camino, los dos asintótica fórmulas utilizadas son bien conocidos, pero no sé el orden inferior efecto.