ベルヌーイ過程

確率と統計において、ベルヌーイ過程（ベルヌーイじゅう、Jacob Bernoulliにちなんで名付けられた）は、有限または無限のバイナリランダム変数の列であり、通常は 0 と 1 の 2 つの値のみを取る離散時間確率過程である。成分ベルヌーイ変数 X _{i は}同一分布に従い、独立している。平凡に言えば、ベルヌーイ過程はコイン投げの繰り返しであり、コインが不公平である可能性もある（ただし、一貫して不公平である）。列内のすべての変数X _{i は}、ベルヌーイ試行または実験に関連付けられている。それらはすべて同じベルヌーイ分布を持つ。ベルヌーイ過程について言えることの多くは、3 つ以上の結果（6 面サイコロの過程など）に一般化することもできます。この一般化はベルヌーイ方式として知られています。

ベルヌーイ試行の限られたサンプルのみを与えられた場合にプロセスを決定する問題は、コインが公正であるかどうかを確認する問題と呼ぶことができます。

ベルヌーイ過程は、独立した 確率変数 X ₁、  X ₂、  X ₃、... の有限または無限の列であり、

• 各iについて、 X _iの値は0 または 1 のいずれかです。
• のすべての値に対して、 X _i = 1となる確率p は 同じです。${\textstyle i}$

言い換えれば、ベルヌーイ過程は、独立した同一分布の ベルヌーイ試行のシーケンスです。

試行の独立性は、プロセスが記憶なしであることを意味します。確率pが既知である場合、過去の結果は将来の結果に関する情報を提供しません。（ただし、 pが不明な場合は、過去はpについての推論を通じて間接的に将来に関する情報を提供します 。）

プロセスが無限である場合、どの時点からでも将来の試行はプロセス全体と同一のベルヌーイ過程、つまりフレッシュスタート特性を構成します。

各X _iの 2 つの可能な値は、多くの場合「成功」と「失敗」と呼ばれます。したがって、数値 0 または 1 として表現される場合、結果はi番目の「試行」での成功の数と呼ばれることがあります。

値のその他の一般的な解釈は、真か偽か、はいかいいえです。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つの実験は、ベルヌーイ分布としてモデル化できます。^[1]ベルヌーイ分布以外にも、ベルヌーイ過程から いくつかのランダム変数と確率分布を導き出すことができます。

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

負の二項変数はランダムな待ち時間として解釈される可能性があります。

ベルヌーイ過程は、確率空間の言語で、表か裏の値を取るランダム変数の独立した実現のランダムなシーケンスとして形式化できます。個々の値の状態空間は次のように表されます。${\displaystyle 2=\{H,T\}.}$

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

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

${\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)^{n-k}}$

ここでkはHが数列に現れる回数、 n − kはTが数列に現れる回数である。上記の表記にはいくつかの種類があるが、一般的な表記は

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

ここで、それぞれはアイバーソン括弧表記の2値のランダム変数であり、の場合またはの場合のいずれかを意味します。この確率は一般にベルヌーイ測度と呼ばれます。^[2]${\displaystyle X_{i}}$${\displaystyle x_{i}=[\omega _{i}=H]}$${\displaystyle 1}$${\displaystyle \omega _{i}=H}$${\displaystyle 0}$${\displaystyle \omega _{i}=T}$${\displaystyle P}$

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

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

が で表され、が で表される標準過程を仮定します。大数の法則によれば、数列の平均、すなわちはほぼ確実に期待値に近づきます。つまり、この限界を満たさないイベントの確率はゼロです。表が出ることの期待値は1 で表されると仮定すると、 で与えられます。実際、 ${\displaystyle H}$${\displaystyle 1}$${\displaystyle T}$${\displaystyle 0}$${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$${\displaystyle p}$

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,}$

ベルヌーイ過程を構成する ベルヌーイ試行の無限シーケンスから任意のランダム変数を選択します。${\displaystyle X_{i}}$

コインをn回投げた時にHがどのくらいの頻度で現れるか知りたいという人は多い。これは単純に数えるだけでわかる。n回連続してコインを投げた場合、つまり長さnのあらゆる文字列の集合が与えられた場合、 Hがk回出現する文字列の数N ( k , n )は二項係数で与えられる。

${\displaystyle N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}}$

表が出る確率がpで与えられるとすると、長さnの文字列でk回表 が出る確率は

${\displaystyle \mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{n-k},}$

