相談記事：こんな感じであってますかね？

学生の研究指導をしている中で、こんな問題に行き当たりました。
色々考えているうちに、自分の中で整理は出来てきたのですが、このような整理でよいのかどうか自信が持てずにいます。
（私が知らないだけで、定番っぽい問題な気もするのですが・・・）

なお、この問題は学生の研究の本題とは直接関係ありませんので、その点はお気になさらず。

頂点集合 $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\to j$ を通ります。そのパスの距離は $d(i, j)$ なので、パスの距離の総和の期待値は

$\displaystyle \sum_{j = 1}^{n} \sum_{i = 1}^{n} p(i) p(j | i) d(i, j) \tag{1}$

となります。

$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\to j \to k$ を通ります。そのパスの距離は $d(i, j) + d(j, k)$ なので、パスの距離の総和の期待値は

$\displaystyle \sum_{k = 1}^{n} \sum_{j = 1}^{n} \sum_{i = 1}^{n} p(i) p(j | i) p(k | j) \left(d(i, j) + d(j, k) \right) \tag{2}$

となります。

このまま続けていくと、どんどん変数が増えて大変なので、次のように書き換えます：

$\displaystyle \begin{align*} &\sum_{i_2 = 1}^{n} \sum_{i_1 = 1}^{n} \sum_{i_0 = 1}^{n} p(i_0) p(i_1 | i_0) p(i_2 | i_1) \left(d(i_0, i_1) + d(i_1, i_2) \right) \\ &= \sum_{i_2 = 1}^{n} \sum_{i_1 = 1}^{n} \sum_{i_0 = 1}^{n} \left\{ p(i_0) \prod_{t=1}^{2} p(i_{t} | i_{t-1}) \left(\sum_{t=1}^{2} d(i_{t-1}, i_t) \right) \right\} \end{align*}$

一般に $T$ ステップ遷移した際のパスの距離の総和の期待値は

$\displaystyle \sum_{(i_0, i_1, \ldots, i_T) \in V^{T+1}} \left\{ p(i_0) \prod_{t=1}^{T} p(i_{t} | i_{t-1}) \left(\sum_{t=1}^{T} d(i_{t-1}, i_t) \right) \right\} \tag{3}$