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

33

É 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 !nnnnn!nnn!

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(ρ)ρP(n)

M(n)=n!nnmaxρP(n)C(ρ)

e

m(n)=n!nnminρP(n)C(ρ) ?

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

limnM(n)=limnm(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 limM(n) é finito ou se limm(n) é delimitado por 0? O que se sabe sobre o comportamento dessas quantidades?

Steven Stadnicki
fonte
8
Boa pergunta. Não sei onde é o melhor lugar para esta pergunta. A menos que esteja claro que outro fórum é melhor para ele, acho que você deve deixá-lo aqui por mais ou menos uma semana e, se não obtiver uma resposta satisfatória, pergunte em um dos outros fóruns (e coloque links nas duas perguntas) )
Peter Shor
4
@vzn "Por que fazer análises difíceis em um algoritmo defeituoso conhecido?" Como a matemática é interessante e você nunca sabe onde outras aplicações podem surgir - veja a análise de Knuth do Bubble Sort, por exemplo. Os gráficos de Atwood fornecem uma análise qualitativa aproximada da falta de homogeneidade, mas isso está muito longe de uma análise matematicamente quantitativa. (E há várias formulações equivalentes diferentes de shuffle Fischer-Yates -. O que eu mencionar funciona muito bem)
Steven Stadnicki
4
Para o registro, a sequência OEIS A192053 é máxima e não lista um formulário fechado. Além disso, as notas para essa entrada sugerem que min pode ser , implicando que . C(ρ)C(ρ)2n1m(n)0
Mhum 8/11
2
@vzn O que há de errado com perguntas abertas?
Yuval Filmus
1
@vzn Discordo da sua última frase, há muitas análises de embaralhamento "imperfeito". Por exemplo, se fizermos transposições aleatórias, sabe-se que o limite de aleatoriedade é aproximadamente . A questão atual pode ser difícil, mas, a priori, é difícil dizer se é "muito difícil". Uma resposta como a de mhum já é muito satisfatória, mostrando que a pergunta era apropriada para o fórum e não apresentava uma barreira intransponível (provas formais retiradas). (1/2)nlogn
Yuval Filmus

Respostas:

13

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".ρn=(2,3,4,,n,1)C(ρn)=2n1nm(n)(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,,n,1)(1,2,3,,n)1n1n

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 itemnii1in1i1jij1ji<j11precisa acabar em primeiro lugar, uma contradição.

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.1n(1,3,4,5,,n,2)(1,2,3,4,,n)ρn12nC(ρn1)=2n21

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.1nn1(2,3,4,,n,1)(n,2,3,4,,n1,1)ρn1C(ρn1)=2n2n11

Assim, .C(ρn)=2C(ρn1)=2n1

Peter Shor
fonte
Perfeito - o argumento por trás do lema se parece muito com o que eu tinha em relação às involuções, sendo a única maneira de obter a permutação de identidade, mas havia perdido a estrutura recursiva na troca explícita. Obrigado!
Steven Stadnicki
10

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 .ι{1n}kι(k)ι(k)kQ(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)C(ne)n/2enQ(n)=Q(n1)+(n1)Q(n2)R(n)=Q(n)Q(n1)n<R(n)<n+1nn/2n!nn na definição de é apenas cerca de , o termo principal de domina e produz (assintoticamente) .M(n)CnenQ(n)M(n)Cn(n+1)/2e3n/2+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.nM(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

Steven Stadnicki
fonte
1
Não é muito difícil mostrar que a permutação é um exemplo com . Se este for o pior caso, como é o primeiro , então . (2,3,4,,n,1)C(ρ)=2n1nm(n)(2/e)n
Peter Shor
@ PeterShor Você pode dar o argumento básico? Sinto que estou perdendo uma versão simples do argumento das involuções que funcionaria, mas não estou entendendo direito. Eu acho que mesmo que isso não seja mínimo, seria bom o suficiente; parece improvável que a contagem mínima seja subexponencial em e apenas saber que o máximo e o mínimo normalizados são "exponencialmente ruins" é uma resposta bastante satisfatória. n
Steven Stadnicki
Eu adicionei uma resposta com o argumento ... é muito longo para um comentário.
Peter Shor