ベルヌーイ過程

各X _iの 2 つの可能な値は、「成功」と「失敗」と呼ばれることが多い。したがって、0 または 1 という数値で表すと、結果はi番目の「試行」における成功回数と呼ばれることがある。

これらの値の一般的な解釈としては、真偽とはい/いいえの2つがあります。これらの2つの値のいずれの解釈においても、個々の変数X _{i は、}パラメータ p を持つベルヌーイ試行と呼ぶことができます。

多くのアプリケーションでは、インデックス i が増加するにつれて、試行の間に時間が経過します。実際には、試行X ₁、X ₂、... X _i、... は「時点」 1、2、...、i、... で発生します。しかし、時間の経過とそれに伴う「過去」と「未来」の概念は必ずしも必要ではありません。最も一般的には、プロセス内の任意のX _iとX _jは、有限ケースの場合は {1、 2、...、n }、無限ケースの場合は {1、2、3、 ...}でインデックス付けされたランダム変数の集合から単に 2 つ選ばれたものです。              

結果が「成功」と「失敗」の2つしかない実験（通常は1と0で表される）は、ベルヌーイ分布としてモデル化できる。^{[ 1 ]}ベルヌーイ過程からは、ベルヌーイ分布以外にもいくつかの確率変数と確率分布を導出できる。

• 最初のn回の試行における成功回数は、二項分布B( n , p )に従います。 
• r 回の成功を得るために必要な失敗の回数は、負の二項分布NB( r , p )に従います。 
• 1回の成功を得るために必要な失敗の回数は、負の二項分布の特殊なケースである幾何分布NB(1, p )に従います。 

負の二項分布に従う変数は、ランダムな待ち時間として解釈できる。

コピーの可算無限直積を考える${\displaystyle 2=\{H,T\}}$片側集合を調べるのが一般的です${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$または両面セット${\displaystyle \Omega =2^{\mathbb {Z} }}$この空間には、積位相と呼ばれる自然な位相が存在します。この位相における集合は、コイン投げの有限列、すなわち、HとT（Hは表、Tは裏を表す）の有限長の文字列であり、残りの（無限長の）列は「気にしない」とみなされます。これらの有限列の集合は、積位相において円筒集合と呼ばれます。このような文字列の集合は、シグマ代数、具体的にはボレル代数を形成します。この代数は、一般的に次のように表記されます。${\displaystyle (\Omega ,{\mathcal {B}})}$要素が$\displaystyle {\mathcal {B}}}$これらは有限長のコイン投げのシーケンス（シリンダーセット）である。

表か裏が出る確率が確率で与えられる場合${\displaystyle \{p,1-p\}}$すると、積空間上に自然な測度を定義することができ、それは次のように表される。${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$（または${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$（両側プロセスの場合）。言い換えれば、離散確率変数X がパラメータpのベルヌーイ分布に従う場合（ただし 0 ≤ p ≤ 1）、その確率質量関数は次のように与えられる。

${\displaystyle pX(1)=P(X=1)=p}$そして${\displaystyle pX(0)=P(X=0)=1-p}$。

この分布を Ber( p )と表記する。^{[ 1 ]}

円筒セット、つまり特定のコイン投げの結果のシーケンスが与えられた場合${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$時々${\displaystyle 1,2,\cdots ,n}$この特定のシーケンスを観測する確率は次のように与えられる。

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{nk}}$

ここで、 kは数列中にHが現れる回数、n − kは数列中にTが現れる回数である。上記にはいくつかの異なる表記法があるが、一般的な表記法は次のように書く。

${\displaystyle P(X_{1}=x_{1},X_{2}=x_{2},\cdots ,X_{n}=x_{n})=p^{k}(1-p)^{nk}}$

それぞれ${\displaystyle X_{i}}$は、二値確率変数であり、${\displaystyle x_{i}=[\omega _{i}=H]}$アイバーソンのブラケット表記では、${\displaystyle 1}$もし${\displaystyle \omega _{i}=H}$または${\displaystyle 0}$もし${\displaystyle \omega _{i}=T}$この確率${\displaystyle P}$これは一般にベルヌーイ測度と呼ばれている。^{[ 2 ]}

任意の特定の無限に長いコイン投げのシーケンスの確率は正確にゼロであることに注意してください。これは、${\displaystyle \lim _{n\to \infty }p^{n}=0}$どのような場合でも${\displaystyle 0\leq p<1}$確率が 1 に等しいということは、任意の無限列の測度がゼロであることを意味します。しかしながら、コイン投げの無限列の中には、他のものよりもはるかに起こりやすいものがあると言えます。これは漸近等分割性によって与えられます。

正式な定義を締めくくると、ベルヌーイ過程は確率の三つ組によって与えられる。${\displaystyle (\Omega ,{\mathcal {B}},P)}$上記で定義したとおり。

ベルヌーイ過程から動的システムを構築する一つの方法は、シフト空間として扱うことである。積空間には自然な並進対称性がある。$\displaystyle \Omega =2^{\mathbb {N} }}$シフト演算子によって与えられる

${\displaystyle T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )}$

