A real centered random variable $X$ is sub-Gaussian random variable with parameter $\sigma \ge 0$ if its moment-generating function satisfiesThe parameter is an upper bound on fluctuation size, not necessarily the standard deviation. For $\sigma >0$ and $u>0$, exponential Markov inequality gives $\mathbb{P}(X\ge u)\le \exp (-tu+{\sigma }^2{t}^2/2)$. Choosing $t=u/{\sigma }^2$ and applying the same argument to $-X$ yields the Chernoff boundA centered normal distribution of variance ${\sigma }^2$ attains equality in the moment-generating-function condition. A Rademacher distribution also satisfies it with $\sigma =1$, since $\cosh t\le e^{t^2/2}$. Products of moment-generating functions show that a sum of independent centered sub-Gaussian random variables with parameters ${\sigma }_i$ is sub-Gaussian with parameter $({\sum }_i{\sigma }_i^2{)}^{1/2}$. Hence the sample mean of $n$ independent variables with a common parameter $\sigma$ has tail bound $2e^{-n{u}^2/(2{\sigma }^2)}$. This gives normal-like concentration without assuming a normal distribution. For an uncentered variable, the convention is to apply the condition to $X-\mathbb{E}X$.

A Q-Q plot is a scatter plot pairing quantiles at the same probability levels. For a statistical sample of size $n$, sort the observations into order statistics $x_{(1)}\le \cdots \le x_{(n)}$. Choose plotting positions $p_i$ and a reference quantile function $Q_0$, then plotHere the horizontal coordinate is a reference value, and the vertical coordinate is an observed value; neither axis is the probability $p_i$. The displayed plotting positions are our chosen convention, placing every level strictly between zero and one. They are not a claim that the $i$th order statistic equals that population quantile. For two statistical samples, use sample quantiles at matching levels, with a stated interpolation convention when their sizes differ. ^[ref]

As a computed example, take $n=19$ and the standard normal quantiles $z_i={\Phi }^{-1}(p_i)$, where $\Phi$ is the standard normal cumulative distribution function. Construct the ordered values $a_i=10+2z_i$. At ranks $1,10,19$, the plotting positions are $1/38,1/2,37/38$, the reference quantiles are approximately $-1.937932,0,1.937932$, and the constructed values are approximately $6.124137,10,13.875863$. Every point lies on $a=10+2z$ by construction. These 19 values are deliberately chosen, not random draws or real measurements.

The usefulness of a Q-Q plot is that it turns a comparison of probability distributions into geometry: if a reference random variable $Z$ is transformed into $X=\mu +\sigma Z$ with $\sigma >0$, its quantile function satisfies $Q_X(p)=\mu +\sigma Q_Z(p)$. This follows because a positive scaling preserves ordering. Thus the location-scale family produces a straight population Q-Q plot, and an approximate sample line suggests a compatible shape over the observed range. Its intercept describes location and its slope describes scale. The identity line requires the same location, scale and units on both axes; even then its displayed angle is 45 degrees only with equal axis scales. Curvature is often more informative than a histogram because it shows which quantiles depart from the reference. ^[ref]

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

Descriptive statistics summarizes observed data, for example through location and spread statistics or graphical summaries such as a histogram.

A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.

The complete binary tree can be stored directly in a zero-indexed array $A=(A_0,\dots ,A_{n-1})$: read its levels from top to bottom, left to right. The root of a tree is at index $0$. The possible children in a rooted tree of index $i$ are at $2i+1$ and $2i+2$, and an index denotes a present entry only when it is less than $n$. For $i>0$, its parent in a rooted tree is at $\lfloor (i-1)/2\rfloor$, using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.

ConsiderThe children in a rooted tree of index $0$ have keys $5,3$; those of index $1$ have keys $9,7$; those of index $2$ have keys $8,4$. The six comparisons $2\le 5$, $2\le 3$, $5\le 9$, $5\le 7$, $3\le 8$, $3\le 4$ establish the heap order. At index $4$, the parent in a rooted tree is index $\lfloor (4-1)/2\rfloor =1$, carrying key $5$.

The array is visibly not a sorted array: $5$ precedes $3$, and $8$ precedes $4$. Nor is the last entry a maximum: it is $4$, whereas the maximum is $9$ at index $3$. The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return $A_0$, a minimum, without inspecting the other entries.

Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key $1$ into the displayed binary heap. It is appended at index $7$, and exchanges with indices $3$, $1$, then $0$:The moving key follows $7\to 3\to 1\to 0$; the keys $9,5,2$ each move down one level. Only this chain needs repair.

