Probabilistic combinatorics Created 2026-09-24 Updated 2026-11-05
Probabilistic combinatorics uses probability to study discrete structures and to prove that particular structures exist. One chooses a random object and shows that the probability of the desired property is positive, without necessarily constructing an explicit example.
For example, color the vertices of a finite graph independently with two colors. Each edge crosses the resulting cut with probability , so the expected cut size is half the number of edges. Some outcome therefore has at least that many crossing edges. Random graphs, concentration inequalities, and the Lovász local lemma extend this idea to more demanding existence questions.
Probability Created 2026-10-03 Updated 2026-10-14
The probability of an event is its value under a probability measure, a real number between zero and one. It compares the mass assigned to that event with the unit mass of the whole sample space. For a finite sample space with equally likely outcomes, . For unequal outcome masses, add their individual probabilities instead.
For example, selecting a coin with head probability with chance , or a coin with head probability with chance , gives head probability . This is the law of total probability: averaging over the hidden selection is part of calculating the outcome's probability.
Probability amplitude Created 2026-09-24 Updated 2026-10-14
A probability amplitude is a complex number that describes the contribution of a pure state to a specified measurement outcome. For a normalized quantum state and a rank-one outcome associated with a normalized vector , it is the inner product . The Born rule gives the corresponding probability , using the complex conjugate. Thus an amplitude can be negative or complex, while a probability is real and nonnegative. A wavefunction is the analogous position amplitude: its squared modulus gives a probability density, which must be integrated over a region to obtain a probability. [ref].
The extra information is the quantum phase. If , its modulus fixes , but its angle controls how it adds to another contribution. In the complex plane, picture amplitudes as arrows: add the arrows, then square the resulting length. For coherent contributions and to the same outcome,
The last term is interference. Adding probabilities first loses it. Contributions with different relative quantum phases can reinforce or cancel even when their individual squared moduli are fixed.
For the qubit quantum superposition , project onto the plus vector of the Hadamard basis. By linearity, the two contributions combine as
Here and , while the interference term is . At , the arrows align and the plus probability is . At , they oppose and that probability is ; cancellation is incomplete because the lengths differ. At , the arrows are perpendicular and the cross term vanishes. The minus amplitude uses , reversing the cross term. These are alternate projective measurements on identically prepared copies, rather than a sequence of measurements on one copy.
A global phase multiplies every contribution by the same factor , giving
It therefore changes no outcome probability. Changing a relative quantum phase can change the angle between contributions and hence their interference. Keeping amplitudes until the last step makes quantum circuits and matter-wave interference calculable; discarding their angles prematurely discards physically testable information. The Born rule example compares two measurement bases explicitly.
Probability calibration 2026-11-05
Probability calibration means that reported probabilities agree with the frequencies of the outcomes they describe. For binary classification, let be the true label and let be the predicted positive-class probability. Population calibration is the conditional expectation condition
Among cases receiving a value near , the positive fraction should therefore be near , with uncertainty in any finite sample.[ref]
A simple example separates calibration from discrimination. Suppose the population has a positive fraction of and a predictor always reports . Then , so it is calibrated, although it cannot rank one case above another. Conversely, replacing a useful score by a strictly increasing transformation such as preserves ranking but generally changes the claimed probability. Thus ordering cases and attaching reliable numerical probabilities are different tasks.
A reliability diagram estimates the agreement by grouping predictions and comparing each group's mean prediction with its observed outcomes. Assess it using suitable held-out observations. A calibrator fitted to predictions on the same observations used to fit the original model can inherit an overly optimistic picture of performance; fitting and evaluation need appropriate separation.[ref]
A 2017 study found substantial confidence miscalibration in the evaluated neural networks, even when prediction accuracy improved. It also tested temperature scaling as a compact post-processing adjustment. These were empirical results on specified models and datasets, rather than a theorem that all neural networks are miscalibrated.[ref]
Probability current velocity Created 2026-10-25 Updated 2026-11-05
Where a probability density is positive, its Fokker-Planck probability current can be written , giving a continuity equation . This velocity transports probability. It is not a differentiable instantaneous velocity of an overdamped Brownian motion path. In the Hookean dumbbell model, its osmotic term is .
Probability distribution Created 2026-09-24 Updated 2026-10-18
A probability distribution describes how the values of a random variable are allocated among possible outcomes. More precisely, the law of a random variable assigns each measurable set the probability
It is a probability measure on the values of . The underlying experiment can be more elaborate than the output: different experiments may produce the same probability distribution. The law of a random variable retains the probabilities needed to answer questions about that output. [ref].
For a finite example, let take values with probability mass function , , . Its probabilities sum to one. The event has probability , whereas has probability : including one endpoint matters when it carries positive probability.
For a contrasting random variable , choose the probability density function on , and zero elsewhere. It integrates to one. Now , while every single outcome has probability zero. The probability density function can have height : probabilities come from integrals over outcome ranges.
Figure 1. . Left: takes values with probability masses , so its cumulative distribution function jumps at those values; open and filled markers show the excluded and included heights at a jump. Right: has probability density function on the interval and cumulative distribution function there. The shaded integral over and the corresponding cumulative distribution function increase both equal . Details.
The cumulative distribution function answers all threshold questions for a real random variable, regardless of whether there are jumps or a probability density function. A quantile function reverses the direction of the question: given a cumulative probability level, find a threshold. This connects descriptive summaries to inverse transform sampling, which constructs a chosen probability distribution from a uniform distribution.
Probability generating function of an independent random sum Created 2026-10-18 Updated 2026-10-25
Let be a nonnegative integer-valued random variable, and let be nonnegative integer-valued independent and identically distributed random variables, with common probability generating function . Require the whole sequence to be independent of , so are jointly independent. Set the random sum
with the empty sum equal to zero. Given , the probability generating function of an independent sum yields the conditional expectation . By the law of total expectation,
The composition is valid because . Merely making the independent of each other does not preserve their conditional laws when depends on them. This is the probability generating function version of transform composition for an independent random sum.
For a Poisson distribution count with mean , substitution into gives a compound Poisson distribution with
If the jumps have finite second moment, conditioning also gives mean and variance . The extra spread comes from randomness in the count as well as randomness in the jumps.[ref]
For an original example, choose and jumps taking values one and two with equal probability. Keep the independence assumptions above. Then
Here , , and . The law of total expectation and law of total variance give
Thus the aggregate is not itself a Poisson distribution, whose mean and variance would coincide.
To recover the probability mass function without repeated differentiation, use and compare coefficients:
For example, . As an independent check, expanding gives
Figure 1.
A random number of one-or-two jumps gives a compound Poisson count
. The upper diagram separates the Poisson distribution count, the independent and identically distributed jumps, and their random sum. Below are calculated coefficients of for , with the omitted tail probability reported explicitly. They are exact model probabilities evaluated numerically, not observed data; the displayed masses have not been renormalized. Details.
The plotted probability masses stop at 20, although the support of a probability distribution is unbounded. The omitted tail probability is
This model has bounded jumps and an unbounded count. Its entire probability generating function does give a finite moment-generating function at every real argument, but the general random sum composition only guarantees the stated domain.
Probability inequality Created 2026-09-24 Updated 2026-10-18
Probability inequalities bound event probabilities from limited information, such as moments, without requiring a complete probability distribution. Markov's inequality uses a nonnegative random variable's expected value; Chebyshev's inequality uses a variance to bound deviations from a mean. The attraction is a guarantee that applies to many possible probability distributions. Their bounds can be conservative for a particular model, and distributions attaining equality show when the available information really cannot give more.
Probability mass Created 2026-10-14 Updated 2026-11-05
The probability mass at an outcome is the probability of its singleton, . It equals the jump of the cumulative distribution function. For a discrete probability distribution these masses form the probability mass function; a continuous probability distribution gives every individual outcome mass zero. Positive probability mass at a point is distinct from the height of a probability density function.
Probability mass function Created 2026-09-24 Updated 2026-11-05
For a discrete probability distribution, the probability mass function of its random variable is
The sum ranges over its finite or countable set of possible values. An event's probability is the sum of the masses of the included values. For the example under probability distribution, . The cumulative distribution function sums masses below a threshold; its jump at a value equals that value's probability mass. This differs from a probability density function, whose height is not a point probability.
Probability measure Created 2026-09-24 Updated 2026-10-14
A probability measure is a nonnegative, countably additive measure with total mass one. Thus , and for pairwise disjoint events ,
The complement of an event has probability . The probability of a union of overlapping events needs a correction: . Counting the overlap once is the simplest instance of the inclusion-exclusion principle.
A zero-probability event need not be impossible as a member of the sample space. Under the continuous uniform distribution on , every individual point has probability zero, while the whole interval has probability one. Countable additivity applies to countable unions, not arbitrary uncountable ones; there is no contradiction.
Probability model Created 2026-10-25 Updated 2026-11-05
A mathematical account of random outcomes using a probability space and specified random variables. It determines probabilities for events or observed data. A statistical model commonly supplies a family of such probability distributions with unknown parameters; choosing a model and estimating its parameters are distinct tasks.
For a string of empirical distribution , independence gives
Multiplying this by the size of a type class gives its exact probability. The entropy bounds for a type class then imply
These bounds apply to one attainable empirical distribution, not automatically to a tail event containing many classes.[ref] If but , every string in that class is impossible and .
As an exact example, take an independent and identically distributed binary source with . Each balanced four-symbol string has probability . There are six such strings, so
The relative entropy is . The exponential upper bound is , visibly larger than the exact probability. It captures the cost of an atypical frequency without supplying the exact finite-length prefactor.
For , the exact probability of twenty ones is
while the exponential upper bound is approximately . At the source frequency , relative entropy is zero and the upper bound is one; the exact probability of ten ones is only about . A likely neighborhood of frequencies need not give a large probability to a single exact profile.
Figure 1.
Relative entropy controls the rarity of an empirical frequency
. Exact probabilities from the binomial distribution for each possible number of ones in forty independent and identically distributed trials with , compared with the exponential relative entropy upper bound. The curves are calculated from a stipulated model, not observed data; the vertical scale is logarithmic. Details.
The striking cancellation is that there are about strings in a class, but each costs about . The information entropy terms cancel, leaving relative entropy as the rarity exponent. Summing over polynomially many classes preserves that leading exponential scale. This is the elementary counting mechanism behind finite-alphabet versions of Sanov theorem and many error exponents in hypothesis testing.
Probability of a useful unit in Shor factorization Created 2026-10-06 Updated 2026-11-05
For an odd integer having at least two distinct prime divisors, choose a uniform unit . The Chinese remainder theorem for unit groups makes its odd-prime-power components independent cyclic groups. Failure of factor extraction from an even modular order requires all components to have equal 2-primary order exponents. For any component each possible exponent has probability at most , so conditioning on another component bounds failure by . Excluding the identity unit only improves the success proportion.
Probability sampling 2026-10-07
Probability sampling chooses observational units by a specified random mechanism with known inclusion probabilities. This separates design-based representativeness from the convenience of obtaining particular observations. Simple random sampling, stratified sampling and cluster sampling are different designs with different precision and cost properties.
Probability space Created 2026-09-24 Updated 2026-10-14
A probability space is a measure space whose total measure is one. The sample space contains the elementary outcomes; the sigma-algebra contains the events to which the model assigns probabilities; the probability measure supplies those values. The sigma-algebra lets us combine observable questions using complements and countable unions while remaining within the model.
For two independent uniform dice, take , , and give each ordered pair mass . A random variable might record the sum, the larger result, or whether both results are even integers. These are different functions on the same sample space, rather than different elementary experiments. A probability distribution records the mass of the values of one such random variable and can forget information retained by the full probability space.
Probability theory Created 2026-09-24 Updated 2026-10-18
Probability theory describes uncertainty through a probability space: possible outcomes form a sample space, observable questions are events, and a probability measure assigns them numbers between zero and one. The Kolmogorov axioms make those assignments consistent. They let us combine information about several events, update it through conditional probability, and study random variables without listing every possible outcome separately.
For example, roll two dice whose results are independent random variables, each with a discrete uniform distribution on . There are 36 equally likely ordered outcomes. Only have sum seven, so that event has probability . The sum itself is not uniformly distributed: sum two has only one outcome. Choosing a probability distribution for the elementary outcomes is part of the model; equal likelihood does not follow merely from counting the named possibilities.
The subject becomes especially useful when complete outcome lists are enormous or infinite. Independence turns a joint calculation into simpler pieces, expected value summarizes a random variable, and the law of large numbers explains how averages can become predictable even when individual observations are uncertain. The central limit theorem describes the scale and shape of many remaining fluctuations. These are distinct claims: a small variance of an average does not make every observation close to its expected value.
There is a satisfying unity here: dice, hidden causes, and Brownian motion all use the same rules for events and conditional probability. A model still needs justification. Its exact deductions describe what its assumptions imply; comparison with observations belongs to statistical inference.
Probability vector Created 2026-10-25 Updated 2026-11-05
A probability vector lists the probabilities of the outcomes in a finite sample space. Its entries are nonnegative and sum to one, so a column probability vector is a point of a probability simplex. Row and column conventions describe the same probability distribution, but they determine whether a stochastic matrix acts on the right or its transpose acts on the left.
Probable error Created 2026-10-14 Updated 2026-11-05
The probable error is the half-width of an interval around a specified central value containing probability . For a normal distribution with , its quantile function gives
where is the standard normal cumulative distribution function and is the standard deviation. The factor is specific to the normal distribution. The centered Cauchy distribution with parameter has probable error , despite having no finite variance. Thus a central probability width need not require a finite second moment.