Este é um seguimento de uma pergunta do Stackoverflow sobre embaralhar uma matriz aleatoriamente .
Existem algoritmos estabelecidos (como o Knuth-Fisher-Yates Shuffle ) que se deve usar para embaralhar uma matriz, em vez de confiar em implementações ad-hoc "ingênuas".
Agora estou interessado em provar (ou refutar) que meu algoritmo ingênuo está quebrado (como em: não gera todas as permutações possíveis com igual probabilidade).
Aqui está o algoritmo:
Faça um loop algumas vezes (o comprimento da matriz deve funcionar) e, a cada iteração, obtenha dois índices aleatórios da matriz e troque os dois elementos.
Obviamente, isso precisa de mais números aleatórios que o KFY (o dobro), mas, além disso, ele funciona corretamente? E qual seria o número apropriado de iterações (o "comprimento da matriz" é suficiente)?
fonte
Respostas:
Está quebrado, embora se você executar baralhamento suficiente, pode ser uma excelente aproximação (como as respostas anteriores indicaram).
Apenas para entender o que está acontecendo, considere com que frequência seu algoritmo irá gerar embaralhamento de uma matriz de elementos na qual o primeiro elemento é fixo, . Quando permutações são geradas com igual probabilidade, isso deve ocorrer do tempo. Seja a frequência relativa dessa ocorrência após embaralhar com seu algoritmo. Sejamos generosos também, e suponha que você esteja realmente selecionando pares distintos de índices uniformemente aleatoriamente para seus embaralhamentos, de modo que cada par seja selecionado com probabilidade =k ≥ 2 1 / k p n n 1 / ( kk k≥2 1/k pn n 2/(k(k-1))1/(k2) 2/(k(k−1)) . (Isso significa que não há desperdícios "triviais" desperdiçados. Por outro lado, ele interrompe totalmente seu algoritmo para uma matriz de dois elementos, porque você alterna entre fixar os dois elementos e trocá-los; portanto, se você parar após um número predeterminado de etapas, não há aleatoriedade para o resultado!)
Essa frequência satisfaz uma recorrência simples, porque o primeiro elemento é encontrado em seu lugar original após embaralhar de duas maneiras disjuntas. Uma é que ele foi corrigido após shuffles e o próximo shuffle não move o primeiro elemento. A outra é que ele foi movido após shuffles, mas o move para trás. A chance de não mover o primeiro elemento é igual a = , enquanto a chance de mover o primeiro elemento para trás é igual a = . De onde:n n n + 1 s t ( k - 1n+1 n n n+1st (k-2)/k1/ ( k(k−12)/(k2) (k−2)/k 2/(k(k-1))1/(k2) 2/(k(k−1))
A solução é
Subtraindo , vemos que a frequência está errada por . Para e grandes , uma boa aproximação é . Isso mostra que o erro nessa frequência específica diminuirá exponencialmente com o número de trocas em relação ao tamanho da matriz ( ), indicando que será difícil detectar com matrizes grandes se você tiver feito um número relativamente grande de trocas. - mas o erro está sempre lá.( k - 31 / k knk-1( k - 3k - 1)nk - 1k k n n/kk - 1kexp( - 2 nk - 1) n / k
É difícil fornecer uma análise abrangente dos erros em todas as frequências. É provável que eles se comportem como este, o que mostra que, no mínimo, você precisaria de (o número de trocas) para ser grande o suficiente para tornar o erro aceitávelmente pequeno. Uma solução aproximada én
onde deve ser muito pequeno comparado a . Isso implica que deve ser várias vezes para aproximações grosseiras ( ou seja , onde é da ordem de vezes ou mais).1 / k n k ϵ 0,01 1 / kϵ 1/k n k ϵ 0.01 1/k
Tudo isso levanta a questão: por que você escolheria usar um algoritmo que não é muito (mas apenas aproximadamente) correto, emprega exatamente as mesmas técnicas que outro algoritmo que é comprovadamente correto e, no entanto, que requer mais computação?
Editar
O comentário de Thilo é adequado (e eu esperava que ninguém apontasse isso, para que eu pudesse ser poupada desse trabalho extra!). Deixe-me explicar a lógica.
Se você gerar trocas reais a cada vez, estará totalmente ferrado. O problema que apontei para o caso se estende a todas as matrizes. Apenas metade de todas as permutações possíveis pode ser obtida aplicando um número par de swaps; a outra metade é obtida aplicando um número ímpar de swaps. Portanto, nessa situação, você nunca pode gerar em lugar algum uma distribuição uniforme de permutações (mas há tantas possíveis que um estudo de simulação para qualquer considerável não será capaz de detectar o problema). Isso é muito ruim.kk=2 k
Portanto, é aconselhável gerar swaps aleatoriamente, gerando as duas posições independentemente, aleatoriamente. Isso significa que há uma chance de cada vez que um elemento é trocado; isto é, de não fazer nada. Esse processo efetivamente diminui um pouco o algoritmo: após etapas, esperamos que apenas cerca de trocas verdadeiras ocorram.n k - 11/k n k−1kN< N
Observe que o tamanho do erro diminui monotonicamente com o número de trocas distintas. Portanto, realizar menos swaps em média também aumenta o erro, em média. Mas este é um preço que você deve estar disposto a pagar para superar o problema descrito no primeiro item. Consequentemente, minha estimativa de erro é conservadoramente baixa, aproximadamente por um fator de .( k - 1 ) / k
Eu também queria destacar uma exceção aparente interessante: uma análise mais detalhada da fórmula do erro sugere que não há erro no caso . Isso não é um erro: está correto. No entanto, aqui examinei apenas uma estatística relacionada à distribuição uniforme de permutações. O fato de o algoritmo poder reproduzir esta estatística quando (ou seja, obter a frequência certa de permutações que fixam qualquer posição) não garante que as permutações tenham sido realmente distribuídas uniformemente. De fato, após swaps reais, as únicas permutações possíveis que podem ser geradas são ,k = 3 2 n ( 123 ) ( 321 ) 2 n + 1 ( 12 ) ( 23 ) ( 13 )k = 3 k = 3 2 n ( 123 ) ( 321 ) e a identidade. Somente o último fixa uma determinada posição; portanto, exatamente um terço das permutações fixa uma posição. Mas metade das permutações está faltando! No outro caso, após swaps reais, as únicas permutações possíveis são , e . Novamente, exatamente um deles fixará qualquer posição, então obteremos a frequência correta de permutações que fixam essa posição, mas novamente obteremos apenas metade das permutações possíveis.2 n + 1 ( 12 ) ( 23 ) ( 13 )
Este pequeno exemplo ajuda a revelar as principais linhas do argumento: por ser "generoso", subestimamos conservadoramente a taxa de erro de uma estatística específica. Como essa taxa de erro é diferente de zero para todos os , vemos que o algoritmo está quebrado. Além disso, analisando o decaimento na taxa de erro dessa estatística , estabelecemos um limite mais baixo para o número de iterações do algoritmo necessário para ter alguma esperança de aproximar uma distribuição uniforme de permutações.k ≥ 4
fonte
Acho que seu algoritmo simples embaralha as cartas corretamente, pois o número de embaralhamentos tende ao infinito.
Suponha que você tenha três cartas: {A, B, C}. Suponha que suas cartas comecem na seguinte ordem: A, B, C. Depois de um shuffle, você tem as seguintes combinações:
Portanto, a probabilidade de a carta A estar na posição {1,2,3} é {5/9, 2/9, 2/9}.
Se embaralharmos as cartas uma segunda vez, então:
Isso dá 0,407.
Usando a mesma idéia, podemos formar um relacionamento de recorrência, ou seja:
Codificar isso em R (veja o código abaixo) fornece a probabilidade de o cartão A estar na posição {1,2,3} como {0,33333, 0,333333, 0,3333} após dez shuffles.
Código R
fonte
Uma maneira de ver que você não terá uma distribuição perfeitamente uniforme é pela divisibilidade. Na distribuição uniforme, a probabilidade de cada permutação é de. Ao gerar uma sequência de transposições aleatórios, e em seguida, recolher por sequências seu produto, as probabilidades chegar são da forma para algum número inteiro . Se , então . Pelo Postulado de Bertrand (um teorema), para existem números primos que ocorrem no denominador e que não dividem , entãonão é um número inteiro e não há como dividir as transposições uniformemente emt A / n 2 t A 1 / n ! = A / n 2 t n 2 t / n ! = A n ≥ 3 n n 2 t / n ! n ! n = 52 1 / 52 ! 3 , 5 , 7 , . . . , 47 1 /1 / n ! t A / n2 t UMA 1 / n ! = A / n2 t n2 t/ n! =A n ≥ 3 n n2 t/ n! n ! permutações. Por exemplo, se , então o denominador deé divisível por enquanto o denominador de não é, portanto não pode ser reduzido para.n = 52 1 / 52 ! 3 , 5 , 7 , . . . , 47 1 / 522 t A / 522 t 1 / 52 !
Quantos você precisa para aproximar bem uma permutação aleatória? A geração de uma permutação aleatória por transposições aleatórias foi analisada por Diaconis e Shahshahani usando a teoria da representação do grupo simétrico em
Diaconis, P., Shahshahani, M. (1981): "Gerando uma permutação aleatória com transposições aleatórias". Z. Wahrsch. Verw. Geb. 57, 159-179.
Uma conclusão foi que são necessárias transposições no sentido de que após as permutações estão longe de serem aleatórias, mas após o resultado é quase aleatório, tanto no sentido da variação total quanto da distância . Esse tipo de fenômeno de corte é comum em caminhadas aleatórias em grupos e está relacionado ao famoso resultado de que você precisa de embaralhamento de rifles antes que um baralho se torne quase aleatório.12n logn ( 1 - ϵ ) 12n logn ( 1 + ϵ ) 12nlogn eu2 7
fonte
Tenha em mente que eu não sou um estatístico, mas vou colocar meus 2 centavos.
Fiz um pequeno teste em R (cuidado, é muito lento para alto
numTrials
, o código provavelmente pode ser otimizado):Isso gerará uma matriz
swaps
comnumTrials+1
linhas (uma por tentativa + o original) enumElements
colunas (uma por cada elemento do vetor). Se o método estiver correto, a distribuição de cada coluna (ou seja, dos valores de cada elemento nas tentativas) não deve ser diferente da distribuição dos dados originais.Como nossos dados originais eram normalmente distribuídos, esperaríamos que todas as colunas não se desviassem disso.
Se corrermos
Nós temos:
o que parece muito promissor. Agora, se queremos confirmar estatisticamente que as distribuições não se desviam do original, acho que poderíamos usar um teste de Kolmogorov-Smirnov (por favor, algum estatístico pode confirmar que isso está certo?) E, por exemplo,
O que nos dá p = 0,9926
Se verificarmos todas as colunas:
E nós corremos
Nós temos:
Portanto, para a grande maioria dos elementos da matriz, seu método de troca deu um bom resultado, como você também pode ver olhando os quartis.
Observe que, obviamente, com um número menor de tentativas, a situação não é tão boa:
50 tentativas
100 ensaios
500 ensaios
fonte
Aqui está como eu estou interpretando seu algoritmo, em pseudo-código:
fonte