Now apply extract-min. Save key $1$, move the last key $9$ to the root of a tree, and shorten the array to length $7$. Use sift down, always choosing the smaller of the present children in a rooted tree:First $9$ exchanges with key $2$ at index $1$, since $2<3$; then with key $5$ at index $3$, since $5<7$. At index $3$, the possible children in a rooted tree would be indices $7,8$, both outside the shortened array, so the process stops. The returned key is $1$, and the remaining binary heap is exactly the original one.

For a nonempty binary heap with $n$ entries, the deepest level is $\lfloor {\log }_{2}n\rfloor$, using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:

These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.

To build a binary heap, begin at index $\lfloor n/2\rfloor -1$ and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives $O(n)$ work, rather than charging $O(\log n)$ to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.^[ref]

The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes $O(\log n)$ time for $n\ge 2$. An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning $n$ entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.

The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives $2,3,4,5,7,8,9$, so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.

A simple cell is a visual cortical neuron whose receptive field has spatially separable ON and OFF receptive-field subregions. Elongated neighboring subregions give a preferred orientation and a sensitivity to the location and polarity of visual contrast. “Simple” describes the response organization; it does not describe a simpler cell body or a particular shape of neuron.

Hubel and Wiesel's 1962 classification emphasized four observations: distinguishable ON and OFF receptive-field subregions, summation within each region, antagonism between regions, and qualitative prediction of responses to differently shaped stimuli from those regions' arrangement. A slit fitting an elongated center was more effective than a smaller spot; a larger patch could invade opposing flanks and lose effectiveness. An edge separating bright and dark regions could be effective when its boundary matched the boundary between subregions. These were observations about spike trains, rather than an assertion of exact linearity. ^[ref]

The following deliberately coarse signed spatial filter model of a simple cell makes the geometry easy to count. A centered bright bar contributes positively at five sites. Rotating it preserves its area but mixes positive and negative weights; shifting it preserves its orientation but changes which weights it samples. The model is useful because it predicts distinct effects of these three manipulations instead of treating any bright stimulus as equivalent.

A simple cell is not an ideal linear sensor. Its spike train is nonnegative in event count, and neural adaptation can change responsiveness. The signed spatial filter model of a simple cell supplies a useful approximation to spatial drive and an explicit output rule. Comparing predictions with unseen stimuli is more informative than assuming the rule from the name “simple”. In contrast, the existing complex cell models explore tolerance to phase and local displacement.

Orientation selectivity is a systematic dependence of a visual neuron's response on the axis of a bar, edge or stripe pattern presented in its receptive field, under specified stimulus conditions. Here the angle $\theta$ measures the stripe axis from horizontal: $0^{\circ }$ is horizontal and $90^{\circ }$ vertical. An axis has no arrow, so $\theta$ and $\theta +180^{\circ }$ describe the same orientation. A preference for one direction of movement across that axis is an additional property; the 1962 recordings included both equal and unequal responses to opposite movements. ^[ref]

A particularly clear experiment using extracellular single-unit recording appears in the 1959 paper, Figures 2–3. A bright $1^{\circ }\times 8^{\circ }$ slit was centered on the same receptive field and rotated through successive angles; each presentation lasted one second. The vertical slit strongly increased the extracellularly recorded spike train, whereas the horizontal slit was ineffective. Small-spot tests had identified ON and OFF receptive-field subregions, with a central ON region and opposing flanks: rotation illuminated less of the center and more of the flanks. Geometry and location therefore mattered together. These dimensions belong to that recorded unit, not to every neuron. ^[ref]

An orientation tuning curve summarizes a controlled angle sweep. Keep location, size and visual contrast fixed; for a stripe pattern also specify spatial frequency and phase. The same signed spatial filter model of a simple cell can produce strong orientation selectivity and strong dependence on phase, as the following original toy illustrates. Its smooth curves are calculated predictions, not digitized or invented biological measurements.

A cortical region whose visual responses preferentially reflect input from one eye. Competitive activity-dependent models can explain segregation of correlated inputs, while anatomical constraints and species differences also matter.

A complex cell typically responds selectively to an oriented edge or bar over a finite spatial region with less dependence on spatial phase and contrast polarity than a simple cell. It need not have the simple cell's separated linear ON and OFF subregions. Phase tolerance is local, not invariance to arbitrary displacement outside its receptive field.

