A finite Markov chain is a Markov chain with a finite state space, represented in discrete time by a transition matrix whose entries are nonnegative and whose rows sum to one. A row-vector distribution evolves by . Every such chain has a stationary distribution; irreducibility makes it unique and positive, while aperiodicity additionally ensures convergence from every starting distribution. For the stationary distribution is , but a chain started at one state alternates forever and does not converge.[ref]
For an irreducible finite Markov chain with stationary distribution , the fraction of visits to any state converges almost surely to , for every initial state. More generally, the empirical average of a function of the state converges to its average under . Aperiodicity is needed for convergence of the one-time distributions, but not for this empirical-frequency conclusion. Regeneration at returns to a state proves the conclusion by applying the strong law to independent excursion lengths and excursion rewards.
For a real function on a finite state space, a state minimizing satisfies , so strictly negative drift cannot hold at every state. Equivalently, telescoping the expected value would give , contradicting boundedness of . Constant negative drift is useful before a target is reached; it must be restricted to the states outside that target.

Articles by others on the same topic (0)

There are currently no matching articles.