Teste Espectral (estatística)

Gráfico tridimensional de 100.000 valores gerados com RANDU . Cada ponto representa 3 valores pseudoaleatórios consecutivos. É claramente visto que os pontos estão em 15 planos bidimensionais .

O teste espectral é um teste estatístico para verificação da qualidade das classes de geradores de números pseudoaleatórios (PRNGs), os geradores congruenciais lineares (LCGs). Os LCGs têm uma propriedade que, quando plotados em 2 ou mais dimensões, formam linhas ou hiperplanos, nos quais todas as saídas possíveis podem ser encontradas. O teste espectral compara a distância entre esses planos; quanto mais distantes eles estiverem, pior será o gerador. Como este teste foi desenvolvido para estudar as estruturas reticulares de LCGs, ele não pode ser aplicado a outras famílias de PRNGs.

De acordo com Donald Knuth, this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDU

o LCG falha neste teste para valores maiores que 3 dimensões.

O primeiro passo é a geração de uma sequência $u_1,u_2,\dots$ utilizando-se o PRNG escolhido. Seja $1/{\nu }_t$ a separação máxima entre os planos paralelos de cobertura da sequência $\{(u_{n+1:n+t})\mid n=0,1,\dots \}$ . O teste espectral verifica se a sequência ${\nu }_2,{\nu }_3,{\nu }_4,\dots$ não se degrada muito rapidamente.

Knuth aconselha verificar se cada um dos 5 números a seguir é > 0,01. $$\begin{array}{cccccc}{\mu }_2& =\pi {\nu }_2^2/m,& {\mu }_3& =\frac{4}{3}\pi {\nu }_3^3/m,& {\mu }_4& =\frac{1}{2}{\pi }^2{\nu }_4^4/m,\\ & & {\mu }_5& =\frac{8}{15}{\pi }^2{\nu }_5^5/m,& {\mu }_6& =\frac{1}{6}{\pi }^3{\nu }_6^6/m,\end{array}$$ onde $m$ é o módulo do LCG.

Números de mérito

Knuth define um número de mérito, que é um valor que descreve quão próxima é a separação $1/{\nu }_t$ do mínimo teórico. Sob a re-notação de Steele & Vigna, para a dimensão $d$, a figura $f_d$ é definida comoPredefinição:Rp$$f_d(m,a)={\nu }_d/\left({\gamma }_d^{1/2}\sqrt[d]{m}\right),$$ onde $a,m,{\nu }_d$ são definidos como antes, e ${\gamma }_d$ é a constante de Hermite de dimensão d . ${\gamma }_d^{1/2}\sqrt[d]{m}$ é a menor separação interplanar possível. Predefinição:Rp

L'Ecuyer (1991) introduziu ainda duas métricas correspondendo ao mínimo de $f_d$ em várias dimensões. Novamente sob re-notação, ${ℳ}_d^{+}(m,a)$ é o mínimo $f_d$ para um LCG de dimensões 2 a $d$, e ${ℳ}_d^{*}(m,a)$ é o mesmo para um gerador de números pseudoaleatórios congruentes multiplicativos (MCG), ou seja, um onde apenas a multiplicação é usada, ou que $c=0$ . Steele e Vigna observam que o $f_d$ é calculado de forma diferente nestes dois casos, necessitando de valores separados. Predefinição:RpEles definem ainda uma média ponderada de mérito “harmônica”, ${\mathscr{H}}_d^{+}(m,a)$ (e ${\mathscr{H}}_d^{*}(m,a)$ ). Predefinição:Rp

Exemplos

Uma pequena variante do algoritmo RANDU, com $x_{n+1}=65539x_n{mod2}^{29}$ tem: Predefinição:Rp

d	2	3	4	5	6	7	8
νPredefinição:Su	536936458	118	116	116	116
μd​	3.14	10 −5	10 −4	10 −3	0,02
fdPredefinição:Nre	0,520224	0,018902	0,084143	0,207185	0,368841	0,552205	0,578329

Os números agregados de mérito são: ${ℳ}_8^{*}(65539,2^{29})=0.018902$, ${\mathscr{H}}_8^{*}(65539,2^{29})=0.330886$.Predefinição:Nre

George Marsaglia (1972) considerava $x_{n+1}=69069x_n{mod2}^{32}$ como "um candidato ao melhor de todos os multiplicadores" porque é fácil de lembrar e tem números de teste espectrais particularmente grandes.

d	2	3	4	5	6	7	8
ν Predefinição:Su	4243209856	2072544	52804	6990	242
μdPredefinição:Nre	3.10	2,91	3.20	5.01	0,017
fdPredefinição:Nre	0,462490	0,313127	0,457183	0,552916	0,376706	0,496687	0,685247

Os números agregados de mérito são: ${ℳ}_8^{*}(69069,2^{32})=0.313127$, ${\mathscr{H}}_8^{*}(69069,2^{32})=0.449578$.Predefinição:Nre

Steele & Vigna (2020) fornecem os multiplicadores com os maiores números agregados de mérito para muitas escolhas de m = 2ⁿ e um determinado comprimento de bit de a . Eles também fornecem os valores $f_d$ e um pacote de software para calcular esses valores. Predefinição:Rp Por exemplo, eles relatam que o melhor a de 17 bits para m = 2³² é:

• Para um LCG (c ≠ 0), (121525). ${ℳ}_8^{+}=0.6403$, ${\mathscr{H}}_8^{+}=0.6588$. Predefinição:Rp
• Para um MCG (c = 0), (125229). ${ℳ}_8^{*}=0.6623$, ${\mathscr{H}}_8^{*}=0.7497$. Predefinição:Rp

Leitura adicional

• Predefinição:Citar periódico – lista $f_d$ (anotado como $S_s$ neste texto) de muitos LCGs conhecidos
  • Uma versão expandida desse trabalho está disponível como: Predefinição:Citar web"A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version".