並列反復定理

同義語:parallel repetition theoremRazの並列反復定理

概要

並列反復定理(parallel repetition theorem)とは、2 人の参加者が通信せずに 1 回ずつ答える協力ゲームを $k$ 個同時に独立に行うとき、値(勝率の最大値)が $1$ 未満のゲームなら、全部に勝つ確率の最大値が $k$ について指数的に減る、という Raz の定理である。Holenstein の形では、値 $v$ のゲームの $k$ 回の反復の値は $(1-(1-v)^3/6000)^{k/\log_2(|A||B|)}$ 以下になる。各参加者は問いを全部見て答えられるので値はちょうど $k$ 乗にはならず、2 回の反復で値が減らない例もあり、証明の核は独立な変数を事象で条件付けたときの情報量の補題である。射影ゲームでは答えの個数によらない評価が成り立ち(Rao)、この定理はギャップを増幅して近似の困難さを導く道具として使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: PCP定理, Kullback–Leiblerダイバージェンス

並列反復定理(parallel repetition theorem)は、2 人の参加者が通信せずに 1 回ずつ答える協力ゲームを $k$ 個同時に独立に行い、全部に勝つ確率の最大値が $k$ について指数的に減ることを述べる定理である。もとのゲームの勝率の最大値(値)が $1$ 未満なら、$k$ 回の並列反復の値は $c^{k}$($c< 1$ は値と答えの個数で決まる定数)以下になる。Raz が 1998 年に示した(Raz98)。
$k$ 個のゲームを 1 つずつ順に行うなら値は $k$ 乗になる。ところが並列では、各参加者は $k$ 個の問いを全部見てから答えるので、座標をまたいだ答え方ができる。実際、2 回の並列反復で値がまったく減らないゲームがある(ex-pr-fortnow)。並列反復定理は、それでも値が指数的に減ることを保証する。2 人の証明者による対話証明の誤りの確率を、問いと答えのやりとりを 1 回に保ったまま下げる道具であり、PCP定理 から近似の困難さを導く議論で中心的に使われる(Rao08 pp. 1–2)。
この記事では、値の基本の不等式(prop-pr-basic)と、値が減らない例(ex-pr-fortnow)を証明し、主定理(thm-pr-main)の証明の柱となる情報量の補題(lem-pr-info)を証明する。主定理の残りの部分と、射影ゲームの改良(thm-pr-projection)は引用する。

2 人 1 回のゲーム

ゲームと値

2 人 1 回のゲーム $G$ とは、有限集合 $X,Y,A,B$、$X\times Y$ 上の確率分布 $\mu$、判定 $V\colon X\times Y\times A\times B\to\{0,1\}$ の組である。審判が $(x,y)\sim\mu$ を選んで $x$ を Alice に、$y$ を Bob に送り、2 人は通信せずに $a\in A$、$b\in B$ を答え、$V(x,y,a,b)=1$ なら勝つ。写像の組 $(\alpha\colon X\to A,\ \beta\colon Y\to B)$ を 戦略 といい、その勝率 $\Pr_{(x,y)\sim\mu}[V(x,y,\alpha(x),\beta(y))=1]$ の最大値を $G$ の 値 $\mathrm{val}(G)$ という(Hol09 Definition 1、p. 3)。

2 人が共有の乱数 $r$ を使ってもよいとしても値は変わらない。勝率は $r$ についての平均なので、勝率が平均以上になる $r$ を 1 つ固定すれば、乱数を使わない戦略で同じ勝率以上が得られるからである(Hol09 (3)、p. 4)。各自の乱数は共有の乱数の特別な場合である。

並列反復

$G$ の $k$ 回の並列反復 $G^{k}$ とは、問いの集合 $X^k,Y^k$、答えの集合 $A^k,B^k$、分布 $\mu^{\otimes k}$($k$ 個の独立な $(x_i,y_i)\sim\mu$)、判定 $V^{k}(x,y,a,b)=\prod_{i=1}^kV(x_i,y_i,a_i,b_i)$ のゲームである(Hol09 Definition 2、p. 4)。

