In this paper, we face a generalization of the problem of finding the distribution of how long it takes to reach a “target” set T of states in Markov chain. The graph problems of finding the number of paths that go from a state to a target set and of finding the n-length path connections are shown to belong to this generalization. This paper explores how the state space of the Markov chain can be reduced by collapsing together those states that behave in the same way for the purposes of calculating...

We give an improved quantitative version of the Kendall theorem. The Kendall theorem states that under mild conditions imposed on a probability distribution on the positive integers (i.e. a probability sequence) one can prove convergence of its renewal sequence. Due to the well-known property (the first entrance last exit decomposition) such results are of interest in the stability theory of time-homogeneous Markov chains. In particular this approach may be used to measure rates of convergence of...

Many complex systems occurring in various application share the property that the underlying Markov process remains in certain regions of the state space for long times, and that transitions between such metastable sets occur only rarely. Often the dynamics within each metastable set is of minor importance, but the transitions between these sets are crucial for the behavior and the understanding of the system. Since simulations of the original process are usually prohibitively expensive, the effective...