Estadísticas de permutación aleatoria

Las estadísticas de permutaciones aleatorias , como la estructura cíclica de una permutación aleatoria , son de vital importancia en el análisis de algoritmos , especialmente de algoritmos de ordenación, que operan sobre permutaciones aleatorias. Supongamos, por ejemplo, que utilizamos quickselect (similar a quicksort ) para seleccionar un elemento aleatorio de una permutación aleatoria. Quickselect realiza una ordenación parcial en el arreglo, ya que lo particiona según el pivote. Por lo tanto, una permutación estará menos desordenada después de ejecutar quickselect. El grado de desorden restante puede analizarse mediante funciones generadoras. Estas funciones generadoras dependen fundamentalmente de las funciones generadoras de las estadísticas de permutaciones aleatorias. Por consiguiente, es de vital importancia calcular estas funciones generadoras.

El artículo sobre permutaciones aleatorias contiene una introducción a las permutaciones aleatorias.

Las permutaciones son conjuntos de ciclos etiquetados. Usando el caso etiquetado del teorema fundamental de Flajolet-Sedgewick y escribiendo${\displaystyle \scriptstyle {\mathcal {P}}}$para el conjunto de permutaciones y${\displaystyle \scriptstyle {\mathcal {Z}}}$Para el conjunto unitario, tenemos

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))={\mathcal {P}}.}$

Al traducirlo a funciones generadoras exponenciales (FGE), tenemos:

${\displaystyle \exp \left(\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}}$

donde hemos utilizado el hecho de que la EGF de la especie combinatoria de permutaciones (hay n ! permutaciones de n elementos) es

${\displaystyle \sum _{n\geq 0}{\frac {n!}{n!}}z^{n}={\frac {1}{1-z}}.}$

Esta única ecuación permite derivar un gran número de estadísticas de permutación. En primer lugar, eliminando términos de${\displaystyle \scriptstyle \operatorname {SET} }$, es decir, podemos restringir el número de ciclos que contiene una permutación, por ejemplo, restringiendo el EGF a${\displaystyle \scriptstyle \operatorname {SET} _{2}}$obtenemos permutaciones que contienen dos ciclos. En segundo lugar, observe que el EGF de ciclos etiquetados, es decir, de${\displaystyle \scriptstyle \operatorname {CYC} ({\mathcal {Z}})}$, es $${\displaystyle \sum _{k\geq 1}{\frac {(k-1)!z^{k}}{k!}}=\sum _{k\geq 1}{\frac {z^{k}}{k}}=\log {\frac {1}{1-z}}}$$ porque hay k !  / k ciclos etiquetados. Esto significa que al eliminar términos de esta función generadora, podemos restringir el tamaño de los ciclos que aparecen en una permutación y obtener una EGF de las permutaciones que contengan solo ciclos de un tamaño determinado. 

En lugar de eliminar y seleccionar ciclos, también se pueden asignar diferentes pesos a ciclos de diferentes tamaños. Si${\displaystyle b:\mathbb {N} \rightarrow \mathbb {R} }$es una función de peso que depende únicamente del tamaño k del ciclo y, por brevedad, escribimos

${\displaystyle b(\sigma )=\sum _{c\in \sigma }b(c),}$

definir el valor de b para una permutación${\displaystyle \sigma }$Si es la suma de sus valores en los ciclos, entonces podemos marcar ciclos de longitud k con u ^{b ( k )} y obtener una función generadora de dos variables.

${\displaystyle g(z,u)=1+\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}u^{b(\sigma )}\right){\frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}}$

Esta es una función generadora "mixta": es una función generadora exponencial en z y una función generadora ordinaria en el parámetro secundario u. Derivando y evaluando en u  =  1, tenemos

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}=\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}b(\sigma )\right){\frac {z^{n}}{n!}}}$

Esta es la función generadora de probabilidad de la esperanza de b . En otras palabras, el coeficiente de${\displaystyle z^{n}}$en esta serie de potencias es el valor esperado de b en permutaciones en${\displaystyle S_{n}}$dado que cada permutación se elige con la misma probabilidad${\displaystyle 1/n!}$.

Este artículo utiliza el operador de extracción de coeficientes [ z ⁿ ], documentado en la página de series de potencias formales .