$G^k$ の戦略では、Alice の第 $i$ 座標の答え $a_i$ は $x_1,\dots,x_k$ 全体に依存してよい。座標ごとに $G$ の戦略を当てる 積の戦略 は特別な場合である。

値の基本の不等式

$k,l\ge1$ とする。

  1. $\mathrm{val}(G)^k\le\mathrm{val}(G^k)\le\mathrm{val}(G)$。
  2. $\mathrm{val}(G^{k+l})\ge\mathrm{val}(G^k)\,\mathrm{val}(G^l)$。
  3. $\mathrm{val}(G^k)=1$ と $\mathrm{val}(G)=1$ は同値である。
積の戦略と、ほかの座標を乱数で埋める戦略

2:$G^{k+l}$ を最初の $k$ 座標と残りの $l$ 座標に分け、それぞれに $G^k$、$G^l$ の最適な戦略を当てる。2 つの部分の問いは独立なので、両方に勝つ確率は値の積である。これを繰り返すと 1 の左の不等式が出る。
1 の右:$G^k$ の戦略 $(\alpha,\beta)$ をとる。$G$ の戦略を次のように作る。2 人は共有の乱数で $(x_2,y_2),\dots,(x_k,y_k)\sim\mu^{\otimes(k-1)}$ を選ぶ。問い $x$ を受けた Alice は $\alpha(x,x_2,\dots,x_k)$ の第 $1$ 座標を、$y$ を受けた Bob は $\beta(y,y_2,\dots,y_k)$ の第 $1$ 座標を答える。$(x,y)\sim\mu$ と共有の乱数を合わせた分布は $\mu^{\otimes k}$ なので、この戦略の勝率は $G^k$ で $(\alpha,\beta)$ が第 $1$ 座標に勝つ確率に等しく、全座標に勝つ確率以上である。共有の乱数は値を変えないので $\mathrm{val}(G)\ge\mathrm{val}(G^k)$ である。
3:1 から直ちに従う。$\square$

勝率が $1$ の戦略は全座標で勝つので、$\mathrm{val}(G)=1$ のゲームの反復はいくら繰り返しても誤りを減らさない。問題は $\mathrm{val}(G)< 1$ のときの減り方である。

値が減らない例

2 回の反復で値が減らないゲーム

$X=Y=A=B=\{0,1\}$、$\mu$ を $(0,0),(0,1),(1,0)$ の上の一様分布とし、$V(x,y,a,b)=1\iff(x\vee a)\ne(y\vee b)$ とするゲームを $F$ とする($\vee$ は論理和)。このとき
$$ \mathrm{val}(F)=\mathrm{val}(F^2)=\frac23>\frac49=\mathrm{val}(F)^2 $$
である(Fortnow の例の変形。Hol09 Appendix A、pp. 24–25)。

言葉で言えば、両者が $0$ を受けたらちょうど 1 人が $1$ を答え、一方が $1$ を受けたら他方は $0$ を答えなければならない。

答えを座標の間で入れ替える

$\mathrm{val}(F)=2/3$. 戦略は $\alpha(0),\beta(0)\in\{0,1\}$ だけで決まる($1$ を受けたときの答えは判定に効かない)。$\alpha(0)=\beta(0)$ なら問い $(0,0)$ で負ける。$\alpha(0)=1$ なら問い $(0,1)$ で $x\vee a=1=y\vee b$ となり負ける。$\beta(0)=1$ なら同様に $(1,0)$ で負ける。よって勝率は $2/3$ 以下で、$\alpha(0)=\beta(0)=0$ なら $(0,1),(1,0)$ で勝つので $2/3$ である。
$\mathrm{val}(F^2)\ge2/3$. Alice は $(x_1,x_2)$ に対して $(a_1,a_2)=(x_2,x_1)$ を、Bob は $(b_1,b_2)=(y_2,y_1)$ を答える。第 $1$ 座標の勝つ条件は $(x_1\vee x_2)\ne(y_1\vee y_2)$、第 $2$ 座標の条件は $(x_2\vee x_1)\ne(y_2\vee y_1)$ で、同じ条件である。$s:=x_1\vee x_2$、$t:=y_1\vee y_2$ とおく。$9$ 通りの問いのうち $s=t$ となるのは、$(x_1,y_1)=(x_2,y_2)=(0,0)$ のとき($s=t=0$)と、$\{(x_1,y_1),(x_2,y_2)\}=\{(0,1),(1,0)\}$ のとき($s=t=1$、$2$ 通り)の $3$ 通りだけなので、両座標に勝つ確率は $6/9=2/3$ である。
上界は prop-pr-basic の 1 による。$\square$

