Expected number of steps to return to a state

Question

Consider a simple finite graph such as this graph

If we start at $A$, what is the expected number of steps to return to $A$?

I know that the answer is $4$, but I'm not too sure how get this. Can anyone help me?

I calculated the transition matrix to be :

$$ P= \begin{pmatrix} 0 & 1 & 1 &1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ \end{pmatrix} $$ with states A,B,C,D,E

and the adjency matrix: $$ B= \begin{bmatrix} 0 & 1/3 & 1/3 &1/3 & 0 \\ 1/3 & 0 & 1/3 & 0 & 1/3 \\ 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ \end{bmatrix} $$ with states A,B,C,D,E

What should i do next?

Answer 1

Hint:. If $\ s_X\ $ is the expected number steps to return to $\ A\ $ starting from state $\ X\ $, then $\ s_A, s_B, s_C, s_D, s_E\ $ must satisfy the following equations: \begin{align} s_A&=1+\frac{1}{3}\left(s_B+s_C+s_D\right)\\ s_B&=1+\frac{1}{3}\left(s_C+s_E\right)\\ s_C&=1+\frac{1}{2}s_B\\ s_D&=1+\frac{1}{2}s_E\\ s_E&=1+\frac{1}{2}\left(s_B+s_D\right)\ . \end{align} The last four of these give you four linear equations for the four unknowns $\ s_B, s_C, s_D, s_E\ $: $$ \pmatrix{1&-\frac{1}{3}& 0& -\frac{1}{3}\\ -\frac{1}{2}&1&0&0\\ 0&0&1& -\frac{1}{2}\\ -\frac{1}{2}&0& -\frac{1}{2}&1}\pmatrix{s_B\\s_C\\s_D\\s_E}= \pmatrix{1\\1\\1\\1}\ , $$ which you should be able to solve by Gaussian elimination. You can then calculate the value of $\ s_A\ $ by substituting the values of $\ s_B, s_C, $ and $\ s_E\ $ back into the first equation.

Note: The titles of the matrices you've given need to be swapped: the adjacency matrix is the one whose entries are all ones and zeroes, and the transition matrix is the one whose entries are zeroes, halves and thirds.

Answer 2

node $A$ has degree 3 in an undirected, connected graph. The total degree is $3+3+2+2+2 = 12$

Then $\pi_A = \frac{3}{12} = \frac{1}{4}$ and a basic result in markov chains tells us that $\pi_A = \frac{1}{\bar{X}} =\frac{1}{4}\longrightarrow \bar{X}=4$, i.e. you have an expected return time of $4$. This is your answer.

The below addresses the steady state probability calculations. I take $\pi_A = \frac{1}{\bar{X}}$ as a known result (it is e.g. implied by the elementary renewal theorem though you can also prove it with linear algebra when there are finitely many states.)

changing the labels since $P$ is typically reserved for the transition matrix

$B= \begin{pmatrix} 0 & 1 & 1 &1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ \end{pmatrix}$ and

$P= \begin{bmatrix} 0 & 1/3 & 1/3 &1/3 & 0 \\ 1/3 & 0 & 1/3 & 0 & 1/3 \\ 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ \end{bmatrix}$

and using diagonal matrix $D = \text{diag}\big(3,3,2,2,2\big)$, you can directly see

$B=B^T$ and $P=D^{-1}B$

It should be pretty intuitive that the steady state probability (or if you prefer, the time averaged probability) is proportional to the degree of a given node. If you want to prove this, consider that the above equations imply $P$ is reversible, because

$P^T = \big(D^{-1}B\big)^T = BD^{-1}\longrightarrow D^{-1}P^TD = D^{-1}\big(BD^{-1}\big)D =D^{-1}B = P$

this is equivalent to the detailed balance equations being satisfied and also shows that $\pi_i \propto d_{i,i}$ where the normalization constant comes from summing all components in $D$, i.e. summing $3+3+2+2+2=12$, so $\pi_i =\frac{d_{i,i}}{12}$

for avoidance of doubt on the steady state distribution, consider

$\mathbf \pi^T P =\mathbf \pi^T \Big(\big(\frac{1}{12} D\big)^{-1}P^T\big(\frac{1}{12}D\big)\Big)=\Big(\mathbf \pi^T\big(\frac{1}{12} D\big)^{-1}\Big)P^T\big(\frac{1}{12}D\big) = \mathbf 1^T P^T\big(\frac{1}{12} D\big) = \mathbf 1^T\big(\frac{1}{12} D\big)= \mathbf \pi^T$

this thread:
If $P$ is the transition matrix of a reversible Markov chain, why are its eigenvalues real?

may be helpful.

An alternative route to this result: you can also directly verify that $d_{i,i}p_{i,j} = d_{j,j}p_{j,i}$ in your transition matrix