Una involución es una permutación σ tal que σ ² = 1 bajo composición de permutaciones. De ello se deduce que σ solo puede contener ciclos de longitud uno o dos, es decir, la función generadora exponencial g ( z ) de estas permutaciones es ^{[ 1 ].}

${\displaystyle g(z)=\exp \left(z+{\frac {1}{2}}z^{2}\right).}$

Esto proporciona la fórmula explícita para el número total.${\displaystyle I(n)}$de involuciones entre las permutaciones σ  ∈ S _n : ^{[ 1 ]} 

${\displaystyle I(n)=n![z^{n}]g(z)=n!\sum _{a+2b=n}{\frac {1}{a!\;2^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/2\rfloor }{\frac {1}{(n-2b)!\;2^{b}\;b!}}.}$

Dividir por n ! da como resultado la probabilidad de que una permutación aleatoria sea una involución. Estos números se conocen como números telefónicos .

Esto generaliza el concepto de involución. Una raíz m -ésima de la unidad es una permutación σ tal que σ ^m = 1 bajo composición de permutaciones. Ahora, cada vez que aplicamos σ, avanzamos un paso en paralelo a lo largo de todos sus ciclos. Un ciclo de longitud d aplicado d veces produce la permutación identidad en d elementos ( d puntos fijos) y d es el valor más pequeño para hacerlo. Por lo tanto, m debe ser un múltiplo de todos los tamaños de ciclo d , es decir, los únicos ciclos posibles son aquellos cuya longitud d es un divisor de m . De ello se deduce que la EGF g ( x ) de estas permutaciones es

${\displaystyle g(z)=\exp \left(\sum _{d\mid m}{\frac {z^{d}}{d}}\right).}$

Cuando m = p , donde p es primo, esto se simplifica a

${\displaystyle n![z^{n}]g(z)=n!\sum _{a+pb=n}{\frac {1}{a!\;p^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/p\rfloor }{\frac {1}{(n-pb)!\;p^{b}\;b!}}.}$

Esto se puede hacer mediante inversión de Möbius . Trabajando con el mismo concepto que en la entrada anterior, observamos que la especie combinatoria${\displaystyle {\mathcal {Q}}}$de permutaciones cuyo orden divide a k está dado por

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{d\mid k}\operatorname {CYC} _{=d}({\mathcal {Z}})\right).}$

Trasladando a funciones generadoras exponenciales obtenemos la EGF de permutaciones cuyo orden divide a k , que es

${\displaystyle Q_{k}(z)=\exp \left(\sum _{d\mid k}{\frac {z^{d}}{d}}\right).}$

Ahora podemos usar esta función generadora para contar permutaciones de orden exactamente k . Sea${\displaystyle p_{n,d}}$sea ​​el número de permutaciones en n cuyo orden es exactamente d y${\displaystyle q_{n,k}}$el número de permutaciones en n el recuento de permutaciones cuyo orden divide a k . Entonces tenemos

${\displaystyle \sum _{d|k}p_{n,d}=q_{n,k}.}$

De ello se deduce, por inversión de Möbius , que

${\displaystyle \sum _{d|k}q_{n,d}\times \mu (k/d)=p_{n,k}.}$

Por lo tanto, tenemos el EGF

${\displaystyle Q(z)=\sum _{d\mid k}\mu (k/d)\times Q_{d}(z)=\sum _{d\mid k}\mu (k/d)\exp \left(\sum _{m\mid d}{\frac {z^{m}}{m}}\right).}$

El recuento deseado viene dado entonces por

${\displaystyle n![z^{n}]Q(z).}$

Esta fórmula produce, por ejemplo, para k  =  6, la EGF.

${\displaystyle Q(z)={\rm {e}}^{z}-{\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/3\,z^{3}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/6\,z^{6}}}$

con la secuencia de valores comenzando en n  =  5

${\displaystyle 20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots }$(secuencia A061121 en el OEIS )

Para k  =  8 obtenemos la EGF

${\displaystyle Q(z)=-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}+{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}+1/8\,z^{8}}}$

con la secuencia de valores comenzando en n  =  8

${\displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots }$(secuencia A061122 en el OEIS )

Finalmente, para k  =  12 obtenemos la EGF.

${\displaystyle Q(z)={\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}-{\rm {e}}^{z+1/2\,z^{2}+1/3\,{z}^{3}+1/6\,z^{6}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/4\,z^{4}+1/6\,z^{6}+1/12\,z^{12}}}$

