In this paper, we face a generalization ofthe problem of finding the distribution of how longit takes to reach a “target” set T of states inMarkov chain. The graph problems of finding the number of paths thatgo from a state to a target set and of finding the n-length path connectionsare shown to belong to this generalization.This paper explores how the statespace of the Markov chain can be reduced by collapsing togetherthose states that behave in the same way for the purposes ofcalculating the distribution ofthe hitting time of T.We prove the existence and the uniqueness of aoptimal projection for this aim which extends the results given in[G. Aletti and E. Merzbach, J. Eur. Math. Soc. (JEMS)8 (2006) 49–75], together with the existence of a polynomial algorithm which reaches this optimum.Some applied examples are presented. Markov complexity is defined an tested onsome classical problems to demonstrate the deeper understanding that ismade possible by this approach.