上で定義したベルヌーイ測度は並進不変である。つまり、任意の円筒集合が与えられた場合、$\displaystyle \sigma \in {\mathcal {B}}$1つは

${\displaystyle P(T^{-1}(\sigma ))=P(\sigma )}$

したがって、ベルヌーイ測度はハール測度であり、積空間上の不変測度である。

確率測度の代わりに${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$代わりに任意の関数を考えてみましょう${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$前進​

${\displaystyle f\circ T^{-1}}$

定義される${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$これもまた何らかの関数です$\displaystyle {\mathcal {B}}\to \mathbb {R} .}$したがって、地図${\displaystyle T}$別のマップを誘導する$\displaystyle {\mathcal {L}}_{T}}$すべての関数の空間において$\displaystyle {\mathcal {B}}\to \mathbb {R} .}$つまり、いくつかの${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$定義する

$\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

地図$\displaystyle {\mathcal {L}}_{T}}$は線形演算子であり、（明らかに）${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$そして${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$関数について${\displaystyle f,g}$そして絶え間ない${\displaystyle a}$この線形演算子は、転送演算子またはリュエル・フロベニウス・ペロン演算子と呼ばれます。この演算子はスペクトル、つまり固有関数とそれに対応する固有値の集合を持ちます。最大の固有値はフロベニウス・ペロン固有値であり、この場合は 1 です。関連する固有ベクトルは不変測度であり、この場合はベルヌーイ測度です。つまり、$\displaystyle {\mathcal {L}}_{T}(P)=P.}$

制限する場合$\displaystyle {\mathcal {L}}_{T}}$多項式に作用すると、固有関数は（不思議なことに）ベルヌーイ多項式になります！^{[ 3 ] [ 4 ]} この命名の一致は、おそらくベルヌーイには知られていなかったでしょう。

上記はより正確に表現できます。無限に続くバイナリ数字列が与えられた場合${\displaystyle b_{0},b_{1},\cdots }$書く

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

