ランダム性の合併

抽出理論では、ランダムネス マージャーは、ランダム変数の集合からランダム性を抽出する関数です。ただし、そのうちの少なくとも 1 つは均一ランダムである必要があります。この名前は、均一ランダム変数に含まれるエントロピーの少なくとも一部を保持しながら、すべての変数を 1 つに「マージ」する手順として見ることができることから付けられました。現在、マージャーは、ランダムネス エクストラクタを明示的に構築するために使用されています。

ランダム変数の集合、を考えます。各変数は少なくとも 1 つの均一ランダムに分布していますが、どれが均一ランダムであるかはわかりません。さらに、変数は任意に相関している可能性があります。つまり、変数は互いの関数であったり、定数であったりするなどです。ただし、変数の少なくとも 1 つは均一であるため、集合全体には少なくともビットのエントロピーが含まれます。 ${\displaystyle k}$ ${\displaystyle X_{1},\ldots ,X_{k}}$${\displaystyle \{0,1\}^{n}}$${\displaystyle n}$

マージの役割は、 に分散され、そのエントロピーを可能な限り保持する新しいランダム変数を出力することです。理想的には、どの変数が均一であるかがわかっていれば、それを出力として使用できますが、その情報はわかっていません。マージの背後にある考え方は、小さな追加のランダムシードを使用することで、どれが均一変数であるかを知らなくても良い結果が得られる可能性があるというものです。 ${\displaystyle \{0,1\}^{n}}$

単純なアイデアとしては、すべての変数のXORを取ることが挙げられます。変数の 1 つが均一に分布し、他の変数から独立している場合、出力は均一になります。ただし、 であり、両方が均一に分布している場合、この方法は機能しません。 ${\displaystyle X_{1}=X_{2}}$

定義（合併）：

関数は、上に分布するランダム変数のすべての集合（そのうちの少なくとも 1 つは均一）に対して、 の分布が滑らかな最小エントロピー を持つ場合、 -マージャーと呼ばれます。変数はビット上の均一分布を表し、 は真にランダムなシードを表します。 ${\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}}$${\displaystyle (m,\varepsilon )}$${\displaystyle (X_{1},\ldots,X_{k})}$${\displaystyle \{0,1\}^{n}}$${\displaystyle Z=M(X_{1},\ldots,X_{k},U_{d})}$${\displaystyle H_{\infty }^{\varepsilon }(Z)\geq m}$${\displaystyle U_{d}}$${\displaystyle d}$

言い換えると、長さ の小さな均一なシードを使用することで、マージは少なくとも最小エントロピー を持つ に近い文字列を返します。つまり、最小エントロピーを持つ文字列からの統計的距離はより大きくないということです。 ${\displaystyle d}$${\displaystyle \epsilon }$${\displaystyle m}$ ${\displaystyle m}$${\displaystyle \epsilon }$

注意：分布のランダム性を測定する概念はいくつかあります。ランダム変数の最小エントロピーは、 の最も可能性の高い値がを超えない確率で発生する最大のものとして定義されます。文字列の最小エントロピーは、そこから抽出できるランダム性の量の上限です。 ^[1]${\displaystyle Z}$${\displaystyle k}$${\displaystyle Z}$${\displaystyle 2^{-k}}$

合併を構築するときに最適化する 3 つのパラメーターがあります。

1. 出力の最小エントロピーは可能な限り高くする必要があります。そうすることで、より多くのビットを出力から抽出できるようになります。${\displaystyle m}$
2. ${\displaystyle \epsilon }$できるだけ小さくする必要があります。そうすれば、マージャーの出力に抽出器を適用した後、結果が均一に近くなります。
3. シードの長さは可能な限り短くする必要があります。そうすることで、マージが機能するために必要な初期の真にランダムなビットが少なくなります。${\displaystyle d}$

比較的良好なパラメータを用いた明示的な合併の構成が知られている。例えば、Dvir とWigderson の構成は次式を与える: ^[2]任意のおよび整数 に対して、 ならば、明示的な-合併が存在し、次式を満たす: ${\displaystyle \alpha >0}$${\displaystyle n}$${\displaystyle k\leq 2^{o(n)}}$${\displaystyle (m,\varepsilon )}$${\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}}$

1. ${\displaystyle m=(1-\alpha )n,}$
2. ${\displaystyle d=O(\log(n)+\log(k)),}$
3. ${\displaystyle \varepsilon =O\left({\frac {1}{n\cdot k}}\right).}$

証明は構成的であり、与えられたパラメータ内で多項式時間でそのような合併を構築することができます。

適切なパラメータを持つランダム性抽出器を生成するために、マージを使用することができます。抽出器は、高い最小エントロピーを持つランダム変数を受け取り、より小さいが均一に近いランダム変数を返す関数であることを思い出してください。任意の最小エントロピー抽出器は、次のマージベースのスキームを使用して取得できます。^{[2] [3]}

• 高い最小エントロピーを持つソースが与えられた場合、それをブロックに分割します。既知の結果^[4]によれば、これらのパーティションの少なくとも1つは、ブロックソースとしても高い最小エントロピーを持ちます。
• すべてのブロックにブロック抽出器を個別に適用します。これは弱い種類の抽出器であり、そのための優れた構成が知られています。^[2]少なくとも1つのブロックの最小エントロピーが高いため、少なくとも1つの出力は均一に非常に近くなります。
• マージャーを使用して、以前のすべての出力を 1 つの文字列に結合します。適切なマージャーが使用されると、結果の文字列は、長さに比べて最小エントロピーが非常に高くなります。
• ランダム性を抽出には、最小エントロピーが非常に高いソースに対してのみ機能する既知の抽出器を使用します。

上記のスキームの本質は、任意の最小エントロピーを持つ文字列を、その過程で多くの最小エントロピーを失うことなく、より小さな文字列に変換するためにマージを使用することです。この新しい文字列は、長さに比べて非常に高い最小エントロピーを持ち、そのタイプの文字列にのみ機能する、古くて既知の抽出機能を使用することが可能になります。

• ランダム性抽出器