Permutação aleatória

Uma permutação aleatória é um ordenação aleatória de um conjunto de objetos, isto é, uma variável aleatória com valor de permutação. O uso de permutações aleatórias é muitas vezes fundamental para campos que utilizam algoritmos aleatórios, tais como teoria de códigos, criptografia e simulação. Um bom exemplo de uma permutação aleatória é a embaralhar um baralho de cartas, isto é, idealmente, uma permutação aleatória de 52 cartas.

Gerando permutações aleatórias

Método de força bruta

Um método de geração de uma permutação aleatória de um conjunto de tamanho $n$ uniformemente ao acaso (isto é, cada uma das $n!$ permutações tem a mesma probabilidade de acontecer) é gerar uma sequência, tomando um número aleatório entre 1 e n sequencialmente, garantindo que não há repetição. Esta sequência $(x_{1},\ldots ,x_{n})$ é interpretada como a permutação mostrada nesta notação.

{\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},

Este método de força bruta exige novas tentativas sempre que o número aleatório escolhido já foi selecionado. Isso pode ser evitado se, na i-ésima etapa (quando $x_{1},\ldots ,x_{i-1}$ já foi escolhido), um número j é escolhido aleatoriamente entre 1 e $n-i+1$ e igualamos $x_{i}$ ao j-ésimo maior número não-escolhido.

Embaralhamento de Knuth

Um algoritmo simples para gerar uma permutação de $n$ itens uniformemente ao acaso sem repetições, conhecido como Embaralhamento de Knuth. O algoritmo começa com qualquer permutação (por exemplo, a permutação identidade), e então itera-se pelas posições 0 à $n-2$ (por convenção, o primeiro elemento tem o índice 0 e o último elemento tem o índice $n-1$ ), e para cada posição $i$ , troque o elemento que existe atualmente com um elemento escolhido aleatoriamente das posições $i$ a $n-1$ , inclusive. Verifica-se que qualquer permutação de $n$ elementos será produzida por este algoritmo com probabilidade exatamente $1/n!$ , resultando assim, em uma distribuição uniforme sobre todas essas permutações.

unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = uniform(n-i); /* A random integer such that 0 ≤ j < n-i*/
        swap(permutation[i], permutation[i+j]);   /* Swap an existing element [i+j] to position [i] */
    }
}

Observe que a função uniforme() pode não ser implementada simplesmente como random() % (m), a menos que um viés nos resultados é aceitável.

Estatísticas sobre permutações aleatórias

Pontos fixos

A distribuição de probabilidade do número de pontos fixos de uma permutação aleatória uniformemente distribuída se aproxima de uma distribuição de Poisson com valor esperado 1 na medida que o valor de $n$ cresce. Particularmente, é uma aplicação elegante do princípio de inclusão-exclusão que mostra que a probabilidade de que não existem pontos fixos se aproxima de $1/e$ . O primeiro n momentos desta distribuição são exatamente demonstrados pela distribuição de Poisson.

Teste de aleatoriedade

Como com todos os processos aleatórios, a qualidade da distribuição resultante de uma implementação de um algoritmo randomizado, como o algoritmo de Knuth (isto é, o quão próximo o algoritmo é da distribuição uniforme desejada) depende da qualidade da fonte de base de aleatoriedade, como um gerador de números pseudo-aleatórios. Existem muitos possíveis testes de aleatoriedade de permutações aleatórias, tais como os testes de Diehard. Um exemplo típico de tal teste é tomar alguma permutação estatística, para a qual a distribuição é conhecida, e testar se a distribuição de um conjunto de permutações gerados aleatoriamente se aproxima da verdadeira distribuição.

Ver também

Fórmula de amostragem de Ewens — uma ligação com a genética de populações
Embaralhamento de Faro
Embaralhamento de Fisher-Yates
Constante de Golomb–Dickman
Estatísticas de permutação aleatória
Algoritmos de Embaralhamento — método da ordenação aleatória, método de troca iterativo