21 votos

Asymptotics de los coeficientes binomiales y la entropía de la función

He encontrado una pregunta mientras yo estaba tratando de practicar la Combinatoria y métodos Probabilísticos.Traté de solucionarlo sin éxito.. la pregunta es esta:

El uso de la aproximación de Stirling el factorial para mostrar que para cada $0\leq p \leq 1$ no tiene

$$\lim _{n\to \infty}\frac{1}{n}\log\binom{n}{pn}=H(p)$$ where $H(p)=-p\log(p) -(1-p)\log(1-p)$ es el binario de la entropía de la función.

Alguna ayuda?

16voto

nav.jdwdw Puntos 544

Deje $q=1-p$.

La aproximación de Stirling afirma $n! \sim (\frac{n}{e})^{n} \sqrt{2\pi n}$. Esto nos da:

$$\binom{n}{pn} \sim \frac{(n/e)^{n}}{(np/e)^{np}(nq/e)^{nq}}\frac{\sqrt{2\pi n}}{\sqrt{2\pi np}\sqrt{2\pi nq}}$$

El $(n/e)^n$ cancela con $(n/e)^{np}(n/e)^{nq}$, por lo que esto se simplifica a:

$$\binom{n}{pn} \sim \frac{1}{p^{np}q^{nq}}\frac{1}{\sqrt{2\pi npq}}$$ Al tomar el logaritmo en base 2, se obtiene:

$$\log_2\binom{n}{pn} \sim -n (p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/2$$ Dividiendo por $n$, se transforma a:

$$\frac{1}{n}\log_2\binom{n}{pn} \sim -(p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/(2n) = H(p) + O(\ln n/ n)$$ Y al $n$ tiende a infinito, se obtiene la deseada límite.

EDIT: no Se necesita toda la fuerza de la aproximación de Stirling. $n! = (n/e)^{n} g(n)$ donde $n^{\alpha} \le g \le n^{\beta}$ es suficiente.

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