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

471 Views Asked by At

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.

1

There are 1 best solutions below

0
On

I think I found the solution myself.
\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}

Now using basic algebra, the given transition probabilities and the formula from the book cited in the question should yield the result.