Tail event Created 2026-09-24 Updated 2026-10-14
A tail event is an event , where is the tail sigma-algebra of the chosen sequence of random variables. It concerns information available arbitrarily far along the sequence. In the measurable coordinate models described in finite-prefix invariance of tail events, any finite edit preserves whether it occurs.
This is stronger than merely needing a long waiting time. On , with denoting heads, let , taking if there is no head. The event
is not a tail event: changing only from zero to one changes membership. Under fair independent Bernoulli trials its probability is . Even the event , of probability one in this model, is not a tail event as a literal set: the all-zero sequence and the sequence with just one initial head differ in one coordinate. A probability of zero or one does not characterize tail events.
Tail measurability of limits of sample averages Created 2026-10-05 Updated 2026-10-14
Let be a sequence of finite real random variables, and write for its sample mean. For fixed and , put . Then, at each outcome,
Consequently . The right-hand limit superior is a measurable function of for every , so the extended-real random variable is measurable with respect to the tail sigma-algebra. The same holds for the limit inferior. Thus the event of convergence to a finite limit of a sequence, and the event for any specified real , are tail events.
For a worked deterministic example, let alternate , and replace its first three entries by . For every the two sample means differ by exactly , so both converge to . Finite edits can change small-sample answers while preserving the infinite limit of a sequence.
Under independence, Kolmogorov's zero–one law makes each specified convergence event have probability zero or one. It does not select which value occurs. If a finite random variable measurable with respect to the tail sigma-algebra exists, the events for rational each have probability zero or one; continuity of probability and their nesting force to be constant almost surely. For fair independent Bernoulli trials, the strong law of large numbers establishes almost surely; the zero–one conclusion alone proves neither convergence nor the value .
Tail of a sequence 2026-10-14
A tail of a sequence consists of its terms from some index onward, retaining their order and repetitions. Discarding finitely many initial terms does not change its limit of a sequence or whether it is a Cauchy sequence. A tail can also be considered as the set of values when forming an infimum, supremum, or tail diameter of a sequence; that set alone forgets the original order and repetitions.
Tail sigma-algebra Created 2026-09-24 Updated 2026-10-14
For a sequence of random variables on a probability space , define
The decreasing sigma-algebras are generated by the listed random variables. Their intersection consists of events expressible after discarding every finite prefix. No independence is required.[ref]
The point is to distinguish a long observation record from a property of an infinite sequence. The event of seeing infinitely many heads and the event that sample means converge survive any finite change, while an exact first-head time does not. Kolmogorov's zero–one law adds the striking conclusion that under independence each tail event has probability zero or one; the tail sigma-algebra itself can still contain many nonempty sets.
Telescoping sum Created 2026-10-14 Updated 2026-10-20
A telescoping sum cancels intermediate sequence terms, leaving boundary terms. For a finite sequence of real numbers , the displayed identity follows because every occurs once with each sign. Applying it to an infinite series also requires checking the limit of the boundary terms; finite cancellation alone does not prove that the series is a convergent series.[ref]
For , expanding the finite sum gives
No monotone sequence assumption is required. Consider the original sequence . Its successive finite differences are , so
The large intermediate rise and fall disappear from the net change. This is useful whenever one knows successive changes rather than every absolute value: adding the changes reconstructs the final value from the initial one. It also checks a cumulative-update calculation without requiring all increments to be positive.
Figure 1.
Opposite signs cancel the intermediate sequence terms, leaving the final value minus the initial value
. Original nonmonotone sequence . Linked green entries have the same magnitude and opposite signs; the unmatched entries are and . The increments are , whose sum is one. Details.
A finite difference measures one discrete change. The identity is the discrete counterpart of the fundamental theorem of calculus: accumulation of changes returns the endpoint difference. The related summation by parts transfers a finite difference from one factor of a product to another, with explicit boundary terms.
Temporal locality 2026-10-13
Temporal locality is the tendency for the same item to be accessed again soon after an earlier access. For computer memory, the item might be an array element, a cache line or a memory page; always specify the unit. Temporal locality concerns reuse over time, whereas spatial locality concerns accesses to nearby addresses. Both are properties of a workload, rather than guarantees about its next memory reference. [ref]
For a worked example, let and denote two distinct cache blocks at unrelated, nonadjacent physical addresses. An initially empty fully associative cache holding two cache lines, with LRU replacement, receives the sequence . The first causes a cache miss and leaves resident; causes another cache miss and leaves both and resident; the last is a cache hit. LRU replacement now regards as older than . The benefit comes from temporal locality of , irrespective of how far apart the cache blocks lie. With capacity one, the same sequence gives three cache misses: reuse helps only if the item survives until it is needed.
The appealing idea is that a small memory cache can serve a large computation when its currently useful data stay small. Repeatedly reading a counter or executing the same instructions can exploit temporal locality. LRU replacement and recency-based approximations try to retain recently used items. A working set records recent demand; if the active working set cannot fit in resident memory pages, memory thrashing can defeat this benefit. At cache line granularity, even accesses to different array elements can reuse the same cache block, as the spatial locality example shows.
Peter J. Denning's May 1968 paper connected recent memory page use to near-future demand through the working set. Section 3 explicitly discusses the clustering of references to the same memory page in time. This is a documented early treatment of the reasoning behind temporal locality, rather than a claim about who first coined the term. [ref]
Test oracle 2026-11-05
A test oracle determines whether an observed test result is acceptable. It can be an explicitly expected output, a mathematical property, a trusted reference implementation or another justified source of comparison. Generating many inputs without an oracle does not by itself establish whether the results are correct.
For a sorting routine, an oracle can check both sortedness and preservation of the input multiset. Returning an empty sequence passes a sortedness check but fails preservation for a nonempty input. A differential test instead compares implementations; a disagreement exposes a problem without necessarily identifying which implementation is wrong. Hypothesis documents both reference-oracle comparisons and differential comparisons in its equivalence-test generator.[ref]
Memory thrashing is repeated costly cycling of memory pages out of and back into computer memory, leaving little useful computation between page faults. Active demand can exceed the available page frames, especially when multiprogramming admits too many operating-system processes. A high page fault rate during initial loading alone does not establish memory thrashing. [ref]
Consider one operating-system process making the 20 memory references : five repetitions of four memory pages. Start with an empty resident set, use demand paging and exact LRU replacement, and assume no prefetching or competing operating-system processes. A hit finds the requested memory page resident; a miss requires a nonresident page fault. With three page frames, references 1–3 load pages 1–3. Reference 4 evicts page 1, reference 5 reloads page 1 and evicts page 2, and the cycle continues: every return finds its memory page evicted. With four page frames, only the first four references miss; all four memory pages then remain resident.
Available page framesMisses in all 20 memory referencesOverall page fault rateMisses in references 5–20Page fault rate in references 5–20320100%16100%4420%00%
The four initial misses with four page frames are compulsory first-use misses from the empty resident set. They are startup work; the three-page frame case keeps faulting after startup. This makes the difference between memory thrashing and loading a new working set visible. For the three-page frame trace, each reused memory page has three distinct intervening memory pages, so LRU replacement has already evicted it before its next use.
Figure 1.
The same 20 memory references under LRU replacement: three page frames miss every time, four miss only during startup
. Details.
To quantify the cost, assume each hit takes 100 nanoseconds and each miss incurs an additional 1 millisecond of page fault service, followed by the same 100-nanosecond memory access. These are toy latencies, not measurements. With miss probability , the expected value of access time is
The service cost is additional: it does not include the final 100 nanoseconds. Thus gives and gives , approximately a fivefold ratio over the complete trace. Over references 5–20, the corresponding ratio is : repeated page faults dominate the useful accesses. The expected value model follows the additive miss-penalty convention of OSTEP chapter 22, section 22.1. [ref]
Not every page fault performs disk input-output: demand paging can allocate zero-filled memory pages, and copy-on-write can copy an existing page frame. The toy service cost models expensive misses; the miss trace alone establishes residency behavior, while memory thrashing additionally concerns repeated costly cycling. [ref]
Possible remedies are more resident page frames, less multiprogramming, or reorganizing accesses to improve temporal locality. For this toy sequence, one extra page frame suffices under LRU replacement; that is not a universal threshold or policy. Page replacement alone cannot make every simultaneously needed memory page fit.
// Target: computer-science.bigb
Tits word reduction theorem Created 2026-09-24 Updated 2026-11-05
Every word in simple Coxeter generators can be reduced by braid moves and cancellations . Consequently, a word is reduced exactly when no sequence of braid moves can make a cancellation possible.
Topological order Created 2026-10-14 Updated 2026-11-05
A topological order of a finite directed graph is a sequence containing every vertex exactly once, with
Thus every directed edge points forward in the list. Equivalently, a bijection assigning positions satisfies for every directed edge . A topological ordering names the same kind of list. [ref]
The toy directed acyclic graph has exactly five topological orders: , , , , and . These lists were checked by enumerating all permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with , since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: and are consecutive in without a directed edge between them.
A directed cycle would force the impossible chain of position inequalities . In the toy example, adding requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a directed acyclic graph. The empty directed graph has the empty sequence as its topological order.
There is also a useful connection to partial orders: define when or there is a directed path from to . For a directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.
Topological vector space Created 2026-09-24 Updated 2026-10-14
A topological vector space is a vector space over or , equipped with a topology such that vector addition and scalar multiplication are jointly continuous:
The domains carry the product topology, and the scalar field carries its usual topology. Joint continuity permits both inputs to vary at once. Here the definition does not impose the Hausdorff condition; we state it separately when needed. [ref].
Every normed vector space is a topological vector space: the triangle inequality gives , while
controls scalar multiplication near any . More generally, a seminorm topology supplies many measurements of smallness, rather than one norm. Translation by any vector is a homeomorphism, so a neighbourhood basis at zero determines all neighbourhoods by translation.
The compatibility matters: on a nonzero real vector space, the discrete topology makes vector addition continuous, but not scalar multiplication. For , the sequence of scalars tends to zero, whereas the sequence never enters the open set . Thus choosing a topology arbitrarily need not respect the linear algebra.
This framework lets functional analysis choose the appropriate notion of limit of a sequence. Norm topology measures one global error, weak topology tests linear functionals, and the Fréchet space of smooth functions controls every order of derivative. In each case the operations forming linear combinations are continuous, making approximation compatible with the underlying equations.
Topologist's sine curve Created 2026-10-14 Updated 2026-10-31
Consider the graph of a function , using the sine of the multiplicative inverse of , together with a vertical closed interval:
Give the subspace topology from the Euclidean plane. The symbol denotes a Cartesian product. The right endpoint belongs to . The continuous map sends the connected real interval onto . Hence is connected, and its closure is connected by closure of a connected set. Every height in is approached as tends to zero; for example,
For , these inputs are and . For any other height , choose with ; then the sequence lies in and has limit of a sequence .
Nevertheless, has exactly two path components, and . Within , join inputs by the continuous path . Within , use for heights .
The obstruction to a continuous path between and is persistent oscillation, not a visible gap. Proof outline: suppose such a path exists, directed from to , and take its last time in . Immediately afterwards its first coordinate approaches zero and its second coordinate is . The intermediate value theorem forces the first coordinate to pass through inputs of both displayed types arbitrarily close to that departure time. The second coordinate therefore takes both values and arbitrarily close to that time, contradicting continuity. [ref]
Figure 1.
The topologist's sine curve has one connected component and two path components; the graph of a function is drawn only for , with further oscillations omitted near the vertical closed interval
. Details.
The sampled graph of a function illustrates the formulas; it does not prove connectedness or the failure of path connectedness. Taking a closure preserves connectedness, but this example shows that it can destroy path connectedness.
Total variation Created 2026-09-24 Updated 2026-11-05
Total variation measures accumulated absolute change rather than just the difference between two endpoint values. For a real or complex sequence , its total variation is
allowing . The triangle inequality gives . Finite variation therefore makes the sequence Cauchy and hence convergent in or .
The converse fails. The sequence tends to zero, but , whose sum diverges. Small late values can still accumulate infinitely much back-and-forth movement.
For a function on an interval, the total variation of a function replaces the sum over consecutive indices by a supremum over all partitions of an interval. For spatial fields, the total variation seminorm on a domain uses the distributional derivative as a measure. Total generalized variation extends that regularization idea to higher-order structure. These settings share cumulative-change control, while their definitions specify different index or spatial domains.
Totient chain Created 2026-10-20 Updated 2026-11-05
The sequence obtained by iterating Euler's totient function on a positive integer. Since for , the sequence reaches 1. Counting both endpoints gives the length recurrence relation and ; increasing order of therefore suffices for dynamic programming.
Trail in a graph 2026-10-14
A trail is a walk whose edge sequence has no repetitions. Its vertices may repeat, including its first and last vertices. The zero-length walk is a trail because it repeats no edge. Every graph path is a trail, but the converse fails: the trail in the shared example is
Its six edges are pairwise distinct, although occurs twice. Visiting a junction again and traversing a road segment again are different events.[ref]
In an undirected graph, traversing and then repeats the same edge; direction of travel does not give it a new identity. In a multigraph with distinct parallel edges joining and , the closed walk is a trail, whereas is not. Both have the same vertex sequence . In a directed graph, separate directed edges and may instead be used once each; record their identities and obey their directions. Thus testing a trail means checking the actual edge records, not merely checking consecutive endpoint labels.
For a finite graph, a trail has length at most ; unrestricted walks can have arbitrarily large length whenever a positive-length closed walk exists, since it can be repeated. An Eulerian trail is the special trail that uses every edge, so its length is exactly . Our length-six trail omits and is therefore not an Eulerian trail. In a road-inspection model, a trail describes servicing its selected segments once while allowing returns to junctions; requiring service of every segment leads to the Eulerian trail question. If extra travel between serviced segments is necessary, the complete journey can be a walk even when each segment is serviced only once. This distinction keeps the service requirement separate from the route actually travelled.
Type I–type II inverse principle for Möbius correlation Created 2026-10-07 Updated 2026-11-05
For , if and , the Vaughan identity for the Möbius function gives a type I sum or a type II sum of modulus at least . The first is , with . The second is , with . Both coefficient sequences are bounded by the divisor function. Thus correlation forces either detection by small-modulus periodic indicators or a large multiplicatively organized bilinear sum, without claiming that itself is literally periodic or multiplicative.
Expand an infinite first-order structure by Skolem functions, choose distinct elements , and fix a nonprincipal ultrafilter on . For each finite subset of the required index order, form the ultrapower over using the ordered Fubini product of ultrafilters. Pullback along coordinate projections gives coherent elementary maps by the Łoś theorem. In their directed limit of elementary embeddings, the classes of the coordinate functions are distinct and form an order-indiscernible sequence; every first-order formula on increasing coordinates has the same nested ultrafilter test. Their Skolem hull gives an Ehrenfeucht-Mostowski model. An index-order automorphism sends a term in the generators to the same term in the transported generators; indiscernibility makes this well defined. Uniqueness is in the specified Skolem expansion, not necessarily in its reduct. If generators must respect a definable infinite order, first produce an increasing sequence by an ultrapower of finite increasing chains.
The Unicode Bidirectional Algorithm computes visual text order from logical text order. Unicode bidirectional classes and context determine bidirectional embedding levels: levels with an even integer value run left-to-right, and those with an odd integer value run right-to-left. Stored code points retain their order; text shaping is separate.[ref]
After levels and line boundaries are resolved, level-based reordering of bidirectional text descends from the largest level to the smallest level that is an odd integer. Each pass reverses maximal consecutive runs at or above its level.[ref]
Here is a small example with the resolved levels supplied. The labels each represent a distinct right-to-left text character, while represent left-to-right text characters. All rows below are written in physical left-to-right order. Start with
The level 2 pass changes the middle digits to . The level 1 pass then reverses the whole five-item middle run, producing
The digits have been reversed twice, preserving their original internal order. Reversing the entire stored sequence once would instead exchange and and leave the digits in the wrong order. This example demonstrates the reordering step, not how all Unicode bidirectional classes are resolved.
Figure 1.
Two level-based reversals preserve the internal order of the digits
. Original illustration with supplied bidirectional embedding levels. The boxes denote individual abstract text characters, not literal multi-character labels. Details.
A bidirectional isolate limits directional interaction between inserted text and its surroundings. Markup can express isolation without storing explicit formatting code points.[ref]
Mark Davis created the annex's initial version; later revisions extended it.[ref]
Uniform convergence Created 2026-09-24 Updated 2026-10-14
A sequence of functions converges uniformly to , where is a metric space with metric , precisely when
For real numbers, use the absolute value . Compare the universal quantification and existential quantification:
The decisive change is whether can depend on . Uniform convergence implies pointwise convergence.[ref]
For functions taking values in real numbers on a nonempty domain of a function, the supremum error is , allowing . Then uniform convergence is equivalent to . The supremum need not be a maximum: pointwise strict bounds below only give , so use tolerance when proving this equivalence. This single error bound controls every possible input, including one chosen after seeing the index.
For and its pointwise limit on , the error is zero at one but approaches one as from below. Consequently
for every positive integer . This supremum is never attained: below one the error is , and at one it is zero. Deleting the endpoint leaves the same supremum error on . To disprove uniform convergence directly, choose : for any proposed , take and . The error equals , violating the strict tolerance. Thus a moving input defeats every proposed common threshold.
On the smaller interval , for a fixed , the pointwise limit is zero and
For and , the exact first successful common threshold is
The logarithm and floor function turn an infinite approximation statement into a finite stopping rule. At , fails tolerance , while succeeds. At and , the ratio is exactly three: is necessary because equality is insufficient. For , every error is zero. The domain of a function determines whether one threshold can certify every input.
Figure 1.
Supremum error and common thresholds distinguish uniform convergence from pointwise convergence
. Left: the error of remains one on and , but falls below from onward on . Right: the first successful threshold at a fixed input grows without bound near one. A common threshold covers all inputs at most . Both vertical axes use a logarithmic scale. Details.
For another explicit stopping rule, let on . Its uniform limit is zero and its supremum error is . For every , works, using the ceiling function. Unlike on , it controls even the endpoint.
The practical beauty of uniform convergence is that one quantitative bound can survive further operations: the uniform limit theorem preserves continuity, and uniform convergence preserves integrals on a compact interval controls accumulated error. Differentiation needs additional hypotheses, such as uniform derivative convergence with an anchored value. These results distinguish an approximation that looks accurate at selected inputs from one that justifies replacing a whole function in a calculation.
For , choose independent random variables, each with the uniform distribution on a finite set , and decode their values as a Prüfer sequence. Every sequence has probability , and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. [ref]
This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability and the path graph shape has probability . Also, for a fixed label , the Prüfer degree formula gives
Here the binomial distribution counts the independent code positions equal to . The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When , simply return the single isolated vertex.