連結グラフにおけるランダムウォーク

こんにちは.今日はBlomの確率論へようこそ(Problems and Snapshots from the World of Probability)

Problems and Snapshots from the World of Probability

確率論へようこそ (シュプリンガー数学リーディングス)

 で掲載されていた連結グラフにおけるランダムウォークについてお話します.

連結なグラフ上でランダムウォークがなされた時にすべての頂点を訪れる平均時間を全訪問時間という

この全訪問時間がグラフの性質によって変わっていくのか調べたりしていくのがこの本での課題です

このわだいはThe American Mathematical Monthly の問題6556に掲載されています.

http://www.jstor.org/discover/10.2307/2324860?uid=3738328&uid=2&uid=4&sid=21104776511391

この本でこの話題について確率論の初等的な（高校程度）知識を用いてお話ししているのですがこれが難しい...（きちんとした確率論の知識があった人が読むほうが概要がつかめて面白い気がします）

このpdfに色々掲載されていますが一つ目のpdfはなんと情報科での講究録

グラフ理論と確率論のつながりがあることがわかる面白い話題だと思います.