Por que o Mersenne Twister é considerado bom?

O Mersenne Twister é amplamente considerado bom. Heck, a fonte do CPython diz que "é um dos geradores mais amplamente testados que existe". Mas o que isso significa? Quando solicitado a listar as propriedades desse gerador, a maior parte do que posso oferecer é ruim:

• É massivo e inflexível (por exemplo, sem busca ou múltiplos fluxos),
• Ele falha nos testes estatísticos padrão, apesar de seu enorme tamanho de estado,
• Ele tem sérios problemas em torno de 0, sugerindo que se randomiza bastante mal,
• Dificilmente é rápido

e assim por diante. Comparado a RNGs simples como o XorShift *, também é irremediavelmente complicado.

Por isso, procurei algumas informações sobre por que isso foi considerado bom. O artigo original faz muitos comentários sobre o período "super astronômico" e a equidistribuição 623 dimensional, dizendo

Entre muitas medidas conhecidas, os testes baseados na uniformidade dimensional mais alta, como o teste espectral (cf. Knuth [1981]) e o teste de distribuição k, descritos abaixo, são considerados os mais fortes.

Mas, para essa propriedade, o gerador é derrotado por um contador de comprimento suficiente! Isso não faz comentários sobre as distribuições locais , o que realmente interessa a você em um gerador (embora "local" possa significar várias coisas). E mesmo os CSPRNGs não se importam com períodos tão grandes, já que isso não é remotamente importante.

Há muita matemática no jornal, mas, tanto quanto posso dizer, pouco disso é realmente sobre a qualidade da aleatoriedade. Praticamente todas as menções disso rapidamente retornam a essas alegações originais, em grande parte inúteis.

Parece que as pessoas entraram nesse movimento às custas de tecnologias mais antigas e confiáveis. Por exemplo, se você apenas aumentar o número de palavras em um LCG para 3 (muito menos que os "apenas 624" de um Mersenne Twister) e emitir a palavra principal a cada passagem, ela passará no BigCrush ( a parte mais difícil do conjunto de testes TestU01 ), apesar da falha do Twister ( papel PCG, fig. 2 ). Diante disso, e as poucas evidências que pude encontrar em apoio ao Mersenne Twister, o que causou atenção para favorecê-lo em relação às outras opções?

Isso também não é puramente histórico. Disseram-me de passagem que o Mersenne Twister é pelo menos mais comprovado na prática do que, digamos, PCG aleatoriamente . Mas os casos de uso são tão exigentes que podem fazer melhor do que nossas baterias de testes? Alguns pesquisadores do Google sugerem que provavelmente não o são.

Em resumo, estou me perguntando como o Mersenne Twister obteve sua reputação positiva generalizada, tanto em seu contexto histórico quanto em outros aspectos. Por um lado, sou obviamente cético em relação a suas qualidades, mas, por outro, é difícil imaginar que se tratou de uma ocorrência inteiramente aleatória.

O MT foi considerado bom por alguns anos, até que se descobriu muito ruim nos testes mais avançados do TestU01 BigCrush e nos melhores PRNGs.

A tabela em pcg-random.org, por exemplo, fornece uma boa visão geral dos recursos de alguns dos PRNGs mais usados, onde o único recurso "bom" do Mersenne Twister é o período imenso, e a possibilidade de usar uma semente (Reprodutível Resultados), ele passa nos testes TestU01 SmallCrush simples e rápidos, mas falha em alguns dos testes estatísticos de qualidade mais recentes, esp. Teste LinearComp do TestU01 e Baterias de esmagamento e BigCrush do TestU01.$2^{219937}$

Esta página lista os recursos de Mersenne-Twister em detalhes:

Qualidades positivas

• Produz números de 32 ou 64 bits (portanto utilizáveis ​​como fonte de bits aleatórios)
• Passa na maioria dos testes estatísticos

Qualidades Neutras

• Período extraordinariamente grande de $2^{219937} - 1$
• 623-dimensionalmente equidistribuído
• O período pode ser particionado para emular vários fluxos

Qualidades negativas