この例では、各座標の勝敗が完全に相関するように答えを選んでいる。座標ごとに独立に勝つ必要はない、という点が並列反復の難しさである。

並列反復定理

並列反復定理(Raz、Holenstein の形)

$G$ を値 $v< 1$ の 2 人 1 回のゲームで、$\lvert A\rvert\lvert B\rvert\ge2$ のものとする。すべての $k\ge1$ について
$$ \mathrm{val}(G^k)\le\Bigl(1-\frac{(1-v)^3}{6000}\Bigr)^{k/\log_2(|A||B|)} $$
である(Hol09 Theorem 4、p. 4。Raz98 は指数が $k/\log(|A||B|)$ の定数倍で、底が $v$ だけで決まる $1$ 未満の定数である形を示した。Hol09 p. 1)。

必要な反復の回数

$\lvert A\rvert\lvert B\rvert\ge2$、$\mathrm{val}(G)\le1-\varepsilon$($0< \varepsilon\le1$)、$0< \delta< 1$ とする。
$$ k\ge\frac{6000\,\log_2(|A||B|)\,\log(1/\delta)}{\varepsilon^3} $$
なら $\mathrm{val}(G^k)\le\delta$ である($\log$ は自然対数)。

指数関数で上から抑える

$v:=\mathrm{val}(G)$ とすると $1-v\ge\varepsilon$ なので、thm-pr-main の底は $1-\varepsilon^3/6000$ 以下である。$1-t\le e^{-t}$ から
$$ \mathrm{val}(G^k)\le\exp\Bigl(-\frac{\varepsilon^3}{6000}\cdot\frac{k}{\log_2(|A||B|)}\Bigr)\le\exp(-\log(1/\delta))=\delta.\qquad\square $$

$G^k$ の問いの集合は $X^k\times Y^k$、答えの集合は $A^k\times B^k$ で、ゲームの記述は $k$ について指数的に大きくなる。そのため近似の困難さの議論では $k$ を定数にとり、cor-pr-rounds で決まる定数 $\delta$ までしか誤りを下げない。$k$ を入力の大きさとともに増やすと、還元の時間は多項式でなくなる(WS11 pp. 428–429。そこでは $k$ を $\log$ の冪にとって、準多項式時間の仮定のもとでのより強い困難さを導いている)。
指数の $\log(|A||B|)$ は答えの長さで、これを除くことは一般にはできない。Feige と Verbitsky は、$\Theta(\log s/\log\log s)$ 回の反復でも値が $3/4$ 以下から $1/8$ 以上までしか減らないゲームを、無限に多くの答えの個数 $s$ について作った(Hol09 p. 2)。

証明の柱:条件付けで分布はあまり変わらない

主定理の証明では、勝つ座標を 1 つずつ選びながら、「すでに選んだ座標で勝った」という事象のもとで、まだ選んでいない座標の問いの分布がもとの分布 $\mu$ に近いことを使う。その核心が次の補題である(Hol09 Lemma 5、pp. 6–7)。対数は自然対数とし、全変動距離 $\delta$ と相対エントロピー $D$ は Kullback–Leiblerダイバージェンス の記号に従う。

独立な変数を事象で条件付ける

$U_1,\dots,U_k$ を有限集合に値をとる独立な確率変数とし、$W$ を $\Pr[W]>0$ の事象とする。$U_j$ の分布を $P_{U_j}$、$W$ のもとでの条件付き分布を $P_{U_j|W}$ と書くと、
$$ \sum_{j=1}^kD(P_{U_j|W}\|P_{U_j})\le\log\frac1{\Pr[W]},\qquad\sum_{j=1}^k\delta(P_{U_j|W},P_{U_j})^2\le\frac12\log\frac1{\Pr[W]} $$
である。

連鎖律と凸性

