Markov chain Monte Carlo asymptotic variance for a stationary Markov chain and is
whenever the limit and series exist. If a reversible Markov chain has positive spectral gap , then the spectral theorem for normal operators on a separable Hilbert space gives
The independent identically distributed sequence is itself a Markov chain, since the conditional law of is its common marginal law and does not depend on the past.
Also,
Because is independent of the past, the conditional law of depends on the history only through . Thus the partial sums are a Markov chain.
With states ordered as and rows representing the current state, the Markov chain has transition matrix
If is a Markov chain, the two forms of the data processing inequality for mutual information are
The chain rule for mutual information and the Markov property give
Using the other order,
because conditional mutual information is nonnegative. This proves the first inequality. Applying the same result to the reversed Markov chain , which has the same conditional-independence statement, proves the second.
Because are independent random variables, adding is an independent noise channel, so
is a Markov chain. The data processing inequality for mutual information gives
Translation in the finite additive group preserves conditional entropy, and independence therefore gives
and
Substitution proves the required entropy submodularity for three independent sums.
Suppose is a Markov chain, so . The chain rule for mutual information gives
and also
because conditional mutual information is nonnegative. Therefore . Similarly,
while , so . These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.
Independence makes
a Markov chain. The data processing inequality for mutual information therefore gives . Translation by the known value of is a bijection, so conditional entropy and independence give
and . Rearranging proves the stated entropy submodularity for three independent sums:
Assume , and work on the support . In rejection sampling, choose a normalized proposal probability mass function and a known finite constant satisfying everywhere. Draw independent random variables and , accepting when . The joint probability of proposing and accepting is , so the overall acceptance probability is and the accepted value has probability mass function . Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number of accepted values, the sample average is an unbiased estimator of the expectation when that expectation is finite. Its variance is if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.
For the Metropolis–Hastings algorithm, choose a proposal transition matrix and, at the current state , propose . Accept with the Metropolis–Hastings acceptance probability
A proposal outside is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at . This constructs a Markov chain satisfying detailed balance with , without computing or a global envelope. Estimate the expectation by averaging over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.
The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable , the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of alone does not guarantee a finite expectation or variance.
For each adjacent pair, the detailed balance equations follows directly:
For nonadjacent distinct states both fluxes vanish, and diagonal fluxes agree trivially. Since , this is a genuine stationary distribution, rather than merely an invariant measure of infinite mass.
Every upward and downward transition probability between neighbouring states is positive for . Any two states can therefore be joined by a finite path of positive probability: the Markov chain is irreducible. Moreover,
State zero has period one; Markov chain irreducibility makes every state aperiodic. Finally, the standard countable-state recurrence theorem states that an irreducible Markov chain admitting a stationary distribution of total mass one is positive recurrent, with that stationary distribution unique. The countable-state Markov chain convergence theorem then states that Markov chain irreducibility, positive recurrence and aperiodicity imply for all states . The hypotheses just verified hold on the infinite state space , not merely on a numerical truncation.[ref]
Consequently, the unique stationary distribution and the limiting distribution are both , from every initial state. The countable-state Markov chain ergodic theorem also gives almost surely whenever .[ref]
A stationary distribution is a nonnegative row vector with and . The balance equations give
The first yields . Substitution into the middle pair yields and ; the fourth equation is then satisfied. Normalization gives , hence
All states communicate, so this is the unique stationary distribution. The self-loop at state 1 additionally makes this finite Markov chain aperiodic, although aperiodicity is not required for the balance calculation.
The Markov property and conditioning on the intermediate state give, for the full history through time ,
Condition this identity again on the smaller history . Its right-hand side is already determined by , so the tower property gives
Thus the sampled sequence is a time-homogeneous Markov chain with transition matrix . Checking only its one-time marginal distributions would not by itself establish the Markov property.
It is the every-second-step case of a subsampled Markov chain.
A stationary distribution is a probability row vector satisfying . Its coordinates obey and . Thus
Because both transitions between distinct states have positive probability, the finite Markov chain is irreducible; its positive self-transition probabilities also make it aperiodic.
The finite irreducible aperiodic Markov chain converges to its stationary distribution, regardless of its initial law. Therefore . Taking the arithmetic means of this convergent sequence gives
This uses linearity of expectation and convergence of Cesàro means; it does not require the variables to be independent.
The sequence is a Markov chain when the conditional law of its next state depends on the past only through the current state. Precisely, for each history of positive probability and every ,
A time-homogeneous chain additionally has transition probabilities independent of , written . The displayed single transition matrix in the subsequent parts specifies this time-homogeneous case.
Reading positive entries as directed edges, the communicating class decomposition is
For the first class, paths establish mutual reachability, and every transition from one of these states stays in this set. States 2 and 3 communicate, but state 2 can enter the first class and never return. States 4,6,7 communicate through , but state 6 can enter state 2 with no route back. These paths also exclude any larger communicating class. In a finite Markov chain, the closed class is recurrent and the two open classes are transient.
For an irreducible positive recurrent Markov chain, the Markov chain ergodic theorem gives a unique stationary distribution , with almost-sure long-run occupation fraction in state . More generally, time averages of an integrable state reward converge to its stationary mean. If the chain is also aperiodic, then for every initial state ; the aperiodicity assumption is needed for this last distributional conclusion.
For either transition rule in part (i), permits progression through the phase-A states and a return from phase B to zero. Both chains are finite and irreducible, hence positive recurrent. State has a positive self-loop, so both are aperiodic. Therefore
using respectively the cumulative or consecutive stationary distribution given in part (i), for every starting distribution.
The excluded endpoint cases are simple: at , phase B is eventually reached and then absorbing, so the limiting law is the point mass at . At , the cumulative rule traps the chain at its current phase-A count (or eventually at zero if started in phase B), so the limit can depend on the initial count; under the consecutive rule zero is eventually absorbing. Irreducibility and the preceding stationary formulas must not be asserted unchanged at these endpoints.
Assume , as required by the source's selection probabilities, and put . Conditional on the red book's current position, the next independent selection determines its move without needing its earlier history. Selecting the red book moves it left, unless already leftmost. Selecting the plain book immediately to its right moves it right. Every other selection leaves its position unchanged. Thus this position process is a Markov chain on , with
and boundary self-loop probabilities , . These account for every selection and each row sums to one.
Stationarity at the first state gives , hence . When , for the second state substitution of this identity into its stationarity equation gives . More generally, summing stationarity over the initial segment equates its sole outward and inward probability flows:
Write . Then . Normalization gives
The expression is positive also for , since both numerator prefactor and denominator are negative. The uniform case is exactly , when all books are equally likely to be selected. Since both neighboring transition probabilities are positive, the finite chain is irreducible; the displayed stationary distribution is therefore unique.
A time-homogeneous Markov chain on a countable state space is a sequence of -valued random variables for which, for every positive-probability finite history,
Thus the conditional next-step law depends only on the current state, and the transition probabilities do not depend on time.
For a Markov chain started at state , let denote the first positive return time, using time for the starting state. A recurrent state has ; a transient state has return probability strictly less than . An absorbing state satisfies , so the chain remains there forever after arrival and it is necessarily a recurrent state.
Given , the number remaining next time is uniform on and is independent of earlier choices; given , the next state is . Thus the conditional law of depends only on , which is the Markov property.
By contrast, observing only the last number removed generally loses information about the remaining stock. For , compare the two positive-probability histories
Both have , but the first leaves stickers, so , whereas the second leaves none, so . Hence fails the Markov property.
The qualification is necessary if a Markov chain is allowed to have time-dependent transitions. For , the removal sequence is the deterministic, time-homogeneous Markov chain . For , it is a time-inhomogeneous Markov chain, although it is not time-homogeneous on its observed removal states: a removal of at the first step forces another removal of , whereas a removal of at the second step forces next. The blanket non-Markov claim should therefore be understood in the generic, nondegenerate setting.