お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2009-05-26 10:05
メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
野中良哲小野廣隆定兼邦彦山下雅史九大COMP2009-10
抄録 (和) グラフ上のランダムウォークとは,グラフ上の頂点をトークンがランダムに遷移していくモデルである.全ての隣接頂点に対して等確率で遷移するものを標準ランダムウォークと呼ぶ.標準ランダムウォークに関しては,頂点数$n$のグラフに対して,到達時間と全訪問時間がともに$O(n^3)$であることが知られている.本発表では,標準ランダムウォークに対してメトロポリス-ヘイスティングスアルゴリズムを適用したランダムウォークであるメトロポリスウォークについて,到達時間が$O(fn^2)$,全訪問時間が$O(fn^2 log n)$であることを示す.ここで,$f$はメトロポリスヘイスティングスアルゴリズムによって実現される定常分布の最大値と最小値の比であり,$f$の小さい定常分布を選ぶことで標準ランダムウォークに比べて高速なランダムウォークが実現される. 
(英) andom walks on finite graphs are random token circulation on graphs. Random walks such that token moves to adjacent vertices with uniformprobability are called standard random walk. For any graph with $n$ vertices, the hitting time and the cover times of standard random walk are bounded by $O(n^3)$. In this report, we would like to show the hitting and the cover times of Metropolis walks are bounded by $O(fn^2)$ and $O(fn^2\log n)$ respectively. Where, $f$ is the maximum ratio of stationary distribution.
キーワード (和) ランダムウォーク / 到達時間 / 全訪問時間 / メトロポリス・ヘイスティングスアルゴリズム / マルコフ連鎖 / / /  
(英) random walk / hitting time / cover time / Metropolis-Hastings algorithm / Markov chain / / /  
文献情報 信学技報, vol. 109, no. 54, COMP2009-10, pp. 9-12, 2009年5月.
資料番号 COMP2009-10 
発行日 2009-05-19 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2009-10

研究会情報
研究会 COMP  
開催期間 2009-05-26 - 2009-05-26 
開催地(和) 埼玉大学 
開催地(英) Saitama Univ. 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2009-05-COMP 
本文の言語 日本語 
タイトル(和) メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界 
サブタイトル(和)  
タイトル(英) A Tight Upper Bound on the Hitting and the Cover times of Metropolis Walks 
サブタイトル(英)  
キーワード(1)(和/英) ランダムウォーク / random walk  
キーワード(2)(和/英) 到達時間 / hitting time  
キーワード(3)(和/英) 全訪問時間 / cover time  
キーワード(4)(和/英) メトロポリス・ヘイスティングスアルゴリズム / Metropolis-Hastings algorithm  
キーワード(5)(和/英) マルコフ連鎖 / Markov chain  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 野中 良哲 / Yoshiaki Nonaka / ノナカ ヨシアキ
第1著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ)
第2著者 氏名(和/英/ヨミ) 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ
第2著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ)
第3著者 氏名(和/英/ヨミ) 定兼 邦彦 / Kunihiko Sadakane / サダカネ クニヒコ
第3著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ)
第4著者 氏名(和/英/ヨミ) 山下 雅史 / Masafumi Yamashita / ヤマシタ マサフミ
第4著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2009-05-26 10:05:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2009-10 
巻番号(vol) IEICE-109 
号番号(no) no.54 
ページ範囲 pp.9-12 
ページ数 IEICE-4 
発行日 IEICE-COMP-2009-05-19 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会