More generally, you could ask this for any irreducible Markov chain and any starting state. For each nonempty set S of vertices not containing the starting state $s_0$, let $T_S$ be the time (in steps) it takes to reach S (i.e. if $X_t$ is the state after $t$ steps, the least $t$ such that $X_t \in S$). Then the expected time to visit all states is $\sum_S (-1)^{|S|-1} E[T_S]$. Each $E[T_S]$ is straightforward to calculate: if $P$ is the transition matrix, $P_{S^c}$ the submatrix for rows and columns not in $S$, and $I_{S^c}$ the corresponding submatrix of the identity matrix, $E[T_S] = \sum_{j \in S^c} ((I_{S^c} - P_{S^c})^{-1})_{s_0,j}$. For your problem I get a final answer of 231978/6651996/95 = 21.01052632.
|
2 | fixed result as per OP's comment | ||
|
|
||||
|
|
1 |
|
||
|
More generally, you could ask this for any irreducible Markov chain and any starting state. For each nonempty set S of vertices not containing the starting state $s_0$, let $T_S$ be the time (in steps) it takes to reach S (i.e. if $X_t$ is the state after $t$ steps, the least $t$ such that $X_t \in S$). Then the expected time to visit all states is $\sum_S (-1)^{|S|-1} E[T_S]$. Each $E[T_S]$ is straightforward to calculate: if $P$ is the transition matrix, $P_{S^c}$ the submatrix for rows and columns not in $S$, and $I_{S^c}$ the corresponding submatrix of the identity matrix, $E[T_S] = \sum_{j \in S^c} ((I_{S^c} - P_{S^c})^{-1})_{s_0,j}$. For your problem I get a final answer of 231978/665. |
||||
