Institute of Natural and Mathematical Sciences
Permanent URI for this communityhttps://mro.massey.ac.nz/handle/10179/4224
Browse
4 results
Search Results
Item Variances of first passage times in a Markov chain with applications to mixing times(Massey University, 2006) Hunter, J.J.In an earlier paper the author introduced the statisticηi j ijπ j m = m = Σ 1 as a measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain with stationary distribution {pj} and mij as the mean first passage time from state i to state j of the Markov chain. This was shown to be independent of the initial state i with ηi = η for all i, minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. In this paper we explore the variance of the mixing time vi , starting in state i. The vi , are shown to depend on i and an exploration of recommended starting states, given knowledge of the transition probabilities, is considered. As a preamble, a study of the computation of second moments of the mixing times, mij (2) , and the variance of the first passage times, in a discrete time Markov chain is carried out leading to some new results.Item Simple procedures for finding mean first passage times in Markov chains(Massey University, 2005) Hunter, Jeffrey J.The derivation of mean first passage times in Markov chains involves the solution of a family of linear equations. By exploring the solution of a related set of equations, using suitable generalized inverses of the Markovian kernel I – P, where P is the transition matrix of a finite irreducible Markov chain, we are able to derive elegant new results for finding the mean first passage times. As a by-product we derive the stationary distribution of the Markov chain without the necessity of any further computational procedures. Standard techniques in the literature, using for example Kemeny and Snell’s fundamental matrix Z, require the initial derivation of the stationary distribution followed by the computation of Z, the inverse I – P + eπT where eT = (1, 1, …,1) and πT is the stationary probability vector. The procedures of this paper involve only the derivation of the inverse of a matrix of simple structure, based upon known characteristics of the Markov chain together with simple elementary vectors. No prior computations are required. Various possible families of matrices are explored leading to different related procedures.Item Stationary distributions and mean first passage times of perturbed Markov chains(Massey University, 2002) Hunter, Jeffrey J.Stationary distributions of perturbed finite irreducible discrete time Markov chains are intimately connected with the behaviour of associated mean first passage times. This interconnection is explored through the use of generalized matrix inverses. Some interesting qualitative results regarding the nature of the relative and absolute changes to the stationary probabilities are obtained together with some improved bounds.Item Generalized inverses, stationary distributions and mean first passage times with applications to perturbed Markov chains(Massey University, 2002) Hunter, Jeffrey J.In an earlier paper (Hunter, 2002) it was shown that mean first passage times play an important role in determining bounds on the relative and absolute differences between the stationary probabilities in perturbed finite irreducible discrete time Markov chains. Further when two perturbations of the transition probabilities in a single row are carried out the differences between the stationary probabilities in the unperturbed and perturbed situations are easily expressed in terms of a reduced number of mean first passage times. Using this procedure we provide an updating procedure for mean first passage times to determine changes in the stationary distributions under successive perturbations. Simple procedures for determining both stationary distributions and mean first passage times in a finite irreducible Markov chain are also given. The techniques used in the paper are based upon the application of generalized matrix inverses.
