Let a simple symmetric random walk start from a deterministic integer , and put . Then is a martingale with . The visit count includes time if .
For every integer and step , the pathwise identity
holds with . Subtract the indicator function and sum over time to obtain
The sign function of the current state is a bounded predictable process for the next increment, so the sum is a martingale transform. Alternatively, averaging the two possible next absolute values shows directly that the conditional drift is . Bounds and verify integrability at each finite time.
This is an absolute-value version of the discrete Tanaka formula. The correction records the occasions when the random walk is at the corner of the absolute-value function; away from zero that function is locally linear along a single step.
Area-coverage antialiasing assigns an edge pixel a value based on the fraction of its footprint covered by a geometric shape. In a simple rasterization model with constant foreground value , constant background value , and a uniformly weighted pixel region , let be the shape. Then
Equivalently, is the average of the shape's indicator function over . This is a spatial average: a partially covered opaque shape can produce an intermediate pixel value without its material being transparent. Filtering the image over a finite region reduces the abrupt changes produced by deciding coverage at one sample point.[ref]
For a worked example, take the unit-square pixel and a white shape covering over a black background. The diagonal divides the square into equal areas, so and the pixel gets half the white value. A single center sample lies exactly on the edge and must choose one side by a convention; a tiny edge movement can flip that binary decision. The covered area instead changes continuously. The arithmetic applies to values proportional to light, before a nonlinear display encoding.
Exact geometric coverage and multiple sample tests are two ways of estimating this average; a finite set of samples can miss a sufficiently thin shape. Uniform footprint averaging also has limits: its abrupt filter boundary does not remove every high-frequency component, so it reduces aliasing without guaranteeing a perfectly band-limited image.[ref]
Baire class one function Created 2026-09-28 Updated 2026-11-05
A real-valued function on a metric space is Baire class one when it is a pointwise limit of continuous functions. On a complete metric space, its continuity points form a dense G-delta set, and its discontinuities form a meagre set. The Baire category theorem also applies after restriction to any nonempty closed subset : the restricted function has a dense G-delta set of relative continuity points in .
Relative continuity here is essential. For the Cantor set , its indicator function is Baire class one, since the continuous functions
converge pointwise to . The distance to a set is continuous, which justifies these approximants. Every point of is a discontinuity of on , because has empty interior. Yet is the constant continuous function one. Thus relative continuity on a closed subset does not assert ambient continuity at one of its points.
Balanced indicator function of a finite subset Created 2026-10-05 Updated 2026-10-06
For nonempty finite set and , let be the density of a finite subset. The balanced indicator function , extended by zero to an ambient finite group, has sum zero and vanishing zero Fourier coefficient. The sum of on a subset is , measuring the excess density of a finite subset there.
Binary selection mask 2026-11-05
A binary selection mask records which pixels belong to a chosen subset of an image. On a finite pixel grid , it is the indicator function
It can represent an area region of interest, the result of image thresholding or a combination of selection rules. The mask describes membership; its entries need not equal the underlying image intensities.
For a selected pixel count , the count and selected arithmetic mean are
Consider the original arrays
The selected values are 0, 20 and 40, so and . The selected zero-valued pixel still contributes to the denominator. Replacing excluded pixels by zeros and averaging all six entries would instead give : that asks a different question. An empty mask has , so this selected-mean formula is undefined.
For rectangular pixels with calibrated dimensions and , the complete-pixel area from a calibrated pixel count is . These are stipulated array values and cell dimensions, not a measurement of an object.
A stored mask can use another two-value encoding. ImageJ's Create Mask command stores 255 inside an area selection and 0 outside, corresponding to in this model.[ref] Summing gives 765 in the example, rather than the selected count 3. Convert the encoding or count selected entries before interpreting a sum as an area.
Two normalized masks and combine by set intersection through . Their complement within the specified grid is . Record the foreground-background polarity, coordinate alignment and grid extent when transferring a mask between images.
This is the part-preserving homomorphism density of a four-cycle in a bipartite graph with independently uniform labels in the first part and in the second. Repeated labels are included. It equals the fourth power of the four-cycle norm of the adjacency indicator function. It differs at finite sizes from a count requiring four distinct vertices.
For every there is a positive integer such that every finite bipartite graph has an -regular pair of partitions with at most cells on each side.
To prove this, give the uniform probability measure, let be the indicator function of the edge set, and for partitions define their energy by
This conditional expectation is an orthogonal projection, so . If the partitions are not -regular, choose witnesses and in every irregular cell pair and refine each by all its and each by all its . The refined energy exceeds the old energy by
On the absolute value function of the mean of the difference is greater than , while this rectangle occupies at least an fraction of . The Cauchy-Schwarz inequality therefore contributes more than from that cell pair. Irregular pairs have total weight greater than , so every refinement raises the energy by more than . The process stops after at most refinements. If the current cell counts are , the construction gives at most new cells, so a finite iterated bound depending only on supplies .
Events turn Boolean operations into operations on sets. For a die with sample space , let be the event “even outcome” and the event “outcome at least four”. At outcome , use the indicator functions and . Then
Thus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within . Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities , , , and , respectively. No assumption of independent events is needed for the set identities; indeed and here are not independent, since .
Boole's inequality 2026-10-14
Boole's inequality, also called the union bound, bounds the probability that at least one of several events occurs by adding their individual probabilities. For a finite or countable family of events in the same probability space,
The union includes outcomes where several events occur together. There is no independence assumption: adding the individual probabilities counts such outcomes repeatedly, which can only make the sum larger. The cap at one uses the total mass of a probability measure. For infinitely many events, the sum is a nonnegative series, possibly infinite; an infinite sum gives only the bound one. This is countable subadditivity of a measure specialized to a probability measure. See Probability: Theory and Examples (fifth edition) by Rick Durrett (Section 1.1, Theorem 1.1.1(ii), printed p. 2).
For example, choose uniformly from the twelve outcomes , using the discrete uniform distribution. Put . If , these are disjoint events and their union has probability , exactly the union bound. If , the union has only six outcomes, so its exact probability is , although both individual probabilities are still and the bound is still . If , the exact probability falls to with the same bound. These examples isolate overlap in the union bound by keeping the individual probabilities fixed.
Figure 1.
The same individual event probabilities give different exact union probabilities as overlap increases
. Each panel is a fully specified discrete uniform distribution on twelve numbered outcomes. Blue means only, orange means only, purple means their intersection, and white means neither. The bottom bars compare the exact union probability with the sum of the individual probabilities. The three unions contain eight, six, and four outcomes; the sum counts eight in every panel. Details.
The union bound is useful when each event is easy to control but their joint behavior is difficult to determine. A short proof uses indicator functions: at every outcome,
Taking expected values and using linearity of expectation proves the finite bound.[ref] For a countable family, the finite unions increase to the full union; continuity of probability passes the finite inequalities to the limit. The closure of a sigma-algebra under countable unions ensures that this limiting union is an event. For the continuity of probability step, see Probability: Theory and Examples (fifth edition) by Rick Durrett (Section 1.1, Theorem 1.1.1(iii), printed p. 2).
Bounded exceptional primes for least quadratic nonresidues Created 2026-10-06 Updated 2026-10-14
If, for every , the smooth numbers up to with all prime factors at most have density at least , then for fixed there are only primes with . Apply the variance form of the large sieve to the indicator function of the -smooth numbers up to . For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times times that count. The density assumption with finishes the argument.
The distributional derivative of this indicator function is on the vertical segment , so its total variation seminorm on a domain is one. This is singular with respect to planar Lebesgue measure, whereas Sobolev space weak derivatives in have integrable densities. Its bounded-variation space norm is .
Cantor's diagonal argument Created 2026-09-24 Updated 2026-10-14
Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is , where is coordinate of row . Construct a new binary sequence by
It differs from row at coordinate , for every . It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.
Figure 1.
Flipping the nth coordinate of the nth row constructs a binary sequence missing from every proposed row
. Details.
For the displayed window, the first six diagonal bits are , so the new sequence starts . The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.
The connection with power sets is exact: a subset corresponds to its indicator function, with a one in position exactly when . Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction . This reusable method turns a purported complete list into an explicit omitted object.
In his paper [ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.
If a strongly additive arithmetic function is supported on primes up to , its th uniform central moment differs from the independent Bernoulli random variables model with probabilities by . Expansion of divisibility indicator functions reduces the comparison to .
For a standard score and , split kurtosis into the contribution from within standard deviations of the mean and the contribution from outside:
The indicator function selects the central outcomes. The bound follows directly from there. Thus : when kurtosis is large, any fixed central range contributes a small fraction. This is a precise reason to emphasize extreme standard scores rather than peak height.[ref]
For the rare-outlier three-point distribution with , and . At the other endpoint , all probability mass lies at , so : central dominance is possible when kurtosis is small. More generally, the Cauchy-Schwarz inequality gives ; the equally weighted outcomes attain this minimum.
Circuit size class Created 2026-10-07 Updated 2026-11-05
The languages whose length- indicator functions have Boolean circuits with at most gates for sufficiently large , over a fixed bounded-fan-in complete basis. The family need not be constructible by one algorithm. Polynomial-size bounds give P/poly; the truth-table upper bound for circuit size applies even to undecidable languages.
In an arbitrage-free one-period market with finitely many assets and an equivalent martingale measure, market completeness is equivalent to uniqueness of the dominated martingale measure. Completeness prices every indicator function, forcing two measures to agree on every event. Conversely, if the attainable payoff span has dimension but is not the whole payoff space, choose disjoint positive-probability events. Their moment vectors against a basis of attainable payoffs are linearly dependent. A nonzero bounded linear combination of their indicators consequently has zero pricing moments. Multiplying an existing equivalent density by , for sufficiently small positive and negative , constructs distinct equivalent martingale measures. This proves the converse without assuming that the original space was finite. On a general probability space, completeness here means replication of all bounded claims, or equivalently all square-integrable claims when asset payoffs are square-integrable.
Computable predicate 2026-11-05
A computable predicate is a yes-or-no relation for which an algorithm halts on every input and returns the correct truth value. Equivalently, its indicator function takes values in and is a total computable function. For predicates of several natural numbers, a fixed effective tuple encoding reduces the inputs to one number if needed.
For example, defined by is computable: with a stated convention for , integer division or finite arithmetic decides it. The predicate that program halts on input within at most steps is also computable, by bounded simulation.
In contrast, the existence of some halting time, , is not a computable predicate in general: it is the halting problem. It is computably enumerable because a successful simulation eventually witnesses it. Thus an unbounded existential quantifier can turn a decidable relation into one whose false instances cannot be recognized by a terminating procedure.
Conditional expectation Created 2026-09-24 Updated 2026-10-14
The conditional expectation is the average of a random variable that can be predicted using specified information. It is itself a random variable: the average appropriate to one observed group may differ from that appropriate to another group. The sigma-algebra records which events can be distinguished with the available information.
For a real integrable random variable on a probability space and a sub-sigma-algebra , the conditional expectation is the almost surely unique integrable random variable that is measurable with respect to and satisfies
Its average therefore agrees with that of on every distinguishable event. The integral characterization handles discrete observations, continuous observations, and information that is not given by a single numerical value.[ref]
If the information tells us which member of a finite measurable partition contains the outcome, then on every member of positive probability,
Here is an indicator function. Zero-probability members do not determine a unique value, which is why uniqueness is only almost surely. For square-integrable , this same conditional mean is the best predictor among -measurable random variables under mean squared error; the conditional variance describes its remaining error. A conditional mean is generally not the same as the actual observed value of .[ref]
For a Borel probability measure on a compact metric space, inner regularity and outer regularity give with compact, open and . The Urysohn lemma supplies a continuous function equal to one on and zero outside , with values in . Its difference from the indicator function of is supported in and bounded by one, proving the displayed estimate. This transfers identities established for continuous test functions to measurable sets.
Convolution Created 2026-09-24 Updated 2026-10-14
Convolution combines two functions by adding their products over all ways of splitting an argument. For Lebesgue integrable functions on the real line, their convolution is
The arguments and always add to . For in the L1 space, the integral exists almost everywhere and defines another element of the L1 space, with by Young's convolution inequality. Particular examples below have a value at every .
To see what the integral counts, take the indicator function . The product equals one exactly when belongs to both intervals and . Its integral is their overlap length, so
At , the overlap is and the output is ; at , the two intervals coincide and the output is one. The result is the shifted triangular function . As changes, is a reflected and translated copy of : the moving overlap makes the entire graph visible without a difficult integration.
Figure 1.
Convolving two interval indicators measures their moving overlap and produces a triangular function
. Details.
The same calculation gives the probability distribution of a sum of two independent random variables. If are independent random variables with the continuous uniform distribution on , each has probability density function . Their sum has probability density function by convolution of probability densities. The probability density function at one is larger than near zero or two because there are more combinations of the two inputs giving that sum. Its total integral is one; its expected value is one and its variance is . These follow equally from integrating the triangular function or from linearity of expectation and variance additivity for independent random variables.
Convolution also gives a useful averaging operation. For , let . Then
the mean of in a neighborhood of . A smaller examines a smaller neighborhood. For a continuous function , this mean tends to as , an example of an approximate identity. Integrating a sharp input against a distributed convolution kernel can produce a smoother output; the triangular example turns two discontinuous inputs into a continuous output.
In signal processing, a linear time-invariant system combines shifted copies of its impulse response by the same rule. In discrete time, an input value at index contributes a scaled response at index , and discrete convolution sums these contributions. This is the superposition interpretation developed in Oppenheim, MIT Signals and Systems, Lecture 4, convolution sums and integrals. The convolution theorem then gives another description: transform both inputs with a Fourier transform and multiply their transforms. Combining shifts, combining independent quantities and multiplying frequency descriptions are three faces of the same operation.