¿Por qué es el Trastorno de Probabilidad tan Cerca de $\frac{1}{e}$?

Question

Un trastorno es una permutación de $\sigma$ de $\{1,2,3,\dots,n\}$ tal que $\sigma(i) \neq i$ por cada $i$. Una aplicación común de la inclusión/exclusión en el pregrado de la combinatoria y probabilidad de las clases es para calcular el número de alteraciones, y en el proceso se demuestra que la probabilidad de una permutación aleatoria es una alteración de los enfoques $\frac{1}{e}$ para $gran$ n.

También existe un "estándar" de la intuición para esta probabilidad, que va más o menos la siguiente: Vamos a $E_i$ ser el caso de que $\sigma(i)=i$.

1) Para un $i$, la probabilidad de $E_i$ es exactamente $\frac{1}{n}$.

2) Si $n$ es grande, que estos eventos deben ser "casi" independiente ($E_i$ ocurren significa que $\sigma(i) \neq j$, lo que es un poco más probable que $\sigma(j)=j$, pero esto no debería haber mucho de un efecto para grandes $n$), por lo que sería de esperar, la probabilidad de que ninguno de los $E_i$ ocurren aproximadamente $\left(1-\frac{1}{n}\right)^n$.

3) Para las grandes $n$, $\left(1-\frac{1}{n} \right)^n \approx \frac{1}{e}$.

Ahora la última aproximación ya solo tiene un error proporcional a $\frac{1}{n}$. Lo sorprendente es que, después de trabajar a través de la inclusión/exclusión, se encuentra que la probabilidad no es sólo de aproximadamente $\frac{1}{e}$, pero muy cerca-el error es menor que $\frac{1}{(n+1)!}$.

¿Hay alguna alternativa intuitiva explicación de la $\frac{1}{e}$ asintótica probabilidad de que da una idea de por qué la convergencia es tan rápido?

Answer 1

De hecho, una mucho más fuerte de lo $e$-relacionadas con la declaración es verdadera: deja de $X_i$ denotar la cantidad de $i$-ciclos en una permutación aleatoria en $$ n elementos. Luego se fijo en $k$, $n \to \infty$ las variables aleatorias $X_1, X_2, ... X_k$ son asintóticamente independientemente de Poisson con tarifas de $1, \frac{1}{2}, ... \frac{1}{k}$. Esta observación acerca de las alteraciones es un caso especial aplicado a $X_1$. Ver esta entrada del blog para más detalles, lo que demuestra este hecho como un corolario de la exponencial de la fórmula. La tasa de convergencia es de suponer que también controlado por la exponencial de la fórmula, pero no he trabajado en los detalles.

Answer 2

Nota: La convergencia es tan rápido, debido a la alteración número $D_n$ y la expansión en series de Taylor de $e^x$ están estrechamente relacionados.

La intuición detrás de esto es (para mí), tratando de desarrollar un mejor sentido de que el mecanismo de la inclusión/exclusión de principio, que codifica esta relación.

De acuerdo a la OPs que se hace referencia en papel sabemos que el trastorno número $D_n$ es

$$\begin{align*} D_n=n!\sum_{j=0}^n(-1)^j\frac{1}{j!} \end{align*}$$ Vamos a compararlo con la expansión de Taylor de la serie de $e^x$ en $x=-1$ $$\begin{align*} \frac{1}{e}=\sum_{j=0}^\infty(-1)^j\frac{1}{j!} \end{align*}$$

Observar, que $\frac{D_n}{n!}$ es el $$n-ésimo Taylor polynom de $\frac{1}{e}$.

También observamos, que la serie $e^{-1}$ satifies el requisito de la alternancia de serie de la prueba.

• Los términos se alternan en signo.

• Ellos son la disminución en valor absoluto.

• Se acercan $0$.

Por lo tanto, la aplicación de la alternancia de la serie de prueba de error que obtenemos si nos detenemos en el $$n-ésimo término de un error absoluto menor que los $(n+1)$-st plazo. Así, el error es

$$\begin{align*} \left|\frac{D_n}{n!}-\frac{1}{e}\right|<\frac{1}{(n+1)!} \end{align*}$$

Nota: Este y agradable el hecho de que $D_n$ es el más cercano entero a $\frac{n!}{e}$ se puede encontrar por ejemplo en Stirling Aproximación y la Alteración de los Números por T. Zaslavsky

Answer 3

No estoy seguro de que este es realmente mejor que la inclusión de la exclusión, pero es diferente:

Deje de $d_n$ ser el número de alteraciones. Entonces tenemos $$d_n = (n-1) (d_{n-1} + d_{n-2})$$ (ver aquí). Deje de $p_n = d_n/n!$ ser la probabilidad de un trastorno. Entonces $$p_n = \frac{n-1}{n} p_{n-1} + \frac{1}{n} p_{n-2} \ \mbox{lo que implica} \ p_{n} - p_{n-1} = - \frac{p_{n-1} - p_{n-2}}{n} .$$

Por lo que $p_{n} - p_{n-1}$ decae factorially rápido, y por lo tanto $p_n = \sum_{m=2}^n (p_m - p_{m-1})$ es factorially cerca de $\sum_{m=2}^{\infty} (p_m - p_{m-1}) = \lim_{n \to \infty} p_n$.

