4
$\begingroup$

Can a finite state Markov chain have essential transient state?

I have found out an example for an infinite state one and I have the intuition (I may be wrong) that for a finite state space .. This isn't possible... But I am not being able to prove it..

$\endgroup$
4
$\begingroup$

According to Wikipedia,

  • A state $i$ is accessible from a state $j$ (written $j\to i$) if a system started in state $j$ has a non-zero probability of transitioning into state $i$ at some point.

  • A state $i$ is essential if for all $j$ such that $i \to j$ it is also true that $j \to i$.

  • A state $i$ is said to be transient if, given that we start in state $i$, there is a non-zero probability that we will never return to $i$.

A Markov chain with an essential transient state can be constructed from three states $i,j,k$ for which $i\to j$, $j\to i$, $j\to k$, and $k$ never returns to $i$. The transition $j\to k$ guarantees $i$ is transient.

Graph

The transition matrix is

$$\pmatrix{0 & 1 & 0\\ 1-\rho & 0 & \rho \\ 0 & 0 & 1}$$

for some number $\rho$ with $0\lt \rho \lt 1$. It is the chance of never returning to $i$ when starting at $i$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If it never returns to $i$ then how is $i$ essential? $\endgroup$ – Qwerty Feb 21 '17 at 19:52
  • $\begingroup$ The chance that $j$ immediately returns to $i$ is $1-\rho \gt 0$. $\endgroup$ – whuber Feb 21 '17 at 20:08
  • 1
    $\begingroup$ Once $k$ is reached.. It never returns to $i$.. How is $i$ essential then? $\endgroup$ – Qwerty Feb 21 '17 at 20:11
  • $\begingroup$ The only state to which $i$ makes a transition is $j$. Since $i$ is accessible from $j$, $i$ satisfies the definition of "essential." $\endgroup$ – whuber Feb 21 '17 at 20:15
  • 1
    $\begingroup$ $i$ leads to $j$ and $j$ leads to $k$ ..i.e. $i$ leads to $k$.. However $k$ doesn't lead to $i$... So how can $i$ be essential.? $\endgroup$ – Qwerty Feb 21 '17 at 20:17
1
$\begingroup$

When there are finite states, a state is recurrent iff it is essential. This is Remark 1.24 in http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf but there is no proof provided.

The following is my proof.

(=>) it is easy to show that a recurrent state is essential

(<=) We show this direction by contradiction. Suppose in a finite chain, there exists an essential state i that is not recurrent. Then, $$ Pr(X_n \not = i, \ \forall n \geq 1| X_0 =i)>0$$ Thus, there exists a sequence $\{ X_0=j_0=i, X_1=j_1, \dots, X_n =j_n, \dots \}$ such that $$ j_n \not = i, \, \forall\, n \geq 1$$ and $$ Pr(X_n = j_n, \ \forall n \geq 1| X_0=j_0) = \Pi_{n=1}^{+\infty} p_{j_{n-1}j_n}>0$$ Taking negative log on both sides gives us $$ \sum_{n=1}^{+\infty} -\log(p_{j_{n-1}j_n})< + \infty$$ Thus, $p_{j_{n-1}j_n}\to 1$.

However, when there are finite states, there are finite values of transition probabilities, so there exists $N$, such that for any $n \geq N$, $p_{j_{n-1}j_n}= 1$. As a result, $j_N$ is accessible from state $i$, but state $i$ is not accessible from $j_N$. This violates the condition that $i$ is essential. The proof is done.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Let's consider a finite Markov chain.

Suppose we have a closed communicating class of essential states and also suppose that all the states in this class are transient.

Now according to Wikipedia:

  • A state i is said to be transient if, given that we start in state i, there is a non-zero probability that we will never return to i.
  • A communicating class is closed if the probability of leaving the class is zero.

Now according to the definition of transience, each state in the closed class will be visited finitely many times. This contradicts the infinite nature of the time interval, hence at least one of the states in this class must be recurrent.

Since recurrence is a class property (this can be shown) we know that all other states in the closed class will be recurrent.

So, in a finite Markov chain, no essential states can be transient.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In the above proof it is written that for a transient state there exists such sequence [Thus, there exists a sequence $\{ X_0=j_0=i, X_1=j_1, \dots, X_n =j_n, \dots \}$ such that $$ j_n \not = i, \, \forall\, n \geq 1$$ and $$ \Pr\left(X_n = j_n, \ \forall n \geq 1| X_0=j_0\right) = \prod_{n=1}^{+\infty} p_{j_{n-1}j_n}>0$$] with positive probability. But in the example of asymmetric (I. E. the forward probability $p<0.5$ or $p>0.5$)random walk on $\mathbb Z$, every state is transient where as no such sequence with positive probability exist for any state. Rather there are many examples of discrete Markov chain with finite state space where a state is transient but no such sequence exist. I think the above consideration for transient state is not always true.

| cite | improve this answer | |
$\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.