$U=(U_1,\dots,U_k)$ の分布を $Q=P_{U_1}\otimes\cdots\otimes P_{U_k}$、$W$ のもとでの分布を $P$ とする。$P(u)=Q(u)\Pr[W\mid U=u]/\Pr[W]$ なので
$$ D(P\|Q)=\sum_uP(u)\log\frac{\Pr[W\mid U=u]}{\Pr[W]}\le\log\frac1{\Pr[W]} $$
である($\Pr[W\mid U=u]\le1$)。次に $\sum_jD(P_j\|Q_j)\le D(P\|Q)$($P_j,Q_j$ は第 $j$ 成分の周辺分布)を示す。$Q$ は積の分布なので、$U_{< j}=(U_1,\dots,U_{j-1})$ を与えたときの $Q$ の第 $j$ 成分の条件付き分布は $Q_j$ である。Kullback–Leiblerダイバージェンス の定理「連鎖律」を $j=1,\dots,k$ と繰り返し当てると
$$ D(P\|Q)=\sum_{j=1}^k\mathbb E_{u_{< j}\sim P}\,D\bigl(P(U_j\in\cdot\mid U_{< j}=u_{< j})\,\big\|\,Q_j\bigr) $$
となる。$P_j$ は条件付き分布 $P(U_j\in\cdot\mid U_{< j}=u_{< j})$ の $u_{< j}$ についての平均なので、$D$ の第 1 引数についての凸性(同記事の定理「同時凸性」)から、各項は $D(P_j\|Q_j)$ 以上である。よって第 1 の不等式が成り立つ。第 2 の不等式は各項に Pinsker の不等式 $D\ge2\delta^2$(同記事の定理「Pinsker の不等式」)を当てて得る。$\square$

$k$ 個の座標の平均をとると、$\delta(P_{U_j|W},P_{U_j})\le\sqrt{\log(1/\Pr[W])/(2k)}$ となる座標 $j$ がある。$W$ が「選んだ $m$ 個の座標で勝つ」という事象なら、$\Pr[W]$ が小さくない限り、残りの大多数の座標の問いはほぼ $\mu$ に従う。

主定理の証明の残りの筋を開く

Hol09 §§3–7 の証明は次の筋である。戦略を固定し、$W_i$ を第 $i$ 座標に勝つ事象とする。座標 $i_1,\dots,i_m$ を選んで $W:=W_{i_1}\cap\cdots\cap W_{i_m}$ とおき、$\Pr[W]$ が十分小さければ終わる。そうでなければ、選んでいない座標 $j$ で $\Pr[W_j\mid W]\le v+\eta$ となるものを見つけて $i_{m+1}:=j$ とする。これを $m$ が $k/\log(|A||B|)$ の定数倍になるまで続けると主定理が出る。

$j$ を見つけるには、$W$ のもとで、問い $(x_j,y_j)$ を受けた 2 人が、ほかの座標の問いと選んだ座標の答えを、通信せずに(共有の乱数だけで)ほぼ正しい分布で生成できることを示す。そうできれば、$W$ のもとでの第 $j$ 座標の勝率は $G$ の 1 つの戦略の勝率に近く、$v$ を大きくは超えない。lem-pr-info に、選んだ座標の答えを付加情報として加えた形(Hol09 Corollary 6、p. 8)を当てると、付加情報の分だけ $m\log(|A||B|)$ の項が加わる。指数に $\log(|A||B|)$ が現れるのはこのためである。2 人がそれぞれ少し異なる分布を知っているとき、共有の乱数で同じ値を高い確率で引く「相関のある抽出」の補題(Hol09 Lemma 8)が、Raz の証明の長い部分を置き換える。

射影ゲームと強い並列反復

各問い $(x,y)$ に写像 $f_{xy}\colon A\to B$ があり、$V(x,y,a,b)=1\iff f_{xy}(a)=b$ となるゲームを 射影ゲーム という。$f_{xy}$ がすべて全単射のものを 一意ゲーム という(Rao08 pp. 1–2)。

射影ゲームの並列反復(Rao)

