¿Cómo puedo generar permutaciones aleatorias de [n] con k ciclos, donde k es mucho mayor que log n?

Question

Ú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.

Answer 1

Encontrará la respuesta en la página 38 de mis apuntes East Side, West Side, que puede descargar gratuitamente de mi sitio web. Es un programa completo y corto de Maple. El problema fue resuelto originalmente en 1978 en Combinatorial Algorithms, por Albert Nijenhuis y yo.

Herb Wilf

Answer 2

Varios algoritmos para la generación insesgada de permutaciones aleatorias de ciertos tipos (como permutaciones en k ciclos) se dan en esta tesis presentada ayer mismo: http://www.jjj.de/pub/ Espero que esto ayude, jj

Answer 3

Una cadena de Markov que funciona: Elige uniformemente dos ciclos A,B y repartir su unión uniformemente en dos nuevos ciclos. Esto es reversible, por lo que la medida uniforme es estacionaria.

Sería interesante saber a qué velocidad se mezcla.

Answer 4

Se puede muestrear a partir de la distribución uniforme de permutaciones en $n$ elementos con $k$ ciclos en el tiempo previsto $O(n\sqrt{k})$ .

Para grandes $n$ y $k$ esto puede ser más factible que el método al que se refiere Herb Wilf en su respuesta, que, si entiendo bien, requiere la generación de los números del ciclo Stirling $S(m,r)$ para $m\leq n$ y $r\leq k$ .

La idea es la siguiente: considere un Poisson-Dirichlet( $\theta$ ) partición de $[n]$ . Los bloques de dicha partición tienen la distribución de los ciclos de una permutación aleatoria de $[n]$ de la distribución que da un peso proporcional a $\theta^r$ a cualquier permutación con $r$ ciclos. En particular, condicionada al número de ciclos, la permutación está uniformemente distribuida. (Una vez que se tiene una partición en bloques correspondientes a los ciclos, basta con rellenar los elementos de $[n]$ en las posiciones de los ciclos uniformemente al azar).

Elija $\theta$ de tal manera que el número medio de ciclos esté en torno a $k$ . Se puede muestrear un PD( $\theta$ ) partición de $[n]$ a tiempo $O(n)$ (véase más abajo). Siga generando muestras independientes de la partición hasta que obtenga una con exactamente $k$ bloques. La varianza del número de ciclos será $O(k)$ (véase más abajo) y el probabilidad de que el número de ciclos sea precisamente $k$ será del orden de $1/\sqrt{k}$ Así que habrá que generar $O(\sqrt{k})$ muestras de este tipo antes de dar con una $m$ ciclos.

Así que en realidad esto no está tan lejos de lo que usted sugiere en la pregunta (generar permutaciones aleatorias hasta encontrar una que encaje) con el matiz de que en lugar de generar a partir de la distribución uniforme (que corresponde a PD(1)) se elige un valor mejor de $\theta$ y generar a partir de PD( $\theta$ ).

Aquí tienes dos buenas formas de muestrear un PD( $\theta$ ) partición de $[n]$ :

(1) "Proceso del restaurante chino" de Dubins y Pitman. Añadimos elementos a la partición de uno en uno. El elemento 1 comienza en un bloque por sí solo. Después, cuando añadimos el elemento $r+1$ , supongamos que actualmente hay $m$ bloques cuyos tamaños son $n_1, n_2, ... n_m$ . Añadir elemento $r+1$ para bloquear $i$ con probabilidad $n_i/(r+\theta)$ para $1\leq i\leq m$ y poner elemento $r+1$ en un nuevo bloque por sí solo con probabilidad $\theta/(r+\theta)$ .

(2) "Representación de Feller". Generar variables aleatorias Bernoulli independientes $B_1, \dots, B_n$ con $P(B_i=1)=\theta/(i-1+\theta)$ . Escribe una cadena de longitud $n$ dividido en bloques, con la regla de que empezamos un nuevo bloque antes de la posición $i$ siempre que $B_i=1$ . Así, por ejemplo, si $n=10$ con $B_1=B_5=B_6=B_9=1$ y el otro $B_i$ igual a 0, entonces el patrón es

(a b c d)(e)(f g h)(i j).

(Tenga en cuenta que siempre $B_1=1$ ). A continuación, asigne los elementos de $[n]$ a las posiciones de los bloques uniformemente al azar.

El número previsto de bloques es $\sum_{i=1}^n \mathbb{E}B_i$ que es $\sum_{i=1}^n \theta/(i+\theta)$ , que es aproximadamente $\theta(\log n-\log \theta)$ . Si es igual a $k$ con $1 << k << n$ entonces el número de bloques será aproximadamente normal con media $k$ y varianza $O(k)$ .

Para más detalles sobre algunas de las cosas mencionadas aquí que tienen que ver con las particiones de Poisson-Dirichlet, las permutaciones aleatorias, etc., véanse, por ejemplo, las notas de Pitman de la conferencia de Saint-Flour: http://bibserver.berkeley.edu/csp/april05/bookcsp.pdf

Answer 5

Otra cadena de Markov que converge a la distribución uniforme es una variación de la mezcla "aleatorio a aleatorio": escoge un elemento aleatorio, sácalo de la permutación y vuelve a ponerlo en un lugar aleatorio, a menos que el elemento aleatorio que escogiste fuera un monociclo, en cuyo caso tienes que volver a ponerlo como monociclo para preservar el número de ciclos.

Esto probablemente converge mucho más lentamente que la cadena de Omer (al menos para k << n), pero tiene la ventaja de que, a menos que me equivoque, se puede utilizar el acoplamiento de trayectorias para acotar el tiempo de mezcla en algo así como n^2 log n. Si tuviera que adivinar diría que el tiempo de mezcla real es n log n. Por suerte, no lo sé.

Tal vez el acoplamiento de caminos podría funcionar también para la cadena de Omer.