Aalen–Johansen estimator Created 2026-10-06 Updated 2026-10-07
The Aalen–Johansen estimator is a product of empirical state-transition matrices over event times. In competing risks, the estimated cumulative incidence function for cause jumps by , while overall survival is updated using all event causes. Right censoring changes subsequent risk sets but does not itself create a probability jump.
Abelian hidden-subgroup Fourier sampling Created 2026-10-05 Updated 2026-11-05
Measuring the coset state in the group shift operator eigenbasis samples uniformly from the annihilator of a subgroup of a finite abelian group . Indeed,
so the character-sum cancellation lemma gives probability on and zero elsewhere. The modulus of is one, so the offset has no effect on the distribution.
A decision problem in which the same information set can be reached more than once along a single path, so the decision-maker does not know which visit is occurring. It violates perfect recall. A behavioural strategy uses a common probability at each visit and independent random draws, making terminal probabilities nonlinear in that probability.
For instance, let stopping at the first visit pay zero, continuing and then stopping pay eight, and continuing twice pay one. With continuation probability , expected payoff is . Its maximum exceeds the best deterministic-plan payoff of one. Randomizing once between the deterministic plans cannot reproduce the two fresh decisions.
Absorbing four-ball Ehrenfest chain Created 2026-10-31 Updated 2026-11-05
Stop the four-ball Ehrenfest urn model upon reaching count zero or four. From count , the transitions are to with Probability and to with Probability . First-step analysis with absorbing boundary values gives the displayed vector of probabilities of absorption at zero and vector of expected hitting times of either endpoint. For instance, and , with , give . From any interior state, absorption has Probability at least within two steps; the resulting geometric tail bound proves both almost-sure absorption and finiteness of the expectations.
Absorbing Markov chain 2026-10-20
A Markov chain with at least one absorbing state, such that from each state an absorbing state can be reached. In a finite such chain, absorption occurs with probability 1. Expected times to absorption satisfy a linear system obtained by conditioning on the first transition.
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.
Absorption time 2026-10-25
For a discrete-time Markov chain and a set of absorbing states, its absorption time is the hitting time . It is zero when the initial state already lies in , and infinite on a sample path that never enters . Finiteness almost surely need not imply a finite expected value. For a finite-state model, a uniform positive probability of absorption within a fixed number of steps gives a geometric series bound on the survival probabilities and proves that the mean is finite. The mean absorption time of a lazy symmetric random walk is an explicit example.
Let a discrete random variable have probability mass function . Given , return with probability ; otherwise draw from a conditional distribution with probability mass function . The law of total probability gives the displayed identity. Its total mass is . If the fallback is a discrete uniform distribution on , then , so the fallback sum includes .
Acyclic Markov chain Created 2026-10-20 Updated 2026-11-05
On a finite state space, an acyclic Markov chain has no directed cycle among its nonabsorbing states. Order those states topologically by their possible transitions. Hitting probabilities and expected absorption times can then be calculated in reverse order, because a state's equations involve only later states.
For example, let go to or to an Absorbing state with equal probabilities, and let go directly to . The expected absorption times are , and . This is dynamic programming on the transition graph, rather than a general simultaneous linear solve.
If a convention permits self-transitions while forbidding cycles between distinct nonabsorbing states, the holding probabilities must be retained. Provided , the same backward calculation uses
A self-loop at of Probability , with probabilities each to , gives instead of . The finite-state assumption is substantive: an infinite deterministic chain is acyclic but has no terminal Absorbing state and no finite reverse recursion of this kind.
Adaptive classifier 2026-11-05
An adaptive classifier updates its decision rule or parameters using information acquired while processing further data. In statistical classification, this can specialize an initially broad model to the conditions of a particular stream or document. The update may use supplied labels or examples accepted under a stated trust rule; adaptation is not evidence that every accepted label is correct.
In the 2007 description of Tesseract, satisfactory first-pass words provide examples for a more document-sensitive classifier. The paper motivates this by the limited collection of fonts within a document and describes normalization differences between static and adaptive classification. It explicitly does not describe the adaptive classifier as a simple template matcher.[ref]
A separate toy calculation illustrates parameter adaptation without claiming to reproduce that implementation. Suppose a class is represented by the mean of one measured feature from trusted examples. Accepting another value gives
With , and , the updated mean is . A classifier using that class mean can change its later decisions as a result.
The trust rule matters as much as the arithmetic. If a wrong prediction is accepted as a label, its update can make related wrong predictions more likely. A confidence score can help select examples, but a numerical score is not automatically a calibrated probability of correctness. A useful evaluation compares a frozen baseline and the adaptive system on checked data, including the possibility of degradation as well as improvement.
For two subsystems with independently specified macrostates, suppose every allowed microstate of can be paired with every allowed microstate of . Their allowed set is a Cartesian product. With equal probability for each pair, Boltzmann's entropy formula gives
For example, take two independent copies of the toy model, each with two labels choosing between its two boxes. Each copy has four configurations and Boltzmann entropy . Combining their independent labels gives sixteen configurations and Boltzmann entropy . This explains why entropy adds even though microscopic counts multiply. [ref]
The product assumption matters. A constraint shared between the subsystems can forbid some pairs; for example, fixing only their combined energy generally requires summing over its possible divisions. See entropy maximization under thermal contact for how thermal equilibrium selects the dominant division. Statistical independence cannot be inferred merely from drawing a boundary between two parts.
Adiabatic matter-enhanced neutrino conversion Created 2026-10-25 Updated 2026-11-05
Flavor conversion in a slowly varying medium when an occupied instantaneous propagation eigenstate follows its eigenvalue branch without transitions to the other branch. For positive electron-neutrino matter potential and normal two-state ordering, a high-density electron neutrino follows the upper branch into the vacuum mass eigenstate . Detection in the electron flavor then has probability , rather than the phase-averaged vacuum value . High production density alone does not guarantee adiabatic evolution.
Adjacency-matrix bound for a discrete SIR epidemic Created 2026-10-14 Updated 2026-11-05
The conditional union bound gives in a discrete SIR epidemic on a graph. Iteration bounds the infection vector at step by . Each vertex is infected at most once, so summing the probabilities in time gives the displayed bound. Powers of the adjacency matrix of a graph count walks, which can overcount impossible reinfections without invalidating the upper bound. Initially removed individuals must be counted separately when bounding all eventual removals.
Affected-sib-pair analysis Created 2026-10-14 Updated 2026-11-05
An affected-sib-pair analysis examines marker identity by descent between affected full siblings. Without genetic linkage to the disease locus, the probabilities of sharing zero, one and two copies are . Excess sharing supplies evidence for linkage under disease models that preferentially transmit a common risk allele to both siblings.
// Target: biology.bigb
If host-specific equilibrium mean burden has a gamma distribution, conditional Poisson distributions produce a Poisson-gamma mixture, hence a negative binomial distribution. With mean and shape , its zero-burden probability is . Decreasing increases aggregation: a smaller infected-host prevalence can accompany the same mean burden and more heavily infected individuals.
Agrawal–Biswas primality test Created 2026-09-24 Updated 2026-11-05
The Agrawal–Biswas primality test tests a formal polynomial identity in :
For , the identity holds exactly when is a prime number. Testing a formal polynomial is stronger than evaluating it at residues.
The randomized algorithm first handles prime numbers at most thirteen, divisibility by them, and perfect powers. For remaining , choose a monic polynomial of polynomial degree , with independent uniform lower coefficients modulo . Compute the remainder of modulo using exponentiation by squaring. A nonzero remainder proves compositeness. The monic polynomial permits division even when the coefficient ring has zero divisors.
Every prime number passes. After preprocessing, a composite number is rejected with probability at least per trial, so independent trials give error at most . Keeping remainders below polynomial degree makes the computation polynomial time in the bit length of .[ref]
Aharonov-Bergmann-Lebowitz rule Created 2026-10-06 Updated 2026-11-05
For an ideal projective measurement with the Lüders rule, condition on both an initial quantum state preparation and a final successful postselection. Its outcome probabilities are proportional to , where is the forward-evolved initial state and the backward-evolved final state. The normalization must be nonzero. The expression is symmetric in these two boundary states, although its derivation uses the ordinary Born rule and conditional state update.
Albert R. Meyer Created 2026-10-13 Updated 2026-11-05
Albert R. Meyer is a coauthor of Mathematics for Computer Science by Eric Lehman and others, which develops proofs, discrete structures and probability for reasoning about computation. Its treatment connects mathematical induction, graph models and counting to algorithmic questions and program correctness.[ref]
Aldous-Broder algorithm Created 2026-09-28 Updated 2026-11-05
The Aldous-Broder algorithm samples a uniform spanning tree of a finite connected graph by running a simple random walk from any initial vertex. Whenever the random walk first visits a new vertex, retain the edge by which it arrived. Stop when every vertex has been visited.
Each retained edge joins a previously unseen vertex to the already visited connected subgraph. It cannot create a graph cycle; at termination the retained edges form a spanning tree. The stopping time is the cover time, finite almost surely. The nontrivial conclusion is that every spanning tree has exactly the same probability, independently of the starting vertex.[ref]
Repeated visits add no edges, which can make the method slow when only a few unvisited vertices remain. Wilson's algorithm instead attaches loop-erased random walks. On a recurrent infinite connected graph, the first-entrance construction continues indefinitely and gives the corresponding infinite-volume uniform spanning tree.