ここで 、このように定義された確率測度は二項分布として知られています。 ${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$

上記の式からわかるように、n=1 の場合、二項分布はベルヌーイ分布に変わります。したがって、 n が 1 の場合、 ベルヌーイ分布はまさに二項分布の特殊なケースであることがわかります。

特に興味深いのは、十分に長いコイン投げのシーケンス、つまり極限 に対するの値の問題です。この場合、階乗に対するスターリングの近似を利用して、次のように書く ことができます。${\displaystyle S_{n}}$${\displaystyle n\to \infty }$

${\displaystyle n!={\sqrt {2\pi n}}\;n^{n}e^{-n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)}$

これをP ( k , n )の式に代入すると正規分布が得られます。これが中心極限定理の内容であり、これはその最も単純な例です。

大数の法則と中心極限定理を組み合わせると、興味深く、おそらくは意外な結果が導かれます。それが漸近的等分配法則です。簡単に言えば、コインを何回も投げると、Hがちょうどp分の数だけ観測され、これがガウス分布のピークと正確に一致することがわかります。漸近的等分配法則は、基本的に、このピークが限りなく鋭く、その両側に限りなく低下することを示しています。つまり、ベルヌーイ過程で発生するHとTのすべての可能な無限長の文字列の集合が与えられた場合、この集合は 2 つに分割されます。確率 1 で発生する文字列と、確率 0 で発生する文字列です。この分割はコルモゴロフの 0-1 法則として知られています。

この集合の大きさも興味深いもので、明示的に決定できます。その対数はベルヌーイ過程のエントロピーとまったく同じです。もう一度、長さnのすべての文字列の集合を考えてみましょう。この集合の大きさはです。これらのうち、特定のサブセットのみが存在する可能性があります。この集合の大きさは です。スターリング近似を使用して、それをP ( k , n ) の式に代入し、ピークの位置と幅を解き、最後に を取ると、次の式が得られます。 ${\displaystyle 2^{n}}$${\displaystyle 2^{nH}}$${\displaystyle H\leq 1}$${\displaystyle n\to \infty }$

${\displaystyle H=-p\log _{2}p-(1-p)\log _{2}(1-p)}$

この値は、ベルヌーイ過程のベルヌーイエントロピーです。ここで、 H はエントロピーを表します。表を表す同じ記号Hと混同しないでください。

ジョン・フォン・ノイマンは、ベルヌーイ過程について、ある過程が別の過程と同型である可能性、つまり動的システムの同型性という可能性について疑問を提起した。この疑問は長い間分析できなかったが、最終的にオルンシュタインの同型定理によって完全に答えられた。この画期的な発見により、ベルヌーイ過程は唯一かつ普遍的であることが理解されるに至った。ある意味では、ベルヌーイ過程は考えられる最もランダムな過程であり、ベルヌーイ過程より「より」ランダムなものはない (ただし、この非公式な発言には注意が必要である。確かに、混合しているシステムは、ある意味では、単にエルゴード的であって混合ではないベルヌーイ過程よりも「強い」。しかし、そのようなプロセスは独立したランダム変数で構成されていない。実際、多くの純粋に決定論的でランダムでないシステムは混合している可能性がある)。

ベルヌーイ過程は、エルゴード系の例として、特に測度保存力学系として、いくつかの異なる方法のうちの1つとして、力学系として理解することもできます。1つの方法はシフト空間としてであり、もう1つはオドメーターとしてです。これらについては以下で説明します。

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

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

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

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

この写像は線形演算子であり、これは (明らかに)関数と定数に対してとが存在するのと同様です。この線形演算子は転送演算子またはルエル・フロベニウス・ペロン演算子と呼ばれます。この演算子にはスペクトル、つまり固有関数とそれに対応する固有値の集合があります。最大の固有値はフロベニウス・ペロン固有値であり、この場合は 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}$${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

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

上記はより正確に表現できる。2進数の無限の文字列が与えられた場合、 ${\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}}.}$${\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 を追加」し、オドメーターがロールオーバーするときにキャリー ビットを使用してオドメーターを「ロールオーバー」させます。これは、無限の文字列のセットに対する 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}$

ベルヌーイ列という用語は、ベルヌーイ過程の 実現を指すために非公式によく使用されます。ただし、この用語には、以下に示すように、まったく異なる正式な定義があります。

ベルヌーイ過程が単一の確率変数として正式に定義されていると仮定する（前のセクションを参照）。コイン投げの無限シーケンスxごとに、整数 シーケンスが存在する。

${\displaystyle \mathbb {Z} ^{x}=\{n\in \mathbb {Z} :X_{n}(x)=1\}\,}$

ベルヌーイ過程に関連付けられたベルヌーイ列^{[検証が必要]}と呼ばれます。たとえば、x がコイン投げの列を表す場合、関連付けられたベルヌーイ列は、コイン投げの結果が表になる自然数または時点のリストです。

このように定義すると、ベルヌーイ数列はインデックス セット、つまり自然数のランダムなサブセットでもあります。 ${\displaystyle \mathbb {Z} ^{x}}$${\displaystyle \mathbb {N} }$

ほとんどすべてのベルヌーイ数列はエルゴード数列です。^{[検証が必要]}${\displaystyle \mathbb {Z} ^{x}}$

任意のベルヌーイ過程から、実際に均一なランダム性を抽出する最も初期のランダム性抽出器であるフォン・ノイマン抽出器によって、 p  = 1/2のベルヌーイ過程を導出することができます。

観察されるプロセスを0と1のシーケンス、つまりビットとして表し、その入力ストリームを(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 になります)。

フォン・ノイマン（古典的）メイン演算疑似コード:

（ビット1 ≠ ビット2）の場合{
   出力(ビット1)
}

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

^{フォン ノイマン アルゴリズムの反復バージョンは、アドバンスト マルチレベル ストラテジー (AMLS) [6]}とも呼ばれ、1992 年に Yuval Peres によって導入されました。^[5]これは再帰的に動作し、2 つのソース (破棄-非破棄のシーケンスと、破棄されたペアの値 (00 の場合は 0、11 の場合は 1) から「無駄なランダム性」をリサイクルします。これは、すでに生成されたシーケンスを考えると、これらのソースの両方がまだ交換可能なビット シーケンスであり、次の抽出ラウンドに適格であるという事実に依存しています。このような追加シーケンスの生成は、利用可能なすべてのエントロピーを抽出するために無限に反復できますが、無限の量の計算リソースが必要になるため、反復回数は通常、低い値に固定されます。この値は事前に固定されているか、実行時に計算されます。

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

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

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

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

フォン・ノイマン・ペレス（反復）主演算疑似コード:

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

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

• Carl W. Helstrom, Probability and Stochastic Processes for Engineers、(1984) Macmillan Publishing Company、ニューヨークISBN 0-02-353560-1。 

• ベルヌーイ過程を記述するための二分木図の使用