0
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.