情報論的識別不能
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/08 05:23 UTC 版)
{ 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}} は情報論的識別不能である。
※この「情報論的識別不能」の解説は、「識別不能」の解説の一部です。
「情報論的識別不能」を含む「識別不能」の記事については、「識別不能」の概要を参照ください。
- 情報論的識別不能のページへのリンク
