Al azar de permutaciones de Z_n

Question

En http://www.springerlink.com/content/y19u81675243r237/fulltext.pdfel autor afirma lo siguiente sin pruebas (ecuación 3.1):

"Considere la posibilidad de una permutación aleatoria de $\pi$ de % de$\mathbb{Z}_n$. ¿Cuál es la probabilidad de que $\pi(i+1)−\pi(i) \mod{n} < n/2$ para todos los $i$?"

El reclamo es que esto es $(2+o(1))^{−n}$, lo que tiene sentido y parece que debería ser un argumento estándar. Sin embargo, no he sido capaz de llegar con un corto de prueba, ni he sido capaz de encontrar una prueba en la literatura.

¿Alguien sabe de una completa prueba?

Answer 1

Envié un correo electrónico Noga a preguntarle a él; he aquí su respuesta (retocado ligeramente para MO; cualquier error en lo que he puesto son probablemente la mina en vez de Noga s). Los únicos detalles que no están presentes son las aplicaciones necesarias de la fórmula de Stirling.

Que yo recuerde el argumento de que tenía en mente era como sigue (no estoy tratando de optimizar el término de error). Deje $k$ ser un entero par, mucho menor que $n$ pero mucho más grande que $\log n$, supongo que $k=n^{0.01}$ o así debería ser correcto. Dividir la conjunto de vértices $[n]$ de los cíclicos torneo a $k$ bloques de consecutivos vértices, cada uno de tamaño $n/k$. Llamada de los bloques de $B_1,..,B_k$. Vamos a contar sólo Hamilton ciclos en el torneo en el que todos los bordes ir entre los distintos bloques, a decir de $B_i$ a $B_j$, con $j \lt i+k/2$ por cada borde, y con exactamente $n/(k(k-2)/2)$ entre los bordes cada par de bloques.

Para contar los que se utiliza el llamado MEJOR teorema de contar la número de circuitos de Euler en el dígrafo en el $k$ vértices $B_1,\ldots,B_k$ con $n/(k(k-2)/2)$ dirigido los bordes de $B_i$ a $B_j$ para $i \neq j$, $j\lt i+(k-2)/2$ (y dividir por $([n/(k(k-2)/2)]!)^{n/(k(k-2)/2)}$ para asegurarse de que todos los bordes de B_i a B_j se considera la misma.)

En el MEJOR de los teorema de omitir el determinante correspondiente a la número de arborecences, que no es necesario aquí (estamos de todos modos sólo demostrando un límite inferior) y es insignificante. Esto le da $[(n/k-1)!]^{k}$ dividido por el término de arriba. Ahora, esto tiene que ser multiplicada por $[(n/k)!]^k$, debido a que dentro de cada bloque B_i podemos decidir el orden en el que tomamos el $n/k$ vértices (entramos en el bloque representado por un vértice $(n/k)$ tiempos, así podemos decidir qué vértice entramos en cada paso). Ahora toma el producto resultante, el uso de Stirling y elegir la mejor $k$: esto debe darle a la demanda (no estoy seguro con que término de error). Bien puede ser que algunos de los más fuertes en cotas inferiores son conocidos, y en de hecho creo que una similar obligado cumple para cualquier regulares torneo (creo que hay un papel por Bill Cuckler acerca de que en el CPC de 2007). Espero que esto tenga sentido, por favor, siéntase libre de hablar de lo que ver ajuste en Mathoverflow.

Answer 2

Por extraño $n$ la respuesta a tu pregunta (como se dice!) se puede encontrar en Noga Alon del papel. Es decir, el número de permutaciones en su pregunta es igual a la permanente de una $n\times n$ matriz $A$ en la que cada fila y cada columna tiene $(n-1)/2$ queridos y $(n+1)/2$ ceros. Por lo tanto, $2/(n-1)*A$ es doblemente estocástico, por lo que por van der Waerden de la conjetura (demostrado por Egorichev y Falikman en 1981) la probabilidad solicitada es $\geq n!^{-1}((n-1)/2)^n n!/n^n=(1/e+o(1))2^{-n}$.

Incluso para $n$ la respuesta es similar. A continuación, el número de permutaciones en su pregunta es igual a la permanente de una $n\times n$ matriz $A$ en la que cada fila y cada columna tiene $n/2$ queridos y $n/2$ ceros. Por lo tanto, $2/n*A$ es doblemente estocástico, por lo que del mismo modo como antes de que la probabilidad solicitada es $\geq n!^{-1}(n/2)^n n!/n^n=2^{-n}$.

Por otro lado, para todos los $n$ la considera permanente es $\ll \sqrt{n} n!/2^n$ por Noga Alon principal del teorema en el papel, por lo tanto la probabilidad solicitada es $\ll \sqrt{n}2^{-n}$.

Por supuesto, esto no explica por qué (3.1) en Noga Alon del papel aguanta. Esta es una declaración acerca de azar cíclico permutaciones $\pi$ satisfacción $\pi(i+1)−\pi(i) \mod{n} < n/2$ para todos los $i$.