コスト付きKolmogorov複雑量と確率過程
スポンサーリンク
概要
- 論文の詳細を見る
計算可能な確率過程{X_i}^∞_<i=1>において, 長さに基づく通常の語頭Kolmogorov複雑量の期待値とShannonエントロピーがたかだか定数しか違わないことは, Leung-Yan-Cheong and Coverが最初に示した[6, 定理7]. 本論文では, 長さを計算可能な実数値コストに一般化しても同種の関係が成り立つことを示す. この種の定理の証明には, コスト付きShannon-Fano-Elias符号の復号アルゴリズムを実数の計算可能性の定義に基づいて厳密化することが不可欠であるが, この厳密化した復号アルゴリズムを与える. 次に, 情報理論では符号化とある意味で双対的と考えられている乱数生成アルゴリズムを同様に厳密化したものを与え, 語頭チューリング機械のコスト付き確率と計算可能な確率過程{X_i}^∞_<i=1>の関係を論じる.
- 社団法人電子情報通信学会の論文
- 1997-03-25
著者
関連論文
- 情報理論と大偏差原理 (大偏差原理とその応用--注目の確率論第3の原理)
- 情報源分離問題に対する代数的オフラインアルゴリズム
- Peres 法によるユニバーサル乱数生成アルゴリズムの拡張とその性能評価
- 指数型分布族の次数推定方式における誤り確率の挙動について
- [招待論文]情報スペクトル : あれこれ(若手研究者のための招待講演)
- 情報スペクトル : あれこれ
- Merhav 法による指数型分布族の次数推定について
- かく乱母数を含む場合のMDL基準の構築と空間図形モデル推定問題への応用
- 一般情報源に対する可変長符号の最適なオーバーフロー確率とアンダーフロー確率
- 一般情報源に対する可変長符号の最適なオーバーフロー確率とアンダーフロー確率
- 一般情報源に対する可変長符号の最適なオーバーフロー確率とアンダーフロー確率
- データ圧縮・MDL原理・チューリング機械 (特集 今日の応用数理)
- シャノン理論50年 : 回顧と展望(情報理論50年の歩みと21世紀への展望 : シャノンから50年)
- 特集「データ圧縮」にあたって
- コスト付きKolmogorov複雑量と確率過程
- 多重アクセス通信路の通信路容量域の計算アルゴリズムについて
- 多重アクセス通信路の通信路容量域の計算アルゴリズムについて
- 多重アクセス通信路の通信路容量域の計算アルゴリズムについて
- 仮設検定・母数推定・デ-タ圧縮の幾何 (情報幾何--情報にひそむ微分幾何的構造)
- 情報圧縮とはなにか (情報圧縮--モデルの推定)
- 多元情報源に対する符号化定理 (情報理論--シャノン以後の展開)