ある普遍定数 $\alpha>0$ があって、値が $1-\varepsilon$ 以下の射影ゲーム $G$ と $k\ge\log(1/\varepsilon)/(\alpha\varepsilon^2)$ について $\mathrm{val}(G^k)\le(1-\varepsilon)^{\alpha\varepsilon k}$ である(Rao08 Theorem 1.4、p. 3)。

右辺はおよそ $(1-\varepsilon^2)^{\alpha k}$ で、答えの個数によらない。値 $1-\varepsilon$ のゲームについて $\mathrm{val}(G^k)\le(1-\varepsilon)^{ck}$ となること(強い並列反復)が期待されたこともあったが、Raz は奇数長の閉路の上の最大カットのゲーム(一意ゲームである)で $\mathrm{val}(G^k)\ge(1-\varepsilon^2)^{O(k)}$ となることを示し、これを否定した(Raz11、Rao08 p. 3)。したがって thm-pr-projection の $\varepsilon^2$ の形は本質的に改良できない。

応用

ギャップの増幅. PCP定理 から、ある定数 $\varepsilon_0>0$ と答えの個数について、値が $1$ の射影ゲームと値が $1-\varepsilon_0$ 以下の射影ゲームを区別することが NP困難であることが従う。射影ゲームの反復は射影ゲームで、値 $1$ は保たれる。thm-pr-main で反復の回数 $k$ を定数にとれば、どの定数 $\varepsilon>0$ についても、値が $1$ のものと $\varepsilon$ 以下のものの区別が NP困難になる(Rao08 p. 2)。この区別の問題は 2 部グラフの上のラベル付けの問題として述べられ、多くの近似困難性の証明の出発点になる(WS11 §16.4、Theorem 16.28 p. 428 は同じ増幅をこの形で述べる)。
Unique Games 予想. 一意ゲームの反復は一意ゲームである。thm-pr-projection を当てると、Unique Games予想 は「どの $\varepsilon,\delta>0$ についても、答えの個数を十分大きくとれば、値が $1-\varepsilon^2$ 以上の一意ゲームと $1-\varepsilon^{1-\delta}$ 以下のものの区別が NP困難である」と同値になる(Rao08 Conjecture 1.5、p. 4)。
量子もつれと反復. 参加者が量子もつれを共有する場合にも反復の値の評価が研究されている。Connesの埋め込み問題 を否定した $\mathrm{MIP}^*=\mathrm{RE}$ の証明は、各参加者の問いを確率 $1/2$ で特別な記号に替える「錨つき」の変形を施したゲームについて、量子もつれを許した値の並列反復定理を使う(JNVWY20 §11・Theorem 11.1。もとは BVY22 による)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなる結論
$G^k$ の戦略を積の戦略に限ることex-pr-fortnow$\mathrm{val}(G^k)=\mathrm{val}(G)^k$($G=F$、$k=2$)
thm-pr-main で $v< 1$ であること値 $1$ のゲーム$\mathrm{val}(G^k)\to0$(prop-pr-basic の 3 により値は $1$ のまま)
thm-pr-main の指数の $\log(\lvert A\rvert\lvert B\rvert)$ を除くFeige–Verbitsky のゲーム答えの個数によらない指数的な減少
thm-pr-projection の指数を $\varepsilon^2$ から $\varepsilon$ に強める奇数長の閉路のゲーム(Raz)$\mathrm{val}(G^k)\le(1-\varepsilon)^{ck}$
表の確かめを開く

1 行目:積の戦略では各座標の勝敗が独立なので、勝率は座標ごとの勝率の積で、その最大値は $\mathrm{val}(G)^k$ である。座標をまたぐ戦略を許すと、ex-pr-fortnow のとおり $\mathrm{val}(F^2)=\frac23>\frac49=\mathrm{val}(F)^2$ となる。2 行目:たとえば $V\equiv1$ のゲームは値 $1$ で、どの $k$ でも $\mathrm{val}(G^k)=1$ である。3 行目と 4 行目は引用である(Hol09 p. 2、Rao08 p. 3)。

関連項目

参考文献

[5]
Zhengfeng Ji; Anand Natarajan; Thomas Vidick; John Wright; Henry Yuen, MIP* = RE, arXiv:2001.04383(v1 2020、v4 2026), 2020, arXiv 版 v4 の §11・Theorem 11.1(p. 177)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する