Absorbing state Created 2026-10-03 Updated 2026-10-14
For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , a state is absorbing exactly when . Nonnegativity and the row sum then force for : once entered, is never left. Equivalently, is a closed communicating class. A larger closed communicating class may keep moving internally; closure means confinement to a set, whereas absorption at a state means remaining at one point.
An absorbing state is useful for recording a terminal outcome: after a toy routine finishes, keep its outcome in the state space so that the same transition matrix still describes subsequent steps. Calling a finite Markov chain absorbing usually also requires that some absorbing state be accessible from every state. Merely containing an absorbing state is insufficient: another closed communicating class could prevent absorption. See Grinstead and Snell, Introduction to Probability, section 11.2 for this convention.
Consider a constructed routine with unfinished modes and terminal outcomes . All the following transition probabilities are chosen for illustration, not estimated from observations. In state order , take
The communicating class is open, while and are closed communicating classes consisting of absorbing states. Both terminal outcomes are accessible from both unfinished modes, sometimes by an indirect path.
Figure 1.
A constructed four-state routine: arrows give transition probabilities, and the two absorbing outcomes have different eventual probabilities and waiting times.
Details.
Let be the terminal hitting time. Write for the absorption probability and for the expected hitting time, with the subscript denoting the starting state. First-step analysis gives
Here , , and . Solving these two pairs of linear equations yields
Starting at therefore ends at with probability and takes steps on average to reach either terminal state. The terminal hitting time counts the transition into the outcome, but no later self-transitions. Outcome and duration answer different questions: from , outcome is less likely, yet termination is faster on average.
The matrix power gives the probability distribution after two steps from as
Thus , and the probability of having already reached is , still below its eventual absorption probability . From either unfinished mode, each next step has terminal probability at least . Consequently , proving termination almost surely and finite expected hitting time directly. The Fundamental matrix of a finite absorbing Markov chain packages both calculations and counts visits to unfinished modes.
For a finite, time-homogeneous Discrete-time Markov chain, state is accessible from when some finite path of positive transition probabilities leads from to . Equivalently, for some , allowing a zero-step path when . Accessibility is reflexive and transitive; communicating states require accessibility in both directions. See Ward Whitt's lecture notes of September 24, 2013, classification of states. In the closed-cycle example in communicating class, despite , because ; fails at every step count.
The Barker acceptance probability accepts a proposal using the displayed ratio. If and , the accepted flux is , symmetric in the two states. This proves detailed balance; define acceptance as zero when . Rejected proposals contribute to the diagonal transition probability. Replacing by an unnormalized target leaves the ratio unchanged. For a common proposal, shows that its acceptance probability never exceeds the Metropolis–Hastings acceptance probability. The name refers to A. A. Barker's work on Monte Carlo methods for a plasma; the initials are retained without an unverified expansion.[ref]
Bellman equation Created 2026-09-24 Updated 2026-10-14
A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let be a dynamic programming state, the allowed actions at time , the immediate reward, and the next dynamic programming state. With terminal time and terminal reward , the deterministic finite-horizon Bellman equation is
Here measures total reward from time through the terminal reward. Start with and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.
In a Markov decision process, the next dynamic programming state is random. If denotes the expected immediate reward and is a discount factor, the finite-horizon Bellman equation becomes
The conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities , the continuation term is . Taking gives the undiscounted finite-horizon problem. With a discount factor , rewards steps ahead carry a factor , including the terminal reward. A maximizing action for each specifies a Markov policy, which contains decisions rather than just optimal scores.
For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards , and a discount factor , the optimal value function satisfies
In this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and , the Bellman equation is merely , so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.
Channel capacity Created 2026-09-24 Updated 2026-10-14
Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities , and no input-cost constraint, it is
in bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.
The operational meaning comes from the Shannon second coding theorem. A block code represents one of possible messages by a word of length , giving a rate bits per use. Take the message label from the uniform distribution on a finite set of those choices when measuring average decoding-error probability. For every fixed rate , there are sequences of such block codes whose decoding-error probability tends to zero as grows; a rate above cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.
For a binary symmetric channel with crossover probability , the binary symmetric channel capacity is approximately bits per use. Thus a binary code rate lies below the limit, while lies above it. At , two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.
The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. [ref].
To see why continuous time removes periodicity, fix . Every finite sequence of Markov chain states connected by positive transition intensities has positive probability of finishing before , followed by no further transition until . Consequently the transition matrix has positive entries between every pair of communicating Markov chain states, including its diagonal. It is an irreducible Markov chain and an aperiodic Markov chain with stationary distribution . The countable-state Markov chain convergence theorem gives convergence at times , also in total variation distance. For , , applying contracts total variation distance and preserves , giving the full continuous-time limit.
For a finite-state homogeneous continuous-time Markov chain with generator matrix , integrate the indicator of occupying state over . Interchanging the bounded time integral and expected value gives the displayed integral of transition probabilities. It counts all visits, not only the first holding time. Summing over states gives . A zero eigenvalue of does not cause a problem for this integral, although it prevents casually writing it with an inverse matrix .
If the initial one-spin set is finite on the square lattice, voter-model duality gives . The transition probabilities tend to zero on this infinite lattice; their Fourier transform also proves the limit of a sequence by dominated convergence. A union bound on any finite set of observation sites then proves weak convergence of probability measures to the all-zero point mass in the product topology.
Consider the chosen finite minimization problem
Only adjacent integers are neighbors. At each interior state propose left or right with probability each; at an endpoint propose its sole neighbor with probability and itself with probability . This proposal distribution is symmetric, including at the endpoints. The local minimum at is relative to these allowed moves; is the unique global minimum.
Figure 1.
An uphill step opens a route out of a local minimum in a chosen five-state problem
. Points are the only allowed states; joining lines show adjacency, not additional feasible points. Starting at , improving-only local search is trapped. The possible route first raises the objective function by , then lowers it twice. Details.
At , improving-only local search rejects both neighbors because and exceed . For simulated annealing, choose , using the natural logarithm. Conditional on proposing from , the acceptance probability is
The one-step transition probability is instead . Both subsequent rightward proposals are downhill, so the conditional probability of the precise next three states being , given and fixed , is
This is one possible escape route, not the probability of eventually reaching . Rejections, excursions toward , and repeated attempts give many other sample paths. The calculation establishes possibility, without claiming a general performance advantage from a selected sample path.
For comparison, halving makes the uphill acceptance probability ; doubling it makes that probability . Cooling makes it harder to leave this local minimum, even though the stationary distribution increasingly favors the global minimum. That tension is the central scheduling problem.
Take a birth-death chain on . At each interior state, move up one state with probability and down one state with probability . The endpoints are absorbing states: . This is a small gambler's ruin model in which the state can represent capital, and reaching is success.
Figure 1.
Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.
Details.
Let be the hitting time of endpoint , and let be the first endpoint hitting time. The desired hitting probability is . First-step analysis and the Markov property give
The interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , so
For example, from state the hitting probability is , and its one-step average is . Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.
Now ask how long it takes to reach either endpoint. The expected hitting time counts steps, including the transition that first reaches an endpoint. First-step analysis gives
This is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic values
satisfy the equations; from state , steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.
For a biased random walk with upward and downward, keep the same absorbing states. The interior harmonic equation becomes . Using biased gambler's ruin probability with these boundary values gives
The three interior hitting probabilities are approximately , , and . Thus starting at now succeeds about of the time. A direct check is . The curved profile reflects the unequal transition weights: its successive increments shrink by the factor . The formula, with the endpoint denoted there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.
Figure 2.
Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.
Details.
Why does harmonic averaging produce the correct hitting probability? With the natural filtration , the Markov property gives the conditional expectation identity
For a function harmonic everywhere, this makes a martingale whenever it is integrable. For a function harmonic only in the interior, is a stopped martingale. In either five-state example, . Also, from any interior state at most three consecutive upward steps reach , with probability at least . Repeated three-step blocks give , so is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at and then the bounded convergence theorem gives
The boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.
Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.
// Target: markov-process.bigb
On a finite state space with finite objective function values, the fixed- target is a Boltzmann distribution:
The partition function normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric and ,
Summing over gives , so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing by ensures this. For asymmetric , require connectivity through bidirectional proposals: one-way proposals are rejected.[ref]
In the five-state barrier example for simulated annealing, gives exact Boltzmann weights . Multiplying by gives
For the uphill edge, detailed balance is visible numerically:
Thus the global minimum has the largest individual stationary probability, , but is far from certain at this positive . At the exact stationary distribution is .
Figure 1.
Lower temperature concentrates equilibrium weights while suppressing uphill acceptance
. Exact Boltzmann distributions for the chosen five-state objective function, and the uphill acceptance probability conditional on the proposal . The one-step transition probability is half that acceptance probability. The bars describe equilibrium at each fixed temperature, not the evolving probability distribution during cooling. Details.
For any finite , let be the set of global minima and the smallest objective function value. Cancelling from numerator and denominator shows that each nonminimal state's weight tends to zero as , while every state in has equal weight. Therefore tends to the uniform distribution on . This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.
A binary erasure channel marks its failed transmissions with a special output symbol, whereas a binary symmetric channel changes a bit without announcing whether it changed. At the same nominal failure probability , the two communication channels therefore leave different uncertainty. With a fair input, an unerased output determines the input exactly, while the erasure flag leaves one bit of conditional entropy. Thus and for the binary erasure channel. This is the binary case of capacity of a finite-alphabet erasure channel.
For the binary symmetric channel at , neither possible received symbol rules out either input, and . Its channel capacity is only . A receiver benefits from knowing where information was lost, even when the fraction of affected transmissions is the same.
Figure 1.
Announced erasures preserve more information than hidden bit flips at the same low failure probability
. Solid arrows carry probability and dashed arrows carry probability in the two illustrated laws of transition probabilities. The erasure flag is distinct from both bits. The lower plot compares channel capacity for , using for the binary erasure channel and for the binary symmetric channel. Details.
This comparison concerns the specified transition probabilities, rather than a general ordering of every error mechanism. In particular, at , an erasure flag conveys no input information, while deterministic inversion still conveys a full bit. Reporting only an error percentage loses the distinction between hidden corruption, announced loss, and a predictable reversible transformation.
A frozen-age approximation holds an age covariate constant at the start of each observation interval, allowing homogeneous transition probabilities to enter a panel-observed multi-state likelihood. It approximates a model with continuously changing age. Reciprocal rate calibration of mean waiting times is exact for a fixed-age exponential distribution, but not for a continuously ageing Gompertz distribution.
Irreducible Markov chain Created 2026-09-24 Updated 2026-10-25
For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , irreducibility means
Equivalently, all states form one communicating class. The step count may depend on ; irreducibility does not require every one-step transition probability to be positive. Drawing an arrow whenever makes the condition exactly that of a strongly connected directed graph. It is a property of the entire chosen state space, independent of the initial probability distribution.
Irreducibility describes where the Markov chain can travel; aperiodicity describes the possible lengths of return paths. For example, restricting the second diagram in communicating class to its closed pair gives
where is the identity matrix. This Markov chain is irreducible, but each state's period of a state in a Markov chain is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at produces alternating one-time probability distributions. See Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.
Adding a holding probability of a Markov chain at each state, with , gives
The arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At , both rows are and for every : the initial state is forgotten after one step. At , however, both states become absorbing states, giving two separate communicating classes and losing irreducibility.
For a finite Markov chain, irreducibility guarantees a unique stationary distribution with positive weight at every state. Adding aperiodicity guarantees convergence for every initial probability distribution; see Hao Wu's MIT lecture 4, convergence theorem. The Markov chain ergodic theorem gives convergence of empirical visit frequencies even for an irreducible periodic Markov chain. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any absorbing state prevents irreducibility if there is another state: it cannot reach that state. The one-state Markov chain is the exception.
Irreversible three-state disease model Created 2026-10-05 Updated 2026-10-06
An irreversible three-state continuous-time multi-state model permits only , with state 3 absorbing. For constant rates and ,
At equal rates use . A panel-observed multi-state likelihood uses these transition probabilities, allowing unobserved intermediate visits between examinations.
Markov chain Created 2026-09-24 Updated 2026-10-14
The term Markov chain commonly denotes a Markov process on a finite or countable state space. Time may be discrete, as for a daily record, or continuous, as for a continuous-time Markov chain. Some authors also use “Markov chain” for discrete-time processes on more general state spaces; specifying both time and state space avoids this ambiguity.
For a Discrete-time Markov chain, its initial probability distribution and transition matrix specify the probability of each finite path:
This is the Markov factorization, obtained by applying conditional probability repeatedly. See Hao Wu's MIT lecture 1, definition and distribution evolution.
For the constructed sunny/rainy Markov chain below, starting sunny makes the path sunny, rainy, sunny have probability . Starting instead with stationary distribution makes that path's probability . The transition probabilities are identical in both experiments; the initial probability distribution distinguishes them.
Markov decision process Created 2026-10-14 Updated 2026-10-20
A Markov decision process specifies states, admissible actions, action-dependent transition probabilities and rewards. A policy chooses actions from observed information; a time-homogeneous problem uses transition and reward rules independent of the date. A Bellman equation optimizes current reward plus the conditional value of subsequent decisions. For nonnegative rewards, finite-horizon values increase as the horizon grows, while identification of their limit with the infinite-horizon value requires an approximation argument for admissible policies.
A clinic-observed interval ending in a recorded state contributes a transition probability. If the next observation is exact entry into an absorbing state but the preceding state is unobserved, its statistical probability density is , not . Multiplying these conditional contributions yields a likelihood for mixed panel and exact-event observations.
Occupation time of a continuous-time Markov chain Created 2026-10-05 Updated 2026-10-14
The occupation time records the duration spent in a state of a continuous-time Markov chain. Conditional on , its expected value is , where is the transition probability.
Expand the time-dependent quantum state in unperturbed energy eigenstates, factoring out free dynamical phases:
The Schrödinger equation gives the exact interaction picture coefficient equations
Initially . To first order in time-dependent perturbation theory, replace the coefficients on the right by these zeroth-order values and integrate. Thus
For a transition , this is the desired leading probability amplitude, and to leading order. The formula is understood with free asymptotic phases removed. For , the full survival amplitude also contains the zeroth-order ; the displayed integral alone is its first-order correction, not the whole amplitude. This specifies the usual scattering operator meaning of the paper's notation at infinite times.
For the ion pulse, write and . Then
Consider an excitation with and put , . The first real pulse is even in time and the second is odd. Their respective surviving Fourier components are therefore cosine and imaginary sine:
Since , the longitudinal term is smaller for comparable position matrix elements. Hence the electric-dipole excitation by a passing ion has
This leading limit extends to either sign of using . If by a selection rule, the retained leading term vanishes and the smaller longitudinal term may give the first nonzero probability. The conditions also include a small total transition probability, approximately straight constant-velocity motion, and large compared with atomic size for the electric-dipole approximation. The paper uses a Coulomb-coupling convention in which the factor is written ; in SI units replace throughout by .
The collision duration is of order . Excitations with angular frequency receive an unsuppressed impulse when this is short relative to . In contrast, for , cancellations in the Fourier transform suppress the transition: a slowly varying distant field approximately preserves the atomic energy eigenstate. The exact dipole-pulse transforms make this explicit:
where is a Modified Bessel function of the second kind. Their large-argument exponential decrease explains the slow-passage cutoff. These transforms are optional refinements of the small- derivation above, not a separate assumption about the target.
To connect the microscopic transition probability to energy loss, suppose the atom begins in a low-energy state. Exciting bound electronic states and causing ionization transfer positive energies from the ion to the material. For target atomic number density and path length , a schematic independent-encounter sum is
with a continuum integral as well as a sum for ionized final states. The short-collision formula gives , so the impact-parameter integral has logarithmic dependence on its cutoffs. Its upper effective cutoff is of order , where the transition ceases to be sudden; the lower cutoff must exclude regions where the dipole or weak-collision approximation fails. Thus the leading high-speed charge and isotope scaling of electronic stopping is
Although a faster ion can access more energetic transitions and a wider range of distant encounters, its shorter interaction time reduces each ordinary excitation probability. In the fast-ion regime shown, the decrease dominates the slower variation of the excitation factor. The energy loss consequently falls with increasing incident kinetic energy. The original figure has increasing downward, so the curves' rise toward the top of the page means decreasing loss, not increasing loss. A low-speed extrapolation of the inverse-square law is invalid because excitation thresholds, slow-passage suppression, changing ion charge and nuclear recoil can then matter.
For nonrelativistic ion mass , . At fixed incident energy the leading prediction becomes
The greater atomic number of nitrogen than carbon than boron therefore gives larger loss; at the same velocity the leading species factor is . Within an isotopic family, the heavier ion moves more slowly at the same and loses more energy. Equivalently, a heavier isotope needs proportionally greater kinetic energy to achieve the same velocity and approximately the same electronic loss. Comparing at fixed energy per nucleon, rather than fixed total , approximately removes this leading isotope mass dependence. This accounts for the separate isotope bands in the original graph without assigning different electronic excitation spectra to isotopes of the same projectile element.
The charge in this scaling is the effective ion charge if screening by bound projectile electrons is important. The interpretation assumes the same traversed material and thickness and uses the paper's small-fractional-loss regime, ; points with loss comparable to incident energy cannot be described quantitatively by treating as constant. The plotted curves support the qualitative ordering and high-energy decrease, rather than determining a universal normalization from the supplied single-atom model.