con la secuencia de valores comenzando en n  =  7

${\displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots }$(secuencia A061125 en el OEIS )

Supongamos que hay n personas en una fiesta, cada una de las cuales trajo un paraguas. Al final de la fiesta, todos toman un paraguas de la pila y se van. ¿Cuál es la probabilidad de que nadie se haya ido con su propio paraguas? Este problema es equivalente a contar permutaciones sin puntos fijos (llamadas desordenamientos ), y por lo tanto la EGF, donde restamos los puntos fijos (ciclos de longitud 1) eliminando el término z de la relación fundamental es

${\displaystyle \exp \left(-z+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}.}$

Multiplicación por${\displaystyle 1/(1-z)}$suma los coeficientes de${\displaystyle e^{-z}}$, entonces${\displaystyle D(n)}$El número total de alteraciones viene dado por:

${\displaystyle D(n)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\;\approx \;{\frac {n!}{e}}.}$

Por lo tanto hay aproximadamente${\displaystyle n!/e}$desordenamientos y la probabilidad de que una permutación aleatoria sea un desordenamiento es${\displaystyle 1/e.}$

Este resultado también puede probarse mediante inclusión-exclusión . Utilizando los conjuntos${\displaystyle A_{p}}$dónde${\displaystyle {\begin{matrix}1\leq p\leq n\end{matrix}}}$Para denotar el conjunto de permutaciones que fijan p , tenemos

${\displaystyle \left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.}$

Esta fórmula cuenta el número de permutaciones que tienen al menos un punto fijo. Las cardinalidades son las siguientes:

${\displaystyle \left|A_{p}\right|=(n-1)!\;,\;\;\left|A_{p}\cap A_{q}\right|=(n-2)!\;,\;\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=(n-3)!\;,\;\ldots }$

Por lo tanto, el número de permutaciones sin punto fijo es

${\displaystyle n!\;\;-\;\;{n \choose 1}(n-1)!\;\;+\;\;{n \choose 2}(n-2)!\;\;-\;\;{n \choose 3}(n-3)!\;\;+\;\;\cdots \;\;\pm \;\;{n \choose n}(n-n)!}$

o

${\displaystyle n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\cdots \pm {\frac {1}{n!}}\right)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

y tenemos la reclamación.

Existe una generalización de estos números, que se conoce como números de encuentro , es decir, el número${\displaystyle D(n,m)}$de permutaciones de${\displaystyle [n]}$que contiene m puntos fijos. La EGF correspondiente se obtiene marcando ciclos de tamaño uno con la variable u , es decir, eligiendo b ( k ) igual a uno para${\displaystyle k=1}$y cero en caso contrario, lo que produce la función generadora.${\displaystyle g(z,u)}$del conjunto de permutaciones por el número de puntos fijos:

${\displaystyle g(z,u)=\exp \left(-z+uz+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}e^{uz}.}$

Resulta que

${\displaystyle [u^{m}]g(z,u)={\frac {e^{-z}}{1-z}}{\frac {z^{m}}{m!}}}$

y por lo tanto

${\displaystyle D(n,m)=n![z^{n}][u^{m}]g(z,u)={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}$

Esto implica inmediatamente que

${\displaystyle D(n,m)={n \choose m}D(n-m,0)\;\;{\text{ and }}\;\;{\frac {D(n,m)}{n!}}\approx {\frac {e^{-1}}{m!}}}$

para n grande, m fijo.

Si P es una permutación, el orden de P es el entero positivo más pequeño n para el cual${\displaystyle P^{n}}$es la permutación identidad. Este es el mínimo común múltiplo de las longitudes de los ciclos de P.

Un teorema de Goh y Schmutz ^{[ 2 ]} establece que si${\displaystyle \mu _{n}}$es el orden esperado de una permutación aleatoria de tamaño n , entonces

${\displaystyle \log \mu _{n}\sim c{\sqrt {\frac {n}{\log n}}}}$

donde la constante c es

${\displaystyle 2{\sqrt {2\int _{0}^{\infty }\log \log \left({\frac {e}{1-e^{-t}}}\right)dt}}\approx 1.1178641511899}$

Podemos utilizar la misma construcción que en la sección anterior para calcular el número de desordenamientos.${\displaystyle D_{0}(n)}$que contiene un número par de ciclos y el número${\displaystyle D_{1}(n)}$que contiene un número impar de ciclos. Para ello necesitamos marcar todos los ciclos y restar los puntos fijos, obteniendo

${\displaystyle g(z,u)=\exp \left(-uz+u\log {\frac {1}{1-z}}\right)=\exp(-uz)\left({\frac {1}{1-z}}\right)^{u}.}$

Ahora bien, un razonamiento muy básico muestra que el EGF${\displaystyle q(z)}$de${\displaystyle D_{0}(n)}$es dado por

${\displaystyle q(z)={\frac {1}{2}}\times g(z,-1)+{\frac {1}{2}}\times g(z,1)={\frac {1}{2}}\exp(-z){\frac {1}{1-z}}+{\frac {1}{2}}\exp(z)(1-z).}$

Por lo tanto, tenemos

${\displaystyle D_{0}(n)=n![z^{n}]q(z)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}n!{\frac {1}{n!}}-{\frac {1}{2}}n!{\frac {1}{(n-1)!}}}$

