Permutaciones alternas aleatorias

Question

Un permutación alternada de {1, ..., n} es uno donde π(1) > π(2) < π(3) > π(4) < ... Por ejemplo: (24153) es una permutación alterna de longitud 5.

Si $E_n$ es el número de permutaciones alternas de longitud n, el $\sec x + \tan x = \sum_{n \geq 0} E_n \frac{x^n}{n!}$ es la función generadora exponencial.

¿Cómo se muestrea la alternancia de permutaciones uniformemente al azar? El muestreo de rechazo se volvería rápidamente ineficaz, ya que $\frac{E_n}{n!} \approx \frac{4}{\pi} \left(\frac{2}{\pi} \right)^n$ decae exponencialmente en n .

Answer 1

Esto es muy fácil - a menudo lo enseño en mis clases de combinatoria. Empiezas con este triángulo de tipo Pascal que tienes que precalcular: http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html (lea el artículo de Arnold al que se hace referencia allí si el patrón no está claro o mi artículo de estudio con Postnikov "Increasing Trees and Alternating Permutations" - vea mi página web).

Ahora bien, tenga en cuenta que $a_{n,i}$ el número i-ésimo de la fila n-ésima es el número de permutaciones alternas con la primera letra $\ge i$ (hay que alternar las direcciones). Luego se utiliza la programación dinámica o simplemente se elige la primera letra que será i con probabilidad $a_{n,i} - a_{n,i+1}$ , lo que reduce el problema a una permutación alterna de $[n-1]$ . Me estoy saltando detalles (fáciles), pero confío en que puedas averiguar el resto a partir de aquí.

ACTUALIZACIÓN (10 de mayo de 2015):
Aparentemente, este algoritmo requiere $O^\ast(n^3)$ tiempo para calcular los números $a_{n,i}$ que no está mal. Sin embargo, si uno sólo quiere calcular el número de permutaciones alternas, hay una manera más rápida: ver esta charla por Richard Brent y las diapositivas aquí .

Answer 2

Un $O(n \log n)$ El algoritmo para muestrear uniformemente la permutación alterna es descrito por P. Marchal en *Generar permutaciones alternas en el tiempo $O(n \log n)$ ." (por el contrario, la respuesta de Pak es $O(n^3),$ El muestreo de Boltzmann es $O(n^2).$

Answer 3

Esto se trata con cierto detalle en el documento " Muestreo de Boltzmann de estructuras ordenadas ".

Answer 4

A continuación se muestra el código de Mathematica basado en la respuesta de Igor Pak. Para obtener una permutación aleatoria hacia abajo en $[n]$ Comienza por elegir la primera entrada $p_1$ con la probabilidad adecuada; a continuación, elija al azar una permutación ascendente-descendente de tamaño $n-1$ de las permutaciones arriba-abajo con la primera entrada $< p_1$ y luego unirlos (incrementando las entradas $\ge p_1$ en la permutación arriba-abajo).

Para implementar este método, en realidad necesitamos un código que genere una permutación aleatoria de downup con la primera entrada $\ge$ un número determinado $k$ y el código siguiente lo hace. Utiliza la operación ComplementPermutation para intercambiar permutaciones updown y downup.

(* e[n,k] es el número Entringer *)

e[0,0] = 1;
e[n_,0]/;n>=1 := 0;
e[n_,k_]/;k>n || k<0 := 0
e[n_,k_] := e[n,k] = e[n,k-1] + e[n-1,n-k]

ComplementoPermutación[perm_] := Módulo[{n=Longitud[perm]}, n+1-perm];

incrementSpecifiedAndUp[perm_,k_]:=perm/.{i_/;i>=k :> i+1};

partialSums[list_] := Drop[FoldList[Plus,0,list],1];

RandomUpDownPermFirstEntryAtMostk[n_,k_]/;k==n :=
RandomUpDownPermFirstEntryAtMostk[n,n-1];
RandomUpDownPermFirstEntryAtMostk[n_,k_]/;1<=k<n :=
ComplementoPermutación[RandomDownUpPermFirstEntryAtLeastk[n,n+1-k]]

RandomDownUpPermFirstEntryAtLeastk[1,1]={1}; RandomDownUpPermFirstEntryAtLeastk[2,2]={2,1};

RandomDownUpPermFirstEntryAtLeastk[n_,k_]/; n>=3 && 2<=k<=n := Módulo[{claves,m,i,primeraEntrada,restoDePerm},

(* elige la primera entrada utilizando la distribución Entringer *)
keys=partialSums[Table[e[n-1,j],{j,k-1,n-1}]];
m=Random[Integer,{1,Last[keys]}];
i=1;
While[Not[ m<=keys[[i]] ],i=i+1];
primeraEntrada=k-1+i;

(* elegir restOfPerm uniformemente de updowns con su primera entrada < primeraEntrada *)
restOfPerm=RandomUpDownPermFirstEntryAtMostk[n-1,k-2+i];

(* amalgamar firstEntry y restOfPerm *)
Join[{primeraEntrada},incrementSpecifiedAndUp[restoDePerm,primeraEntrada]] ]

RandomDownUpPerm[1]={1};
RandomDownUpPerm[n_]/;n>=2 := RandomDownUpPermFirstEntryAtLeastk[n,2]

Muestra de salida:
In[264]:=RandomDownUpPerm[15]
Out[264]=
{8, 2, 4, 1, 15, 6, 7, 3, 10, 9, 13, 11, 14, 5, 12}

Answer 5

Una observación es que (como se menciona en Encuesta de Stanley ), las Permutaciones Alternas satisfacen una recurrencia $$E_{n+1}=\sum_{\textrm{odd } j \leq n}^n \binom{n}{j} E_j E_{n-j}$$ Aquí $j$ en el lado derecho corresponde al número de elementos que aparecen antes de $1$ en la permutación.

Probablemente no sea la forma más eficiente, pero parece que se podría calcular $E_k$ para todos $k$ hasta $n$ y luego construye tu permutación recursivamente eligiendo sucesivamente dónde va el elemento más pequeño y dividiendo las variables restantes en dos permutaciones alternas del tamaño adecuado en función de eso.