The question I have is stated as follows:

Show that for any finite-state irreducible Markov chain $$\max_{i,j}\mathbb E_iT_j\le C$$where the constant $C$ only depends on the number of states and $\min\lbrace P(i,j):P(i,j)>0\rbrace$. Here $T_j:=\inf \lbrace n\ge 1:X_n=j\rbrace$.

What I've tried so far is: $$\mathbb{E}_iT_j=\sum_{n=1}^{\infty}n\mathbb{P}_i(X_1\neq j,X_2 \neq j,\dots,X_{n-1} \neq j, X_n=j)$$ I believe the probability under summation is $$\mathbb{P}_i(X_1\neq j,X_2 \neq j,\dots,X_{n-1} \neq j, X_n=j)=\sum_{z_k\in S \setminus \lbrace j\rbrace}p(i,z_1)p(z_1,z_2)\times\dots\times p(z_{n-1},j)$$where $k$ runs from 1 to $n-1$.

Since there are finitely many states, then $\underline{P}:=\min\lbrace P(i,j):P(i,j)>0\rbrace$ is well-defined, and I can bound the probability below by $ \underline{P}^n\times \lbrace \text{number of combinations over which I add up [depends on the number of states]} \rbrace$ .

I was wondering if the above makes sense, and asking for a hint if it doesn't. Thanks.

  • $\begingroup$ Hint: Show that $\mathbb{P}_i(T_j>n)\leq K\rho^n$ where $0<\rho<1$, and $K,\rho$ only depend on the number of states and the minimum of $P_{ij}$. $\endgroup$
    – user940
    Mar 8, 2016 at 18:49


Your Answer

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

Browse other questions tagged or ask your own question.