計算量的識別不能とは何？わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

識別不能

(計算量的識別不能から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/08 05:23 UTC 版)

ナビゲーションに移動検索に移動

識別不能（しきべつふのう）とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。

情報論的識別不能

$\{X_{k}\}_{k\in N},\{Y_{k}\}_{k\in N}$ を確率変数の族とする。

ある $k_{0}$ があって任意の $k>k_{0}$ に対し $X_{k}$ の従う確率分布と $Y_{k}$ の従う確率分布が同一である時、族 $\{X_{k}\}_{k\in N}$ と $\{Y_{k}\}_{k\in N}$ は情報論的識別不能であるという。

二つの確率変数（の確率分布）が同一であれば、どんなに計算能力があろうとも見分けることができない。つまり、情報論的識別不能は、「どんなに計算能力があろうとも」見分けることができないことを意味する。

例：

確率変数 $X_{k}$ ：公正なコインを $k$ 回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、 $k$ 個の0,1列で表現する。
確率変数 $Y_{k}$ ：公正な2つのコインを $k$ 回ふって、各回に同じ面が出るか、という実験の結果。2つのコインで同じ面が出たら1、異なる面が出たら0、として $k$ 個の0,1列で表現する。

$X_{k}$ と $Y_{k}$ は異なる実験によって得られる確率変数であるが、共に、任意の $k$ ビット列が確率 $1/2^{k}$ で生じる。よって、 $X=\{X_{k}\}_{k}$ と $Y=\{Y_{k}\}_{k}$ は情報論的識別不能である。

統計的識別不能

$A$ 、 $B$ を確率変数とする。 $A$ と $B$ との統計的距離を $\sum _{x\in \{0,1\}^{k}}|Pr(A=x)-Pr(B=x)|$ 　により定義する。 $X_{k}$ と $Y_{k}$ との統計的距離が、 $k$ に対して無視できるとき、すなわち任意の多項式 $P$ に対し、ある $k_{0}$ があって任意の $k>k_{0}$ に対し、 $\sum _{x\in \{0,1\}^{k}}|Pr(X_{k}=x)-Pr(Y_{k}=x)|<1/P(k)$ となる時、族 $\{X_{k}\}_{k\in N}$ と $\{Y_{k}\}_{k\in N}$ は統計的識別不能であるという。

二つの確率変数を見分けたい人が、いずれかの確率変数（の確率分布）によって選ばれた値を次々に観測し続けて、見分けることを考えよう。二つの確率分布が大きく異なる場合、観測値の頻度分布を求めることで、どちらの確率分布であるのかを見分けることができるだろう。逆に、確率分布がほとんど同じ場合、多くの値を観測したとしても見分けはつきにくい。統計的識別不可能は、多項式個の値を観測しても見分けがつかないことを意味する。

例：

確率変数 $X_{k}$ ：公正なコインを $k$ 回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、 $k$ 個の0,1列で表現する。
確率変数 $Z_{k}$ ： $X_{k}$ と同じ実験をするが、 $k$ 回続けて裏が出たら、最初からやり直すという実験の結果。

$Z_{k}$ では、0が $k$ 個並んだものは生じず（ $Pr[Z_{k}=0000...0]=0$ ）、それ以外の $k$ ビット列が確率 $1/(2^{k}-1)$ で生じる。よって、 $X_{k}$ と $Y_{k}$ の統計的距離は $(2^{k}-1)\times |1/2^{k}-1/(2^{k}-1)|+|1/2^{k}-0|=1/2^{k-1}$ である。よって、 $X=\{X_{k}\}_{k}$ と $Z=\{Z_{k}\}_{k}$ は統計的識別不能である。