Optimal ventcel graphs, minimal cost spanning trees and asymptotic probabilities
Tzuu-Shuh Chiang, Chow Yunshyong · Applicable Analysis and Discrete Mathematics · 2007
For each ε > 0, let be an irreducible, time-homogeneous Markov chain with a finite state space S and transition function where is a cost function. (We assume if It has been shown [2] that independent of the initial distribution there are constants and βi > 0 such that for any , where µis the invariant distribution of {X}. Let , which is called the global minimum set. Various asymptotic probabilities related to S have been established in [3]. Among others, starting with the uniform or invariant distribution, the expected hitting time ET of S is of order and the constants δ and h(i) above can be expressed in terms of a complicated hierarchy of "cycles" related to the cost function U. In this paper, we shall express these constants in terms of Ventcel graphs (minimum cost spanning trees) to simplify the concept and computation of these constants. We also establish some new properties of optimal Ventcel graphs .