エルゴード理論の計算機工学への応用

点击翻译按钮获取中文摘要

本年度は主に次の2つのことを行った。1.有限グラフ上の確率的局所多数決問題における平均合意時間の研究2.確率的ネットワークにおける最短路の調査1.については有限グラフにおいて局所的な多数決を行い、自分の意見の更新れを確率的に決める方法を固定して、それについての平均合意時間について研究した。既に得られていたオーダに関する一般論を具体的におしすすめて、初期状態を見ただけで判断できるような評価式を得ることに成功した。しかし、それはまだタイトな評価とは言えないので、まだまだ改良の余地はある。さらに平均合意時間だけではなくて、合意するまでの分布も調べる必要があるが、今のところは解析が難解で今後の課題となっている。2.は具体的には次のような問題を考えている:「各枝に確率的な重みを持ったサイクルをもたないネットワークにおいて入口と出口が一点ずつあるとする。このとき、入口から出口までのパスの重みの最小のものと最大のものの分布を調べよ」一般のグラフについての考察は困難なので、特殊なグラフについて調査している。手段としてはネットワーク理論の既存の結果や極値理論や順序統計学を用いた結果を用いる。なお、この研究は九州大学システム情報科学研究院、山下雅史氏のグループとの共同研究であり、LSIの設計応用面から見ても有用な研究であると思われるが、まだまだ発展途上の話題である。