que es

${\displaystyle {\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}(1-n)\sim {\frac {1}{2e}}n!+{\frac {1}{2}}(1-n).}$

Restar${\displaystyle D_{0}(n)}$de${\displaystyle D(n)}$, encontramos

${\displaystyle D_{1}(n)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}-{\frac {1}{2}}(1-n).}$

La diferencia de estos dos (${\displaystyle D_{0}(n)}$y${\displaystyle D_{1}(n)}$) es${\displaystyle n-1.}$

Un alcaide quiere hacer espacio en su prisión y está considerando liberar a cien prisioneros, liberando así cien celdas. Por lo tanto, reúne a cien prisioneros y les pide que jueguen al siguiente juego: coloca cien urnas en fila, cada una con el nombre de un prisionero, donde cada nombre aparece exactamente una vez. El juego se desarrolla así: cada prisionero puede mirar dentro de cincuenta urnas. Si no encuentra su nombre en ninguna de las cincuenta urnas, todos los prisioneros serán ejecutados inmediatamente; de ​​lo contrario, el juego continúa. Los prisioneros tienen unos instantes para decidir una estrategia, sabiendo que una vez que comience el juego, no podrán comunicarse entre sí, marcar las urnas de ninguna manera ni mover las urnas ni los nombres que contienen. Si eligen las urnas al azar, sus posibilidades de supervivencia son casi nulas, pero existe una estrategia que les da un 30% de posibilidades de supervivencia, suponiendo que los nombres se asignan a las urnas al azar. ¿Cuál es?

En primer lugar, la probabilidad de supervivencia utilizando elecciones aleatorias es

${\displaystyle \left({\frac {99 \choose 49}{100 \choose 50}}\right)^{100}={\frac {1}{2^{100}}},}$

Por lo tanto, esta definitivamente no es una estrategia práctica.

La estrategia de supervivencia del 30% consiste en considerar el contenido de las urnas como una permutación de los prisioneros y recorrer los ciclos. Para simplificar la notación, se asigna un número a cada prisionero, por ejemplo, ordenando sus nombres alfabéticamente. A partir de entonces, se puede considerar que las urnas contienen números en lugar de nombres. Ahora bien, el contenido de las urnas define claramente una permutación. El primer prisionero abre la primera urna. Si encuentra su nombre, ha terminado y sobrevive. De lo contrario, abre la urna con el número que encontró en la primera. El proceso se repite: el prisionero abre una urna y sobrevive si encuentra su nombre; de ​​lo contrario, abre la urna con el número que acaba de obtener, hasta un límite de cincuenta urnas. El segundo prisionero comienza con la urna número dos, el tercero con la número tres, y así sucesivamente. Esta estrategia es precisamente equivalente a recorrer los ciclos de la permutación representada por las urnas. Cada prisionero comienza con la urna que contiene su número y continúa su ciclo hasta un límite de cincuenta urnas. El número de la urna que contiene su número es la preimagen de ese número bajo la permutación. Por lo tanto, los prisioneros sobreviven si todos los ciclos de la permutación contienen como máximo cincuenta elementos. Debemos demostrar que esta probabilidad es de al menos el 30%.

Cabe señalar que esto presupone que el alcaide elige la permutación al azar; si el alcaide anticipa esta estrategia, puede simplemente elegir una permutación con un ciclo de longitud 51. Para evitar esto, los prisioneros pueden acordar de antemano una permutación aleatoria de sus nombres.