Answer 4

Estoy de acuerdo con Quiaochu que tu pregunta es muy general. En el papel de los Límites de la logarítmica de la combinatoria de las estructuras por Arratia-Barbour-Tavaré, se discute el acondicionamiento de relación. Deje de $C_1, \dots, C_n$ ser el número de "componentes" de diferentes tamaños (por ejemplo, ciclos en un permutaiton). A continuación, el uso de la probabilidad condicional

$$\mathbb{P}\big[ C_1 = c_1, \dots, C_N = c_N \big] = \mathbb{P}\big[ Z_1 = c_1, \dots, Z_N = c_N \bigg| \sum_{i=1}^N i Z_i = N \big]$$

donde $Z_i$ son independientes de las variables aleatorias. Aquí $N = \sum i Z_i$ es el tamaño de nuestra estructura combinatoria.

---

Ciclos de una permutación aleatoria definitivamente tienen esta propiedad. Ya que estamos preocupados de los eventos $E_i = \{ \sigma(i) = i\}$ no son bastante independientes, vamos a olvidar.

Vamos a construir una permutación aleatoria con independiente de números aleatorios $C_k$ de ciclos de varios tamaños $1 \leq k \leq$ N y el tamaño de esta permutación es $N = \sum k C_k$. A continuación, elegimos la permutación de el tamaño que queremos usar funciones de generación o de la probabilidad condicional.

El ABT papel requiere un segundo axioma que sin duda es cierto para las permutaciones al azar. Para algún parámetro $\theta \in \mathbb{R}$:

$$k \cdot \mathbb{E}[Z_i] = \theta \etiqueta{$\ast$}$$

De hecho, lo que se suele dar es que $Z_k$ se distribuye Poisson con una media de $\frac{\theta}{k}$.

---

Esta técnica se llama Poissonization y es utilizado aquí y no en la probabilidad, combinatoria y la física estadística.

• Ordenó la Longitud del Ciclo en una Permutación Aleatoria L. Ovejas y S. Lloyd
• El número de ciclos de una permutación aleatoria
• Física estadística (pdf) ver la discusión de Grand Ensemble Canónico

Creo que es interesante tener en cuenta que Larry Shepp es Profesor en el Departamento de Estadística de la Escuela de Negocios de Wharton, a pesar de que su salud se está deteriorando.

Answer 5

Vamos a ser de $N_{n}$ el número de permutaciones en $\mathfrak{S}_{n}$ sin puntos fijos. Vamos a ser de $A_{i}$ el conjunto de permutaciones de $\left\{ 1,\ldots,n\right\}$ que $i$ como punto fijo. Tenemos $$\#\left(A_{i}\right)=\left(n-1\right)!$$ desde $A_{i}$ coressponds $\mathfrak{S}_{n-1}$ (permutaciones en $\left\{ 1,\ldots,i-1,i+1,\ldots,n\right\}$ ). Entonces, el número de permutaciones que tienen exactamente $i_{1},\ldots,i_{k}\in\left\{ 1,\ldots,n\right\}$ como puntos fijos es de $$\#\left(\bigcap_{j=i_{1},\ldots,i_{k}}A_{j}\right)=\left(n-k\right)!$$ desde estas permutaciones son en todos los $A_{i_{1}},\ldots,A_{i_{k}}$.

Ahora vamos a utilizar la de Poincaré fórmula (o también el principio de inclusión/exclusión mencionada en el OP) : $$\#\left(\bigcup_{i}^{n}A_{i}\right)=\sum_{I\subconjunto\left\{ 1,\ldots,n\right\} ,I\neq\emptyset}\left(-1\right)^{\#I+1}\#\left(\bigcap_{i\in I}A_{i}\right)=\sum_{I\subconjunto\left\{ 1,\ldots,n\right\} ,I\neq\emptyset}\left(-1\right)^{\#I+1}\left(n-\#I\right)!=\sum_{k=1}^{n}\begin{pmatrix}n\\ k \end{pmatrix}\left(-1\right)^{k+1}\left(n-k\right)!$$ whence $$N_{n}=\#\left(\mathfrak{S}_{n}\setminus\bigcup_{i}^{n}A_{i}\right)=n!-\#\left(\bigcup_{i}^{n}A_{i}\right)=n!-\sum_{k=1}^{n}\begin{pmatrix}n\\ k \end{pmatrix}\left(-1\right)^{k+1}\left(n-k\right)!$$ $$=\sum_{k=0}^{n}\left(-1\right)^{k}\frac{n!}{k!}.$$ Entonces, la probabilidad p $$tener un trastorno, dividimos por el número de todas las posibles permutaciones y conseguir$$ p=\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\longrightarrow e^{-1}$$ cuando $n\rightarrow+\infty$.

Aquí mi probabilidad de espacio $\left(\Omega\mathcal{F},\mathbb{P}\right)$ está dada por $\Omega=\mathfrak{S}_{n}$ , $\mathcal{F}=\mathcal{P}\left(\Omega\right)$ y $\mathbb{P}\left (\right)=\frac{\#A}{n!}$ para todo $A\subconjunto\mathfrak{S}_{n}$ .