Consider afferent activities $z_i$, cortical activity $y_a$ and a constrained Hebbian learning rule ${\dot{w}}_{ai}=ϵ⟨y_a{z}_i⟩-{\Lambda }_a$. If $y_a={\sum }_{b,j}{K}_{ab}{w}_{bj}{z}_j$, then $⟨y_a{z}_i⟩={\sum }_{b,j}{K}_{ab}{w}_{bj}{C}_{ji}$, where $C$ is the input correlation matrix. Thus input correlations and lateral interactions select growing weight modes, while synaptic normalization and bounds stop unlimited growth. The model tests how organization can emerge without assigning every final cortical feature in advance.

A predator is an organism that consumes prey through predation. A predator need not occupy the highest trophic level of an ecosystem, and the label does not specify its size or guarantee that it has no predators of its own. In the illustrative food chain, the small fish is a predator at level 3 and also prey for the large fish at level 4. Separating these relational labels from species names prevents a misleading division of the world into permanent predator and prey categories.

Prey is an organism consumed by a predator in predation. The name describes the receiving end of that interaction: a small fish can be prey for a large fish while being a predator of zooplankton. In a food web drawn with resource-to-consumer arrows, a feeding arrow goes outward from the prey toward its predator. This convention makes the route of food and energy easy to follow.

Linkage disequilibrium means that knowing an allele at one genetic locus changes the probability of an allele at another genetic locus in population haplotypes. It compares their joint probability distribution with the product of their marginal distributions. This is useful because a genetic marker can carry information about another genetic locus: tag SNPs exploit this redundancy, without establishing a causal genetic association.

Consider two genetic loci with alleles $A,a$ and $B,b$. Sample one haplotype, rather than an unphased diploid genotype. Write its four haplotype frequencies as $f_{AB},f_{Ab},f_{aB},f_{ab}$, summing to one, and set the marginal allele frequencies to $p=f_{AB}+f_{Ab}$ and $q=f_{AB}+f_{aB}$. The linkage disequilibrium coefficient isThe second expression follows by substituting $f_{ab}=1-f_{AB}-f_{Ab}-f_{aB}$. The entire two-locus joint probability distribution is thenEvery row and column sum is unchanged when $D$ varies. Linkage equilibrium means $D=0$: all four haplotype frequencies equal products of allele frequencies, so the two allele indicators are independent random variables. For $p>0$, the conditional probability $P(B\mid A)=q+D/p$ shows directly how positive $D$ enriches $B$ among copies carrying $A$, while negative $D$ depletes it. Positive $D$ also enriches $ab$; negative $D$ enriches $Ab$ and $aB$. Swapping the labels $A$ and $a$ reverses the sign of $D$, so neither sign is intrinsically favorable.

For example, fix the allele frequencies at $p=0.60,q=0.40$. At linkage equilibrium, the haplotype frequencies in the order $AB,Ab,aB,ab$ are $(0.24,0.36,0.16,0.24)$. Positive linkage disequilibrium $D=0.12$ instead gives $(0.36,0.24,0.04,0.36)$, with $P(B\mid A)=0.60$; negative linkage disequilibrium $D=-0.12$ gives $(0.12,0.48,0.28,0.12)$, with $P(B\mid A)=0.20$. Counting each allele separately would miss the difference.

Nonnegative haplotype frequencies constrain $D$. Define the nonnegative bounds $L=\min (pq,(1-p)(1-q))$ and $U=\min (p(1-q),(1-p)q)$. The four entries above giveThus $|D|\le 1/4$ globally, but a particular pair of allele frequencies usually permits a smaller, asymmetric interval. The standardized linkage disequilibrium convention used here retains the sign:This convention requires $0<p,q<1$; if either genetic locus has only one allele in the population, $D=0$ but normalized measures are undefined. Some presentations report only $|D^{\prime }|$. At $D^{\prime }=1$ or $-1$, at least one of the four haplotypes has zero frequency; this alone does not prove that genetic recombination has never occurred.

For the indicator random variables $X=1_A$ and $Y=1_B$, their covariance is $D$, and their variances are $p(1-p)$ and $q(1-q)$. The allelic correlation measure is their squared correlation coefficient,The subscript distinguishes it from the recombination fraction $r$ in linkage-disequilibrium decay under recombination. Squaring loses the association's sign. In the illustrated positive and negative examples, $r_{\mathrm{LD}}^2=0.25$ in both, whereas $D^{\prime }=0.75$ and $-0.50$, respectively. For another original example, take $p=0.10,q=0.50,f_{AB}=0.10$: then $D=0.05,D^{\prime }=1$, yet $r_{\mathrm{LD}}^2=1/9$. Every $A$ carries $B$, but most copies carrying $B$ lack $A$. The frequency constraints and the distinction between these normalizations are analyzed in Mathematical properties of the r² measure of linkage disequilibrium by Jenna M. VanLiere and others (sections 2.1 and 2.5, pp. 131–132 and 135–136).

