¿Para qué sirve la aproximación de Stirling a un factorial?

Question

La aproximación de Stirling a un factorial es $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$

Me pregunto qué beneficio se puede obtener de ello.

Desde el punto de vista computacional (admito que no sé demasiado sobre cómo se implementa cada operación aritmética y cuál es más barata que cuál), un factorial $n!$ contiene $n-1$ multiplicaciones. En la aproximación de Stirling, también hay que calcular una división y $n$ multiplicaciones para $\left(\frac{n}{e}\right)^n$ ¿No? Más dos multiplicaciones y una raíz cuadrada para $\sqrt{2 \pi n}$ ¿Cómo reduce la aproximación el cálculo?

Puede haber consideraciones desde otras perspectivas. También me gustaría saberlo. Por favor, señale su perspectiva si puede.

Añadido : Para simplificar el análisis mediante la aproximación de Stirling, por ejemplo, la respuesta del usuario1729 Mi preocupación es que, al fin y al cabo, se trata de una aproximación, e incluso si la expresión aproximada converge, ¿no tenemos que demostrar que la expresión original también converge y lo hace a lo mismo que su aproximación?

Gracias y saludos.

Answer 1

El propósito (como para todas las expresiones asintóticas) es sustituir una función "complicada" (en este caso el factorial) por alguna expresión que sea "más sencilla". Así que se podría objetar que $\sqrt{2\pi n} (n/e)^n$ es más sencillo que $n!$ . Pero si te hago la pregunta de si $e^n$ o $n!$ crece más rápido cuando $n \to \infty$ podría apreciar el resultado de Stirling. O tratar de responder a la pregunta, ¿cuántos dígitos $n!$ tiene cuando $n$ es grande. O ...

Answer 2

Un resultado de la informática:

El número mínimo de comparaciones necesarias para ordenar cualquier $n$ elementos utilizando una comparación-ordenación es

$$\log_2(n!)$$

(esto se puede ver tomando cada ordenación posible, y formando un árbol binario de comparaciones necesarias de altura mínima) .

Por la aproximación de Stirling, tenemos

$$\log_2(n!)$$ $$> \log_2\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)$$ $$= n \log_2\left(\frac{n}{e}\right) + \log_2\left(\sqrt{2\pi n}\right)$$

O, como lo verás escrito en todos los libros de Informática,

El número de comparaciones necesarias para cualquier comparación-ordenación está limitado por $\Omega(n \log_2n)$

---

También, una nota lateral: el OP declaró que ambos $n!$ y $n^n$ requiere $O(n)$ multiplicaciones para calcular. Esto es falso - $n^n$ se puede calcular fácilmente en $O(log_2(n))$

Answer 3

Abraham de Moivre fue la persona que introdujo por primera vez la fórmula de Stirling. Su amigo James Stirling es el que encontró que la constante es $\sqrt{2\pi}$ ; de Moivre sólo lo conocía numéricamente.

Demoivre lo utilizó para aproximar la probabilidad de que el número de caras que se obtiene al lanzar una moneda 1800 veces sea $x$ , para $x$ no a muchas desviaciones estándar de 900. Escribió sobre esto en su libro titulado La doctrina del azar (¡busca el título en Google!). El título del libro es, en efecto, "la teoría de la probabilidad" en inglés del siglo XVIII. La frase aparece de nuevo en el famoso artículo póstumo de Thomas Bayes "An essay towards solving a problem in the doctrine of chances" (busque también ese título en Google). De Moivre obtuvo la curva en forma de campana $$ x\mapsto \text{constant} \cdot e^{-x^2/2} $$ de esta fórmula.

Answer 4

La aproximación de Stirling se utiliza mucho en Física, en la descripción de Boltzmann de la entropía:

$$ S = k \log_e W$$

Donde W es el número de permutaciones posibles de un grupo de materiales, dado por

$$W = \frac{N!}{\prod_i N_i!}$$

Tomar la aproximación hace que las matemáticas sean mucho más fáciles.

Answer 5

Me gustaría añadir varios puntos, que no parecen haber sido cubiertos por las respuestas existentes.

• La fórmula de Stirling reduce la cuestión del cálculo de una función "especial" (factorial) a una expresión explícita en la que sólo intervienen funciones "elementales". Esta definición de "elemental" puede parecerle bastante arbitraria. Sin embargo, todas las funciones que aparecen en la fórmula de Stirling están implementadas en el hardware, con una precisión garantizada e implementaciones altamente optimizadas que probablemente no se puedan superar. Por supuesto, nadie va a calcular $(n/e)^n$ por $n$ multiplicaciones: ambas $\ln$ y $\exp$ están disponibles como funciones "elementales".

Se puede argumentar que la multiplicación directa puede resulta que funciona más rápido para valores muy pequeños de $n$ . Sin embargo, el programador de una función matemática de propósito general normalmente preferirá una implementación de tiempo fijo, si es posible. Esto tiene la ventaja de poder estimar los tiempos de ejecución de los cálculos que dependen de la computación $n!$ . Por supuesto, siempre se puede imaginar una situación en la que $n$ es pequeño "la mayor parte del tiempo". Un buen programador puede encontrar una solución que incluya una tabla de búsqueda de valores precalculados para los pequeños $n$ . Una vez más, se tiende a preferir las implementaciones de tiempo fijo.

• También parece que le preocupa la precisión. En primer lugar, es probable que se necesiten más términos para lograr la precisión requerida con un tamaño moderadamente pequeño $n$ . Por ejemplo, un tipo de datos de punto flotante común tiene unos 15 dígitos significativos; se necesitan unos 5-7 términos en la expansión de Stirling para obtener la precisión necesaria para $n\ge12$ . Para valores menores de $n$ una tabla de búsqueda va a ser la solución más rápida. Por lo tanto, uno diseñaría con un compromiso en mente, eligiendo entre el almacenamiento permitido y la velocidad en el peor de los casos. En segundo lugar, el término del resto, omitido en tu pregunta, puede utilizarse para establecer el límite superior del error de aproximación; véase, por ejemplo, el libro "Special Functions" de Temme (1996). Por lo tanto, la aproximación de Sterling puede ser (y fue) una solución sólida para el problema de calcular los valores de la función factorial.

• Por último, pero no menos importante. La fórmula de Stirling funciona igual de bien en el caso de que $n$ no es entero, es decir, para calcular la función gamma (normalmente definida con un desplazamiento trivial del argumento). También funciona para argumentos complejos (aunque hoy en día esta propiedad no se utiliza muy a menudo debido a la disponibilidad de mejores aproximaciones). Es, por tanto,