17 votos

Una pregunta sobre la aproximación de Stirling, y $\log(n!)$

En el análisis de un algoritmo de esta declaración ha llegado hasta:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ n\log(n) = \log(n^n)$$ and it is easy to see that $\log(n!) \en O(\log(n^n))$, but the "$\Theta$" part is still perplexing. I tried calculating the limit: $$\lim_{n \to\infty} \frac{\log(n!)}{\log(n^n)}$$but the only way that I thought of doing this was to substitute the Stirling approximation in the numerator, and it works, but this would only be justified if $$\lim_{n \to\infty}\frac{\log(n!)}{\log(\sigma(n))} = 1$$(with $\sigma(n) = \sqrt{2\pi} \cdot n^{\frac{1}{2} + n} \cdot e^{-n} $) and is it? It is certainly wrong that $$a_n \sim b_n \ \Rightarrow \ f(a_n) \in \Theta(f(b_n))$$ for a general (continuous) $f : \mathbb{R} \rightarrow \mathbb{R}$, since, for example, $a_n =n^2+n, b_n=n^2$ and $f(x) = e^x$ is a counterexample (since $\frac{n^2 + n}{n^2} \rightarrow 1$, but $ \frac{e^{n^2+n}}{e^{n^2}} \rightarrow +\infty$). Así que aquí están mis preguntas:

  1. Es la afirmación verdadera, bajo ciertas hipótesis en $f$ (por ejemplo, $f \in O(x)$ sería plausible), y, en particular, en el caso de la $f(x) = \log(x)$?
  2. Si no, ¿cómo puedo proceder en la prueba inicial, el uso de Stirling, o de otra manera?