Consideramos el caso general de${\displaystyle 2n}$prisioneros y${\displaystyle n}$urnas que se abren. Primero calculamos la probabilidad complementaria, es decir, que hay un ciclo de más de${\displaystyle n}$elementos. Con esto en mente, presentamos

${\displaystyle g(z,u)=\exp \left(z+{\frac {z^{2}}{2}}+{\frac {z^{3}}{3}}+\cdots +u{\frac {z^{n+1}}{n+1}}+u{\frac {z^{n+2}}{n+2}}+\cdots \right)}$

o

${\displaystyle {\frac {1}{1-z}}\exp \left((u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

de modo que la probabilidad deseada sea

${\displaystyle [z^{2n}][u]g(z,u),}$

porque el ciclo de más de${\displaystyle n}$Los elementos serán necesariamente únicos. Utilizando el hecho de que${\displaystyle 2(n+1)>2n}$, encontramos que

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}][u]{\frac {1}{1-z}}\left(1+(u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

lo cual produce

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}]{\frac {1}{1-z}}\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

Finalmente, utilizando una estimación integral como la suma de Euler-Maclaurin o la expansión asintótica del n -ésimo número armónico , obtenemos

${\displaystyle H_{2n}-H_{n}\sim \log 2-{\frac {1}{4n}}+{\frac {1}{16n^{2}}}-{\frac {1}{128n^{4}}}+{\frac {1}{256n^{6}}}-{\frac {17}{4096n^{8}}}+\cdots ,}$

de modo que

${\displaystyle [z^{2n}][u]g(z,u)<\log 2\quad {\mbox{and}}\quad 1-[z^{2n}][u]g(z,u)>1-\log 2=0.30685281,}$

o al menos el 30%, como se afirma.

Un resultado relacionado es que, asintóticamente, la longitud esperada del ciclo más largo es λn, donde λ es la constante de Golomb-Dickman , aproximadamente 0,62.

Este ejemplo se debe a Anna Gál y Peter Bro Miltersen; consulte el artículo de Peter Winkler para obtener más información y vea el debate en Les-Mathematiques.net . Consulte las referencias de «100 prisioneros» para acceder a los enlaces a dichas referencias.

El cálculo anterior se puede realizar de una manera más simple y directa, como sigue: primero observe que una permutación de${\displaystyle 2n}$los elementos contienen como máximo un ciclo de longitud estrictamente mayor que${\displaystyle n}$Por lo tanto, si denotamos .

${\displaystyle p_{k}=\Pr[{\mbox{there is a cycle of length }}k],}$

entonces

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}p_{k}.}$

Para${\displaystyle k>n}$, el número de permutaciones que contienen un ciclo de longitud exactamente${\displaystyle k}$es

${\displaystyle {{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!.}$

Explicación: ${\displaystyle {{2n} \choose k}}$es el número de formas de elegir el${\displaystyle k}$elementos que componen el ciclo; ${\displaystyle {\frac {k!}{k}}}$es el número de formas de ordenar${\displaystyle k}$elementos en un ciclo; y ${\displaystyle (2n-k)!}$es el número de maneras de permutar los elementos restantes. Aquí no hay doble conteo porque hay como máximo un ciclo de longitud${\displaystyle k}$cuando${\displaystyle k>n}$. De este modo,

${\displaystyle p_{k}={\frac {{{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!}{(2n)!}}={\frac {1}{k}}.}$

Concluimos que

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

Existe un problema muy similar que se ajusta perfectamente al método aquí presentado. Supongamos que tenemos n cajas ordenadas. Cada caja contiene una llave para alguna otra caja o, posiblemente, para sí misma, lo que da lugar a una permutación de las llaves. Se nos permite seleccionar k de estas n cajas a la vez y abrirlas simultáneamente, obteniendo así k llaves. ¿Cuál es la probabilidad de que, utilizando estas llaves, podamos abrir las n cajas, donde usamos una llave encontrada para abrir la caja a la que pertenece y repetimos el proceso?

El enunciado matemático de este problema es el siguiente: elija aleatoriamente una permutación de n elementos y k valores del rango de 1 a n , también al azar, y llame a estos valores marcas. ¿Cuál es la probabilidad de que haya al menos una marca en cada ciclo de la permutación? Se afirma que esta probabilidad es k/n .

La especie ${\displaystyle {\mathcal {Q}}}$de permutaciones por ciclos con algún subconjunto no vacío de cada ciclo marcado tiene la especificación

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{q\geq 1}\operatorname {CYC} _{=q}({\mathcal {Z}})\times \sum _{p=1}^{q}{q \choose p}{\mathcal {U}}^{p}\right).}$

El índice en la suma interna comienza en uno porque debemos tener al menos una marca en cada ciclo.

Al traducir la especificación a funciones generadoras, obtenemos la función generadora bivariada.

${\displaystyle G(z,u)=\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}\sum _{p=1}^{q}{q \choose p}u^{p}\right).}$

