Quão assintoticamente ruim é o embaralhamento ingênuo?

É sabido que esse algoritmo 'ingênuo' para embaralhar uma matriz trocando cada item por outro escolhido aleatoriamente não funciona corretamente:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Especificamente, como em cada uma das iterações, uma das escolhas é feita (com probabilidade uniforme), existem possíveis 'caminhos' através da computação; porque o número de permutações possíveisnão se divide uniformemente no número de caminhos , é impossível para esse algoritmo produzir cada um dospermutações com igual probabilidade. (Em vez disso, deve-se usar o chamado embaralhamento de Fischer-Yates , que essencialmente altera a chamada para escolher um número aleatório entre [0..n) com uma chamada para escolher um número aleatório entre [i..n); isso é discutível para minha pergunta.)n n n n ! n n n $n$$n$$n^n$$n!$$n^n$$n!$

O que me pergunto é: quão "ruim" pode ser o ingênuo baralhar? Mais especificamente, deixar ser o conjunto de todas as permutações e ser o número de caminhos através do algoritmo ingênuo que produz a permutação resultante , qual é o comportamento assintótico do funçõesC ( ρ ) ρ ∈ P ( n $P(n)$$C(\rho)$$\rho\in P(n)$

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

e

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$ ?

O fator principal é 'normalizar' esses valores: se o embaralhamento ingênuo for 'assintoticamente bom', então

$\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$ .

Eu suspeito (com base em algumas simulações de computador que eu vi) que os valores reais são limitados a 1, mas é sabido se $\lim M(n)$ é finito ou se $\lim m(n)$ é delimitado por 0? O que se sabe sobre o comportamento dessas quantidades?

Mostraremos por indução que a permutação é um exemplo com . Se esse for o pior caso, como ocorre nos primeiros (consulte as notas para a sequência OEIS A192053 ), então . Portanto, o mínimo normalizado, como o máximo normalizado, é "exponencialmente ruim".$\rho_n = (2,3,4,\ldots, n,1)$$C(\rho_n) = 2^{n-1}$$n$$m(n) \approx (2/e)^{n}$

O caso base é fácil. Para a etapa de indução, precisamos de um lema:

Lema: em qualquer caminho de a , o primeiro movimento troca as posições e ou o último movimento troca as posições e .$(2,3,4, \ldots, n, 1)$$(1,2,3, \ldots, n)$$1$$n$$1$$n$

Esboço de prova: suponha que não. Considere o primeiro movimento que envolve a ésima posição. Suponha que seja o ésimo movimento, e . Este movimento deve colocar o item no ésimo lugar. Agora considere a próxima jogada que toca no item . Suponha que este movimento é o 'ésimo movimento. Esse movimento deve trocar e , movendo o item para o ésimo lugar, com . Um argumento semelhante diz que o item só pode ser movido posteriormente para a direita. Mas o item$n$$i$$i\neq 1$$i \neq n$$1$$i$$1$$j$$i$$j$$1$$j$$i < j$$1$$1$precisa acabar em primeiro lugar, uma contradição. $\square$

Agora, se o primeiro movimento troca as posições e , os movimentos restantes devem levar a permutação para . Se os movimentos restantes não tocarem na primeira posição, então esta é a permutação nas posições , e sabemos por indução que existem caminhos que fazem isso. Um argumento semelhante à prova do lema diz que não existe um caminho que toque a primeira posição, pois o item deve terminar na posição incorreta.$1$$n$$(1, 3,4,5, \ldots, n,2)$$(1,2,3,4, \ldots, n)$$\rho_{n-1}$$2 \ldots n$$C(\rho_{n-1})=2^{n-2}$$1$

Se o último movimento troca as posições e , os primeiros movimentos devem levar a permutação para a permutação . Novamente, se esses movimentos não tocam a última posição, então esta é a permutação e, por indução, existem caminhos que fazem isso. E novamente, se um dos primeiros se mover aqui toca a última posição, o item nunca pode terminar no lugar correto.$1$$n$$n-1$$(2,3,4,\ldots, n,1)$$(n,2, 3,4, \ldots, n-1, 1)$$\rho_{n-1}$$C(\rho_{n-1})=2^{n-2}$$n-1$$1$

Assim, .$C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$

Após algumas pesquisas, graças ao ponteiro de mhum para o OEIS, finalmente encontrei uma excelente análise e um bom argumento (relativamente) elementar (devido, tanto quanto posso dizer, a Goldstein e Moews [1]) que cresce superexponencialmente rápido em :$M(n)$$n$

Qualquer involução de corresponde a uma execução do algoritmo de embaralhamento 'ingênuo' que produz a permutação de identidade como resultado, uma vez que o algoritmo trocará por e posteriormente trocará com , mantendo os dois inalterados. Isso significa que o número de execuções do algoritmo que produz a permutação de identidade é pelo menos o número de involuções (de fato, um pouco de reflexão mostra que a correspondência é 1-1 e, portanto, é exatamente ) e, portanto, o máximo em é delimitado abaixo por .$\iota$$\{1\ldots n\}$$k$$\iota(k)$$\iota(k)$$k$$Q(n)$$Q(n)$$M(n)$$Q(n)$

$Q(n)$ aparentemente atende vários nomes, incluindo os números de telefone : consulte http://oeis.org/A000085 e http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 . Os assintóticos são bem conhecidos, e acontece que ; da relação de recorrência , pode ser indutivamente mostrado que a razão satisfaz e a partir daí a análise básica obtém o termo nos assintóticos, embora o outro termos exigem um esforço mais cuidadoso. Desde o 'fator de escala'$Q(n) \approx C\left(\frac{n}{e}\right)^{n/2}e^\sqrt{n}$$Q(n) = Q(n-1)+(n-1)Q(n-2)$$R(n) = \frac{Q(n)}{Q(n-1)}$$\sqrt{n}\lt R(n)\lt\sqrt{n+1}$$n^{n/2}$$\frac{n!}{n^n}$ na definição de é apenas cerca de , o termo principal de domina e produz (assintoticamente) .$M(n)$$C\sqrt{n}e^{-n}$$Q(n)$$M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$

Goldstein e Moews, de fato, mostram [1] que a permutação de identidade é a mais provável para grande , de modo que o é de fato a e o comportamento de é totalmente resolvido. Isso ainda deixa em aberto a questão do comportamento de ; Eu não ficaria muito surpreso se isso também ceder à análise em seu trabalho, mas ainda não tive a oportunidade de ler de perto o suficiente para realmente entender seus métodos, apenas o suficiente para obter o resultado básico.$n$$\geq$$\approx$$M(n)$$m(n)$

[1] Goldstein, D. e Moews, D.: "A identidade é o shuffle de troca mais provável para grandes n", http://arxiv.org/abs/math/0010066