結果として${\displaystyle y}$は単位区間内の実数である${\displaystyle 0\leq y\leq 1.}$シフト${\displaystyle T}$準同型を誘導する、${\displaystyle T}$単位区間において。${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$分かるように${\displaystyle T(y)=2y{\bmod {1}}.}$ このマップは、2 倍無限ビット列に対して、2 進変換と呼ばれます。${\displaystyle \Omega =2^{\mathbb {Z} },}$誘導される準同型写像はベイカーの写像である。

次に、関数空間を考えてみましょう。${\displaystyle y}$. いくつかの${\displaystyle f(y)}$次のようなことがわかる

${\displaystyle \left[{\mathcal {L}}_{T}f\right](y)={\frac {1}{2}}f\left({\frac {y}{2}}\right)+{\frac {1}{2}}f\left({\frac {y+1}{2}}\right)}$

オペレーターの行動を制限する${\displaystyle {\mathcal {L}}_{T}}$多項式上の関数については、離散スペクトルが次のように与えられることがわかる。

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

どこで${\displaystyle B_{n}}$はベルヌーイ多項式である。実際、ベルヌーイ多項式は次の恒等式を満たす。

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

合計に注意してください

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

これは、慣習的に定義されたカントール関数を与えます。これが、この集合が である理由の 1 つです。${\displaystyle \{H,T\}^{\mathbb {N} }}$これはカントール集合と呼ばれることもあります。

動的システムを作成するもう 1 つの方法は、オドメーターを定義することです。非公式には、これは文字通り、最初の位置に「1」を加え、オドメーターがオーバーフローしたときにキャリービットを使用してオドメーターを「オーバーフロー」させるだけです。これは、無限文字列の集合に対する 2 進数の加算に他なりません。加算は群を形成し、ベルヌーイ過程は既に上で位相を与えられているので、これは位相群の簡単な例となります。

この場合、変換${\displaystyle T}$は

${\displaystyle T\left(1,\dots ,1,0,X_{k+1},X_{k+2},\dots \right)=\left(0,\dots ,0,1,X_{k+1},X_{k+2},\dots \right).}$

これは、ベルヌーイ測度を不変にするのは、${\displaystyle p=1/2}$（「公正なコイン」）そうでなければそうではない。したがって、${\displaystyle T}$この場合は尺度保存力学系であり、そうでない場合は単なる保存系である。

観測されたプロセスをゼロとイチ、つまりビットのシーケンスとして表現し、その入力ストリームを (11)(00)(10)... のように重複しない連続するビットのペアにグループ化します。次に、各ペアについて、

• ビットが等しい場合は破棄する。
• ビットが等しくない場合は、最初のビットを出力する。

この表は計算結果をまとめたものです。

例えば、8ビットの入力ストリーム10011011は、(10)(01)(10)(11)のようにペアにグループ化されます。次に、上記の表に従って、これらのペアはプロシージャの出力(1)(0)(1)() (= 101 )に変換されます 。

出力ストリームでは、0と1が等しい確率で出現します。これは、元のストリームで10と01が等しい確率で出現するのと同様で、どちらも確率はp (1− p )  =  (1− p ) pです。この均一なランダム性の抽出では、入力試行が独立している必要はなく、無相関であれば十分です。より一般的には、交換可能な任意のビット列に適用できます。つまり、有限の並べ替えであるすべてのシーケンスは等しい確率で出現します。

フォン・ノイマン抽出器は、2つの入力ビットを使用して0または1の出力ビットを生成するため、出力は入力よりも少なくとも 2倍短くなります。平均して、この計算では入力ペア(00と11)のp ²  +  (1  − p ) ^{2の割合が破棄されます。これは、} pが0または1に近い場合に1に近くなり、元のプロセスでp = 1/2の場合に1/4で最小になります（この場合、出力ストリームは平均して入力ストリームの1/4の長さになります）。   

フォン・ノイマン（古典的）主操作の擬似コード：

if (Bit1 ≠ Bit2) { 出力（ビット1） } 

入力ストリームに存在するランダム性のこの効率低下、つまり無駄は、入力データに対してアルゴリズムを反復することで軽減できます。このようにして、出力を「エントロピーの限界に任意に近づける」ことができます。^{[ 5 ]}

フォン・ノイマン・アルゴリズムの反復バージョンは、高度多段階戦略 (AMLS) ^{[ 6 ]}としても知られ、 1992 年に Yuval Peres によって導入されました。^{[ 5 ]}これは再帰的に動作し、破棄と非破棄のシーケンスと破棄されたペアの値 (0 の場合は 0、11 の場合は 1) という 2 つのソースから「無駄なランダム性」を再利用します。既に生成されたシーケンスが与えられた場合、これらのソースはどちらも交換可能なビットのシーケンスであり、したがって別の抽出ラウンドの対象となるという事実に依存しています。このような追加のシーケンスの生成は、利用可能なすべてのエントロピーを抽出するために無限に反復できますが、無限の計算リソースが必要となるため、反復回数は通常、低い値に固定されます。この値は、事前に固定するか、実行時に計算されます。

より具体的には、入力シーケンスに対して、アルゴリズムは入力ビットをペアで消費し、出力とともに2つの新しいシーケンスを生成します。（）はAMLS論文表記です。

（入力の長さが奇数の場合、最後のビットは完全に破棄されます。）その後、入力が空になるまで、このアルゴリズムが2つの新しいシーケンスそれぞれに再帰的に適用されます。

例：AMLS論文からの入力ストリーム11001011101110（Hには1、Tには0を使用）は、次のように処理されます。

ステップ 1 から始め、入力は前のステップのシーケンス 2 とシーケンス 1 の連結です (順序は任意ですが、固定する必要があります)。最終出力は()()(1)()(1)()(1)(1)()()(0)(0)()(0)(1)(1)()(1) (= 1111000111 ) なので、14 ビットの入力から 10 ビットの出力が生成されますが、フォン ノイマン アルゴリズムのみでは 3 ビットしか生成されません。1 ビット ペアあたり 1 ラウンドあたり正確に 2 ビットの固定出力 (古典的な VN では 0 ビットから 1 ビットまで可変) により、タイミング攻撃に耐性のある定数時間実装も可能です。

フォン・ノイマン＝ペレス（反復）主操作の擬似コード：

if (Bit1 ≠ Bit2) { 出力(1, シーケンス1) 出力（ビット1） } それ以外 { 出力(0, シーケンス1) 出力(ビット1、シーケンス2) } 

2016年には、Sequence2チャネルはスループットがあまり高くないという観察に基づき、有限レベルのハードウェア実装では、Sequence1のより多くのレベルを処理するために、それを早期に破棄することでメリットが得られるという別の改良が提案された。^{[ 7 ]}