Esto se simplifica a

${\displaystyle \exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}(u+1)^{q}-\sum _{q\geq 1}{\frac {z^{q}}{q}}\right)}$

o

${\displaystyle \exp \left(\log {\frac {1}{1-(u+1)z}}-\log {\frac {1}{1-z}}\right)={\frac {1-z}{1-(u+1)z}}.}$

Para extraer los coeficientes de esto, reescríbalo de la siguiente manera:

${\displaystyle (1-z)\sum _{q\geq 0}(u+1)^{q}z^{q}.}$

Ahora se deduce que

${\displaystyle [z^{n}]G(z,u)=(u+1)^{n}-(u+1)^{n-1}}$

y por lo tanto

${\displaystyle [u^{k}][z^{n}]G(z,u)={n \choose k}-{n-1 \choose k}.}$

Dividir por${\displaystyle {n \choose k}}$para obtener

${\displaystyle 1-{\frac {(n-1)!}{k!(n-1-k)!}}{\frac {k!(n-k)!}{n!}}=1-{\frac {n-k}{n}}={\frac {k}{n}}.}$

No necesitamos dividir por n! porque${\displaystyle G(z,u)}$es exponencial en z .

Aplicando el teorema fundamental de Flajolet-Sedgewick , es decir, el teorema de enumeración etiquetada con${\displaystyle G=S_{m}}$, al conjunto

${\displaystyle \operatorname {SET} _{=m}(\operatorname {CYC} ({\mathcal {Z}}))}$

obtenemos la función generadora

${\displaystyle g_{m}(z)={\frac {1}{|S_{m}|}}\left(\log {\frac {1}{1-z}}\right)^{m}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m}.}$

El término

${\displaystyle (-1)^{n+m}n!\;[z^{n}]g_{m}(z)=s(n,m)}$

produce los números de Stirling con signo de primera especie y${\displaystyle g_{m}(z)}$es la EGF de los números de Stirling sin signo de primera especie, es decir

${\displaystyle n![z^{n}]g_{m}(z)=\left[{\begin{matrix}n\\m\end{matrix}}\right].}$

Podemos calcular la OGF de los números de Stirling con signo para n fijo, es decir

${\displaystyle s_{n}(w)=\sum _{m=0}^{n}s(n,m)w^{m}.}$

Comience con

${\displaystyle g_{m}(z)=\sum _{n\geq m}{\frac {(-1)^{n+m}}{n!}}s(n,m)z^{n}}$

lo cual produce

${\displaystyle (-1)^{m}g_{m}(z)w^{m}=\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}.}$

Sumando esto, obtenemos

${\displaystyle \sum _{m\geq 0}(-1)^{m}g_{m}(z)w^{m}=\sum _{m\geq 0}\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}z^{n}\sum _{m=0}^{n}s(n,m)w^{m}.}$

Utilizando la fórmula que involucra el logaritmo para${\displaystyle g_{m}(z)}$a la izquierda, la definición de${\displaystyle s_{n}(w)}$a la derecha, y el teorema del binomio , obtenemos

${\displaystyle (1-z)^{w}=\sum _{n\geq 0}{w \choose n}(-1)^{n}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}s_{n}(w)z^{n}.}$

Comparando los coeficientes de${\displaystyle z^{n}}$y utilizando la definición del coeficiente binomial , finalmente tenemos

${\displaystyle s_{n}(w)=w\;(w-1)\;(w-2)\;\cdots \;(w-(n-1))=(w)_{n},}$

un factorial descendente . El cálculo de la OGF de los números de Stirling sin signo de primera especie funciona de manera similar.

