# Teste Espectral (estatística)

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{aligned}\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,\\[1ex]&&\mu _{5}&={\frac {8}{15}}\pi ^{2}\nu _{5}^{5}/m,&\mu _{6}&={\frac {1}{6}}\pi ^{3}\nu _{6}^{6}/m,\end{aligned}}$ 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 como$^{:3}$$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. $^{:3}$
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, ${\mathcal {M}}_{d}^{+}(m,a)$ é o mínimo $f_{d}$ para um LCG de dimensões 2 a $d$, e ${\mathcal {M}}_{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. $^{:13}$Eles definem ainda uma média ponderada de mérito “harmônica”, ${\mathcal {H}}_{d}^{+}(m,a)$ (e ${\mathcal {H}}_{d}^{*}(m,a)$ ). $^{:13}$

## Exemplos

Uma pequena variante do algoritmo RANDU, com $x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}$ tem: $^{(Tabela1)}$
| d | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ν2 d | 536936458 | 118 | 116 | 116 | 116 |
| μ$_{d​}$ | 3.14 | 10 $^{−5}$ | 10 $^{−4}$ | 10 $^{−3}$ | 0,02 |
| f$_d$ | 0,520224 | 0,018902 | 0,084143 | 0,207185 | 0,368841 | 0,552205 | 0,578329 |
Os números agregados de mérito são: ${\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902$, ${\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886$.
George Marsaglia (1972) considerava $x_{n+1}=69069\,x_{n}{\bmod {2}}^{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 |
| ν 2 d | 4243209856 | 2072544 | 52804 | 6990 | 242 |
| μ$_d$ | 3.10 | 2,91 | 3.20 | 5.01 | 0,017 |
| f$_d$ | 0,462490 | 0,313127 | 0,457183 | 0,552916 | 0,376706 | 0,496687 | 0,685247 |
Os números agregados de mérito são: ${\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127$, ${\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578$.
Steele & Vigna (2020) fornecem os multiplicadores com os maiores números agregados de mérito para muitas escolhas de m = 2$^n$ 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. $^{:14–5}$ Por exemplo, eles relatam que o melhor a de 17 bits para m = 2$^{32}$ é:
* Para um LCG (c ≠ 0), (121525). ${\mathcal {M}}_{8}^{+}=0.6403$, ${\mathcal {H}}_{8}^{+}=0.6588$. $^{:14}$
* Para um MCG (c = 0), (125229). ${\mathcal {M}}_{8}^{*}=0.6623$, ${\mathcal {H}}_{8}^{*}=0.7497$. $^{:14}$