Bernoulli distribution Created 2026-09-28 Updated 2026-10-14
A Bernoulli random variable records one success as and one failure as . For , its probability mass function is
with zero mass elsewhere. The terms success and failure merely name outcomes; success need not be desirable. Any event produces such a variable through its indicator random variable , with . A single Bernoulli distribution requires no independence assumption; independence becomes relevant when several trials are combined.
Because , the expected value and variance follow immediately:
For a constructed trial with , these are and . The variance is greatest at , where it equals , since . At or , the outcome is certain and the variance vanishes.
The beauty of an indicator random variable is that counting becomes addition: summing such indicators counts successes, and the linearity of expectation gives the expected count even when the indicators are dependent. With independence and a shared , the full count law is the binomial distribution. These models are summarized in Penn State STAT 504, discrete distributions.
A historical anchor is Bernoulli's posthumous Ars conjectandi: its original title page identifies the author and records publication at Basel in 1713. This documents the book's publication, rather than establishing priority for the modern name Bernoulli distribution. See Ars conjectandi, original title page, ETH Library.
Birthday collision count 2026-10-14
The birthday collision count counts equal-label unordered pairs. Write it as a sum of indicator random variables:
This uses linearity of expectation; mutual independence of the pair indicators is unnecessary. For 23 uniform calendar labels, , whereas . A configuration with three equal labels contributes three pairs, so counting pairs and recording whether any pair exists are different random variables.
Treating every pair event as mutually independent would give the wrong exact formula. For three draws, and force . The probability that all three equalities hold is , while the product of their individual probabilities is for . This distinguishes independence of the original label draws from mutual independence of events built from overlapping draws.
Conditional expectation choice invariant Created 2026-10-18 Updated 2026-10-31
Let be a real-valued objective function of finitely many choices, with finite expected value. Suppose a prefix has positive probability. Write . If the next choice is a fair bit, the law of total expectation gives
At least one child is at least this average. Choose a child with the larger value, using a fixed rule for ties. The resulting loop invariant is . At a complete assignment , there is only one completion left, so and therefore .
For a biased choice or more than two possibilities, use the corresponding weighted average:
Some positive-probability child is at least the weighted average. For minimization, choose a child at most the current conditional expectation and reverse the invariant. The averaging identity is the same in both directions.[ref]
The word "probabilities" in the method's name also covers an indicator random variable for an undesirable outcome: keeping its conditional expectation, which is its conditional probability, strictly below one eventually forces that indicator to be zero. Optimizing an ordinary numerical objective function is the method of conditional expectations formulation used below.
Let be a finite undirected simple graph, with vertices and edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.
For the analysis, assign independent fair bits to the vertices. For each edge , the indicator random variable has expected value : exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:
Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.
Conditional independence Created 2026-09-24 Updated 2026-10-14
Random variables and are conditionally independent given when, for every pair of Borel sets , the following identity holds almost surely:
Here conditional probabilities are conditional expectations of the corresponding indicator random variables given the sigma-algebra generated by . This defines the condition even when . In terms of regular conditional distributions, the conditional joint law is the product of the conditional marginal distributions for almost every conditioning value.
For discrete random variables, at every with , the condition becomes
Where , this is equivalent to . Once is known, observing provides no further information about .[ref]
For a worked example, suppose a latent variable chooses between two environments with . Given , take to be independent and identically distributed with a Bernoulli distribution of parameter , where and . Think of two separate trials run under the same quiet or active environment. Their conditional joint probability mass functions, with rows and columns , are
Each is exactly the product of its own conditional marginal distributions: for , and for . Thus are conditionally independent given .
If the environment is unobserved, the law of total probability averages the two tables:
Both unconditional marginal distributions are fair, but . The law of total expectation gives
Figure 1.
An unobserved shared environment creates statistical dependence between conditionally independent trials
. The first two tables show independent Bernoulli trials at conditional success probabilities and . Averaging them with equal weights gives the third table. The fourth table is the product of the resulting unconditional marginal distributions, which differs from the actual joint table. These are stipulated model probabilities, not observed frequencies. Details.
Observing makes the active environment more plausible, so it raises to . Knowing the actual environment removes this source of statistical dependence. The covariance induced by a shared latent variable lemma explains the calculation without listing all the outcomes.
This is why conditional independence is useful in statistical modelling: a model can multiply simple conditional laws and then average over a shared latent variable. The resulting observations can remain statistically dependent. Conditional independence graphs organize such information relations; their interpretation as causes requires additional assumptions from causal inference. Conditioning describes the information available to an observer. It does not, by itself, describe what would happen if an experimenter changed a variable.
Covariance induced by a shared latent variable Created 2026-10-06 Updated 2026-10-14
Let be indicator random variables with conditional independence given a latent variable , and suppose . Then
For a short proof, conditional independence gives . The law of total expectation gives and . Subtract their product to obtain the claimed variance. Since , all the required expected values exist.
In the two-environment example of conditional independence, is or with equal probabilities. Hence and . The two trials have zero conditional covariance in either environment, yet their unconditional covariance is positive because their success probabilities rise and fall together.
More generally, square-integrable conditionally independent random variables satisfy
by the law of total covariance. Equal conditional means reduce this to the displayed variance; unequal conditional means need not give a nonnegative covariance. The equal-mean result explains correlated component evolutionary states in a coeval binary population without correlation between initial masses: variation in a shared environment can supply the entire covariance.
Draw two distinct positions uniformly from a fixed population with . Let and . Each draw has expected value , while
Subtracting the product of the expected values proves the covariance formula and explains the finite population correction. If the sampled values are coin biases and the actual tosses are conditionally independent given those biases, the law of total covariance gives the same covariance for their head indicator random variables.
Discrete probability distribution Created 2026-09-24 Updated 2026-10-14
A discrete probability distribution is a probability distribution concentrated on a finite or countable set of possible values : a random variable with this law satisfies . Its probability mass function assigns a probability to each value:
Thus the probability of an event is obtained by adding masses, rather than integrating a probability density function. The possible values need not be equally spaced, or even integers. When the relevant moments are finite, its expected value and variance are
For a constructed example, assign values masses . They sum to one; , , and . Hence the variance is . A mean can lie between possible values: no outcome here equals .
The useful organizing question is what an experiment records. One yes/no indicator random variable gives a Bernoulli distribution; a success count in a fixed number of independent attempts gives a binomial distribution; the attempt number of the first success gives a geometric distribution. A Poisson distribution describes an event count under different assumptions. Naming the quantity first helps prevent selecting a familiar formula for the wrong experiment.
Discrete uniform distribution Created 2026-09-29 Updated 2026-10-14
A discrete uniform distribution gives every element of a nonempty finite set the same probability. Write for its cardinality. A random variable with this law has support of a probability distribution and probability mass function
The masses sum to . Conversely, if all masses equal , their sum is , so necessarily . Thus equal chances determine the whole law.[ref]
Counting now computes an event's probability: for any set of possible values,
In particular, when , the answer is . The intersection matters: values outside the support of a probability distribution contribute zero. This turns a probability question into a combinatorics question, provided that equal chances are justified by the model.
For an ideal fair six-sided die, and each face has probability . The event of an even integer is , so its probability is ; the event has probability . Direct summation gives the expected value and the variance . The mean is a balance point between possible outcomes. These are exact consequences of stipulated fairness, rather than measured frequencies from physical dice.
Figure 1.
An ideal fair die: six equal probability masses and a mean between the faces
. Details.
Uniformity describes probabilities, not distances between values. For a second constructed model, stipulate equal-chance selection from . Every value has probability , despite the unequal gaps . Here , while the expected value and variance are
Neither the midpoint of the extreme values, , nor a formula using only the cardinality gives these moments. For a general numerical support of a probability distribution, use its actual values:
Figure 2.
Equal chances for unequal gaps: four masses and four equal-width sampling intervals
. Details.
Choosing an item from a finite list with equal chances is a basic building block of simple random sampling. A bijection that relabels the items preserves equal probabilities, although changing numerical labels can change the expected value and variance. A function that merges labels can destroy uniformity: for the fair-die model, has masses at , since four faces map to three. Always count the original equally likely outcomes.
An indicator random variable for membership in a set has a Bernoulli distribution with parameter ; counting that event over independent repetitions gives a binomial distribution with parameters and . Equal chances among individual values need not produce equal chances among aggregated counts.[ref]
Effective repetition count across independent calibration blocks accounts for dependence confined to each acquisition block rather than shared by every stored trace. Suppose block contains empty-interval indicator random variables, all with common probability and within-block correlation coefficient . Assume different blocks are independent. With , summing within-block covariances gives
Matching this to the variance of an average of independent indicators yields
For equal blocks of size , this reduces to . The denominator involves the block size, not the total ; the single-block expression in effective repetition count for detector intervals with shared drift must not be applied as though the same drift state affected every block.
For an original comparison, fix and . One block gives . Six independent blocks of twenty give . Six very uneven blocks of sizes instead give
All three designs store the same number of traces. The difference comes from how often the same fluctuating condition is reused. For fixed , , and positive , minimizing favors balanced blocks; this motivates optimal allocation of detector repetitions across calibration blocks when block-preparation costs also matter.
Independence must come from the physical acquisition model. Starting another file does not erase a shared clock, reference calibration, or slowly varying environmental influence. NIST's uncertainty law retains shared-input covariance explicitly.[ref] If drift persists between nominal blocks, those cross-block terms must be added and the displayed formula changes. A cluster bootstrap likewise requires blocks that are suitable independent resampling units.
Place balls independently and uniformly into boxes. If indicates that box is empty, then , , and, for ,
Indeed all balls avoid one specified box with probability and two specified boxes with probability . The indicator random variable identities give the expectations, variances, and covariance. Finally proves strict negativity. Thus the number of empty boxes has and by the variance of a sum.
For independent uniform points in a rectangle, condition on one point with normalized coordinates . It is a maximal external point if all others avoid the upper-right rectangle of area , giving conditional probability . Integrating gives , where is a harmonic number. Linearity of expectation over the indicator random variables gives . The same answer holds for independent continuous coordinate distributions, by transforming each coordinate with its distribution function.
In independent trials with category probabilities , let count the distinct categories observed. Write it as the sum of indicator random variables for the categories' appearances. Category is absent with probability , so linearity of expectation gives the displayed formula. The appearance indicators need not be independent. For equally likely categories the expression becomes ; uneven probabilities can substantially delay observation of rare categories.
Expected subgraph count in the Erdős-Rényi model Created 2026-09-24 Updated 2026-09-24
If a fixed graph has vertices, edges, and unlabelled copies in , then the number of its copies in satisfies
This follows by writing as a sum of indicator random variables.
Fano's inequality via an error indicator Created 2026-10-06 Updated 2026-10-14
Under the hypotheses of Fano's inequality, let , , and let be the indicator random variable of an error. Its probability of being one is . The in the displayed bound denotes binary entropy in bits. Since is a deterministic function of , . Applying the chain rule for conditional entropy in both orders gives the exact decomposition
The first term is bounded by , because conditioning reduces entropy. For the second term, fix a report : if , then is known; if , then lies among at most other symbols. Maximum entropy on a finite alphabet bounds the latter uncertainty by . Averaging over the reports and the error flag gives
This proves Fano's inequality. Events of zero probability contribute zero to this average, so the proof also covers without assigning a conditional distribution to an impossible event.[ref]
Figure 1.
The four-symbol entropy budget peaks at chance-level error and separates the error flag from the three alternatives
. Details.
The decomposition also explains equality. The first bound is exact when the indicator random variable and are independent random variables: knowing the report does not change the error probability. The second is exact when, for every report with positive error probability, the wrong-symbol conditional distribution is uniform on all alternatives. Both conditions hold in the four-symbol toy channel of Fano's inequality. At , the second condition is vacuous; at , the flag is constant but three alternatives remain, giving . For , there is just one alternative after an error, so the second term vanishes: all remaining uncertainty is whether the single alternative must replace the guess.
For fixed , the vector converges in distribution to , where is a standard Brownian bridge. To prove it, write the vector as times the sum of independent centred bounded indicator vectors. Their covariance matrix is . The multivariate central limit theorem gives a centred multivariate normal distribution with this covariance, exactly the bridge vector. Singular covariance matrices, including endpoint times or repeated values of , cause no problem. This is a finite-dimensional assertion; a full function-space limit additionally requires tightness.
For uniform sampling without replacement from a population of objects, the finite population correction accounts for the reduced spread caused by drawing distinct objects. For the marked-object count in a hypergeometric distribution, put . Then
Relative to the corresponding binomial distribution, the variance is multiplied by and the standard deviation by . The square-root convention for the correction is used in Philip Stark's discussion of sample sums.[ref]
The factor has a direct interpretation. For , replacement makes no difference and . For , the entire population is observed and the marked count is exactly , so . In the ten-object, five-draw example, and . The exceptional population size is deterministic and should be handled directly rather than inserting it into a zero denominator.
A short explanation uses an indicator random variable for a marked object at draw . Each has expected value and variance . For distinct draw positions ,
Since , the variance of a sum includes individual terms and ordered covariance terms, giving the displayed correction. Linearity of expectation still gives despite this dependence.
For arbitrary fixed real population values, use for population size and for sample size. Write the finite population mean , the finite population variance and . Under simple random sampling without replacement, the sample mean satisfies
Thus is the variance factor relative to , while is the exact variance ratio to independent uniform sampling with replacement, whose sample mean has variance . The standard error uses the square root of the corresponding factor. These formulas agree because ; the denominator convention must be specified. The sample mean under simple random sampling gives a derivation and an exact six-value example.
For a uniform random permutation of objects, let count its fixed points. Write . Each indicator random variable has expected value , so linearity of expectation gives for every . This average does not require independence: for , fixing two specified objects has probability , greater than the product of their individual probabilities.
For four objects, exact enumeration gives counts for fixed points among the equally likely permutations. Their weighted arithmetic mean is . Exactly three fixed points are impossible: the last object must then also be fixed.
Figure 1.
The fixed point count of a uniform random permutation averaged over all permutations of four objects
. Each card lists . Green entries equal their positions and therefore mark fixed points. The probability mass function on the right counts those cards; its expected value is one. Details.
Choose the fixed objects and derange the remaining . Their count is among equally likely permutations. The inclusion-exclusion principle for proves the displayed law, valid for and zero otherwise. With , it includes the all-fixed case and the impossibility of exactly fixed objects. For fixed , the law tends to , the Poisson distribution of mean one.
F. Thomson Leighton Created 2026-10-13 Updated 2026-11-05
F. Thomson Leighton is a coauthor of Mathematics for Computer Science by Eric Lehman and others. The text develops proofs, graph theory, counting and probability as tools for analyzing algorithms and discrete structures. Its presentation ties formal arguments to computing questions, such as using indicator random variables and linearity of expectation to evaluate a complicated random count.[ref]
Inclusion indicator 2026-11-05
An inclusion indicator records whether a specified population unit appears in a sample :
It is an indicator random variable, with expected value and variance . Its randomness comes from sample selection; the population value attached to unit may be treated as fixed in a sampling calculation.[ref]
Inclusion indicators turn a sum over a changing sample into a sum over fixed population labels:
If every , the same identity immediately proves
The inverse-inclusion-probability total is unbiased because , not because the selected units must look typical in every realization.
Pair products connect the notation to joint inclusion probabilities: , so . For a fixed sample size , in every realization. Consequently,
In simple random sampling with , the four individual variances sum to , while the six distinct pair covariances are each . Their doubled sum is , giving total variance zero. Treating the inclusion indicators as independent would incorrectly predict a random sample size. The notation makes that error easy to detect.