ランダムネスの合併

抽出器理論において、ランダムネス・マージャーとは、少なくとも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つは一様）に対して、 の分布が滑らかな最小エントロピー を持つとき、 -mergerと呼ばれます。変数 はビット上の一様分布を表し、 は真にランダムなシードを表します。 ${\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 \varepsilon }$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle \varepsilon }$

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

パラメータ

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

1. 出力の最小エントロピーは可能な限り高くする必要があります。そうすることで、より多くのビットを出力から抽出できるようになります。${\displaystyle m}$
2. ${\displaystyle \varepsilon }$ できるだけ小さくする必要があります。そうすることで、マージャーの出力に抽出器を適用した後、結果が均一に近くなります。
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つの文字列に結合します。適切なマージャーが使用された場合、結果の文字列は長さに比べて非常に高い最小エントロピーを持ちます。
• ランダム性を抽出には、最小エントロピーが非常に高いソースにのみ機能する既知の抽出器を使用します。

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

参照

• ランダムネス抽出器

参考文献

1. De, Portmann, Vidick, Renner (2009). 「量子サイド情報が存在する場合のTrevisanの抽出器」. SIAM Journal on Computing . 41 (4): 915– 940. arXiv : 0912.5514 . doi :10.1137/100813683. S2CID  5387876.セクション2.2.
2. Zeev Dvir & Avi Wigderson. 「Kakeya集合、新しい合併、そして古い抽出子」(PDF) .
3. Noam Nissan & Amnon Ta-Shma. 「ランダム性の抽出：概要と新たな構築」（PDF） .セクション4.3.
4. アムノン・タ・シュマ。 「ランダム性の洗練」。博士論文。