ファンデルコルプト数列

0から1の単位区間（横軸）を充填していく、最初n項のファンデルコルプト数列（上から順にnが 0 から 999 へと増加し、色が濃くなっている。

ファンデルコルプト数列（van der Corput sequence）は、単位区間に対する超一様分布列（準乱数列）の1つであり、1935年にオランダの数学者ヨハネ・ファン・デル・コルプトによって考案された。この数列は自然数のn進表記を逆順にしたものを小数点以下に並べたものである。

自然数nのb-進表記は、

$n=\sum _{k=0}^{L-1}d_{k}(n)b^{k}$

であり、k桁目のd_kは0 ≤ d_k(n) < bを満たす。 このとき、ファンデルコルプト数列のn項目であるg_b(n)は

$g_{b}(n)=\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}$

である。

例

例えば、10進のファンデルコルプト数列を得るためには、まず 1 から 9 を10で割ったものを並べる (x/10)。そして、分母を100として、分子に 10 から 99 を並べる。しかしここで、10 からそのまま並べるのではなく、01, 11, 21, 31, 41, 51, 61, 71, 81, 91 ... というように、10の位と1の位を入れ替えて並べる。そして、20以降は分子が2で終わる数字が続き、 02, 12, 22, 32, 42, 52, 62, 72, 82, 92、更に 03, 13, 23 ... と続く。

そのため、ファンデルコルプト数列（10進）は

$\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.22, 0.32, …

となる。

2進法でも同様であり、2進ファンデルコルプト数列は

${\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$

または

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

と続く。

任意の底において、ファンデルコルプト数列は単位区間での稠密集合となる。つまり、[0, 1]内の任意の実数に対して、その実数に収束するファンデルコルプト数列の部分列が存在する。また、単位区間で一様である。

C での実装

double corput(int n, int base){
  double q = 0;
  double bk = 1.0 / base;
  while (n > 0) {
    q += (n % base) * bk;
    n /= base;
    bk /= base;
  }
  return q;
}

関連項目

• ビット反転順
• ハルトン数列：高次元へのファンデルコルプト数列の拡張
• モンテカルロ法：準モンテカルロ法により、収束が早い場合がある

参考文献

• van der Corput, J.G. (1935), “Verteilungsfunktionen (Erste Mitteilung)” (German), Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam 38: 813–821, Zbl 0012.34705, http://www.dwc.knaw.nl/DL/publications/PU00014607.pdf 
• Kuipers, L.; Niederreiter, H. (2005) [1974], Uniform distribution of sequences, Dover Publications, p. 129,158, ISBN 0-486-45019-8, Zbl 0281.10001 

外部リンク

• Van der Corput sequence at MathWorld