数理解析研究所講究録
第 833 巻 1993 年 42-52

42$\epsilon$-偏りの確率変数と -依存の確率変数の間の関係について$\epsilon$

On Relationship between -biased Random Variables
and -dependent Random Variables$\epsilon$$\epsilon$

東北大工情報 神保秀司 (Shuji Jimbo)
東北大工情報 丸岡章 (Akira Maruoka)

1

まえがき
確率アルゴリズムで使われる無作為抽出は確率変数と看倣せる. 例えば, アルゴリズム中で $\{0,1\}$ の中から一様に
$x_{i}$$n$

ビットを選ぶ無作為抽出は $\{0,1\}$ の中の値を取る

個の独立な確率変数系$n$$x_{1},$$\ldots,$$x_{n}$

で各確率変数の分布が全て一様, つまり,
$Pr[x_{i}=0]=Pr[x_{i}=1]=\frac{1}{2}$となっているものと看倣せる.

アルゴリズム中でランダムな$n$個のビットが要求される場合は一様分布の$n$個の独立確率変数系と看倣すことが多いが, 実際にはしばしばより弱い性質を持った確率変数系と看倣しても問題が無いことがある. そのような, 確率変数系
ある. ただし,$k$$x_{1},$$\ldots,$$x_{n}$に要求される独立性に関する弱い性質として -限定 -依存と -限定 -偏りが
$k$

$k$

$\epsilon$$\epsilon$

は $1\leq k\leq n$ を満足する整数, $0\leq\epsilon\leq 1/2$ とする.

これらの独立性に関する弱い性質を持つ確率変数系の利点の一つは, その定義域となる確率空間の標本空間のサイズの小さいものが存在するという点である. もし, 標本空間のサイズが十分小さければ, その標本空間に属する全ての値に対して必要な処理を施すことによって, その確率変数系を用いる確率アルゴリズムを実用性
をそれほど失うこと無く決定性のものに変更できる. この方向での最近の結果として, [NN90], [LV91] がある.

本論文の主結果は,$k,$ $n$

を $1\leq k\leq n$ を満足する整数として, 確率変数系 $\{x_{1}, \ldots, x_{n}\}$ が -限定 -偏りな$k$$\epsilon$

らば, 最大値ノルムの意味で -限定 $4(1-2^{-k})\epsilon$ -依存であり, かつ最大値ノルムの意味で, 一様分布に関して k$k$

限定 $2(1-2^{-k})\epsilon$ -依存であるというものである.

関連する従来の結果として, [NN90], [AGHP90] では次の点が指摘されている.

1. 確率変数系$(X_{1}, \ldots, X_{n})$:$\Omegaarrow\{0,1\}^{n}$

が -限定
$n$

$\epsilon/2$-偏りならば, 任意の $1\leq k\leq n$ に対して,(a) 最大値ノルムの意味で, 一様分布に関して -限定 -依存であり,
$k$

(b)

2.

$k,$ $n$$L_{1}$

ノルムの意味で, 一様分布に関して -限定$k$$\epsilon$$2^{k}\epsilon$-依存である.

を $1\leq k\leq n$ を満足する整数として, 確率変数系 $(X_{1}, \ldots, X_{n})$ : $\Omegaarrow\{0,1\}^{n}$ が -限定

らば,

$k$

$L_{1}$

ノルムの意味で, 一様分布に関して 根定$k$$2^{k}\epsilon$$\epsilon/2$-偏りな-依存である.

従って, 本論文の結果によって, 最大値ノルムの意味で -限定 -依存の確率変数系を要求する確率アルゴリ$k$$\delta$

ズムを決定性のものに変更するような状況下で変更後のアルゴリズムの効率化が期待できるようになった. なぜなら, 従来, k- 限定 \delta -依存の確率変数を構成するために 限定 -偏りの確率変数を転用していたからである$k$$\epsilon$([NN90], [LV91]).
2. では, 確率空間と確率変数に関する基本的な概念の定義を与える. 3. では, 本論文の主結果を証明する.

4. では, 本論文の結果の具体的な応用例として, [LV91] で扱われた問題: DNF 式を充足する変数への割当の

43
個数の全体の個数 (変数の個数を

$n$

として

$2^{n}$) に対する割合の近似値を求める問題を解く決定性アルゴリズ

ムの効率化を紹介する.

2

準備
有限集合 $A$ に対して, $\Sigma_{x\in A}D(x)=1$ を満足する関数 $D:Aarrow[01]$ を $A$ 上の確率分布と呼ぶ.

定義 1$(\Omega, \mathcal{F}Pr)$は確率空間,$f$:$\Omega|f(\omega)\in T\}=\sum_{s\in\tau}D(s)$は確率変数とする. $D(s)=Pr[\{\omega\in\Omega|f(\omega)=s\}]$ によって定義され$\Omegaarrow S$

る関数 $D$ : $Sarrow[0,1]$ は確率変数$f$$\square$の分布であると言われる.

