For finite alphabets, , so
For 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
The second moment of a real random variable is . Its variance is when these quantities are finite.
For a nonnegative random variable with positive expected value and finite second moment, write . The Cauchy-Schwarz inequality gives
which 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 gives
Equivalently, . 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 gives
Consequently . 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.
Figure 1.
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 is
Independence 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].
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]
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 :
Figure 1.
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]
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 value
by 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.
Draw one random variable , taking values zero and two with equal probabilities. Conditional on , generate a Poisson point process on the real line with constant rate . This is a Cox process directed by the random measure : the same rate is shared by every window. It is a locally finite simple point process and a stationary point process. The law of total expectation gives ; the law of total variance and law of total covariance give, for bounded Borel sets with ,
The conditional covariance vanishes by independence, but the shared conditional means fluctuate together. This distinguishes conditional from unconditional independence.[ref]
For a window of length , the exact probability mass function is
In particular, its void probability functional is , compared with for the unit-rate Poisson point process. Whole realizations can be empty or comparatively crowded, while their mean density remains one. This example demonstrates shared-rate statistical dependence, rather than a model of short-range offspring clusters.
Choose one random variable with the continuous uniform distribution on , and reuse it in every event:
Each probability is , so their harmonic series diverges, just as in summable and harmonic event probabilities. But the events are decreasing: . For every outcome , all indices with fail. Only finitely many events occur on that outcome. The limsup of events is exactly , a zero-probability event. This is a concrete closed-interval version of the shrinking-interval dependence example.[ref]
The missing assumption is visible already in two events. For , their intersection is , hence
Moreover, the whole tail union is just , with probability . This calculation explains directly why divergence alone fails: overlapping events keep spending their individual probabilities on the same outcomes.
Let be the total number of occurrences, a sum of indicator random variables. Although almost surely, Tonelli theorem gives . More explicitly, for : very small positive values of give very long, but finite, initial runs. Infinite expected value does not imply a positive probability of an infinite count.
Figure 1.
Equal harmonic event probabilities with fresh independent inputs or one shared input
. Each row is one finite simulation of the indicator random variables of for ; a dot means the event occurred. Fresh independent random variables allow scattered returns; a shared uniform random variable yields an initial run followed by zeros. The horizontal axis uses a logarithmic scale to show early runs clearly. These finite simulations illustrate the two models and cannot prove infinitely many occurrences or eventual stopping. Details.
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, with
The 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 function
In 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.
Figure 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 deviation
A 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 therefore
For 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 are
These 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 by
for 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].
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.