識別不能

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2011年2月18日 (金) 19:37時点における219.96.254.43 (トーク)による版 (情報論的識別不能)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

識別不能(しきべつふのう)

情報論的識別不能

{Xk}k∈N、{Yk}k∈N確率変数とする。

あるk0があって任意のk>k0に対しXkの従う確率分布とYkの従う確率分布が同一である時、族{Xk}k∈Nと{Yk}k∈N情報論的識別不能であるという。

統計的識別不能

A、Bを確率変数とする。 AとBとの統計的距離を∑xはkビットのビット列|Pr(A=x)-Pr(B=x)| により定義する。 XkとYkとの統計的距離がkに対して無視できるとき、 すなわち任意の多項式Pに対し、あるk0があって任意のk>k0に対し、∑xはkビットのビット列|Pr(Xk=x)-Pr(Yk=x)|<1/P(k)となる時、族{Xk}k∈Nと{Yk}k∈N統計的識別不能であるという。

計算量的識別不能

任意の多項式時間機械D (識別機(distinguisher)という)と任意の多項式Pに対し、あるk0があって任意のk>k0に対し |Pr(D(Xk)=1)-Pr(D(Yk)=1)|<1/P(k)となる時、XkとYk計算量的識別不能であるという。


関連項目