正規数
本記事では数学のみならず計算機科学の用語および記号も用いる。Σ を r 個の文字の集合(アルファベット)とする。Σ で Σ の元からなる無限列全体の集合を、Σ で有限列全体の集合を表すものとする。これらの集合の元は文字列 (string) とみなす。自然数(本記事では 1 以上の整数を意味する)n、Σ の元 S、Σ の元 w に対し、NS ( w, n ) で「S の最初の n 個の列に w が現れる回数」を表すものとする。例えば、S = 01010101... に対して NS ( 010, 8 ) = 3 である。
Σ の元 S が正規であるとは、任意の Σ の元 w に対し、
lim n → ∞ N S ( w , n ) n = 1 r | w | {\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{r^{|w|}}}}
が成り立つことを言う(ここに、|w| は w の長さを意味する)。言い換えると、長さが同じ文字列たちが漸近的に同じ頻度で現れる場合にその無限列を正規と呼ぶのである。例えば、二進列(0, 1 の列)が正規であるとは、0 と 1 が 1/2 ずつの頻度で現れ、00, 01, 10, 11 が 1/4 ずつの頻度で現れ、000, 001, 010, 011, 100, 101, 110, 111 が 1/8 ずつの頻度で現れ...(以下同様に続く)ということを意味する。
Agafonov (1968) は有限オートマトンと正規列との関係を指摘した。正規列からある正則言語によって得る部分列はまた正規列である。言い換えると、正規列を有限オートマトンに入力し、受理状態のときのみ入力した文字をそのまま出力することにすれば、そうして出力される部分列はまた正規である。
以下の二つの事実が示すように、正規列と有限オートマトンとの間にはより深い関係がある。
有限状態ギャンブラー(finite-state gambler または finite-state martingale、以下 FSG)とは、有限アルファベット Σ 上の有限オートマトンの状態に応じて文字たち(Σ の各元)に金を賭けるギャンブラーのモデルのことである。例えばバイナリアルファベット Σ = { 0, 1 } 上の FSG は、現在の状態 q に対して定められた割合 q0 (0 ≤ q0 ≤ 1), q1 (= 1 - q0) に従い、ギャンブラーは持ち金の q0 倍を 0 に賭け、残りを 1 に賭ける。それから文字が入力され、その文字に賭けられた金の2倍(一般には |Σ| 倍)が次の賭けの元手となる。入力された文字に従い、有限オートマトンの状態が移り、ギャンブラーの賭け方が変わる。ある FSG d が無限列 S に対して成功するとは、有限の元手から始めていつかは任意の目標額に到達すること、すなわち
lim sup n → ∞ d ( S ↾ n ) = ∞ {\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty }
数学における正規数(、英: normal number)とは、実数のうち、その小数部の数字が一様に分布し、数字の列が現れる頻度に偏りがないものをいう(より詳細な定義については #定義 を参照)。
r 進法での表示についてこの性質を持つ数を r 進正規数という。単に正規数と述べた場合は、2 以上の任意の整数 r に対して r 進正規数であることを意味する。
一般論としてほとんど全ての実数が正規数であることが知られているが、その証明は構成的(英語版)でないため、正規数であることが判明している具体的な数は非常に限られている。例えば、2の平方根、円周率、ネイピア数はそれぞれ正規数だと予想されているが、その通りか否かは未だ知られていない。
さらに直感的に言い換えるならば、S のある位置に w が現れる「確率」が、乱数列のそれと一致するということである。(乱数列であるためには正規列であることが望まれるが、正規列であれば必ず乱数列とみなせるかというと必ずしもそうではない。)
以降は r を 2 以上の整数とし、x を実数とする。x を r 進法で無限小数表示したときの小数点以降の文字列(この場合は数字の列)が正規であるとき、x は r 進正規数、もしくは基数 r に関して正規数であるという。x が任意の r に対して r 進正規数であるとき、x を単に正規数と呼ぶ。
当然、無限列は正規か正規でないかのいずれかである。一方、実数については、ある r に対しては r 進正規であるのに、別の s に対しては s 進正規ではない、ということがあり得る (Cassels, 1959)。任意の r 進正規数が s 進正規数でもあるためには log r /log s が有理数であることが必要十分である (Schmidt, 1960)。
定義より明らかなように、正規数の無限小数表示の中には任意の文字列が現れる。デジタルデータを二進数だとみなせば、二進正規数にはあらゆるデータが含まれると考えることができる。しかし、逆は成り立たず、任意の文字列が現れるからといって正規とは限らない。
正規より弱い概念として、単正規 (simply normal) がある。それは |w| = 1 の場合のみ上記の性質を満たすことを意味する。すなわち r 進単正規数とは、r 進小数表示において各数字が 1/r の割合で現れる実数のことである。