Últimamente he estado pensando mucho en las permutaciones aleatorias. Es bien sabido que la media y la varianza del número de ciclos de una permutación elegida uniformemente al azar entre S n son ambos asintóticamente log n, y la distribución es asintóticamente normal.
Quiero saber qué "aspecto" tiene (en términos de estructura de ciclos) una permutación típica de [n] con k(n) ciclos, donde k(n)/(log n) → ∞ a medida que n → ∞. El caso especial que tengo en mente son las permutaciones de [n] con n 1/2 ciclos, ya que me he encontrado con este tipo de permutaciones en otro contexto, pero también tengo curiosidad por el problema más general. Para ello me gustaría disponer de un algoritmo que genere permutaciones de n con k ciclos uniformemente al azar --es decir, que genere cada una con probabilidad 1/S(n,k) donde S(n,k) es un número de Stirling de primer orden-- para poder experimentar con ellas. (Estaría dispuesto a conformarme con una cadena de Markov que converja a esta distribución si lo hace razonablemente rápido).
Desgraciadamente la única forma que conozco de hacerlo es tomar una permutación de [n] uniformemente al azar (esto es fácil) y luego desecharla si no tiene k ciclos. Si k está lejos de log(n) esto es muy ineficiente, ya que esas permutaciones son raras.
He encontrado algunas referencias relacionadas: Este documento de Granville examina las permutaciones con o(n 1/2-ε ) ciclos o Ω(n 1/2+ε ) y muestra que la longitud de sus ciclos tiene una "distribución de Poisson", pero en torno a n 1/2 es una zona de transición. Y este artículo de Kazimirov estudia "el comportamiento asintótico de varias estadísticas" bajo la distribución que he reclamado, pero aún no lo he leído porque no sé leer ruso y estoy esperando la traducción al inglés. Por último, el algoritmo que busco podría estar en uno de los fascículos del volumen 4 de Knuth, pero nuestra biblioteca no los tiene.
