Scope and scale of total correlation 2026-10-14
For finite alphabets, , soFor identical copies of one fair bit, the upper bound is attained and total correlation is bits. Adding another copy increases the result without introducing a new underlying random choice. The choice of coordinates and their grouping therefore matters when comparing systems of different sizes.
For more general random variables, the relative entropy against the product of the marginals supplies a definition of total correlation that may be infinite. Subtracting differential entropies is justified only when those quantities are finite and the entropy identity is valid; an undefined difference of infinities is not a definition. The finite-alphabet examples above avoid that problem entirely.
Scoring rule Created 2026-10-07 Updated 2026-10-14
A scoring rule turns a probability distribution forecast and an observed outcome into a number. For example, a forecast of rain with probability should express uncertainty more usefully than a bare prediction of rain. A scoring rule lets us compare such forecasts after observations arrive, and its choice determines whether exaggerating confidence pays. A proper scoring rule rewards an honest account of uncertainty in expected value.
There are two sign conventions. A reward is maximized; a loss function is minimized. The conversion reverses every comparison. Here the linear probability score is a reward, while the binary Brier score and the negative logarithmic scoring rule are losses. Calling all three a "score" without specifying the direction would hide the central difference.
Throughout the binary examples, the random variable has a Bernoulli distribution with actual success probability , and the report assigns probability to and to . The value is stipulated by this statistical model; it is not inferred from data or a claim that a forecasting system is calibrated. In practice the true predictive distribution is unknown, and the relevant is the conditional probability of success given the information available when the forecast is issued. Propriety evaluates incentives for reporting that predictive distribution; it does not supply the unknown probabilities.
Second moment Created 2026-10-05 Updated 2026-10-06
Second-moment bound for positivity 2026-10-14
For a nonnegative random variable with positive expected value and finite second moment, write . The Cauchy-Schwarz inequality giveswhich proves the bound in second moment method. It is the zero-threshold case of the Paley-Zygmund inequality. Equality occurs when is a fixed positive value on the event and zero elsewhere, almost surely. For with a Bernoulli random variable of parameter , equals the exact positivity probability.
The variance identity turns the lower bound into a statement about variance relative to the squared mean. A small ratio forces positivity to be likely. A positive expected value alone does not do so: keeping while taking with probability and zero otherwise makes the positivity probability as small as any chosen .
Second moment method Created 2026-09-24 Updated 2026-10-14
The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.
For a nonnegative random variable with and finite second moment, the second-moment bound for positivity givesEquivalently, . The method also includes the simpler Chebyshev's inequality bound . Thus a sequence of such random variables with has with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. [ref].
For an original toy count, let count successes in ten independent Bernoulli trials with success probability . The binomial distribution givesConsequently . The exact probability is . The first moment method and union bound only give the upper bound here. First and second moments therefore answer complementary existence questions.
The second moment method certifies a positive count, while statistical dependence can change the conclusion despite an unchanged mean
. Left: exact binomial distribution probabilities of at least one success and second-moment lower bounds for ten independent trials as the success probability varies. Right: the same ten trials with either occur independently or share one common Bernoulli outcome. Both counts have mean one, but the perfectly linked count has much larger variance and only probability of being positive. All data are original specified probability models. Details.For a sum of indicator random variables, the variance of a sum isIndependence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable : then , with mean one, variance nine, and . The second-moment lower bound is exactly . Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. [ref]
https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/mit18_226_f22_lec06-07.pdf. Zhao, MIT 18.226, §4.1: indicator covariances and Bernoulli counts
. Separable stochastic process 2026-11-05
A separable stochastic process admits a fixed countable set of indices that captures the relevant sample path behavior outside one common null set. In the usual real-valued setting on a metric space , one formulation requires a countable set that is a dense subset and a null set such that, whenever , each lies in the closure of . Thus and the corresponding process value can be approximated together from .
In particular, outside . The right side is a supremum over a countable set of random variables, so its measurability is accessible through the usual sigma-algebra operations. Continuous sample paths on have this property using the rational numbers as indices and endpoints.
The common null set matters. If has a uniform distribution on and , each fixed is zero almost surely, yet always. For any fixed countable , almost surely. Agreement at every fixed time therefore does not imply agreement of pathwise suprema.[ref]
Measurability Woes by David Pollard. Section 10.4, separable versions and the random-spike counterexample
Separate chaining Created 2026-10-13 Updated 2026-10-20
With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.[ref]
For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting in that order makes hash bucket hold , hash bucket hold , and the other two hash buckets empty. All five subsequent operations below select hash bucket because :
Separate chaining traces lookup, replacement, deletion and insertion through key equality
. Original deterministic model with . The table counts actual keys inspected, not elapsed machine time. Operations occur from top to bottom; only an absent key adds a new record, and the untouched record remains in hash bucket . Details.get(5) rejects key , accepts key , and returns after two key equality comparisons. get(13) rejects and reports absence after three comparisons. put(5,B*) examines and replaces the value without changing . delete(9) examines just the head record, removes it, and gives . Finally, put(13,E) rejects before inserting the new head record; returns to and the chain is . The successive hash table load factors are . These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.For a chain of length , lookup and deletion by key take time complexity in Big O notation. The same applies to
put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is if absence is already known; that is a different precondition. These bounds assume bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of indices. The keys and query are fixed independently of this random assignment. Then lookup has expected time complexity, where is the hash table load factor; it is expected when stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.[ref]
Lecture 8: Hashing I. 6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; pp. 4–5, chaining worst case and simple uniform hashing assumption
Here is the short calculation. For an absent query and stored keys , let be the indicator random variable of . The number of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value ; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.
The worst case remains , and an absent query takes comparisons if all records occupy its hash bucket. For instance, all collide under . Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.
Shape parameter Created 2026-09-24 Updated 2026-10-03
A shape parameter changes the form of a probability distribution without merely translating it or rescaling its random variable.
Sigma-algebra generated by a random variable 2026-10-25
For a real random variable on a probability space, is the smallest sigma-algebra making a measurable function into the Borel sigma-algebra on . The collection of all inverse images of Borel sets is already a sigma-algebra, since inverse images preserve complements and countable unions; this proves the displayed formula without completing any measure.
Simple random walk on the integer line Created 2026-09-24 Updated 2026-10-14
A simple random walk on the integer line starts at and takes independent and identically distributed random variables as unit increments, withThe simple symmetric random walk has ; a biased random walk has . At or every step is deterministic, giving or respectively.
Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at the endpoint means exactly three rightward steps and one leftward step. There are possible orders, so its probability is , equal to in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as : . For the support of a probability distribution is exactly . At only even integers in are reachable; at only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.
Exact binomial endpoint probabilities for fair walks of 20 and 80 steps and a biased walk of 80 steps; only even endpoints are possible.
Details. The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives and , hence . Then apply linearity of expectation and the variance of a sum of independent random variables.
The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from to , while shrinks from to . At , the standard deviation is , or times the fair width, and . Centering and dividing by each walk's own standard deviation gives, for ,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is : approximately for the fair -step walk, for the fair -step walk, and for the biased -step walk.
The positions themselves are dependent. For , , where the second term is independent of . Their covariance is thereforeFor example, in the fair case allows or , whereas allows or . Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both and by the same integer leaves unchanged. Thus the Markov property and independent increments coexist with dependent positions.
Size-biased distribution Created 2026-09-24 Updated 2026-11-05
For a nonnegative random variable with , its size-biased version is defined byfor bounded measurable . If has density , then has density .
Size-biased probability generating function Created 2026-10-31 Updated 2026-11-05
For a positive integer-valued random variable with finite mean , the size-biased distribution has probabilities . They sum to one by the definition of expected value. Multiplying the differentiated probability generating function by gives the displayed identity for , with the endpoint interpreted by its limit.
Skewness Created 2026-10-05 Updated 2026-11-05
For a real random variable with finite third absolute moment and positive variance , its skewness is . It is dimensionless and unchanged by positive rescaling or translation; a reflection reverses its sign. A symmetric distribution has zero skewness, but the converse fails: values with probabilities have mean zero and third moment zero without symmetry. Constant variables have no defined standardized skewness because . The cosmological reduced skewness uses a different normalization.
Square of a standard Laplace variable Created 2026-10-25 Updated 2026-11-05
For a random variable with probability density function , the event is for . Integrating the symmetric density gives the displayed cumulative distribution function; it is zero for negative . The density on is . Its integrable singularity at zero does not create an atom, because the cumulative distribution function is continuous there.
Standard score 2026-10-14
A standard score expresses an outcome as a signed number of standard deviations from a mean , assuming . It is a dimensionless quantity. For a random variable with finite positive variance , has mean zero and variance one; it has a standard normal distribution when has a normal distribution, but centering and scaling alone do not make other probability distributions normal. [ref]
https://ocw.mit.edu/courses/18-05-introduction-to-probability-and-statistics-spring-2022/mit18_05_s22_class06-prep-b.pdf. MIT 18.05, Reading 6b, §5.1: standardization
. Statistical dependence 2026-10-14
Two random variables are statistically dependent when their joint probability distribution differs from the product of their marginal probability distributions. Equivalently, some events determined by the two variables violate the product rule that defines independence. Nonzero covariance implies statistical dependence when the moments exist, but zero covariance does not in general imply independence.
Statistical estimate Created 2026-10-25 Updated 2026-10-31
A statistical estimate is the realized numerical value of an estimator after observing a statistical sample. Before observation, the estimator is a random variable or random vector; its realized value is the estimate. Both are commonly written , so context distinguishes them.
Steinhaus random variable Created 2026-10-06 Updated 2026-11-05
A Steinhaus random variable is uniformly distributed on the complex unit circle. It can be generated as using independent signs and an independent uniform angle . This conditional sign representation transfers Rademacher sum inequalities to random complex phases.



