Nearest-neighbor interpolation assigns each requested location the value of its nearest available sample, with a specified convention for ties. In lossy block averaging, samples are placed at block centres and each is copied into its four original pixel positions. This enlarges the raster image without recovering discarded detail.

Quantization maps numerical values to a specified discrete collection of representable values. In lossy block averaging, $Q(m)=\lfloor m+1/2\rfloor$ maps block arithmetic means in $[0,255]$ to eight-bit integers. Thus $Q(40.25)=40$ and $Q(40.5)=41$. Different means can share a stored value, making this step irreversible.

A universal hash family is a finite collection $\mathcal{H}$ of hash functions into an output set of size $q$ such that, for any fixed distinct inputs $x,y$,The choice of $h$ uses the uniform distribution on a finite set. The keys are fixed before that choice: the randomness belongs to the hash function, so the guarantee does not assume naturally random keys. Choose one member and keep it while using the table; changing it requires redistributing the stored records. The bound holds separately for every distinct pair, without requiring uniform individual outputs or independent random variables. A strongly universal hash family supplies those stronger properties.

The practical payoff follows from linearity of expectation. If $n$ stored keys are distinct from a fixed query, let $C$ count how many share its bucket. Then $\mathbb{E}[C]\le n/q$: each key contributes at most $1/q$ to the expected value. With $100$ stored keys and $100$ buckets, an unsuccessful search encounters at most one record on average over the random choice of hash function. This is an expected value, not a limit on every search; one unlucky choice can still create a long chain.

This calculation needs no independence between the collision events: linearity of expectation adds their individual probabilities. The fixed-query condition matters, since deliberately choosing keys after inspecting the selected hash function can target a crowded bucket.

Carter and Wegman introduced this way of analyzing storage and retrieval in their 1977 paper: average over a chosen class of hash functions while allowing any fixed sequence of inputs. Their 1979 journal version develops the same universal-pair collision condition and constructions. The insight is useful because a randomized algorithm can obtain a performance guarantee through its own choices, even when its inputs have inconvenient patterns.^[ref][ref]

An almost strongly universal hash family relaxes the exact ordered pair balance of a strongly universal hash family. In the convention used here, choose $h$ with the uniform distribution on a finite set from a family with $q$ possible outputs. Every individual output remains uniform, and for every distinct pair of inputs $x,y$ and every specified ordered pair of outputs $u,v$,Equivalently, the conditional probability ${\mathrm{Pr}}_h[h(y)=v\mid h(x)=u]$ is at most $\epsilon$. This asks how predictable a second output can become after the first is known.

For $q=5$, strongly universal hash families give $\epsilon =1/5$: learning one output leaves each specified second output with conditional probability $1/5$. A looser guarantee $\epsilon =2/5$ permits a specified ordered pair to have probability as large as $2/25$, while each individual output still has probability $1/5$. Summing over the five equal ordered pairs bounds the collision probability by $2/5$, rather than the $1/5$ required of a universal hash family. Thus an almost strongly universal hash family need not be a universal hash family. Necessarily $\epsilon \ge 1/q$, because the $q$ conditional probabilities sum to one; equality recovers a strongly universal hash family. This relaxation is useful in Wegman–Carter authentication, where efficiency can be traded against a quantified forgery bound within a complete message authentication protocol.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

In Newtonian gravity, the gravitational field $\mathbf{g}$ specifies the acceleration of a freely falling test particle at each position. A gravitational potential $\Phi$ gives $\mathbf{g}=-\nabla \Phi$, with the gradient taken in the spatial geometry of the model. In general relativity, the metric tensor describes gravitational effects, and tidal forces are encoded by spacetime curvature.

Population genetics studies the frequencies of alleles and genotypes in biological populations, and their changes through inheritance, mutation, selection, migration and random sampling. Kingman's coalescent describes a neutral sample's ancestry backward in time.

An allele is one of the alternative inherited states at a genetic locus, often distinguished by a difference in DNA sequence. A population can contain many alleles, although a two-copy diploid individual carries at most two at that genetic locus, one inherited from each parent. See NHGRI: allele.

Count copies, not just individuals, when computing allele frequency: in 100 individuals with genotype counts $49AA$, $42Aa$, $9aa$, there are $2(49)+42=140$ copies of $A$ among 200, so $p_A=0.70$. The heterozygotes contribute to both allele counts. This converts observed genotypes into the population quantity needed by the Hardy-Weinberg principle.

