Sequência de Van der Corput

Uma sequência de van der Corput é uma sequência de baixa discrepância no intervalo unitário, publicada em 1935 pelo matemático neerlandês Johannes van der Corput. Ela é construída pela inversão da representação na base n da sequência dos números naturais positivos (1, 2, 3, …). Por exemplo, para base 10, a sequência de van der Corput começa com:

0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, …

enquanto que, na base 2, a sequência de van der Corput começa com:

0.1₂, 0.01₂, 0.11₂, 0.001₂, 0.101₂, 0.011₂, 0.111₂, 0.0001₂, 0.1001₂, 0.0101₂, 0.1101₂, 0.0011₂, 0.1011₂, 0.0111₂, 0.1111₂, …

ou, equivalentemente:

{\frac {1}{2}},{\frac {1}{4}},{\frac {3}{4}},{\frac {1}{8}},{\frac {5}{8}},{\frac {3}{8}},{\frac {7}{8}},{\frac {1}{16}},{\frac {9}{16}},{\frac {5}{16}},{\frac {13}{16}},{\frac {3}{16}},{\frac {11}{16}},{\frac {7}{16}},{\frac {15}{16}},\ldots

Os elementos da sequência de van der Corput (em qualquer base) formam um conjunto denso no intervalo unitário; em particular, para todo número real r em [0, 1] existe uma subsequência da sequência de van der Corput que converge para r. Os números da sequência estão uniformemente distribuídos sobre o intervalo unitário.

Implementação

Na linguagem de programaçao R, a sequência de van der Corput para a base 2 é gerada por runif.halton(n, 1), como um caso particular da sequência de Halton.