識別不能

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

情報論的識別不能

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

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

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

例：

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

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

統計的識別不能

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

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

例：

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

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

計算量的識別不能

任意の多項式時間機械 D {\displaystyle D} （識別機(distinguisher)という）と任意の多項式 P {\displaystyle P} に対し、ある k 0 {\displaystyle k_{0}} があって任意の k > k 0 {\displaystyle k>k_{0}} に対し | P r ( D ( X k ) = 1 ) − P r ( D ( Y k ) = 1 ) | < 1 / P ( k ) {\displaystyle |Pr(D(X_{k})=1)-Pr(D(Y_{k})=1)|<1/P(k)} となる時、 { X k } k ∈ N {\displaystyle \{X_{k}\}_{k\in N}} と { Y k } k ∈ N {\displaystyle \{Y_{k}\}_{k\in N}} は計算量的識別不能であるという。

定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。

例： 暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある．


関連項目