A locus is a position or region of a genome. An allele specifies an inherited state there; a haplotype specifies states at several loci on one chromosome.

A genotype records the inherited alleles carried by an individual at one or more genetic loci. At a two-copy diploid genetic locus with alleles $A,a$, the possible unordered genotypes are $AA,Aa,aa$. The first and last are homozygotes; the middle is a heterozygote. The notation records inherited states, without yet asserting their phenotypes. See NHGRI: genotype.

An unordered $Aa$ combines the two parental orders $Aa$ and $aA$. This small bookkeeping point explains the factor two in Hardy-Weinberg proportions and in an $Aa\times Aa$ cross. If parental origin or arrangement across several genetic loci matters, a phase-known genotype retains extra information about the two haplotypes.

A phenotype is an observable characteristic of an organism, arising from its genotype, environment and other influences. Seed shape is a phenotype; $Aa$ is a genotype. The distinction prevents appearance from being mistaken for a complete inherited description. See NHGRI: phenotype.

For a specified binary phenotype $T$, let its penetrance in genotype $g$ be $r_g=P(T\mid g)$. The law of total probability gives $P(T)={\sum }_g{r}_{g}P(g)$. Thus the ideal $Aa\times Aa$ example has $P(T)=r_{AA}/4+r_{Aa}/2+r_{aa}/4$: the familiar $3/4$ follows only when these penetrances are $1,1,0$. A pedigree likelihood keeps inheritance and the conditional phenotype model as separate factors.

In a fully penetrant autosomal recessive model with normal allele $A$ and disease allele $a$, $aa$ is affected and $AA,Aa$ are unaffected. A carrier cross $Aa\times Aa$ has offspring probabilities $1/4,1/2,1/4$ for $AA,Aa,aa$, respectively, from the two independent parental meioses.

A pedigree records parent–offspring relationships. A founder in a pedigree has no recorded parents; all other individuals have a genotype conditional on their parental genotypes. Inbreeding can produce loops in the undirected diagram while the directed ancestry remains acyclic.

Genetic recombination rearranges inherited genetic material into new combinations. In the meiosis example considered here, chromosomal crossover exchanges segments between nonsister chromatids of homologous chromosomes. A transmitted chromatid can consequently contain DNA from both parental homologues. This produces new haplotypes without requiring a new mutation at either scored genetic locus. See Meiosis.

For phase-known genotype $AB/ab$, a single chromosomal crossover between the selected genetic loci can yield $Ab$ and $aB$ on the participating chromatids; the other two chromatids can remain $AB$ and $ab$. Thus an exchange in the four-chromatid bundle does not mean every resulting gamete is recombinant. Only a chromosomal crossover encountered along the transmitted chromatid within the selected interval affects its two-locus score.

Follow parental origin along the transmitted chromatid from the first genetic locus to the second. Each exchange switches that origin. An odd number of such chromosomal crossovers changes the endpoint combination; an even number restores parental phase. Two exchanges can therefore leave the scored haplotype as $AB$ even though an internal segment came from the other parental homologous chromosome. Recombinant status is relative to the chosen genetic loci, not a complete record of exchanges along the chromosome.

This integer parity distinction connects the physical process of genetic recombination to the observed recombination fraction. It also explains why a long genetic map interval can accumulate many exchanges while its endpoint recombination fraction approaches $1/2$ in the Haldane mapping function model.

Why can two individually fair allele transmissions fail to be independent? Genetic loci on the same chromosome can travel together through meiosis. This tendency is genetic linkage; in an ordinary two-locus model, detectable genetic linkage means a recombination fraction below $1/2$. A genetic marker can therefore help track a neighboring genetic locus through a pedigree. See Clark, Douglas and Choi, Biology 2e: chromosomal theory and genetic linkage.

Take a diploid individual heterozygous at two genetic loci, with phase-known genotype $AB/ab$: one homologous chromosome carries alleles $A,B$, the other $a,b$. The parental haplotypes are $AB,ab$; the recombinant haplotypes are $Ab,aB$. Assume fair Mendelian segregation, equal probabilities within each reciprocal pair of gametes, and no allele-dependent differences in gamete recovery. If the recombination fraction is $r=0.2$, the gamete probabilities are $0.4,0.4,0.1,0.1$ in that order. Each genetic locus still transmits its two alleles equally, but $P(AB)=0.4$ exceeds $P(A)P(B)=0.25$: fairness at each genetic locus does not imply independence between genetic loci.