Genetic linkage describes transmission through meiosis; linkage disequilibrium describes a population's haplotype frequencies. Nearby genetic loci on a chromosome can be in linkage equilibrium. Conversely, mixing populations can create linkage disequilibrium even between genetic loci on different chromosomes. For example, mix equal numbers of independently sampled haplotypes from two populations, each internally at linkage equilibrium, with $p=q=0.80$ in one and $p=q=0.20$ in the other. The pooled allele frequencies are $p=q=0.50$, but $f_{AB}=(0.64+0.04)/2=0.34$, giving $D=0.09$. This is a consequence of population stratification, not a measurement of the recombination fraction.

Measured haplotype frequencies also depend on the sample. Finite sample size, related individuals, genetic-study ascertainment, genotyping error and uncertain haplotype estimation can change an estimate. A missing rare haplotype can give empirical $|D^{\prime }|=1$ without demonstrating its absence from the population. Report the sample definition and allele frequencies alongside the association measure; a nonzero sample estimate alone does not establish nonzero population linkage disequilibrium.

A concrete dataset is the 2005 A haplotype map of the human genome by The International HapMap Consortium. The International HapMap Consortium used genotyping platforms including Illumina BeadArray to obtain SNP genotype calls from 269 DNA samples across four collections: 30 parent–offspring trios from Ibadan, 30 trios from Utah, 45 unrelated individuals from Beijing and 44 from Tokyo. Parent–offspring trios and the PHASE algorithm supplied haplotype estimation, rather than direct observation of every chromosome. In Figure 7, 36 SNPs resolve seven haplotypes in a chromosome 2 region in the Utah panel; seven tag SNPs capture the 36 SNPs at $r_{\mathrm{LD}}^2\ge 0.8$. The readout demonstrates reusable allelic correlation, not causal effects.

Controls required over 80% complete calls, at most one discordance among five duplicate genotypes, at most one Mendelian segregation error per trio panel, and a Hardy-Weinberg equilibrium test with $P>0.001$; blind reassessment checked performance. Minor allele frequencies of at least 0.05 were targeted, the collections were not population-representative, and inferred haplotypes retain phase uncertainty. These limits restrict extrapolation of linkage disequilibrium.^[ref]

Inbreeding is reproduction between genetically related individuals. It increases the chance that an offspring's maternal and paternal copies at a locus are identical by descent. Such homozygosity by descent is autozygosity.

The infinite-sites model assumes that every mutation occurs at a previously unmutated site, so each mutation on the sample genealogy produces a distinct segregating site. If mutation rate per lineage is $\theta /2$ in standard coalescent time units, a tree of total length $L$ has a Poisson distribution of mutation count with mean $\theta L/2$.

A segregating site is a position at which at least two states occur in the sampled chromosomes. Under an infinite sites mutation model, mutations below the sample's common ancestor correspond one-to-one to segregating sites. Their number is commonly denoted $S$.

Effective population size is the size of an idealized biological population giving the relevant rate of genetic drift or ancestral coalescence in the biological population being modeled. In the standard neutral diploid coalescent, time is measured in $2N_e$ generations and the population-scaled mutation parameter is $\theta =4N_e\mu$.

// Target: biology.bigb

Genetic drift is random variation of allele frequencies due to finite-population reproduction. In the neutral ancestry description, randomly sampled gene copies merge into common ancestors according to Kingman's coalescent.

// Target: probability-and-statistics.bigb

A population bottleneck is a temporary large decrease in biological population size. It changes ancestral coalescence rates and can leave fewer ancestral haplotypes and increased linkage disequilibrium after the biological population expands.

// Target: biology.bigb

An ancestral recombination graph records ancestral coalescences and genetic recombination events for sampled chromosomal material. Backwards in time, each pair of ancestral lineages merges at rate one in standard diploid coalescent units, while a lineage splits at a recombination breakpoint at rate $\rho /2$ times the genetic span of the material it carries. The breakpoint splits that lineage's ancestral material into two parental contributions. Waiting times are exponential with the sum of the current event rates. At each genomic position, retaining the ancestry at that position gives a marginal phylogenetic tree with the neutral Kingman's coalescent distribution. Different positions have dependent trees because they share parts of the graph.

// Target: biology.bigb