Let and define
The probabilities sum to . For , the incoming probability is
using a telescoping sum. Similarly,
Thus is a stationary distribution. Every state can reach in one step, and can reach every lower positive state in one step, so the chain is irreducible. The self-loop at has probability , hence the chain is aperiodic. The convergence theorem for a finite irreducible aperiodic Markov chain now gives
For , the conclusion follows directly from the single absorbing/refilled state.
This is the limiting law of the uniform depletion and refill Markov chain.
Use the state space , since an empty box is refilled immediately. The probability that formerly led from to now leads to . Thus the transition matrix is
For , the second line includes the self-loop obtained when all stickers are taken. When , this is simply the one-state Markov chain.
A Markov chain is irreducible if every state communicates with every other: for any there is an integer with . Thus any state can be reached from any other in finitely many steps with positive probability.
The first Markov chain is a finite irreducible Markov chain: its positive-probability directed cycle reaches all four states. The self-loop at state 1 makes it an aperiodic Markov chain. Convergence to an invariant distribution therefore gives
The second chain alternates between the sets and . It is a periodic Markov chain with period two, so . From either state 2 or state 4 the next-step probability of entering state 1 is . Therefore for every . The subsequences have different limits, so the second return-probability sequence does not converge.
Start the Markov chain at a state and define the strictly positive first return time . A recurrent state satisfies ; a transient state has this probability strictly below one. Equivalently a recurrent state is visited infinitely often almost surely when started there, whereas a transient state receives finitely many visits almost surely. The recurrence criterion by return probabilities gives the equivalent test
States in a communicating class share this classification. In an irreducible Markov chain all states communicate, so the chain is called a recurrent Markov chain if all its states are recurrent and a transient Markov chain if all are transient.
The difference process is a Markov chain. If the columns are equal, the next block creates a height difference of one. If the difference is , landing in the taller column increases it to , while landing in the shorter column makes it zero. Therefore its only nonzero transition probabilities are
These probabilities depend only on the present difference, not on the absolute heights or their history. This is the reset-or-increment Markov chain with .
For its stationary distribution, the incoming-flow equations give and for . Normalization uses a geometric series:
Thus
The remaining balance equation is also satisfied: the flow into zero is . Every state can reach zero and every positive state can be reached from zero, so it is an irreducible Markov chain. Its invariant probability distribution makes it positive recurrent, and that distribution is unique.
The maximum-height process is not Markov. Starting empty, condition first on the positive-probability history . After two blocks the columns were equal, so after three their difference is one. Hence .
For the history , the first two blocks built one column and the third caught the other column up, leaving equal heights. Hence . Both histories have the same time and present height , but different predictions. This violates the Markov property and illustrates why a function of a Markov chain need not be Markov.
Figure 1.
The height difference has reset-or-increment transitions and a geometric stationary tail
. Original transition diagram and stationary probabilities. Independent simulated height averages illustrate the proved limiting growth rate; the finite diagram continues indefinitely to the right. Details.
The history is contained in . The increment is independent of this history by the given independence of random variables. Therefore
This depends only on the current state and not on time. It is precisely the time-homogeneous Markov property, so is a Markov chain with transition probabilities
The conditional identity is an identity that holds almost surely; histories of zero probability require no division by their probabilities.
Let and put , . Then are coprime integers, and . The six requested revisions are as follows.
(b)(i): communicating classes. Every increment is divisible by , so the residue class modulo is preserved. Conversely, if is divisible by , Bézout's identity applied to gives a path just as in (b)(i). Thus the original Markov chain is reducible on , with exactly the closed communicating classes
The specified walk starting at zero stays in .
(b)(ii): period of a state in a Markov chain. The return equation reduces to . Hence , . For every state, the period of a state in a Markov chain is therefore
This is still at least two, so no state is aperiodic.
(b)(iii): stationary distribution. The conclusion is unchanged: there is no stationary distribution on . The maximum-mass proof in (b)(iii) applies verbatim, without using coprimality. Equivalently, each closed communicating class, after translating and dividing its state labels by , is the same centered random walk with step sizes and has no stationary distribution.
(b)(iv): occupation of zero. On , the rescaled walk has exactly the transition probabilities of the coprime walk with parameters . The return-probability argument in (b)(iv) therefore makes this class null recurrent. The renewal process proof of the occupation limit applies unchanged:
Starting in another residue class would make every visit to zero impossible, also giving occupation proportion zero.
(c)(i): modified communicating classes. These are unchanged: is one finite closed communicating class, and all other states are transient singleton classes. The original proof used consecutive reset destinations and never used coprimality. Resetting to the consecutive integers connects different residue classes, so it would be incorrect to split according to residue classes modulo .
(c)(ii): limiting distribution. The column-sum calculation, the irreducible Markov chain property on a finite class, positive self-transition probabilities, and geometric entrance argument also required no coprimality. Thus for every initial state the same convergence in distribution holds:
In particular, the denominator is unchanged; it is not divided by .
For the countable-state Markov chain ergodic theorem, let the Markov chain be irreducible and positive recurrent, with its unique stationary distribution . From any initial state, for every real satisfying ,
In particular, almost surely. This time-average conclusion requires no aperiodicity.
The countable-state Markov chain convergence theorem adds the hypothesis of an aperiodic Markov chain and concludes
It also follows that for every initial probability distribution . For an irreducible recurrent chain, the occupation-frequency theorem can also be stated as a limit , interpreted as zero for a null recurrent state; in the positive recurrent case this equals .
Condition on the full sampled history through time . The Markov property of implies that its future after depends on that history only through . Summing over the intermediate state gives
Thus is a Markov chain with transition matrix . This is a deterministic-time sampled 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 state-zero stationary distribution equation is , so . The state-one equation is , giving . More generally, the stationary probability flow across the cut is balanced, so . This also follows inductively from .
Hence . Since , the geometric series is summable, and normalization gives
These probabilities satisfy detailed balance and therefore all the stationarity equations. The Markov chain is an irreducible Markov chain, so this normalized stationary distribution is unique.
A time-homogeneous Markov chain on a countable state space satisfies, whenever the conditioning event has positive probability,
where the last probabilities do not depend on . Thus the present state contains all the past information relevant to the next transition. Time homogeneity is the convention used here, since the problem specifies a single transition matrix.
Given , the next child takes a fresh uniform choice from , making uniform on . At zero the count stays zero. This conditional law depends only on the current count, so is a Markov chain.
The amounts taken do not generally retain that state information. For , compare two positive-probability histories with the same current value : if , exactly one sticker remains and ; if , none remains and . Thus the next amount depends on earlier history even after conditioning on the current amount, violating the Markov property.
The non-Markov assertion needs this nondegenerate range of . With the amount process is trivial; for it is also Markov if time-inhomogeneous transitions are permitted. The history counterexample establishes the intended failure for every .
Choose distinct coordinates uniformly for the starting ones; each element of then has starting probability . At each iteration choose one current one and one current zero uniformly and swap them. This implements the normalized proposal distribution from (c)(i), remains in , and needs just one precomputed matrix inverse.
mymcmc <- function(x, k, sigma) {
  n <- length(x)
  stopifnot(length(k) == 1L, is.finite(k), k == floor(k),
            k > 0L, k < n, is.matrix(sigma),
            all(dim(sigma) == c(n, n)))
  sigma_inv <- invsigma(sigma)
  u <- integer(n)
  u[sample.int(n, k, replace = FALSE)] <- 1L
  draws <- matrix(0, 100L, n)
  for (iteration in seq_len(100L)) {
    ones <- which(u == 1L)
    zeros <- which(u == 0L)
    i <- ones[sample.int(length(ones), 1L)]
    j <- zeros[sample.int(length(zeros), 1L)]
    v <- u
    v[i] <- 0L
    v[j] <- 1L
    alpha <- mylogapp(x, u, v, sigma_inv)
    if (runif(1L) < alpha) u <- v
    draws[iteration, ] <- u
  }
  colMeans(draws)
}
Sampling positions with sample.int and then indexing into ones or zeros also works when or . In R, a call such as sample(ones, 1) would incorrectly sample from 1:ones when ones is a single numeric value greater than one.
The code records the state after each of exactly transitions, including repetitions after rejection. Its answer is the vector Monte Carlo estimator
This estimates the posterior mean coordinate by coordinate; because each coordinate is binary, its entries estimate the posterior probabilities of inclusion. Every stored state has coordinate sum , so the estimated means lie in and sum to .
For neighbouring states, the symmetry of the proposal and the Metropolis–Hastings acceptance probability give detailed balance:
Thus the posterior distribution is a stationary distribution. Any two states in can be connected by moving the ones that occupy the wrong positions, and the multivariate normal distribution gives strictly positive target masses. The resulting Markov chain is therefore an irreducible Markov chain, and its long-run state averages estimate the posterior mean.
The requested iterations are a finite approximation, without a convergence guarantee or discarded burn-in. A randomly chosen starting subset has the prior distribution, rather than generally the posterior distribution. No aperiodicity assumption is needed for the finite-state Markov chain ergodic theorem for averages; indeed a uniform two-state target with gives a period-two alternating chain. This does not invalidate either the code or the state-average estimator.
Let be a Markov chain with transition kernel , and let be an independent Poisson process of constant rate . A Pseudo-Poisson process is . On the Banach space of bounded Borel measurable functions, with the supremum norm, write
Its infinitesimal generator, transition semigroup, and resolvent operator are respectively
and, for ,
The transition semigroup averages against the Poisson distribution of the number of updates. Since is a Markov operator, ; both series converge in operator norm. Updates with are allowed and do not count as changes of the observed state. The degenerate rate gives , , and .
Use the state order Tall, Medium, Short and column probability distributions, so that . The th column records the child's probability distribution given parent state . Thus the transition matrix is
Every entry is nonnegative and every column sums to one. This convention also gives the requested property . A row-distribution convention would use the transposed transition matrix consistently instead. The stated Markov chain is the mathematical model to analyze; no additional biological assumptions are needed.
Periodic Markov chain Created 2026-09-24 Updated 2026-11-05
For a state of a Markov chain, its period is the greatest common divisor of the positive return lengths,
A state is periodic when . All states in an irreducible class have the same period: paths connecting two states transfer return cycles between them. A reducible chain can have classes of different periods, so a single period for the whole chain requires qualification.
The deterministic two-state chain has period two: its distributions alternate forever despite the existence of the uniform Stationary distribution. More generally, an irreducible nearest-neighbour walk on a bipartite graph alternates its two vertex classes. A positive holding probability at any state of an irreducible class supplies a one-step return and makes the entire class aperiodic. Aperiodicity therefore concerns possible return lengths rather than merely the existence of an invariant law.
Let a policyholder have one fixed exponential distribution intensity of rate , with conditionally independent annual Poisson distribution counts. Its one-year marginal count is geometric, but averaging that count does not make the discount process a Markov chain. In the three-level rule, start at zero discount. At time three, the histories and both end at the same top level. The first means three no-claim years, giving next no-claim probability . The second means a positive count followed by two zero counts, giving : divide the integrals of and . These are distinct, so the Markov property fails when only the current discount is recorded. Conditioning on the intensity, or recording its Bayesian posterior, restores the required predictive information.