学生の研究指導をしている中で、こんな問題に行き当たりました。
色々考えているうちに、自分の中で整理は出来てきたのですが、このような整理でよいのかどうか自信が持てずにいます。
(私が知らないだけで、定番っぽい問題な気もするのですが・・・)
なお、この問題は学生の研究の本題とは直接関係ありませんので、その点はお気になさらず。
頂点集合 V={1,2,3,4,5,6} の完全グラフ G を考えます。頂点数はさして問題ではないので一般に n=|V| としておきます。
各辺には距離 d(i,j) が設定されています。
頂点 i から頂点 j へと条件付き確率 p(j|i) で遷移することを考えます。初期状態 t=0 は確率 p(i) で決まります。
t=0 から初めて、頂点間を t=T ステップ遷移することを考えたとき、そのパスの距離の総和は期待値は?
という問題です。
複雑な計算になりそうなので、T=1,2 あたりから計算してみます。
T=1 のとき:
t=0 で確率 p(i) で頂点 i が選ばれます。
そこから t=1 のとき、頂点 j に条件付き確率 p(j|i) で遷移します。
したがって、確率 p(i)p(j|i) でパス i→j を通ります。そのパスの距離は d(i,j) なので、パスの距離の総和の期待値は
n∑j=1n∑i=1p(i)p(j|i)d(i,j)
となります。
T=2 のとき:
t=0 で確率 p(i) で頂点 i が選ばれます。
t=1 のとき、頂点 j に条件付き確率 p(j|i) で遷移します。
t=2 のとき、頂点 k に条件付き確率 p(k|j) で遷移します。
したがって、確率 p(i)p(j|i)p(k|j) でパス i→j→k を通ります。そのパスの距離は d(i,j)+d(j,k) なので、パスの距離の総和の期待値は
n∑k=1n∑j=1n∑i=1p(i)p(j|i)p(k|j)(d(i,j)+d(j,k))
となります。
このまま続けていくと、どんどん変数が増えて大変なので、次のように書き換えます:
n∑i2=1n∑i1=1n∑i0=1p(i0)p(i1|i0)p(i2|i1)(d(i0,i1)+d(i1,i2))=n∑i2=1n∑i1=1n∑i0=1{p(i0)2∏t=1p(it|it−1)(2∑t=1d(it−1,it))}
一般に T ステップ遷移した際のパスの距離の総和の期待値は
∑(i0,i1,…,iT)∈VT+1{p(i0)T∏t=1p(it|it−1)(T∑t=1d(it−1,it))}
となります。
・・・たぶんこれでいいと思うんですが、もうちょっとすっきりしないですかね?
もう少しすっきりできる?
と、ここまで考えて、もうちょっと整理できそうな気がしました。
今考えている問題は、長さ T のパス w=i0→i1→⋯→iT の距離の総和の期待値を考える問題でした。
パス w=i0→i1→⋯→iT の生起確率を p(w) とすると、これは
p(w):=p(i0,i1,⋯,iT)=p(i0)T∏t=1p(it|it−1)
です。そのパス w の距離の総和を d(w) で表すと、これは
d(w):=T∑t=1d(it−1,it)
となります。
以上から、長さ T のパスの距離の総和の期待値は
∑wp(w)d(w)
ただし、総和記号は長さ T のパス w をわたる。と単に表してもよさそうです。
グラフィカルモデルとか、そういう文脈でこういう問題たくさん出てきそうな気がするんですが、どうやって表すんですかね?
知っている方がいましたら教えてください。