$S$の部分集合 $T$ に対しては $D(T)=Pr[\{\omega\in$と定義する. また, 同一の確率空間を定義域とする複数の確率変数がある場合, それらをーまとめにして確率変数系と呼ぶことがある.

$\{01\}$の中の値を取る確率変数系$x_{1},$$\ldots,$$x_{k}$の結合分布とは,$D(a_{1}, \ldots, a_{k})=Pr[x_{1}=a_{1}\wedge\ldots\wedge x_{k}=a_{k}]$を満足する関数 $D$ : $\{01\}^{k}arrow[01]$ のことである.
定義 2
る.

を

$\{x_{1}, \ldots, x_{n}\}$$Ss_{1},$$\ldots,$$s_{J},j,$$\sigma,$$\{01\}$$\sigma_{1}\cdots\sigma j$$\sigma=(\sigma_{1}\cdots\sigma_{J})\in\{01\}^{j}$の中の値を取る確率変数系,$k\leq n$は正整数かつ$0\leq\epsilon\leq 1/2$の動く範囲は, $S=\{S_{1}, \ldots, Sj\}\subseteq\{1, \ldots, n\},$ $s_{1}<.$ . .

とす$<Sj,$ $j\leq k$ ,とする. さらに,$\Delta_{A}(S, \sigma)=|Pr[x_{s_{1}}=\sigma_{1}\wedge\cdots\wedge x_{Sj}=\sigma_{j}]-Pr[x_{s_{1}}=\sigma_{1}]\cdots Pr[x_{Sj}=\sigma_{j}]|$,$\triangle_{B}(S, \sigma)=|Pr[x_{s_{1}}=\sigma_{1}\wedge\cdots\wedge x_{s_{\dot{J}}}=\sigma_{i}]-\frac{1}{2^{j}}|$と表す. $\{x_{1}, \ldots, x_{n}\}$ は,$(\forall S)(\forall\sigma)(\triangle(S\sigma)\leq\epsilon)$が成立するとき最大値ノルムの意味で$k$-限定 -依存であると言い,$\epsilon$$( \forall S)(\sum_{\sigma}\triangle(S, \sigma)\leq\epsilon)$が成立するとき$L_{1}$を表すものとする.
して$k$

ノルムの意味で$\Delta$が$\Delta_{A}$-限定 -依存であると言う. ただし, 定義式の中の-限定 -依存であると言う$\triangle$$\epsilon$

なのか, それとも$\triangle_{B}$

なのかを区別するために\Delta が$\Delta_{B}$は$\Delta_{A}$または$\Delta_{B}$の場合は一様分布に関$\square$$\epsilon$

定義 3$\{x_{1}, x_{2}, \ldots, x_{n}\}$とする.

$S,$ $s_{1},$ $\ldots s_{J,J^{\sigma,\sigma_{1}\cdots,\sigma^{j}}}$

る.

$k$

,

は $\{01\}$ の中の値を取る確率変数系, $k,$ $n$ は $1\leq k\leq n$ を満足する整数, $0\leq\epsilon\leq 1/2$の動く範囲は, $S=\{S_{1}, \ldots, Sj\}\subseteq\{1, \ldots, n\},$ $s_{1}<\cdots<Sj,$ $j\leq k$ とすは$\{x_{1}, \ldots x_{n}\}$$( \forall S)(|Pr[x_{s_{1}}\oplus\cdots\oplus x_{Sj}=0]-\frac{1}{2}|\leq\epsilon)$が成立するとき

上記の

$k$

$k$

-限定 -偏りであると言う. ただし,$\epsilon$-限定 -偏りの定義の中の$\epsilon$$\oplus$は排他的論理和の演算を表す.

$| Pr[x_{s_{1}}\oplus\cdots\oplus x_{Sj}=0]-\frac{1}{2}|\leq\epsilon$

は, [NN90] では,$|Pr[x_{s_{1}}\oplus\cdots\oplus x_{Sj}=0]-Pr[x_{s_{1}}\oplus\cdots\oplus x_{Sj}=1]|\leq\epsilon$$\square$44と定義されているが, この意味で -限定 -偏りであることは本論文の意味では -限定 (\epsilon /2)-偏りとなり特に異
$k$

$k$

$\epsilon$

なる概念を表しているものではない.

従来の文献に見られるの意味でのものと$L_{1}$$k$-限定 -依存の概念には幾つかの変種があり, それらを整理する為に, 最大値ノルム$\epsilon$

ノルムの意味でのものの 2 種類に分類し, またそれとは別の観点から, 一様ノルムに関するものとそうでないものの 2 種類に分類した. 例えば [LV91] では最大値ノルムの意味での概念が使われ, [NN90] では$k$-限定 -依存の$\epsilon$

ノルムの意味でかつ一様分布に関しての -限定 -依存の概念が使われている.
$k$$L_{1}$$\epsilon$

定義から, 確率変数系が -限定 -依存であるかどうか, あるいは -限定 -偏りであるかどうかはその定義
$k$

$k$

$\epsilon$$\epsilon$

域となる確率空間とは無関係に分布だけで決まる点に注意されたい.

3

確率変数における偏りと依存の間の関係
本論文では, 正整数 $m$ に対して $[m]=\{1, \ldots, m\}$ と表し, 有限集合

まり $S$ の部分集合全体からなる集合を表す. 以下では, 正整数$\{0,1\}^{n}$

$n$

$S$

に対して

$2^{S}$

で $S$ のべ $*$ 集合, つを固定し, $X=2^{[n]}$ とおく. さらに, $X$ との間の自然な 1 対 1 の対応に従ってこれら二つの集合を同一視する. つまり, 各 $(a_{1}, \ldots, a_{n})\in\{0,1\}^{n}$と $\{i\in[n]|a_{i}=1\}\in 2^{[n]}$ を同一視する. さらに, 次に述べる定義に従って, $X$ を定義域とし $R$ の中の値を取る関数全体の集合$R^{X}$に内積を導入し,$R^{X}$

を $X$ を添字の集合とする$2^{n}$

次元ユークリッドベクトル空間と

考える.
定義 4

$f,$ $g\in R^{X}$$I\in X$

に対して

に対して
$\lambda_{I}$

$f$

と

$g$

の内積

$\langle f, g\rangle$

を $\langle f, g\rangle=\sum_{x\in X}f(x)g(x)$ と定義する.

$\square$: $Xarrow R$ を$\lambda_{I}(x)=\{\begin{array}{l}1(x=I\emptyset t\ovalbox{\tt\small REJECT}_{D}^{A})0(x\neq I\emptyset \mathscr{B}_{D}^{\Delta\sim})\end{array}$と定義すれば,$\{\lambda_{I}\}_{I\in X}$

は, 明らかに

また, $I\in X$ に対して$\chi_{I}$$R^{X}$の正規直交基底となる.

: $Xarrow R$ を$\chi_{I}(x)=\{\begin{array}{l}1(|x\cap I|\equiv 0(mod2))-1(|x\cap I|\equiv 1(mod2)\text{の場合})\end{array}$と定義すれば,$\{2^{-n/2}\chi_{I}\}_{I\in X}$

は $R^{X}$ の正規直交基底となる. これは次のようにして示される.

任意の $I\in X$ に対して $||\chi_{I}||=2^{n/2}$ が成立することは明らかであるので, $A\neq B$ を満足する $A\in X,$ $B\in X$

を任意に選んだとき,$\langle\chi_{A}, \chi_{B}\rangle=0$となることを示せば十分である. $A,$ $B$ をこのように選んだとき,$\langle\chi_{A},$$\chi_{B}$$\chi_{A},$$\chi_{B}$の定義から} $=|\{x\in X : |x\cap A|\equiv|x\cap B| (mod 2)\}|-|\{x\in X : |x\cap A|\not\equiv|x\cap B| (mod 2)\}|$

が成立する. $A$ と $B$ の対称差を $A\triangle B=(A\backslash B)\cup(B\backslash A)$ とおけば,$A\triangle B\neq\emptyset$

であり, さらに,$\{x\in X : |x\cap A|\equiv|x\cap B| (mod 2)\}=\{x\in X : |x\cap(A\triangle B)|\equiv 0 (mod 2)\}$かつ$\{x\in X : |x\cap A|\not\equiv|x\cap B| (mod 2)\}=\{x\in X : |x\cap(A\triangle B)|\equiv 1 (mod 2)\}$45が成立する. 従って, 一般に空でない有限集合 $S$ に対して, 偶数サイズの $S$ の部分集合の個数と奇数サイズの$S$の部分集合の個数が等しいことから,$\{\chi_{A},$$\chi_{B}\rangle$$=|\{x\in X : |x\cap(A\triangle B)|\equiv 0 (mod 2)\}|-|\{x\in X:|x\cap(A\triangle B)|\equiv 1 (mod 2)\}|=0$が導かれる.
定義 5$K\subseteq I\in X$

を満足する有限集合 $K,$

$I$

に対して,

$R(I, K)=\{x\in X : x\cap I=K\}$と定義する.
$D$$\square$は $\{0,1\}$ の中の値を取る確率変数系 $\{x_{1}, \ldots, x_{n}\}$ の結合分布を $X$ 上の確率分布と看倣したもの,$s_{1},$$\ldots s_{j}$は $1\leq s_{1}<\cdots<Sj\leq n$ を満足する整数, $S=\{s_{1}, \ldots, s_{j}\},$ $\sigma=(\sigma_{1}, \ldots, \sigma_{j})\in\{0,1\}^{j},$ $j\leq n$ とする. このとき, $\sigma=\{si |i\in\{1, \ldots,j\}\wedge\sigma_{i}=1\}\subseteq S$ と看倣せば, 定義 2 と定義 5 より,$\Delta_{B}(S, \sigma)=|(\sum_{x\in R(S,\sigma)}D(x))-\frac{1}{2^{|S|}}|$

および $\Delta_{A}(S, \sigma)=|(\sum_{x\in R(S,\sigma)}D(x))-\prod_{y\in S}(\sum_{z\in R(\{y\},\sigma\cap\{y\})}D(z))|$が成立する.

補題 1

$k$

は高々

$n$

の正整数, $D\in R^{X}$ は $X$ 上の確率分布とし,(1)$(\forall A\in X)(1\leq|A|\leq k\Rightarrow|\langle D, \chi_{A}\}|\leq 2\epsilon)$を満足すると仮定する. このとき, $1\leq|I|\leq k$ および$|\{D,$$K\subseteq I$

を満足する任意の $I\in X,$ $K\in X$ に対して,$( \sum_{x\in R(I,K)}\lambda_{x})-\frac{1}{2^{|I|}}\chi\emptyset\}|\leq 2(1-\frac{1}{2^{|I|}})\epsilon$が成立する.

(証明)に選んで$\sum_{x\in R(I,K)}\lambda_{x}$$B\backslash I\neq\emptyset$

奇数サイズの$S$は$\{\chi_{A}\}_{A\in 2^{J}}$の張る部分空間に属することが次のようにして示される. $B\in X$ を任意と仮定すれば, 一般に空でない有限集合$S$に対して, 偶数サイズの$S$の部分集合の個数との部分集合の個数が等しいことから以下の等式が導かれる.

$\{\chi_{B},\sum_{x\in R(I,K)}\lambda_{x}\}$$=$$\sum_{x\in R(IK)},\langle\chi_{B}, \lambda_{x}\rangle$$=$$|\{x\in R(I, K):|x\cap B|\equiv 0 (mod 2)\}|-|\{x\in R(I, K) : |x\cap B|\equiv 1 (mod 2)\}|$$=$$|2^{(B\cup I)^{C}}|(|\{x\in 2^{(B\backslash I)} :$-|\{x\in 2^{(B\backslash I)} :さらに,$\{2^{-n/2}\chi_{I}\}_{I\in X}$|x|\equiv|K\cap B| (mod 2)\}|$|x|\not\equiv|K\cap B| (mod 2)\}|)=0$.

が $R^{X}$ の正規直交基底であることから$\sum_{x\in R(I,K)}\lambda_{x}=2^{-n}\sum_{A\in 2^{I}}\{\sum_{x\in R(IK)},\lambda_{x},$ $\chi_{A}\}\chi_{A}$と展開できる.

46
このことと$\{\sum_{x\in R(IK)},\lambda_{x},$ $\chi\emptyset\}=\sum_{x\in R(IK)},\langle\lambda_{x}, \chi_{\emptyset}\rangle=|R(I, K)|=2^{n-|I|}$から$( \sum_{x\in R(IK)},\lambda_{x})-\frac{1}{2^{|I|}}\chi_{\emptyset}=2^{-n}\sum_{A\in 2^{I}\backslash \{\emptyset\}}\{_{x\in R(K})$

が成立する. 従って, $D$ に対する条件 (1) より,$|\{D,$$( \sum_{x\in R(IK)},\lambda_{x})-\frac{1}{2^{|I|}}\chi\emptyset\}|$$=$$|\{D,$$=$$2^{-n}| \sum_{A\in 2^{I}\backslash \{\emptyset\}}(\langle D, \chi_{A}\rangle\sum_{x\in R(IK)},\langle\lambda_{x}, \chi_{A}\rangle)|$$\leq$$2^{-n} \sum_{A\in 2^{I}\backslash \{\emptyset\}}(|\langle D, \chi_{A}\rangle||\sum_{x\in R(IK)},\langle\lambda_{x}, \chi_{A}\rangle|)$$\leq$$2^{-n}2 \epsilon\sum_{A\in 2^{I}\backslash \{\emptyset\}}|\sum_{x\in R(IK)},\{\lambda_{x},$ $\chi_{A}\rangle$

$=$

ただし,

$\chi_{A}^{-1}$

任意のは$\chi_{A}$$A\subseteq I$$2^{-n} \sum_{A\in 2^{I}\backslash \{\emptyset\}}\{\sum_{x\in R(I,K)}\lambda_{x},$$\chi_{A}\}\chi_{A}\}|$$|$$2^{-n}2 \epsilon\sum_{A\in 2^{I}\backslash \{\emptyset\}}||R(I, K)\cap\chi_{A}^{-1}(1)|-|R(I, K)\cap\chi_{A}^{-1}(-1)||$.

の逆関数を表す.

に対して,ならば $R(I, K)\subseteq\chi_{A}^{-1}(1)$ または $R(I, K)\subseteq\chi_{A}^{-1}(-1)$ のいずれか一方のみ$A\neq\emptyset$が必ず成立するので,$2^{-n}2 \epsilon\sum$$||R(I, K)\cap\chi_{A}^{-1}(1)|-|R(I, K)\cap\chi_{A}^{-1}(-1)||$$A\in 2^{I}\backslash \{\emptyset\}$$=$

従って, 補題 1 は証明された.

口系 1 $0\leq\epsilon\leq 1/2$ かつゐは高々$n$$\epsilon$-偏りならば(証明)$\{x_{1}, \ldots, x_{n}\}$定義から,$2^{-n}2 \epsilon(2^{|I|}-1)|R(I, K)|=2^{-n}2\epsilon(2^{|I|}-1)2^{n-|I|}=2(1-\frac{1}{2^{|I|}})\epsilon$の正整数とする. $\{0,1\}$ の中の値を取る確率変数系

は最大値ノルムの意味で一様分布に関して$\{x_{1}, \ldots, x_{n}\}$

が

$k$

$k$

-限定 2

$\{x_{1}, \ldots, x_{n}\}$$(1- \frac{1}{2^{k}})\epsilon$

が -限定
$k$

-依存である.

-限定 -偏りであることは, $D$ をその結合分布として,$\epsilon$$(\forall A\in X)(1\leq|A|\leq k\Rightarrow|\{D, \chi_{A}\rangle|\leq 2\epsilon)$と同値であり, 従って, 補題 1 より, これを仮定すれば $1\leq|I|\leq k,$$K\subseteq I$

を満足する任意の $I\in X,$ $K\in X$ に対して,$\triangle_{B}(I, K)=|(\sum_{x\in R(IK)},D(x))-\frac{1}{2^{|I|}}|=|\{D,$ $( \sum_{x\in R(IK)},\lambda_{x})-\frac{1}{2^{|I|}}\chi\emptyset\}|\leq 2(1-\frac{1}{2^{|I|}})\epsilon\leq 2(1-\frac{1}{2^{k}})\epsilon$が導かれる. これは, $\{x_{1}, \ldots, x_{n}\}$ が最大値ノルムの意味で一様分布に関してことを表している.

口

$k$

-限定 2

$(1- \frac{1}{2^{k}}I^{\epsilon}$-依存である.

47
定理 1 $0\leq\epsilon\leq 1/2$ かつ

$k$

は高々

$n$

の正整数とする. $\{0,1\}$ の中の値を取る確率変数系

定 -偏りならば $\{x_{1}, \ldots, x_{n}\}$ は最大値ノルムの意味で$\epsilon$(証明)$1\leq|I|\leq k$

$k$

-限定 4

$(1- \frac{1}{2^{k}})\epsilon$$\{x_{1}, \ldots, x_{n}\}$

が

$k$

-限

-依存である.

を満足する $I\in X=2^{[n]}$ と $J\in X$ を任意に選ぶ. 補題 1 と $\{x_{1}, \ldots, x_{n}\}$ が -限定 -偏$k$$\epsilon$

りであるという仮定から, $D$ をその結合分布として,$|( \sum_{x\in R(I,K)}D(x))-\frac{1}{2^{|I|}}|=|\{D,$

$B$

“成立し,

$\#^{\prime\backslash }$っ$\vee C$$( \sum_{x\in R(I,K)}\lambda_{x})-\frac{1}{2^{|I|}}\chi\emptyset\}|\leq 2(1-\frac{1}{2^{|I|}})\epsilon$,$\frac{1}{2^{|I|}}-2(1-\frac{1}{2^{|I|}})\epsilon\leq\sum_{x\in R(I,J\cap I)}D(x)\leq\frac{1}{2^{|I|}}+2(1-\frac{1}{2^{|I|}})\epsilon$および,$( \forall x\in I)(\frac{1}{2}-\epsilon\leq x\in R(\{x\}J\cap\{x\})\sum_{)}D(x)\leq\frac{1}{2}+\epsilon)$が成立する. 従って,$\frac{1}{2^{|I|}}-2(1-\frac{1}{2^{|I|}})\epsilon-(\frac{1}{2}+\epsilon)^{|I|}$$\leq$$\leq$$( \sum_{x\in R(I,J\cap I)}D(x))-\prod_{y\in I}(\sum_{z\in R(\{y\},J\cap\{y\})}D(z))$(2)$\frac{1}{2^{|I|}}+2(1-\frac{1}{2^{|I|}})\epsilon-(\frac{1}{2}-\epsilon)^{|I|}$が成立する. $0\leq\epsilon\leq 1/2$ に注意されたい. 従って, 不等式 (2) より次の不等式が導かれ定理 1 の証明は完了
する.

$\Delta_{A}(I, J\cap I)=|(\sum_{x\in R(I,J\cap I)}D(x))-\prod_{y\in I}(\sum_{z\in R(\{y\},J\cap\{y\})}D(z))|$$\leq$

一 $\{|\frac{1}{2^{|I|}}-2(1-\frac{1}{2^{|I|}})\epsilon-(\frac{1}{2}+\epsilon)^{|I|}|,$ $| \frac{1}{2^{|I|}}+2(1-\frac{1}{2^{|I|}})\epsilon-(\frac{1}{2}-\epsilon)^{|I|}|\}$$=$

一 $\{(\sum_{i=1}^{|I|}\frac{1}{2^{|I|-i}}(\begin{array}{l}|I|i\end{array})\epsilon^{i})+2(1-\frac{1}{2^{|I|}})\epsilon,$

$=$

2

(

$1- \frac{1}{2^{|I|}})\epsilon+\sum_{i=1}^{|I|}(\frac{1}{2^{|I|-i}}(\begin{array}{l}|I|i\end{array})\epsilon^{i})\leq 2(1-\frac{1}{2^{|I|}})\epsilon+\sum_{i=1}^{|I|}(\frac{1}{2^{|I|-i}}(\begin{array}{l}|I|i\end{array})(\frac{1}{2})^{i}$

$=$

2

(

$1- \frac{1}{2^{|I|}})\epsilon+\frac{2\epsilon}{2^{|I|}}\sum_{i=1}^{|I|}(\begin{array}{l}|I|i\end{array})=2(1-\frac{1}{2^{|I|}})\epsilon+\frac{2\epsilon}{2^{|I|}}(2^{|I|}-1)=4(1-\frac{1}{2^{|I|}})\epsilon$$( \sum_{i=1}^{|I|}\frac{1}{2^{|I|-i}}(\begin{array}{l}|I|i\end{array})(-1)^{i-1}\epsilon^{i})+2(1-\frac{1}{2^{|I|}})\epsilon\}$

翫 $)$

.

口

4

$\epsilon$-偏りの確率変数の応用

十分小さい$\epsilon$

に対する

$k$

-限定 -依存の確率変数の組が -限定独立な確率変数の組の代用となる例を挙げ,$\epsilon$$k$

本論文の前節までに導かれた結果がどのように活用されるかを見る. その例は, [LV91] で研究された, DNF 式を充足する, 変数への値の割り当ての割合の近似評価方法に関するものである.

48

$F$

は $m$ 個の項を持つ $n$ 変数の DNF 式とする. 通常の方法で, $F$ を $\{0,1\}^{n}$ から $\{0,1\}$ への関数と看倣すことができる. $F$ を充足する変数への値の割り当ての割合は次の値である:$Pr[F(x_{1}, \ldots, x_{n})=1]=\frac{|\{x\in\{0,1\}^{n}|F(x)=1\}|}{|\{0,1\}^{n}|}=\frac{1}{2^{n}}|\{x\in\{0,1\}^{n}|F(x)=1\}|$

この式の中の $\{x_{1}, \ldots, x_{n}\}$ は, それぞれ, 分布が一様な, つまり, 各 $i=1,$$\ldots,$$n$.

に対して, $Pr[x_{i}=0]=Pr[x_{i}=$$1]=1/2$ を満足する独立確率変数系である. $x=(x_{1}, \ldots, x_{n})$ とおく. この $Pr[F(x)=1]$ を正確に計算する問題

は, Valiant [Va179] によって, $\#P$ 完全であることが示されているので, 現在この問題を解決することは大変困難であると考えられている. [LV91] では, 確率アルゴリズムを確定的なアルゴリズムに変形した形の $Pr[F(x)=1]$の近似値を計算するアルゴリズムを紹介している. その近似値を $Y$ としたとき, 真の値 $Pr[F(x)=1]$ との誤差は$(1-\delta)Pr[F(x)=1]-\epsilon\leq Y\leq Pr[F(x)=1]+\epsilon$の形で評価される. 与えられた引数$\delta$および$\epsilon$に対して, この許容範囲に入る近似値 $Y$ を計算するための時間

を如何に短くするかが問題となる. [LV91] に詳しく書かれているアルゴリズムは 2-限定独立な確率変数系と,
適当な

$l$

に対する -限定独立な確率変数系を用いている. しかし, 適当な $\theta>0$ を選んで, -限定 -依存の確率
$l$

$l$

$\theta$

変数系を用いる方法も言及されていて, 実際, その方法を用いるとより計算時間の短いアルゴリズムが得られた. なお, どちらの方法の場合でも, 評価された計算時間の上界は引数 $n,$ $m,$$\delta$および$\epsilon$の多項式を超えるものになっていることに注意する必要がある.

41

アルゴリズムの概要

以下, 近似値を計算するアルゴリズムの概要を述べる. このアルゴリズムは [LV91] のものを次の二つの点に関して改良したものである. 一つ目は, ある整数$\epsilon$

に対する

$k$

$k$

に対する

$k$

-限定独立な確率変数系の替わりにある正の値-限定 -依存の確率変数系を用いている点である. 二つ目は, 変数の色付を値とする確率変数を実$\epsilon$

現する場合, その確率変数に対して要求する性質が異なる点である. [LV91] のアルゴリズムでは, -良性 (原文$\delta$では$\delta$-good”) と呼ばれる性質を持つように実現したが, 本論文では,実現する.

$(\delta, c)$$(\delta, c)$-良性と呼ばれる性質を持つように-良性に関しては後の節で述べる. これらの改良に関しては [LV91] で言及されているが, その改良による具体的な影響に関しては述べられていない.

なお, 記述中の変数

1. $F$ の項で長さが$t,$ $c,$$t$$k=2^{\nu},$ $\eta,$ $l,$$\theta$

は, $n,$ $m,$

$1/\delta$

およびより大きいものを除去し, DNF 式

2. 変数の集合上の色付けの類$C$$1/\theta$の値に基いて, 予め設定される.

を作る.

$G$

を次のように定義する. $\eta>0$ ならびに整数$c,$$1\leq c\leq t$, および$\nu\geq 0$

は予め設定されている. $k=2^{\nu}$ とおく. 最大値ノルムの意味で, 一様分布に関して $(c+1)\nu$ -限定 -依存の$\eta$$\nu n$個の確率変数の系

一色を表す

$n$

を定め, それらを添え字の順に$\{b_{1}, b_{2}, \ldots, b_{\nu n}\}$個のベクト)$sc_{1}=(b_{1}, \ldots, b_{\nu}),$く. $f=(c_{1}, \ldots, c_{n})$ は付からなる類を$C$$n$$c_{n}=(b_{n-\nu+1}, \ldots, b_{n})$$f$の定義域となっている標本空間を$k$$\ldots,$に対して,$X_{i^{g}}$

で色付

$g$

値ノルムの意味で, 一様分布に関して -限定 -依存の$l$

する確率変数を$X_{i^{g}}$個ずつ連結して, $k=2^{\nu}$ 色中のを作り, $f=(c_{1}, \ldots, c_{n})$ とお個の変数の色付の一つを値として取る確率変数である.

と表し,

3. 各 $g\in C$ および各 $i=1,$$\ldots,$$\nu$$\theta$により色$|X_{i}^{g}|$に属する DNF 式の変数に対応させる.

数と看倣せる. このように看倣したとき,$\Omega^{c}$$\{\mathcal{X}_{1}^{g}, \ldots , \mathcal{X}_{k^{g}}\}$

$i$

$f$

の取り得る全ての色と表す.

が付けられた変数の集合を表す. 最大個の確率変数の系艀を実現し, その系に属$\mathcal{X}_{i^{g}}$は$\{0,1\}^{X_{;^{g}}}$の中の値を取る単一の確率変が独立確率変数系となるように,$\mathcal{X}_{1}^{g},$$\mathcal{X}_{k^{g}}$$\ldots,$を

49実現する. このようにして得られた個の確率変数の系を

$n$

と表す.

$\mathcal{X}^{g}$$\mathcal{X}^{g}$の定義域となる標本空間$\Omega^{g}$は有限集合となるようにできる.

4. DNF 式

DNF 式を
て,

と色付

$G$

$G_{f(\tau)}$$G_{g}$

と

$g$

に対して,

$G$

を

$g$

と表す. $f$ の各標本点$x=\mathcal{X}^{f(\tau)}(\omega)$で色付したとき, どの色も高々と,$c$

色しか現れない $G$ の項からなる$(\tau, \omega)$に対しを求め, さらに, $G_{f(\tau)}(x)=1$ かどうかを判定することによって, 各$\tau\in\Omega^{c}$$\tau\in\Omega^{C}$

個の標本点$|\Omega^{f(\tau)}|$$\omega\in\Omega^{f(\tau)}$

の全ての組

に対する
$Y_{\tau}=Pr[\{\omega\in\Omega^{f(\tau)}|G_{f(\tau)}(\mathcal{X}^{f(\tau)}(\omega))=1\}]$を計算する.
$Y=\max_{\tau\in\Omega^{C}}Y_{\tau}$がこのアルゴリズムの返す近似値である.

4.2

アルゴリズムの実行時間の評価

アルゴリズムの変数$t,$ $c,$$k,$ $\eta,$ $l,$$\theta$の設定と与えられた $k,$に対する$\epsilon$$k$-限定 -依存の確率変数の実現方法を$\epsilon$

明確にすればアルゴリズムは具体的なものとなる. さらに, アルゴリズムが正しく動作する為には, 計算された
近似値 $Y$ が許容範囲に入っていなくてはならない. このことを保証する為に, 変数$t,$ $c,$ $k,$$\eta,$$l,$$\theta$の設定方法にある制限が付く. この制限に関しては, 後の節で述べる.
以下では, 本論文の前節までの結果がこのアルゴリズムの実行時間の減少にどのように効果があるかを見る

為に, 変数$t,$ $c,$$k,$ $\eta,$ $l,$$\theta$に対して求まるアルゴリズムの実行時間の上界が, 本論文の結果を利用した場合としない場合でどのように異なるかを見る.
明らかに, 概要の 1 の動作は$n$と $m$ に関する多項式時間で可能である. また, 2 あるいは 3 に現れる各確率変数に対して, その確率変数の標本空間中の標本点を一つずつ逐次発生する為の時間, 確率変数の値を標本点から計算する為の時間およびそれらの計算を容易にする為の前処理の時間は, [NN90] あるいは [AGHP90] で紹介された方法を用いることにより, 全て $n,$ $m,$$c,$$\nu,$$1/\eta,$$l$の設定を工夫することにより, これらの時間は $n,$ $m,$て, 概要の 4 において調べるべきとする二つの多項式$P_{1}$$(\tau, \omega)$および$1/\delta$$1/\theta$

およびの組の個数が\Sigma \mbox{\boldmath $\tau$}\in \Omega cの多項式時間で可能である. 変数$\eta,$$l,$$\theta$の多項式時間になるようにできる. 従っ$1/\epsilon$$|\Omega^{f(\tau)}|$$t,$ $c,$ $k,$であるので, $n,$ $m,$

$1/\delta$

および$1/\epsilon$

を引数

および乃を用いて, アルゴリズムの実行時間は,(3)$P_{1}(n, m, 1/ \delta, 1/\epsilon)+P_{2}(n, m, 1/\delta, 1/\epsilon)\sum_{\tau\in\Omega^{C}}|\Omega^{f(\tau)}|$と表すことができる. 従って, $P_{3}=P_{1}+P_{2}$ とおけば,(4)$P_{3}(n,m, 1/ \delta, 1/\epsilon)\sum_{\tau\in C}|\Omega^{f(\tau)}|$はアルゴリズムの実行時間の上界となる. なお, 本論文の方法では, 式 (4) の中の\Sigma \mbox{\boldmath $\tau$}\in \Omega c$|\Omega^{f(\tau)}|$が多項式で上から抑えられるようにはできていない.

上記の君および乃は, 本論文の結果を利用する場合としない場合でそれほど違わないと考えられるので,$\sum_{f\in C}|\Omega^{f}|$がどのように異るかを見ることによって実行時間の違いを概略的に知ることができる.

[AGHP90] によると, $\{0,1\}$ の中の値を取る, 最大値ノルムの意味で, 一様分布に関してゐ- 限定 -偏りの$\epsilon$$n$2個の確率変数の組を作り, その標本空間のサイズが高々となるようにできる. さらに, [NN90]$( \frac{k\lceil\log_{2}n\rceil}{2\epsilon}$ノ50$\text{で^{}\backslash }\}h$, BC 且符号 (7) 理論 1? 用

偏りの当て, 任意 (2) 正整数と$k$$m\#_{\sim}$

行列を掛けるというものである.

ら$arrowh$$\text{の^{};}\beta_{\ddagger\ddagger}$

大値ノルムの意味で, 一様分布に関して -限定 -依存の$k$$\ovalbox{\tt\small REJECT}$々$\zeta\epsilon$-偏 ) の km 個 O) 確率変数 (\emptyset l) 系 $kk$ -限定$V$$\epsilon-$$\epsilon$$n$

果と本論文の結果から, $\{0,1\}$ の 中 の 値$\not\in i$

取 6, 最個の確率変数の系を作り, その標本空間のサイズがとなるようにできる. 一方, [LV91] あるいは [NN90] にある依存と偏りに関する記述では$( \frac{k\lceil\log_{2}n\rceil}{\epsilon})^{2}$$\{0,1\}$対し個の確率変数の系に変形する方法が紹介されている. その方法は, 有限体 $GF(2)$ を成分とする適$2^{m}$$km\cross 2^{m}$$f_{i}\backslash$$\backslash _{/}a$の中の値を取る, 最大値ノルムの意味で, 一様分布に関して -限定 -偏りの確率変数系は最大値ノルム$k$の意味で, 一様分布に関して -限定$k$$2^{k}\epsilon$$\epsilon$-依存であることだけを保証している. 従って, 上記と同様の率変数の系の標本空間のサイズの上界は$2^{2k}( \frac{k\lceil\log_{2}n\rceil}{\epsilon})^{2}$

ノルムの意味で, 一様分布に関して -限定 -依存の$k$$\epsilon$

$n$

$n$

個の確

である. 以上から, $\{0,1\}$ の中の値を取る, 最大値個の確率変数の系を作った場合の標本空間のサイズの上界の評価値は, [LV91] あるいは [NN90] にあるような従来の方法の場合は, 本論文の評価方法を利用する場合と比べて,$2^{2k}$倍大きくなってしまうことが解る.

本論文では,色付$g$$\sum_{\tau\in\Omega^{C}}|\Omega^{f(\tau)}|$に対して,$\Omega^{g}$は$\mathcal{X}^{g}$の精密な評価が困難な為, その上界として,の定義域である.

$\mathcal{X}_{i^{g}}$の定義域を大値ノルムの意味で, 一様分布に関して -限定 -依存の$l$積$\theta$$\Omega_{i}^{g}$$| \Omega^{C}|\cdot\max_{\tau\in C}|\Omega^{f(\tau)}|$と表すと, 各$|X_{i}^{g}|\leq n$$\mathcal{X}_{i^{g}}$を採用する.

は $\{0,1\}$ の中の値を取る, 最個の確率変数の系であり, さらに,$\Omega^{g}$は直と同型であるので, 本論文の結果を利用した場合は$\Omega_{1}^{g}\cross\cdots\cross\Omega_{k}^{g}$$| \Omega^{c}|\cdot\max_{\tau\in\Omega^{C}}|\Omega^{f(\tau)}|\leq(\frac{(c+1)\log_{2}\text{ゐ}\lceil\log_{2}\log_{2}k+\log_{2}n\rceil}{\eta})^{2}(\frac{l\lceil\log_{2}n\rceil}{\theta})^{2k}$(5)という上界が得られ, 従来の方法に従った場合はこの値よりも $k^{2(c+1)}2^{2kl}$ 倍大きい上界が得られる.

4.3

アルゴリズムの変数に関する制限

この節では, アルゴリズムの変数に関する, 近似値 $Y$ が許容範囲に入るための十分条件を示し, その十分条

件を満足する変数の値の設定例を挙げる. 実行時間の上界である式 (5) を最適化するような設定例を求めるのは困難なので, より粗い評価式を最適化する設定例を求め, その値を式 (5) に代入して本論文での検討の対象とする実行時間の上界を求める. また, この設定例から, 従来の方法に従った場合の実行時間の, 利用した場合の実行時間に対する評価値 $k^{2(c+1)}2^{2kl}$ の値を $n,$ $m,$$\delta$および$\epsilon$

によって表す.

命題 2 アルゴリズムの計算する近似値 $Y$ と真の値 $Pr[F(x)=1]$ は不等式$(1-\tilde{\delta})Pr[F(x)=1]-\tilde{\epsilon}\leq Y\leq Pr[F(x)=1]$ 十$\tilde{\epsilon}$を満足する、 ただし,$\tilde{\delta}(t, c, k, \eta)=(\begin{array}{l}tc+1\end{array})(\frac{1}{k^{c}}$十 $k\eta),\tilde{\epsilon}(m, t, c, k, l, \theta)=m2^{-t}+k(e^{-l/c2^{c}}+2^{l+1}\theta)$

である.

この命題は以下に述べる四つの補題から得られる. これらの補題は [LV91] にある定理あるいは補題を本論文で利用できる形に修正したものである. これらの証明は省略する.
補題 3$x_{I},$$\ldots,$

関して -限定$l$$\theta$$x_{n}$

は確率空間$(\Omega_{1}, \mathcal{F}_{1}, Pr_{1})$-依存の確率変数の系とし,上の $\{0,1\}$ の中の値を取る, 最大値ノルムの意味で, 一様分布に$y_{1},$$\ldots,$$y_{n}$

は確率空間 (

様分布の独立確率変数系とする. $G$ を項の長さの最大値が高々$c$$\Omega_{2},$$\mathcal{F}_{2}$, Pr2) 上の $\{0,1\}$ の中の値を取る,の $DNF$ 式としたとき,$|Pr_{1}[G(x_{1}, \ldots, x_{n})=1]-Pr_{2}[G(y_{1}, \ldots, y_{n})=1]|\leq e^{-l/c2^{c}}+2^{l+1}\theta$

一51が成立する.

補題 4

および

$c$

る. どの項にも
$g$

により色

$k$

$g$

を $c\leq k$ を満足する正整数とする. $G$ は $DNF$ 式,\iota こより同じ色が付けられた$c$

変数系 $\{x_{1}, \ldots, x_{n}\}$ を次のように実現する. 各 $i=1,$$k$$\ldots,$

たとき,$\{\mathcal{X}_{1}, \ldots, \mathcal{X}_{k}\}$$y_{1},$

色使った色付とす$k$$\ldots,$に対して

で$X_{i}$

に対して, 確率変数系 $\mathcal{X}_{i}=\{x_{j}|j\in X_{i}\}$ は最大$k$$\theta$は独立な確率変数系である. 一方,$k$とその上の $\{0,1\}$ の中の値を取る確率$(\Omega_{1}, \mathcal{F}_{1}, Pr_{1})$値ノルムの意味で, 一様分布に関して -限定 -依存であり, 各 $i=1,$$l$は $G$ の変数上の個の変数は存在しないとする. 各 $i=1,$が付けられた変数の集合を表す. 確率空間

$i$

$g$

$\ldots,$$y_{n}$$\ldots,$に対しては確率空間 ($\Omega_{2},$を確率変数と看倣し$\mathcal{X}_{i}$$\mathcal{F}_{2}$, Pr2) 上の $\{0,1\}$ の中の値を取る, 一様分布の独立確率変数系とする. このとき,$|Pr_{1}[G(x_{1}, \ldots, x_{n})=1]-Pr_{2}[G(y_{1}, \ldots , y_{n})=1]|\leq k(e^{-l/c2^{c}}+2^{1+1}\theta)$が成立する.

定義 6
より色

$G$

$i$

を

$n$

変数かつ $m$ 項の DNF 式,が付けられた変数の集合を表す.

に対して,の中の値を取る確率変数

$C$

$f$

$C$

を

$k$

色使った $G$ の変数の色付の類とする.

$X_{i}^{g}$

で色付 $g\in C$ にで $G$ の第 $j$ 項に現れる変数の集合を表す. $\eta>0$ および正整数$T_{j}$

が $(\eta, c)$ -良性であるとは, 各項 $i=1,$$\ldots,$

$m$

$c$

に対して,

$Pr[(\forall i=1, \ldots, k)(|X_{i}^{f}\cap T_{j}|\leq c)]=\sum_{g\in W_{j}}Pr[f=g]\leq\eta$が成立することを言う. ただし, $W_{j}=\{g\in C|(\forall i=1, \ldots, k)(|X_{i}^{g}\cap T_{j}|\leq c)\}$ とする.
補題 5

$\nu$

を正整数とし, $k=2^{\nu}$ とおく. 最大値ノルムの意味で, 一様分布に関して $(c+1)\nu$ -限定 -依存の$\eta$

個の確率変数の系
す$n$$\{b_{1}, b_{2}, \ldots, b_{\nu n}\}$を定め, それらを添え字の順に個のベクトル $c_{1}=(b_{1}, \ldots, b_{\nu}),$$\ldots,$$c_{n}=(b_{n-\nu+1}, \ldots, b_{n})$個の変数の色付の一つを値として取る確率変数
補題 6 $\eta>0$ かつ$\{x_{1}, \ldots, x_{n}\}$$(\Omega_{1}, \mathcal{F}_{1}, Pr_{1})$($\Omega_{2},$$\mathcal{F}_{2}$$\square$$c$は正整数とする.

$G$$f$

個ずつ連結して, $k=2^{\nu}$ 色中の一色を表$\nu$を作り, $f=(c_{1}, \ldots, c_{n})$ とおく. このとき,

$c$

$n$

は $(\eta, c)$ -良性である.

を $DNF$ 式とする.

$C$を $G$ の変数の集合上の色付の類とする.

を $\{0,1\}$ の中の値を取る, 一様分布の独立確率変数系とし, その定義域となっている確率空間をとする. $f$ を$C$の中の値を取る$(\eta, c)$-良性な確率変数とし, その定義域となっている確率空間を, Pr2) とする. また, アルゴリズムの概要 4 にある通り, 色付の色も高々$\nu n$色しか現れない $G$ の項からなる $DNF$ 式を$G_{f}$$g$に対して, $G$ を$g$で色付したとき, どと表す. このとき,$\sum_{g\in C}Pr_{1}[G_{g}(x_{1}, \ldots, x_{n})=1]Pr_{2}[f=g]\geq(1-\eta)Pr_{1}[G(x_{1}, \ldots, x_{n})=1]$が成立する.

命題 2 により,$\delta\leq\tilde{\delta}$($t,$ $c$, ゐ, ) および\epsilon$\eta$$\leq\tilde{\epsilon}(m, t, c, k, l, \theta)$が成立するように変数すれば, アルゴリズムが正しく動作することが保証される.
$\epsilon\leq\tilde{\epsilon}(m, t, c, k, l, \theta)$

より $t\geq\log_{2}(m/\epsilon)$ が成立する. また,$k \geq(\frac{1}{\delta}((\log_{2}$モー$\delta\leq\tilde{\delta}(t, c, k, \eta)$$c)/(c+1))^{c+1})^{1/c}$

より,$t,$ $c,$ $k,$$l$$\eta,$

および$\theta$を設定

52が成立する.

$c$を未定にした上で, このような考察を続けることにより, 以下の式を得る.

$\log(|\Omega^{C}|\cdot\max_{\tau\in\Omega^{C}}|\Omega^{f(\tau)}|)=O((\frac{1}{\delta})^{1/c}(\log\frac{m}{\epsilon})^{(1+\frac{1}{c})}(\log\log n+\log\log\frac{m}{\epsilon}+c2^{c}\log\frac{1}{\epsilon}+2^{c}\log\frac{1}{\delta}))$

この値を最小値に近付ける為に, $c=\sqrt{\log_{2}(1}/\delta$) とおく. この$c$の値から, 次の$k$および

$l= \Omega(c2^{c}(\log\frac{1}{\epsilon}+\log k))$$\log k=\Omega(\sqrt{\log\frac{1}{\delta}}+\log\log\frac{m}{\epsilon}),$$l$.

の下界が得られる.

.

これらは, 本論文を利用しない場合の実行時間の, 利用した場合の実行時間に対する比の評価値 $k^{2(c+1)}2^{2k1}$ が無視できない大きさであることを示している.

5

むすび
確率変数系の弱い独立性として, -限定 -偏りと$k$

確率変数系に対して, それを$k$$\epsilon$$k$-限定 -依存の二種類を取り上げ,$\epsilon$-限定 -依存と看倣すことを考えた場合,$\delta$$\delta\leq 4$$k$-限定 -偏りの任意の$\epsilon$とできることを示した. 弱い独立性の定義には幾つかの変種が有るが, 現在, 一般的に提案されている定義に関してはこの不等式が成立する.
また, 従来, -限定 -依存の確率変数を構成するために -限定 -偏りの確率変数を転用しているため, 本論文の
$k$

$k$

$\delta$$\epsilon$

結果は, 弱い独立性を持つ確率変数系で, その標本空間のサイズが小さいものを構成して, その標本空間の要素全てを調べるような形のアルゴリズムの効率化に効果的であり, その一例を紹介した.
本論文では, -限定 -偏りの任意の確率変数系に対して, それを -限定 -依存と看倣すことを考えたが, 逆
$k$

に,

$k$

$k$

$\epsilon$-限定 -依存の任意の確率変数系に対して, それを$\epsilon$の場合, 偏りの度合$\delta$が依存の度合$\epsilon$$k$$\delta$-限定 -偏りと看倣すことを考えることもできる.
$\delta$こに対して, どの程度の大きさになるかは知られていない. これは, 今後の興味深い課題の一つである.

謝辞
御討論頂いた丸岡研究室の皆様に感謝致します.

なお, 本研究は一部, 文部省科学研究費奨励研究 (A)(04750293) の援助を受けている.

参考文献[AGHP90] N. Alon, O. Goldreich, J. HSstad, and R. Peralta. Simple constructions of almost k-wize independent random variables. In Proceedings of the $31st$ Annual Symposium on Foundations ofComputer Science, pp. 544-553, 1990.
[LV91]

M. Luby and B. Veli\v{c}kovi\v{c}. On deterministic approximation of DNF. In Proceedings of the $23rd$
Annual $ACM$ Symposium on Theory of Computing, pp. 430-438, 1991.

[NN90]J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. In
Proceedings of the $22nd$ Annual $ACM$ Symposium on Theory of Computing, pp. 213-223, 1990.

[Va179]L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science,Vol. 8, pp. 189-201, 1979.