En este problema utilizamos una función generadora bivariada g ( z , u ) como se describe en la introducción. El valor de b para un ciclo que no es de tamaño m es cero, y uno para un ciclo de tamaño m . Tenemos 

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z^{m}}{m}}}$

o

${\displaystyle {\frac {1}{m}}z^{m}\;+\;{\frac {1}{m}}z^{m+1}\;+\;{\frac {1}{m}}z^{m+2}\;+\;\cdots }$

Esto significa que el número esperado de ciclos de tamaño m en una permutación de longitud n menor que m es cero (obviamente). Una permutación aleatoria de longitud al menos m contiene, en promedio, 1/ m ciclos de longitud m . En particular, una permutación aleatoria contiene aproximadamente un punto fijo.

Por lo tanto, la OGF del número esperado de ciclos de longitud menor o igual a m es

${\displaystyle {\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ and }}[z^{n}]{\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\mbox{ for }}n\geq m}$

donde H _m es el m -ésimo número armónico . Por lo tanto, el número esperado de ciclos de longitud como máximo m en una permutación aleatoria es aproximadamente ln m . 

El GF mixto${\displaystyle g(z,u)}$del conjunto de permutaciones por el número de puntos fijos es

${\displaystyle g(z,u)=\exp \left(-z+uz+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp(-z+uz).}$

Sea X la variable aleatoria que representa el número de puntos fijos de una permutación aleatoria. Utilizando números de Stirling de segunda especie , tenemos la siguiente fórmula para el m -ésimo momento de X :

${\displaystyle E(X^{m})=E\left(\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}(X)_{k}\right)=\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}E((X)_{k}),}$

dónde${\displaystyle (X)_{k}}$es un factorial descendente . Usando${\displaystyle g(z,u)}$, tenemos

${\displaystyle E((X)_{k})=[z^{n}]\left({\frac {d}{du}}\right)^{k}g(z,u){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}}\exp(-z+uz){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}},}$

que es cero cuando${\displaystyle k>n}$y uno en caso contrario. Por lo tanto, solo términos con${\displaystyle k\leq n}$contribuir a la suma. Esto produce

${\displaystyle E(X^{m})=\sum _{k=0}^{n}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}.}$

Supongamos que eliges una permutación aleatoria.${\displaystyle \sigma }$y elevarlo a algún poder${\displaystyle k}$, con${\displaystyle k}$un número entero positivo y preguntar sobre el número esperado de puntos fijos en el resultado. Denotemos este valor por${\displaystyle E[F_{k}]}$.

Para cada divisor${\displaystyle d}$de${\displaystyle k}$un ciclo de longitud${\displaystyle d}$se divide en${\displaystyle d}$puntos fijos cuando se elevan a la potencia${\displaystyle k.}$Por lo tanto, necesitamos marcar estos ciclos con${\displaystyle u^{d}.}$Para ilustrar esto, considere${\displaystyle E[F_{6}].}$

Nosotros obtenemos

${\displaystyle g(z,u)=\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}+\log {\frac {1}{1-z}}\right)}$

que es

${\displaystyle {\frac {1}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right).}$

Continuando una vez más como se describe en la introducción, encontramos

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right)\right|_{u=1}}$

que es

${\displaystyle {\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}.}$

La conclusión es que${\displaystyle E[F_{6}]=4}$para${\displaystyle n\geq 6}$y hay cuatro puntos fijos en promedio.

El procedimiento general es

${\displaystyle g(z,u)=\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right).}$

Una vez más continuando como antes, encontramos

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {\sum _{d\mid k}z^{d}}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right)\right|_{u=1}={\frac {\sum _{d\mid k}z^{d}}{1-z}}.}$

Hemos demostrado que el valor de${\displaystyle E[F_{k}]}$es igual a${\displaystyle \tau (k)}$(el número de divisores de${\displaystyle k}$) tan pronto como${\displaystyle n\geq k.}$Comienza en${\displaystyle 1}$para${\displaystyle n=1}$y aumenta en uno cada vez${\displaystyle n}$alcanza un divisor de${\displaystyle k}$hasta e incluyendo${\displaystyle k}$sí mismo.

Construimos la función generadora bivariada${\displaystyle g(z,u)}$usando${\displaystyle b(k)}$, dónde${\displaystyle b(k)}$es uno para todos los ciclos (cada ciclo contribuye con uno al número total de ciclos).