No sé (y no quieres usar nada andvanced en la aproximación de Stirling, tales como las estimaciones de error; yo sé que $n! = \sigma(n)(1+ O(\frac{1}{n}))$, y no mucho más.


Cualquier ayuda es muy apreciada. Gracias.

11voto

tooshel Puntos 475

He aquí otra respuesta a la pregunta 2. Por el Stolz–Cesàro teorema,

$$\lim_{n\to\infty}\frac{\log(n!)}{\log(n^n)}=\lim_{n\to\infty}\frac{\log(n+1)}{\log(n+1)+\log\left(\left(1+\frac{1}{n}\right)^n\right)}=1.$$


Para una respuesta parcial a la pregunta 1, he aquí una manera de ver que $a_n\sim b_n$ implica $\log(a_n)\sim\log(b_n)$ (bajo hipótesis razonables como $|\log(b_n)|>\varepsilon$ fijos $\varepsilon>0$ y suficientemente grande $n$). Tenga en cuenta que

$$\frac{\log(a_n)}{\log(b_n)}=\frac{\log(b_n)+\log\left(\frac{a_n}{b_n}\right)}{\log(b_n)}.$$

Esto también implica que si $a_n\in\Theta(b_n)$$|\log(b_n)|\to\infty$,$\log(a_n)\sim \log(b_n)$.

5voto

Dave Carpeneto Puntos 123

Bien, permite trabajar las matemáticas.

Por el trapecio, regla de, $\ln n! \approx \int_1^n \ln(x)\,{\rm d}x = n \ln n - n + 1$. Ahora nos encontramos con el error en la aproximación, en la que uno puede calcular por Euler–Maclaurin de la fórmula. Después de algunos crudo de la aritmética, se puede calcular que

$$ \ln (n!) - \frac{\ln n}{2}= n \ln n - n + 1 + \sum_{k=2}^{m} \frac{\mathcal{B}_k\,(-1)^k}{k(k-1)} \left( \frac{1}{n^{k-1}} - 1 \right) + S_{m,n}, $$ where $\mathcal{B}_k$ denota la de Bernoulli del número.

Ahora tomando límites, se puede calcular $$\lim_{n \to \infty} \left( \ln n! - n \ln n + n - \frac{\ln n}{2} \right) = 1 - \sum_{k=2}^{m} \frac{\mathcal{B}_k(-1)^k}{k(k-1)} + \lim_{n \to \infty} S_{m,n}$$.

Ahora desde $S_{m,n}$ satisface la siguiente propiedad, $$S_{m,n} = \lim_{n \to \infty} S_{m,n} + O \left( \frac{1}{n^m} \right),$$ we get the approximation in the logarithmic form. Taking exponent on both the sides and plugging $m=1$, obtenemos el resultado: $$n! = \sqrt{2 \pi n}~{\left( \frac{n}{e} \right)}^n \left( 1 + O \left( \frac{1}{n} \right) \right).$$

Si usted no se preocupe de la $\sqrt{2 \pi n}$ plazo, supongo que sólo puede utilizar la aproximación $\ln n! \approx \sum_{j=1}^n \ln j$ como sigue:

$$\sum_{j=1}^n \ln j \approx \int_1^n \ln x \,{\rm d}x = n\ln n - n + 1 = \Theta(n \ln n)$$.

3voto

Davide Giraudo Puntos 95813

Poner $s_n:=\sum_{k=1}^n\ln k$. A continuación, $s_n\leq n\ln n$ $$s_n=\sum_{k=1}^n\log (n-k+1)=n\log n+\sum_{k=1}^n\log\left(1-\frac{k-1}n\right)$$ y el uso de $\log(1+t)\geq t-t^2/2$ tenemos
\begin{align*} s_n&\geq n\log n-\sum_{j=0}^{n-1}\frac jn+\frac{j^2}{2n^2}\\ &=n\log n-\frac{n-1}2-\frac{(n-1)(2n-1)}{6n}\\ &=n\log n-\frac{n-1}{2n}\left(n+\frac{2n-1}3\right)\\ &=n\log n-\frac{n-1}2\frac{5n-1}{3n}\\ &=n\log n-\frac{n-1}6\left(5-\frac 1n\right), \end{align*} por lo $$\frac{s_n}{n\log n}\geq 1-\left(1-\frac 1n\right)\frac 1{6\log n}\left(5-\frac 1n\right),$$ que está por debajo de acotado por una constante positiva, por ejemplo, $\frac 12$ $n$ lo suficientemente grande.

2voto

Did Puntos 1

Una respuesta a la pregunta 1. implica lentamente/regularmente diferentes funciones, cuyo estudio es, a veces, se resumen como Karamata la teoría. Lentamente diferentes funciones son funciones positivas $L$ tal que, para cada positivos $\lambda$, $L(\lambda x)/L(x)\to1$ al $x\to+\infty$.

A ver que tal de las funciones que la implicación en la pregunta 1. cierto, supongamos que $f$ es poco a poco diferentes, y además, para simplificar las cosas, que $f$ es no decreciente. Entonces, si $a_n\sim b_n$ y $a_n,b_n\to+\infty$, $\frac12a_n\leqslant b_n\leqslant 2a_n$ para cada $n$ lo suficientemente grande, por lo tanto $$ \frac{f(\frac12a_n)}{f(a_n)}\leqslant \frac{f(b_n)}{f(a_n)}\leqslant \frac{f(2a_n)}{f(a_n)}. $$ Desde el límite inferior y el límite superior de ambos convergen a $1$, esto demuestra que $f(a_n)\sim f(b_n)$.

Gracias a Karamata del teorema de caracterización, el mismo tipo de argumento puede aplicarse a la categoría más amplia de regularmente diferentes funciones. Estas son funciones positivas $L$ tal que, para cada positivos $\lambda$, $L(\lambda x)/L(x)$ tiene un finito positivo límite al $x\to+\infty$.

De ahí la implicación: $a_n\sim b_n$ implica $f(a_n)\sim f(b_n)$ si $a_n,b_n\to+\infty$, se tiene para cada regularmente variación de la función $f$.

Ejemplos de lenta variación de funciones de los poderes de la $\log(x)$. Ejemplos de forma regular diferentes funciones de los poderes de la $x$ (posiblemente, a veces lentamente variación de la función). Ejemplos de no regularmente diferentes funciones son las exponenciales de los poderes de $x$ (posiblemente, a veces regularmente variación de la función).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X