• Falha em alguns testes estatísticos, com apenas 45.000 números.
• Previsível - após 624 saídas, podemos prever completamente sua saída.
• O estado do gerador ocupa 2504 bytes de RAM - por outro lado, um gerador extremamente utilizável com um período de mais do que qualquer um que possa usar pode caber em 8 bytes de RAM.
• Não é particularmente rápido.
• $2^{219937}$
• Desigual na sua produção; o gerador pode entrar em "estados ruins" que demoram a recuperar.
• As mudas que diferem apenas levemente levam muito tempo para divergirem umas das outras; a semeadura deve ser feita com cuidado para evitar estados ruins.
• Embora o salto em frente seja possível, os algoritmos para fazer isso são lentos na computação (ou seja, requerem vários segundos) e raramente são fornecidos pelas implementações.

Resumo : Mersenne Twister não é mais suficiente, mas a maioria dos aplicativos e bibliotecas ainda não existe.

Sou o editor que aceitou o artigo de MT no ACM TOMS em 1998 e também sou o designer do TestU01. Não uso MT, mas principalmente MRG32k3a, MRG31k3p e LRSR113. Para saber mais sobre isso, sobre o MT e sobre o que mais existe, você pode consultar os seguintes documentos:

F. Panneton, P. L'Ecuyer e M. Matsumoto, `` Geradores de longo período aprimorados com base no módulo 2 de recorrências lineares '', ACM Transactions on Mathematics Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, `` Random Number Generation '', capítulo 3 do Handbook of Computational Statistics, JE Gentle, W. Haerdle e Y. Mori, eds., Segunda Edição, Springer-Verlag, 2012, 35-71 . https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3

O objetivo deste artigo é apresentar uma revisão bibliográfica sobre o uso de softwares de computação em nuvem, bem como sobre o uso de tecnologias de computação em nuvem. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

L'Ecuyer, `` Geração de números aleatórios com múltiplos fluxos para computadores sequenciais e paralelos '', convidou o tutorial avançado, Anais da Conferência de Simulação de Inverno de 2015, IEEE Press, 2015, 31-44.

Um pouco como os algoritmos de classificação a esse respeito, não existe PRNG "tamanho único". Diferentes são usados ​​para diferentes fins e há uma grande variedade de critérios e usos de design. É possível aplicar PRNGs de maneira incorreta, como usar um para criptografia para o qual não foi projetado. A entrada da Wikipedia no Mersenne Twister também menciona que não foi projetada para "simulações de Monte Carlo que exigem geradores de números aleatórios independentes".

Conforme observado na Wikipedia, esse PRNG é realmente usado em um grande número de linguagens de programação e aplicativos, mesmo como um PRNG padrão. Seria necessária uma análise quase sociológica para explicar por que um PRNG é favorecido. Alguns possíveis fatores que podem estar contribuindo para este PRNG:

• O autor possui boas / fortes credenciais científicas na área e trabalha em PRNGs há décadas.

• Foi projetado especificamente para ser superior a outros métodos da época.

• O autor está envolvido em implementações e rastreá-las, contribuindo também para elas. Alguns PRNGs são mais teóricos e os autores nem sempre se preocupam com implementações reais.

• O sistema é bem suportado / atualizado em uma página da web.

• Novas versões do PRNG foram desenvolvidas para lidar com os pontos fracos. Não existe um único algoritmo Mersenne Twister, é mais como versões diferentes e uma família de variantes que podem lidar com necessidades diferentes.

• Foi extensivamente analisado / testado pelo software padrão de análise aleatória e aprovado por autoridades independentes.

• Há um efeito conhecido medido nos sites e em muitos outros contextos, como citações científicas chamadas "anexo preferencial" que podem ser medidos. É basicamente onde fontes históricas estabelecidas há muito tempo adquirem mais uso. Tal efeito poderia explicar as opções de PRNG ao longo do tempo.

Em outras palavras, você está perguntando sobre um fenômeno de "popularidade" associado e inter-relacionado às escolhas humanas e não está estritamente ligado a qualidades particulares, mas é um tipo de propriedade complexa / emergente e interação entre diferentes algoritmos, usuários e ambiente. / contextos de uso.

Aqui está uma análise independente do algoritmo Mersenne Twister - um gerador de números pseudo-aleatórios e suas variantes por Jagannatam (15p). O parágrafo final é essencialmente uma resposta à sua pergunta. citando apenas os 1 ^st algumas frases:

Mersenne Twister é teoricamente comprovado como um bom PRNG, com um longo período e alta equidistribuição. É amplamente utilizado nos campos de simulação e modulação. Os defeitos encontrados pelos usuários foram corrigidos pelos inventores. O MT foi atualizado, para usar e ser compatível com as novas tecnologias emergentes de CPUs, como SIMD e pipelines paralelos em sua versão do SFMT.