Secuencia de Van der Corput

Secuencia unidimensional de baja discrepancia

Ilustración del llenado del intervalo unitario (eje horizontal) utilizando los primeros n términos de la secuencia decimal de Van der Corput, para n de 0 a 999 (eje vertical)

Una secuencia de van der Corput es un ejemplo de la secuencia unidimensional más simple con baja discrepancia en el intervalo unitario ; fue descrita por primera vez en 1935 por el matemático holandés JG van der Corput . Se construye invirtiendo la representación en base n de la secuencia de números naturales (1, 2, 3, …).

La representación -aria del entero positivo es donde es la base en la que se representa el número, y es decir, el -ésimo dígito en la expansión -aria de El -ésimo número en la secuencia de van der Corput es ${\displaystyle b}$ ${\displaystyle n\geq 1}$ $${\displaystyle n~=~\sum _{k=0}^{L-1}d_{k}(n)b^{k}~=~d_{0}(n)b^{0}+\cdots +d_{L-1}(n)b^{L-1},}$$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle 0\leq d_{k}(n)<b;}$ ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle n.}$ ${\displaystyle n}$ $${\displaystyle g_{b}(n)~=~\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}~=~d_{0}(n)b^{-1}+\cdots +d_{L-1}(n)b^{-L}.}$$

Ejemplos

Por ejemplo, para obtener la sucesión decimal de van der Corput, comenzamos dividiendo los números del 1 al 9 en décimas ( ), luego cambiamos el denominador a 100 para comenzar a dividir en centésimas ( ). En cuanto al numerador, comenzamos con todos los números de dos dígitos del 10 al 99, pero en orden inverso de dígitos. En consecuencia, obtendremos los numeradores agrupados por el dígito final. Primero, todos los numeradores de dos dígitos que terminan en 1, por lo que los siguientes numeradores son 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Luego los numeradores que terminan en 2, por lo que son 02, 12, 22, 32, 42, 52, 62, 72, 82, 92. Y después de eso, los numeradores que terminan en 3: 03, 13, 23 y así sucesivamente... ${\displaystyle x/10}$ ${\displaystyle x/100}$

Así, la secuencia comienza o en representación decimal: $${\displaystyle \left\{{\tfrac {1}{10}},{\tfrac {2}{10}},{\tfrac {3}{10}},{\tfrac {4}{10}},{\tfrac {5}{10}},{\tfrac {6}{10}},{\tfrac {7}{10}},{\tfrac {8}{10}},{\tfrac {9}{10}},{\tfrac {1}{100}},{\tfrac {11}{100}},{\tfrac {21}{100}},{\tfrac {31}{100}},{\tfrac {41}{100}},{\tfrac {51}{100}},{\tfrac {61}{100}},{\tfrac {71}{100}},{\tfrac {81}{100}},{\tfrac {91}{100}},{\tfrac {2}{100}},{\tfrac {12}{100}},{\tfrac {22}{100}},{\tfrac {32}{100}},\ldots \right\},}$$

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,32,…,

Se puede hacer lo mismo para el sistema de numeración binario , y la secuencia binaria de van der Corput es

0,1 ₂ , 0,01 ₂ , 0,11 ₂ , 0,001 ₂ , 0,101 2 , 0,011 2, 0,111 2 _, 0,0001 _{2 ,} 0,1001 _{2 ,} 0,0101 ₂ , 0,1101 ₂ , 0,0011 0 .1011 ₂ , 0.0111 ₂ , 0.1111 _{2 ,} …

o, equivalentemente, $${\displaystyle {\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {3}{4}},{\tfrac {1}{8}},{\tfrac {5}{8}},{\tfrac {3}{8}},{\tfrac {7}{8}},{\tfrac {1}{16}},{\tfrac {9}{16}},{\tfrac {5}{16}},{\tfrac {13}{16}},{\tfrac {3}{16}},{\tfrac {11}{16}},{\tfrac {7}{16}},{\tfrac {15}{16}},\ldots .}$$

Los elementos de la sucesión de van der Corput (en cualquier base) forman un conjunto denso en el intervalo unitario; es decir, para cualquier número real en , existe una subsucesión de la sucesión de van der Corput que converge a ese número. Además, están equidistribuidos en el intervalo unitario. ${\displaystyle [0,1]}$

Implementación en C

doble corput ( int n , int base ){ doble q = 0 , bk = ( doble ) 1 / base ;        mientras ( n > 0 ) { q += ( n % base ) * bk ; n /= base ; bk /= base ; }                 devolver q ; } 

Véase también

• Permutación de inversión de bits  : permutación que invierte los números binarios
• Construcciones de secuencias de baja discrepancia  – Tipo de secuencia matemáticaPáginas que muestran descripciones breves de los objetivos de redireccionamiento
• Secuencia de Halton  : tipo de secuencia numérica utilizada en estadística, una generalización natural de la secuencia de van der Corput a dimensiones superiores.

Referencias

• van der Corput, JG (1935), "Verteilungsfunktionen (Erste Mitteilung)" (PDF) , Actas de la Koninklijke Akademie van Wetenschappen te Amsterdam (en alemán), 38 : 813–821, Zbl  0012.34705
• Kuipers, L.; Niederreiter, H. (2005) [1974], Distribución uniforme de secuencias , Publicaciones de Dover , p. 129.158, ISBN 0-486-45019-8, Zbl0281.10001 ​

Enlaces externos

• Secuencia de Van der Corput en MathWorld