| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 1 |
| 発表日時 | 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 |
[研究会発表申込システムのトップページに戻る]