Números aleatórios uniformes falsos: mais uniformemente distribuídos que os dados uniformes verdadeiros

43

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?

Anony-Mousse
fonte
7
Você já ouviu falar de sequências de Halton ? Para "muito uniformemente", as pessoas (começando com a investigação de Fisher dos resultados do experimento de Mendel com ervilhas) referiram-se à estatística (usual) do qui-quadrado à cauda inferior de uma distribuição do qui-quadrado.
whuber
Uma maneira de formalizar esta seria a distribuição quer de um de tal modo que (1) g ( ) marginalizar a 1 sobre x 1 , . . . , X n - 1 , (2) g é simétrica, isto é, X 1 , . . . , X n são permutáveis, e (3) g ( x 1 , .g(x1,...,xn)g()1x1,...,xn1gX1,...,Xn é grande quando x 1 , . . . , x n são dispersos. Eu acho que existe um problema real com (2) e (3), já que seqüências infinitas de troca em R não podem ser negativamente correlacionadas; portanto, quanto maior n queremos usar, menos repulsão podemos aplicar; por outro lado, para grandes n , devemos ter uma boa propagação de qualquer maneira. g(x1,...,xn)x1,...,xnRnn
cara
As sequências de Halton estão bem próximas da abordagem em que eu estava pensando. Incluindo pular as primeiras entradas para reduzir o risco de correlação. Eu também estava pensando em usar uma permeação aleatória para cada nível. Obrigado por esse ponteiro, pois isso me dá um bom ponto para procurar métodos relacionados!
Anony-Mousse
wrt. Sequências de Halton novamente. Eu preciso tê-los não determinísticos, pelo menos, exceto por uma semente inicial. Eu vejo duas maneiras aqui. Eu posso fazer um deslocamento cíclico por um deslocamento aleatório + um deslocamento inicial aleatório + tamanho da etapa. O problema é que, obviamente, o "tesouro" a permanecer no exemplo do jogo também não deve estar nas mesmas posições em relação a cada vez. Ou eu poderia usar essa abordagem uniforme do subintervalo que eu tinha na minha pergunta para adicionar uma certa quantidade de "reviravolta aleatória". Por assim dizer: Halton parece novamente previsível e regular demais para o meu uso.
Anony-Mousse
3
en.wikipedia.org/wiki/Low-discrepancy_sequence ou mathworld.wolfram.com/QuasirandomSequence.html . Vários dos testes comuns de RNGs uniformes (como os das baterias de testes Diehard / Dieharder) são sensíveis a essas coisas; por exemplo, existem poucas 'pequenas distâncias' entre pontos.
Glen_b

Respostas:

60

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

nx1,x2,,xn[0,1]ddR

Dn:=supRR|1ni=1n1(xiR)vol(R)|,
R[ 0 , 1 ] d 0 um i  b i1 R R R v o l ( R ) = Π i ( b i - a i )[a1,b1]××[ad,bd][0,1]d0aibi1Ré o conjunto de todos esses retângulos. O primeiro termo dentro do módulo é a proporção "observada" de pontos dentro de e o segundo termo é o volume de , .RRvol(R)=i(biai)

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

Dn=supRA|1ni=1n1(xiR)vol(R)|.
Aa1=a2==ad=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 AR R R 2 d ADnDn2dDnnd
ARRR2dA

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 nDnDnn

discrepância extremal e estelar

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 .Dn

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=1ib

ϕb(i)=k=0akbk1,
i=k=0akbkakbi41101001a0=1 , , , , e . Portanto, o 41º ponto na sequência de van der Corput é .a1=0a2=0a3=1a4=0a5=1x41=ϕ2(41)=0.100101(base 2)=37/64

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 .i01xii[1/2,1)xii(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 .pjjixid

xi=(ϕp1(i),ϕp2(i),,ϕpd(i)).
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 .Dn=O(n1(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 .

xi=(i/n,ϕp1(i),ϕp2(i),,ϕpd1(i)).
Dn=O(n1(logn)d1)

Aqui está um exemplo das seqüências de Halton e Hammersley em duas dimensões.

Halton e Hammersley

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.iaki0b1

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,,βd1

xi=(i/n,{iβ1/n},,{iβd1/n}),
{y}yβ

Malhas boas e ruins

(t,m,s) redes . redes na base são conjuntos de pontos de modo que todo retângulo de volume em contenha pontos. Esta é uma forte forma de uniformidade. Small é seu amigo, neste caso. As seqüências de Halton, Sobol 'e Faure são exemplos de redes. Estes se prestam muito bem à randomização via embaralhamento. A mistura aleatória (feita corretamente) de uma rede produz outra rede . O projeto MinT mantém uma coleção dessas seqüências.(t,m,s)bbtm[0,1]sbtt(t,m,s)(t,m,s)(t,m,s)

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]dUU(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).

Cranley Patterson

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=3x1=(u1,u2,u3)x2=(u2,u3,u4) s1Dn(x1,,xn)0(ui)dimensão que possui propriedades desejáveis .Dn

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=2x2i(0,1/2)×[1/2,1)x2i1[1/2,1)×(0,1/2)(0,1/2)×(0,1/2)s=2Dn1/4n

Referências padrão

A monografia de Niederreiter (1992) e o texto de Fang e Wang (1994) são lugares a serem explorados.

cardeal
fonte
4
Essa resposta é excelente e eu só queria apreciar o esforço que você coloca nela. Obrigado!
Anony-Mousse
11
Uma pequena pergunta de acompanhamento. As sequências de Halton parecem boas, porque também parecem não ser muito regulares. O material da treliça é muito regular para mim, e também a sequência de Hammersley parece ter muitos objetos nas linhas através da origem. Qual é uma boa maneira de controlar o equilíbrio entre o uniforme verdadeiro e o uniforme falso? Basta ter 80% de contribuição de Halton + 20% de uniforme aleatório?
Anony-Mousse
11
+ 10k e definitivamente com um recorde de respostas baixas (87 !!!!)! Ah, e eu gosto muito deste post. Marquei a pergunta por causa disso, na verdade. Muito bem, @ cardinal.
Macro
@ Macro: Obrigado por um comentário tão bom! Você é muito gentil. Eu acho que essa coisa de 10K pode ser temporária para mim. Suspeito que possa ficar bem abaixo de 10 mil assim que os votos do Procrastinador forem revertidos. Estou surpreso que isso ainda não tenha acontecido. Eu acredito que eles deram quase 3000 votos neste site. Obrigado também por postar aqui; de alguma forma, nunca vi as perguntas de acompanhamento de Anony-Mousse!
cardeal
@ Anony-Mousse: Desculpas pela terrível demora em responder. Eu devo ter esquecido esses comentários. Eu acho que criar um equilíbrio dependeria dos seus objetivos. Teoricamente falando, a introdução de quaisquer pontos uniformes aleatórios é obrigada a destruir as propriedades ideais de , por exemplo. Por uma questão prática, pode ser melhor usar um jitter muito pequeno dos pontos do QMC em que o jitter é escolhido com base nas propriedades da sequência. Você também pode introduzir transformações aleatórias de corpo rígido em todos os pontos, por exemplo, mudanças e rotações de coordenadas. D DD
cardeal
3

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).

Peter Flom - Restabelece Monica
fonte
2
Um dos (muitos) problemas com essa abordagem é que é muito difícil caracterizar a distribuição resultante.
whuber
O OP parece mais preocupado com amostras pequenas. Isso sugere que ele não precisa se preocupar com toda a distribuição. Suponha que você tenha um conjunto de coordenadas, gere outra e calcule a distância euclidiana em relação a todas as outras. Se a menor distância estiver abaixo de algum limite, jogue o número para fora e gere um novo. Eu acho que a solução de Peter funciona bem.
John
@whuber Ele não parece estar interessado nisso, embora eu possa estar errado.
Peter Flom - Restabelece Monica
2
Deixe-me declarar minha objeção um pouco mais claramente, Peter: quando você remove e / ou ajusta valores pseudo-aleatórios de uma maneira ad hoc para aproximar alguma propriedade desejada, como falta de agrupamento, é difícil garantir que as seqüências resultantes tenham quaisquer propriedades desejáveis. Com o seu método, por exemplo, você poderia nos dizer qual seria o primeiro momento do processo resultante? (Ou seja, você pode nos garantir que a intensidade é uniforme?) E o segundo momento? Geralmente, estas constituem as informações mínimas necessárias para usar as seqüências efetivamente para inferência.
whuber
2
OK, mas, no exemplo da pergunta, ele deseja colocar um tesouro no mapa em um jogo. Isso não envolverá inferência, momentos ou qualquer coisa do tipo. Admito que meu método não seria bom para muitos propósitos, mas acho que combina com o exemplo. Claro, talvez o exemplo não seja realmente o que ele quer ... Talvez ele queira algo mais formal, caso em que todas as outras respostas devem ser analisadas.
Peter Flom - Restabelece Monica
3

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

Sean
fonte
2

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. Np1N

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α)

- Reinstate Monica
fonte
1

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(1kij|xixj|k)1kk<0

Uma maneira fácil de gerar esses vetores é fazer a amostragem de Gibbs.

Neil G
fonte
Você pode elaborar sobre isso? A amostragem de Gibbs não parece ajudar aqui, como distribuição condicional = distribuição marginal = uniforme? Ou sua sugestão é usar as amostras anteriores para produzir "buracos" na distribuição da qual coletar amostras?
Anony-Mousse
Escolha um vetor aleatório uniforme e escolha repetidamente de maneira uniforme um índice reamostrar . Calcule a razão de antes e depois da reamostragem e rejeite a reamostragem com as probabilidades . Isso é muito mais rápido do que as outras respostas que você obteve quando possui um vetor muito longo porque está realizando rejeições locais e não globais. x i r f ( x ) rixirf(x)r
Neil G