文献

J-GLOBAL ID：201702229875240878   整理番号：17A1357483

多次元コストを持つMarkov連鎖における分位数計算【Powered by NICT】

Computing quantiles in Markov chains with multi-dimensional costs

著者 (3件)： Haase Christoph (University of Oxford, UK) ,  Kiefer Stefan (University of Oxford, UK) ,  Lohrey Markus (Universitaet Siegen, Germany)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： LICS  ページ： 1-12  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： エネルギーやコストのような量を蓄積する確率的システムは自然にコストが,その転移は数値コストのベクトルで標識されるMarkov連鎖によりモデル化した。全蓄積コストの確率分布に及ぼす計算情報は,このモデルにおける基本的問題である。本論文では,いわゆるコスト問題,全コストの分位数,平均コストや大きなコストの確率を計算することであることを研究した。そのような確率は常に計算可能なまたは有理もか未解決の問題であるが,確率を近似する任意の精度で可能にするアルゴリズムを提案した。アルゴリズムを述べ,実装し,有向グラフにおけるオイラー回路の数を計算する効率的にいわゆるBEST定理のようなグラフ理論からの強い結果を利用することも簡単であった。さらに,提案アルゴリズムは,コスト問題の決定版は計数階層,後者を含み,PSPACEに含まれていることを多項式時間階層への計数アナログであることを示すことができた。最後に,それを実験的に評価することにより,提案アルゴリズムの適用性を示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 適応性 ,  アルゴリズム ,  ベクトル ,  有向グラフ ,  *高次元 ,  モデリング ,  *Markov連鎖 ,  アナログ系 ,  確率分布 ,  グラフ理論
準シソーラス用語： 多項式時間 ,  計数 ,  *位数 , 【Automatic Indexing@JST】

分類 (3件)： 交通調査  (TB01031B) ,  計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (3件)： 多次元 ,  Markov連鎖 ,  計算