At $r=0$, only the parental haplotypes occur, each with probability $0.5$: this is complete genetic linkage. At $r=0.5$, all four haplotypes have probability $0.25$, giving independent assortment. A recombination fraction near $0.5$ alone cannot establish whether the genetic loci lie on different chromosomes or far apart on one chromosome.

Genetic linkage concerns joint transmission through meiosis. Linkage disequilibrium concerns haplotype frequencies in a population, while genetic association compares allele or genotype frequencies with a phenotype. These questions require different observations; pedigrees directly reveal co-transmission.

A genetic association is a statistical dependence between a genetic variant and a phenotype. An associated marker need not be causal: linkage disequilibrium can correlate it with a causal locus, and population stratification can produce an association without such a link.

Allele copies are identical by descent if they derive from the same specified ancestral copy. Identical observed states need not imply this ancestry. Two diploid individuals are 2-IBD when both of their allele copies can be paired as identical by descent; autozygous individuals carrying two copies of the same ancestral copy are mutually 2-IBD when that ancestor is shared.

A genetic marker is an observed inherited genomic state used to track chromosomes, test genetic association, or perform genetic linkage analysis. Genetic marker alleles need not themselves cause the phenotype. Several genetic markers on one nonrecombining region form a single observed haplotype.

In ordinary diploid meiosis, the two copies at a genetic locus separate: each gamete receives one copy. With fair transmission, a heterozygote $Aa$ produces gametes carrying $A$ or $a$ with probability $1/2$ each. This is a transmission mechanism conditional on a parental genotype, rather than a statement about how common either allele is in a population.

For the one-locus cross $Aa\times Aa$, assume independent parental transmissions, no new mutation, and no differences in fertilization or survival between the resulting genotypes. Multiplying the two gamete probabilities gives four equally likely ordered outcomes: $AA,Aa,aA,aa$, each with probability $1/4$. Combining the two orders of the heterozygote givesOnly under the additional ideal model of complete dominance of $A$, complete penetrance, and no environmental changes to the scored characteristic do $AA$ and $Aa$ share the dominant phenotype. Its probability is then $0.25+0.50=0.75$. The inheritance calculation alone does not determine a phenotype or predict a generic disease risk.

These are probabilities, not a requirement that every four offspring contain one $AA$, two $Aa$ and one $aa$. For 100 independent offspring under the ideal model, the expected values of the three counts are $25,50,25$; the $aa$ count has a binomial distribution with standard deviation $\sqrt{100(0.25)(0.75)}\approx 4.33$. Each new transmission keeps the same conditional probabilities given the parental genotypes.

In his paper published in 1866, Mendel reported 5,474 round and 1,850 wrinkled pea seeds: $5474/7324\approx 0.7474$ round, close to the ideal $0.75$. Following descendants also distinguished two inherited classes within the round phenotype, illustrating why genotype cannot always be read from appearance.^[ref] At several genetic loci, transmission patterns additionally depend on genetic linkage and genetic recombination.

Meiosis reduces two sets of chromosomes to one. In the ordinary diploid life cycle, this makes it possible for fertilization of two haploid gametes to restore the diploid state rather than double the number of sets in every generation. Its two divisions perform different tasks: meiosis I separates homologous chromosomes, whereas meiosis II separates sister chromatids. One round of DNA replication precedes both divisions; there is no second round between them. See ^[ref].

Two homologous chromosomes carry corresponding genetic loci, potentially with different alleles; two sister chromatids originate by DNA replication of one chromosome. After chromosomal crossover between nonsister chromatids, the sister chromatids need not carry identical alleles everywhere. Separating the two relationships explains why a haploid product of meiosis I still contains replicated chromosomes.

The two divisions explain Mendelian segregation; variable orientation of different homologous chromosome pairs connects it to independent assortment. Genetic recombination adds another source of allele combinations. These mechanisms reshuffle inherited material without requiring a new mutation.

The symmetric diagram is useful for counting, but human oogenesis produces one functional ovum rather than four. The polar bodies receive discarded chromosomes and little cytoplasm. See Human Reproductive Anatomy and Gametogenesis (§43.3, Oogenesis and Figure 43.13: unequal divisions and polar bodies).