Tenga en cuenta que${\displaystyle g(z,u)}$tiene la forma cerrada

${\displaystyle g(z,u)=\left({\frac {1}{1-z}}\right)^{u}}$

y genera los números de Stirling sin signo de primera especie .

Tenemos

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\sum _{k\geq 1}{\frac {z^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

Por lo tanto, el número esperado de ciclos es el número armónico.${\displaystyle H_{n}}$o sobre${\displaystyle \log n}$.

(Tenga en cuenta que la sección Cien prisioneros contiene exactamente el mismo problema con un cálculo muy similar, además de una demostración elemental más sencilla ).

Una vez más, comencemos con la función generadora exponencial.${\displaystyle g(z,u)}$, esta vez de la clase${\displaystyle {\mathcal {P}}}$de permutaciones según el tamaño donde ciclos de longitud mayor que${\displaystyle n/2}$están marcados con la variable${\displaystyle u}$:

${\displaystyle g(z,u)=\exp \left(u\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}+\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right).}$

Solo puede haber un ciclo de longitud mayor que${\displaystyle {\frac {n}{2}}}$Por lo tanto, la respuesta a la pregunta viene dada por

${\displaystyle n![uz^{n}]g(z,u)=n![z^{n}]\exp \left(\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

o

${\displaystyle n![z^{n}]\exp \left(\log {\frac {1}{1-z}}-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

que es

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\exp \left(-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)^{m+1}}$

El exponente de${\displaystyle z}$en el término siendo elevado al poder${\displaystyle m+1}$es más grande que${\displaystyle \lfloor {\frac {n}{2}}\rfloor }$y por lo tanto ningún valor para${\displaystyle m>0}$posiblemente pueda contribuir a${\displaystyle [z^{n}].}$

De ello se deduce que la respuesta es

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n!\sum _{k=\lfloor {\frac {n}{2}}\rfloor +1}^{n}{\frac {1}{k}}.}$

La suma tiene una representación alternativa que se encuentra, por ejemplo, en el OEIS OEIS : A024167  .

${\displaystyle \sum _{k=1}^{n}{\frac {1}{k}}-\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{k}}=\sum _{k=1}^{n}{\frac {1}{k}}-2\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{2k}}=\sum _{k=1 \atop k\;{\text{even}}}^{n}(1-2){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{odd}}}^{n}{\frac {1}{k}}}$

finalmente dando

${\displaystyle n!\sum _{k=1}^{n}{\frac {(-1)^{k+1}}{k}}\sim n!\log 2.}$

Podemos utilizar la descomposición en ciclos disjuntos de una permutación para factorizarla como un producto de transposiciones, reemplazando un ciclo de longitud k por k  −  1 transposiciones. Por ejemplo, el ciclo${\displaystyle (1\;2\;34)}$factores como${\displaystyle (1\;2)\;(2\;3)\;(3\;4)}$. La función${\displaystyle b(k)}$para ciclos es igual a${\displaystyle k-1}$y obtenemos

${\displaystyle g(z,u)=\left({\frac {1}{1-uz}}\right)^{1/u}}$

y

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}(k-1){\frac {z^{k}}{k}}={\frac {z}{(1-z)^{2}}}-{\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

Por lo tanto, el número esperado de transposiciones${\displaystyle T(n)}$es

${\displaystyle T(n)=n-H_{n}}$

dónde${\displaystyle H_{n}}$es el${\displaystyle n^{th}}$Número armónico . También podríamos haber obtenido esta fórmula observando que el número de transposiciones se obtiene sumando las longitudes de todos los ciclos (lo que da n ) y restando uno por cada ciclo (lo que da${\displaystyle \log n}$(por la sección anterior).

Tenga en cuenta que${\displaystyle g(z,u)}$nuevamente genera los números de Stirling sin signo de primera especie , pero en orden inverso. Más precisamente, tenemos

${\displaystyle (-1)^{m}n!\;[z^{n}][u^{m}]g(z,u)=\left[{\begin{matrix}n\\n-m\end{matrix}}\right]}$

Para ver esto, tenga en cuenta que lo anterior es equivalente a

${\displaystyle (-1)^{n+m}n!\;[z^{n}][u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=\left[{\begin{matrix}n\\m\end{matrix}}\right]}$

y eso

${\displaystyle [u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=[u^{m}]\left({\frac {1}{1-z}}\right)^{u}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m},}$