Estou procurando uma maneira de gerar números aleatórios que pareçam ser distribuídos uniformemente - e todos os testes mostrarão que eles são uniformes - exceto que eles são distribuídos de maneira mais uniforme que os dados uniformes verdadeiros .
O problema que tenho com os randoms uniformes "verdadeiros" é que eles ocasionalmente se agrupam. Esse efeito é mais forte em um tamanho de amostra baixo. Aproximadamente: quando eu desenho dois randoms uniformes em U [0; 1], as chances são de cerca de 10% de que elas estejam dentro do intervalo de 0,1 e de 1% de 0,01.
Então, estou procurando uma boa maneira de gerar números aleatórios que são distribuídos de maneira mais uniforme do que randoms uniformes .
Exemplo de caso de uso: diga que estou fazendo um jogo de computador e quero colocar um tesouro aleatoriamente em um mapa (sem me importar com outra coisa). Não quero que o tesouro esteja em um só lugar, deve estar em todo o mapa. Com randoms uniformes, se eu colocar, digamos, 10 objetos, as chances não são tão baixas de que existam 5 ou mais próximos um do outro. Isso pode dar a um jogador uma vantagem sobre o outro. Pense no limpador de minas, as chances (embora baixas, se houver minas suficientes) são que você tenha muita sorte e ganhe com um único clique.
Uma abordagem muito ingênua para o meu problema é dividir os dados em uma grade. Desde que o número seja grande o suficiente (e tenha fatores), é possível impor uniformidade extra dessa maneira. Então, em vez de desenhar 12 variáveis aleatórias de U [0; 1], eu posso desenhar 6 de U [0; 0,5] e 6 de U [0,5; 1] ou 4 de U [0; 1/3] + 4 de U [1/3; 2/3] + 4 de U [2/3; 1]
Existe alguma maneira melhor de obter essa uniformidade extra no uniforme? Provavelmente só funciona para randoms em lote (ao desenhar um único aleatório, obviamente tenho que considerar todo o intervalo). Em particular, posso embaralhar os registros novamente depois (para que não sejam os quatro primeiros do primeiro terço).
Que tal fazer isso de forma incremental? Então o primeiro está em U [0; 1], então dois de cada metade, um de cada terço, um de cada quarto? Isso foi investigado e quão bom é? Talvez eu tenha que tomar cuidado para usar geradores diferentes para xey para não correlacioná-los (o primeiro xy sempre estaria na metade inferior, o segundo na metade esquerda e na terceira parte inferior, o terceiro no terceiro centro e na terceira parte superior. .. então pelo menos alguma permutação aleatória de lixeira também é necessária e, a longo prazo, será muito uniforme, eu acho.
Como nó lateral, existe um teste bem conhecido se alguma distribuição é distribuída de maneira muito uniforme para ser realmente uniforme? Então, testando "verdadeiro uniforme" vs. "alguém mexeu com os dados e distribuiu os itens de maneira mais uniforme". Se bem me lembro, o Hopkins Statistic pode medir isso, mas também pode ser usado para testes? Também um teste KS inverso: se o maior desvio estiver abaixo de um certo limite esperado, os dados serão distribuídos de maneira muito uniforme?
fonte
Respostas:
Sim , existem muitas maneiras de produzir uma sequência de números que são distribuídos de maneira mais uniforme que os uniformes aleatórios. De fato, existe todo um campo dedicado a essa questão; é a espinha dorsal do quase-Monte Carlo (QMC). Abaixo está um breve tour do básico absoluto.
Uniformidade de medição
A quantidade é frequentemente chamada de discrepância ou extrema discrepância do conjunto de pontos . Intuitivamente, encontramos o "pior" retângulo onde a proporção de pontos se desvia mais do que seria de esperar sob perfeita uniformidade. ( x i ) RDn (xi) R
Isso é pesado na prática e difícil de calcular. Na maioria das vezes, as pessoas preferem trabalhar com a discrepância em estrela , A única diferença é o conjunto sobre o qual o supremo é assumido. É o conjunto de retângulos ancorados (na origem), ou seja, onde .A a 1 = a 2 = ⋯ = a d = 0
Lema : para todos , . Prova . A mão esquerda é ligada óbvio desde . O limite à direita segue porque todo pode ser composto por uniões, interseções e complementos de não mais que retângulos ancorados (isto é, em ). n d A ⊂ R R ∈ R 2 d AD⋆n≤Dn≤2dD⋆n n d
A⊂R R∈R 2d A
Assim, vemos que e são equivalentes no sentido de que se um for pequeno à medida que cresce, o outro também será. Aqui está uma figura (desenho animado) mostrando os retângulos candidatos para cada discrepância.D ⋆ n nDn D⋆n n
Exemplos de sequências "boas"
Sequências com discrepância estelar verificávelmente baixa são freqüentemente chamadas, sem surpresa, de sequências de baixa discrepância .D⋆n
van der Corput . Este é talvez o exemplo mais simples. Para , as seqüências de van der Corput são formadas expandindo o número inteiro em binário e depois "refletindo os dígitos" em torno do ponto decimal. Mais formalmente, isso é feito com a função inversa radical na base , onde e são os dígitos na expansão da base de . Essa função também forma a base de muitas outras seqüências. Por exemplo, no binário é e, portanto,i b φ b ( i ) = ∞ Σ k = 0 um k b - k - 1d= 1 Eu b
Observe que, como o bit menos significativo de oscila entre e , os pontos para ímpar estão em , enquanto os pontos para par estão em .Eu 0 0 1 1 xEu i [1/2,1) xi i (0,1/2)
Sequências de Halton . Entre as sequências clássicas de baixa discrepância mais populares, essas são extensões da sequência de van der Corput para múltiplas dimensões. Vamos ser a th menor prime. Então, o ésimo ponto da seqüência dimensional de Halton é Para baixo eles funcionam muito bem, mas têm problemas em dimensões mais altas .pj j i xi d
As seqüências de Halton satisfazem . Eles também são bons porque são extensíveis , pois a construção dos pontos não depende de uma escolha a priori do comprimento da sequência .D⋆n=O(n−1(logn)d) n
Sequências de Hammersley . Esta é uma modificação muito simples da sequência Halton. Em vez disso, usamos Talvez surpreendentemente, a vantagem é que eles têm melhor discrepância em estrela .
Aqui está um exemplo das seqüências de Halton e Hammersley em duas dimensões.
Sequências de Halton permutadas por Faure . Um conjunto especial de permutações (fixado em função de ) pode ser aplicado à expansão de dígitos para cada ao produzir a sequência de Halton. Isso ajuda a remediar (até certo ponto) os problemas mencionados em dimensões superiores. Cada uma das permutações tem a propriedade interessante de manter e como pontos fixos.i ak i 0 b−1
Regras de treliça . Seja números inteiros. Pegue onde indica a parte fracionária de . A escolha criteriosa dos valores produz boas propriedades de uniformidade. Escolhas ruins podem levar a sequências ruins. Eles também não são extensíveis. Aqui estão dois exemplos.β1,…,βd−1
Randomização simples: rotações de Cranley-Patterson . Seja uma sequência de pontos. Seja . Então os pontos são distribuídos uniformemente em .xi∈[0,1]d U∼U(0,1) x^i={xi+U} [0,1]d
Aqui está um exemplo com os pontos azuis sendo os pontos originais e os pontos vermelhos sendo os rotacionados com linhas conectando-os (e mostrados ao redor, quando apropriado).
Sequências completamente uniformemente distribuídas . Essa é uma noção ainda mais forte de uniformidade que às vezes entra em jogo. Seja a sequência de pontos em e agora forme blocos sobrepostos de tamanho para obter a sequência . Então, se , tomamos , em seguida, , etc. Se, por cada , , então é dito estar completamente distribuído uniformemente . Em outras palavras, a sequência produz um conjunto de pontos de qualquer(ui) [0,1] d (xi) s=3 x1=(u1,u2,u3) x2=(u2,u3,u4) s≥1 D⋆n(x1,…,xn)→0 (ui) dimensão que possui propriedades desejáveis .D⋆n
Como exemplo, a sequência de van der Corput não é completamente uniformemente distribuída, pois para , os pontos estão no quadrado e os pontos são em . Portanto, não há pontos no quadrado que implica que para , para todos os .s=2 x2i (0,1/2)×[1/2,1) x2i−1 [1/2,1)×(0,1/2) (0,1/2)×(0,1/2) s=2 D⋆n≥1/4 n
Referências padrão
A monografia de Niederreiter (1992) e o texto de Fang e Wang (1994) são lugares a serem explorados.
fonte
Uma maneira de fazer isso seria gerar números aleatórios uniformes, testar a proximidade usando qualquer método que você quiser e excluir itens aleatórios muito próximos dos outros e escolher outro conjunto de uniformes aleatórios para compensá-los.
Essa distribuição passaria em todos os testes de uniformidade? Espero que não! Já não é distribuído uniformemente, agora é outra distribuição.
Um aspecto não probatório da probabilidade é que o acaso é desajeitado. Existem mais execuções em dados aleatórios do que as pessoas pensam que haverá. Acho que Tversky fez alguma pesquisa sobre isso (ele pesquisou tanto, porém, que é difícil lembrar).
fonte
Isso é conhecido como um processo de ponto de poisson "hard-core" - assim chamado por Brian Ripley na década de 1970; ou seja, você deseja que seja aleatório, mas não deseja que nenhum ponto fique muito próximo. O "núcleo duro" pode ser imaginado como uma zona de buffer em torno da qual outros pontos não podem se intrometer.
Imagine que você está gravando a posição de alguns carros em uma cidade - mas você está apenas registrando o ponto no centro nominal do carro. Enquanto estão nas ruas, dois pares de pontos não podem se aproximar porque os pontos são protegidos pelo "núcleo duro" da carroceria - ignoraremos a possível superposição em estacionamentos de vários andares :-)
Existem procedimentos para gerar esses processos de pontos - uma maneira é apenas gerar pontos de maneira uniforme e remover os que estiverem muito próximos!
Para mais detalhes sobre esses processos, consulte, por exemplo, este
fonte
Com relação à geração de lotes com antecedência, eu geraria um grande número de conjuntos de variáveis pseudo-aleatórias e as testaria com um teste como o teste de Kolmogorov-Smirnov. Você deseja selecionar o conjunto com o maior valor p (ou seja, é o ideal). Observe que isso será lento, mas à medida que aumenta, provavelmente se torna menos necessário. Np≈1 N
Com relação à geração incremental, você está basicamente procurando uma série com uma autocorrelação moderadamente negativa. Não tenho certeza de qual seria a melhor maneira de fazer isso, pois tenho uma experiência muito limitada com séries temporais, mas suspeito que existem algoritmos para isso.
Com relação a um teste para "muito par", qualquer teste para saber se uma amostra segue uma distribuição específica (como o KS observado acima) será suficiente, basta verificar se , em vez de abordagem padrão. Escrevi sobre um exemplo dessa abordagem alternativa aqui: o qui-quadrado sempre é um teste unilateral .p>(1−α)
fonte
Eu formalizaria seu problema da seguinte maneira: Você deseja uma distribuição acima de modo que a densidade seja por alguns quantificando a repulsão de pontos. f ( x ) ∝ e ( 1[0,1]n k<0f(x)∝e(1k∑ij|xi−xj|k)1k k<0
Uma maneira fácil de gerar esses vetores é fazer a amostragem de Gibbs.
fonte