Transience and recurrence

Given that we start at state i, it is called transient if there is a non-zero probability that we will never return to state i. To define this in more formal terms, let's consider a random variable T_i as the first return time to state i:

Let's now define another term, , as the probability of the system returns to state i after n steps:

Now we can define that any given state i is transient if the following condition is met:

In the preceding equation, we are basically checking whether the total sum of probabilities of returning to state i in step sizes less than  is less than 1. If the total sum is less than 1, it would mean that the probability of T_i to be  is greater than 0 which would mean that the state i is transient. The given state i is called recurrent if it is not transient:

In the preceding example, we can see that states A and B are transient because A doesn't have any incoming edge. B does have an incoming edge, but it's incoming from another transient state and therefore it is also transient. Hence, once the system leaves state A or B, it won't be able to come back.

It is really simple to check whether a given state is transient or not. We can simply check whether there are any incoming edges from other states or not. If not, the state is transient. Let's write a simple method to check this for our MarkovChain class:

def is_transient(self, state):
    """
    Checks if a state is transient or not.

    Parameters
    ----------
    state: str
        The state for which the transient property needs to be checked.
    """
    if all(self.transition_matrix[~self.index_dict[state], self.index_dict[state]] == 0):
        return True
    else:
        return False

Now we can use this method in our example in Figure 1.6 to check which nodes are transient:

>>> transient_matrix = [[0, 0.5, 0.5, 0],
                        [0, 0, 0.25, 0.75],
                        [0, 0, 0, 1],
                        [0, 0, 0.5, 0.5]]
>>> transient_markov = MarkovChain(transition_matrix=transient_matrix,
                                   states=['A', 'B', 'C', 'D'])

>>> transient_markov.is_transient('A')
True
>>> transient_markov.is_transient('B')
True
>>> transient_markov.is_transient('C')
False

In the following subsections, we will talk about the statistical properties of the random variable T_i.