# Expected number of visits before hitting a certain state in a Markov chain.

Let $$(X_n)_{n \in \mathbb{N}}$$ be a discrete-time Markov chain with state space $$S = \{a,b,c,d\}$$. The transition matrix is $$\begin{pmatrix} 0 & 1/(1+\lambda) & 0 & \lambda/(1+ \lambda) \\ 1/(1+\lambda) & 0 & \lambda/(1+ \lambda) & 0 \\ 0 & 1/2 & 0 & 1/2\\ 1/2 & 0 & 1/2 & 0 \end{pmatrix}$$ where $$\lambda > 1$$.

Let $$G_{\tau_z}(x,y) = \mathbb{E}_x\left[\sum_{n = 0}^{\tau_z} \mathbb{1}_{X_n = y}\right]$$ and $$\tau_z = min\{n>0 : X_n = z\}$$
What I am trying to calculate is $$G_{\tau_d}(a,b)$$ and $$G_{\tau_d}(a,c)$$.
I know $$G_{\tau_d}(a,a)$$ may be calculated using the interpretation of probabilities as Resistances. See e.g. the chapter "Random Walks on Networks" in "Markov Chains and Mixing Times" by Levin, Peres and Wilmer.

• The first row has 5 entries? Do you want the last 0 there? – Yuval Peres Jun 23 at 23:27
• Thanks for the hint, I corrected the typo. Of course that last 0 should not have been there. – Mithos Jun 25 at 10:05

\begin{align} G_{\tau_d}(a,b) &= \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = b} | X_1 = b\right] \mathbb{P}(X_1=b) + \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = b} | X_1 = d\right] \mathbb{P}(X_1=d) \\ &= G_{\tau_d}(b,b) \mathbb{P}(X_1=b) \end{align} and similarly \begin{align} G_{\tau_d}(a,c) &= \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = c} | X_1 = b\right] \mathbb{P}(X_1=b) + \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = c} | X_1 = d\right] \mathbb{P}(X_1=d) \\ &= G_{\tau_d}(b,c) \mathbb{P}(X_1=b) \\ &= \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = c} | X_2 = c,X_1 = b\right] \mathbb{P}(X_2 = c| X_1=b)\mathbb{P}(X_1=b) \\&+ \mathbb{E}_a\left[\sum_{n = 0}^{\tau_d} \mathbb{1}_{X_n = c} | X_2 = a,X_1 = b\right] \mathbb{P}(X_2 = a|X_1=b)\mathbb{P}(X_1=b) \\&= G_{\tau_d}(c,c)\mathbb{P}(X_2 = c|X_1=b)\mathbb{P}(X_1=b) + G_{\tau_d}(a,c)\mathbb{P}(X_2 = a|X_1=b)\mathbb{P}(X_1=b) \end{align}