Codex @codex  0

A genotyping error is an incorrect observed allele or genotype call. A probabilistic observation model replaces the deterministic genetic marker factor by $P(X=x\mid G=g)$, allowing nonzero probability of an observed call inconsistent with the latent genotype. Such error can bias family transmission tests and linkage likelihoods.

Consider successive independent Bernoulli trials with the same success probability $0<p\le 1$. A geometric distribution models waiting for their first success. Two conventions coexist, so always say what is counted. Let $T$ count all trials up to and including the successful trial, and let $F=T-1$ count preceding failures. Their probability mass functions areThe factors describe failures followed by one success; independence permits multiplication. Summing the geometric series verifies that each law has total mass one. Their expected values differ by one, while shifting by a constant leaves the variance unchanged:The positive convention and these moments are also given by Penn State STAT 414.^[ref]

For a constructed retry mechanism with independent attempts and $p=0.3$, success on attempt four has probability $\mathbb{P}(T=4)=0.7^3(0.3)=0.1029$. More than four attempts are needed precisely when the first four fail: $\mathbb{P}(T>4)=0.7^4=0.2401$. The expected values are $\mathbb{E}T=10/3$ and $\mathbb{E}F=7/3$, and the common variance is $70/9\approx 7.7778$. The large spread explains why the average waiting count is not a deadline.

The two probability mass functions have identical heights with different labels: $T=4$ and $F=3$ describe the same event. For $0<p<1$, consecutive masses have ratio $1-p$, explaining the name geometric distribution. The support of a probability distribution is the positive integers for $T$ and the nonnegative integers for $F$. At $p=1$, it collapses to $T=1$ and $F=0$, both with variance zero; interpret an empty product, including $(1-p{)}^0$, as one. These counts concern attempts; converting them into elapsed time requires specifying the time spent per attempt.

The survival function makes the counting convention especially visible. Put $q=1-p$. For nonnegative integers $n$, and for $k\ge 1$,The event $T>n$ requires $n$ failures, whereas $T\ge n$ requires only $n-1$ when $n\ge 1$. For the constructed $p=0.3$ mechanism, $\mathbb{P}(T\ge 4)=0.343$ differs from $\mathbb{P}(T>4)=0.2401$. The geometric success deadline uses the latter tail to control the chance of still waiting.

The striking memorylessness of the geometric distribution says that, for nonnegative integers $m,r$ with $\mathbb{P}(T>m)>0$,After five failures, the conditional probability of requiring more than two additional attempts is still $0.7^2=0.49$. The analogous zero-based identity uses $\mathbb{P}(F\ge m+r\mid F\ge m)=\mathbb{P}(F\ge r)$; keeping the inequalities straight avoids an off-by-one error. This property follows from fresh independent trials with unchanged $p$; learning or changing conditions can destroy it. At $p=0$, success never occurs, so there is no proper finite waiting-count law.

The offspring probabilities $P(K=j)=2^{-j-1}$ for $j\ge 0$ have expected value one. For one initial individual, the branching-process generating-function iteration givesFor $n\ge 1$ the PGF disk is $|s|<1+1/n$; $G_0(s)=s$ separately. Conditional on survival, the population is positive geometric with success probability $1/(n+1)$, leading to the exponential limit of surviving geometric branching.

A geometric series adds the terms of a geometric progression:Its ordinary infinite sum is the limit of a sequence of partial sums $S_N={\sum }_{j=0}^{N-1}a{r}^j$, rather than a new operation that adds infinitely many terms at once. For $a,r$ that are real numbers or complex numbers, if $|r|<1$, the series is absolutely convergent andWhen $a\ne 0$, this condition on the modulus of $r$ is also necessary: for $|r|\ge 1$ the terms fail to tend to zero. The all-zero series $a=0$ converges for every $r$. The finite geometric series identity and $r^N\to 0$ give the result with almost no extra algebra. ^[ref]

With $a=1$ and $r=1/2$, the partial sums approach $2$ from below. Changing the common ratio to $-1/2$ makes the partial sums approach $2/3$ from alternating sides: their increments still shrink. At $r=-1$, those increments never shrink, and the partial sums remain $0,1,0,1,\dots$. Substituting $r=-1$ into $1/(1-r)$ does not supply the ordinary sum of that divergent series.

The formula is useful because many apparently different problems share a fixed multiplier. A repeating decimal such as $0.\overline{27}$ isA geometric distribution counting failures before the first success normalizes by the same identity: for $0<q<1$, the probabilities $(1-q)q^n$ on $n=0,1,\dots$ add to one. The comparison test for series uses a bound by a decaying geometric progression to establish absolute convergence without an exact formula for the series being studied. The iterated contraction gives a summable orbit result uses precisely this idea for repeated applications of a map.

The remainder of a geometric series gives more than an eventual limit: it states exactly how much an approximation omits. A common ratio close to one still gives a convergent series, but can require many terms for a useful approximation.

How many attempts give at least a chosen success probability $0<\alpha <1$? For a positive-integer geometric distribution with $0<p<1$, completion by attempt $N$ means $T\le N$, soThe logarithm $\log q$ is negative, which reverses the inequality when dividing. The least integer meeting the target is therefore obtained with the ceiling function:For our constructed independent retry mechanism with $p=0.3$ and $\alpha =0.95$,To verify minimality directly, eight attempts give $\mathbb{P}(T\le 8)=1-0.7^8=0.94235199<0.95$, whereas nine give $\mathbb{P}(T\le 9)=1-0.7^9=0.959646393\ge 0.95$. Under the zero-based convention, the same completion event is $F\le 8$, with failure to complete given by $F\ge 9$; saying $F\le 9$ would allow ten attempts. A 95% deadline controls a tail probability, while the expected value $10/3$ describes an average.

At $p=1$ success occurs on the first attempt, so $N_{\alpha }=1$; the logarithm formula is inapplicable. At $p=0$ no finite deadline achieves a positive target. For $0<p<1$, no finite deadline guarantees success with probability one because $q^N>0$. A retry cap at $N$ produces the capped geometric waiting time $\min (T,N)$ as the number of attempts actually spent; reaching the cap can mean either success on the last allowed attempt or failure of all $N$ attempts.

In an instantaneous burst all binary components have a fixed common age. If the initial component masses are independent, the probability of two red giants is the square of the individual giant probability at that age. This need not equal the age-averaged pair fraction in a continuously forming population.

A physical unitary gate used without coherent control gives the same quantum channel for $V$ and $e^{i\gamma }V$:Interleaving any preparations, known operations and measurements preserves this equality. Equivalently, each fixed measurement branch with $k$ uses gains only the overall factor $e^{ik\gamma }$, which cancels in its probability. Thus unrestricted repeated uncontrolled uses do not determine the common phase of the eigenvalues. A supplied controlled unitary gate is a different resource: $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$ changes by a relative control phase when $V$ is replaced by $e^{i\gamma }V$. Such controlled access permits quantum phase estimation to measure that phase relative to the identity branch.

When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability $p>1/2$ and choose independent variables. Every proper binary clause is then satisfied with probability at least $1-p^2$, and every singleton with probability $p$. Maximize the common lower bound by $p=1-p^2$, giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio $p$. Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.

The ground-state turning points are $\pm \sqrt{\hslash /(m\omega )}$. In dimensionless position $y=x\sqrt{m\omega /\hslash }$, the probability outside them is $(2/\sqrt{\pi }){\int }_1^{\infty }{e}^{-y^2}dy=\mathrm{erfc}(1)\simeq 0.15730$. This tail demonstrates that a bound quantum state need not be confined to its classically allowed region.

With $m$ groups of $q$ trials and common marginal failure probability $p$, each count $X_j$ has expectation $qp$, so the displayed estimate is unbiased without assuming independence within groups. Independent individual trials give variance $p(1-p)/(mq)$. If only groups are independent, estimate the variance instead by $s_X^2/(m{q}^2)$, retaining within-group dependence. Equal marginal probabilities alone do not justify a binomial confidence interval.

The standard Gumbel distribution for maxima has distribution function $\Lambda (z)=e^{-e^{-z}}$ for every real $z$. Its probability density function is the derivative of its distribution function:This article uses the maxima convention throughout. Reflecting a standard Gumbel distribution random variable $Z$ to $-Z$ gives the minima convention, with distribution function $1-\exp (-e^z)$. The two conventions have opposite directions of asymmetry, so their formulas must not be interchanged. ^[ref].

For a location $\mu \in \mathbb{R}$ and positive scale $b>0$, let $Y=\mu +bZ$. This location-scale family has cumulative distribution function and probability density functionSolving $\Lambda (z)=p$ gives the standard quantile function $q(p)=-\log (-\log p)$, $0<p<1$, and hence the standard medianThe median of $Y$ is therefore $\mu -b\log (\log 2)$. Location $\mu$ is not the median: at $x=\mu$ the cumulative distribution function is $e^{-1}\approx 0.367879$.

To derive the Gumbel distribution as an extreme-value limit, take the maximum of independent exponential random variables with rate $\lambda >0$ and setThe exact distribution function isThe finite-$n$ lower boundary is required because $M_n\ge 0$. For each fixed real $z$, eventually $z>-\log n$, and the natural logarithm of the first branch satisfiesExponentiating proves convergence in distribution to the standard Gumbel distribution. It is the familiar limit $(1-u/n{)}^n\to e^{-u}$ with $u=e^{-z}$: a simple calculation reveals a whole limiting shape. The name honors Emil Gumbel; Siegrist gives this exponential-maxima derivation and the standard Gumbel distribution formulas. ^[ref].

For the toy delay model $\lambda =1{\mathrm{s}}^{-1}$, $n=100$, the limiting Gumbel distribution approximation to $M_{100}$ has $\mu =(\log 100)\mathrm{s}$ and $b=1\mathrm{s}$. Its predicted median iscompared with the exact median $-\log (1-2^{-1/100})\mathrm{s}\approx 4.975147\mathrm{s}$. The approximation is about $0.003464$ seconds lower in this example. It is not an exact finite-sample probability distribution: the approximating Gumbel distribution assigns positive probability to negative delays, while the exact sample maximum cannot be negative.

The maximum domain of attraction of the Gumbel distribution is characterized by an exponential tail ratio on the scale of a Gumbel auxiliary function. This allows many original probability distributions to share the limiting shape, but it does not make the centering $\log n$ appropriate to all of them.

The Hadamard gate is the unitary operatorwhere $I$ is the identity operator. It maps the computational basis to the Hadamard basis:

These outputs have equal computational-basis measurement probabilities, but their relative quantum phase differs. Applying another Hadamard gate sends them to different definite outputs. Calling this gate a classical coin toss would discard precisely the information that makes this possible. ^[ref].

Starting from $|0⟩$, compare two quantum circuits, reading matrix products from right to left:Here $Z$ is the Pauli Z gate. After the first Hadamard gate, the probability amplitudes are $(1/\sqrt{2},1/\sqrt{2})$. Inserting $Z$ changes them to $(1/\sqrt{2},-1/\sqrt{2})$ without changing their squared magnitudes. At the final gate, the contributions to output zero cancel and those to output one add. Without $Z$, cancellation occurs at output one instead. This is controlled interference, with the quantum phase determining which answer emerges.

The same calculation works for any phase gate $P_{\varphi }=\mathrm{diag}(1,e^{i\varphi })$:For example, $\varphi =\pi /3$ gives $P(1)=1/4$, while $\varphi =\pi /2$ gives $P(1)=1/2$. The output-one amplitude at $\varphi =\pi /2$ is $(1-i)/2$: its two complex contributions add before the Born rule is applied. A phase gate alone leaves the populations unchanged; recombination converts its relative quantum phase into observable probabilities.

If quantum decoherence completely removes the computational basis coherence between the gates, the intermediate density matrix becomes $I/2$. Both the phase gate and final Hadamard gate leave $I/2$ unchanged, so $P(1)=1/2$ for every $\varphi$. The disappearing fringe explains why preserving quantum coherence matters: it enables the gate sequence to carry phase information into the final measurement.

The normalized Hadamard transform maps a vector indexed by binary strings through entries $2^{-n/2}(-1{)}^{x\cdot y}$, where the dot product is evaluated modulo two. It is its own inverse and an orthogonal transformation, hence also a unitary operator on complex input vectors. The Hadamard gate is the $n=1$ quantum case, and the Hadamard basis is the image of the computational basis. The Walsh-Hadamard transform gives the same tensor product construction.

For two qubits, applying one Hadamard gate to each prepares the uniform quantum superpositionEach probability amplitude is $1/2$, so each computational-basis measurement outcome has probability $1/4$. Applying the Hadamard transform again reconstructs $|00⟩$: signed contributions cancel at the other three outputs. Its usefulness lies in combining simple local quantum gates into an operation on exponentially many amplitudes. Extracting useful information still requires an appropriate subsequent transformation and measurement.

The half-normal distribution describes the absolute value of a centered Gaussian random variable. Its unit-scale version is $H=|Z|$ for a standard normal random variable $Z$. It folds the negative half of the standard normal distribution onto the positive half, retaining the size of a deviation while discarding its sign. If a centered Gaussian random variable models measurement error, its magnitude therefore has a half-normal distribution.Here $\varphi$ is the standard normal density and $\Phi$ is the standard normal distribution function. For $x\ge 0$, the event $H\le x$ is $-x\le Z\le x$, so the symmetric probability distribution of $Z$ gives $F_H(x)=\Phi (x)-\Phi (-x)=2\Phi (x)-1$. The upper-tail probability is therefore $\mathbb{P}(H>x)=2(1-\Phi (x))$. For example, $\mathbb{P}(H\le 1)\approx 0.6826894921$. The doubled probability density function integrates to one on $[0,\infty )$, and $\mathbb{P}(H=0)=0$.

The mean and variance of the unit-scale half-normal distribution areFor a short derivation, $\mathbb{E}[H]=2{\int }_0^{\infty }x\varphi (x)dx=2\varphi (0)$ because ${\varphi }^{\prime }(x)=-x\varphi (x)$, while $H^2=Z^2$ gives $\mathbb{E}[H^2]=1$. More generally, $\sigma |Z|$ for $\sigma >0$ has a half-normal distribution with probability density function $2\varphi (x/\sigma )/\sigma$ for $x\ge 0$. Its mean is $\sigma \sqrt{2/\pi }$ and its variance is ${\sigma }^2(1-2/\pi )$; here $\sigma$ is the scale of the underlying Gaussian random variable, not the standard deviation of its absolute value.

For a nonempty integer set with doubling constant at most $K$, Plünnecke-Ruzsa inequality bounds $|2A-2A|$ by $K^4|A|$. Embed the set modulo a sufficiently large auxiliary prime $q$, randomly dilate it, and select the more populated of two half-intervals of representatives. Differences of two pair sums on that half have absolute value less than $q$, so the lift preserves original relations. Every nonzero original difference is uniformly dilated among nonzero residues; avoiding all residues represented by nonzero multiples of $p$ of absolute value less than $q$ has positive probability when $p>4|2A-2A|$. Reduction modulo $p$ then yields a Freiman 2-isomorphism on the selected half.

Hamming distortion is zero for a correctly reconstructed symbol and one for a mismatch. Its expected distortion is the symbol-error probability:For strings of length $n$, separable distortion divides their Hamming distance by $n$. Thus $001$ reconstructed as $000$ has Hamming distance one and average Hamming distortion $1/3$. Counting only whether the whole string is correct would give a different criterion.

A two-setting nonlocality argument in which several zero-probability events forbid a further coincidence in any deterministic local hidden-variable model, but quantum theory assigns that coincidence positive probability. For binary indicators, suppose $C_{+}^R{C}_{-}^R=0$, $D_{+}^I=1\Rightarrow C_{-}^R=1$ and $D_{-}^I=1\Rightarrow C_{+}^R=1$. Any assignment with $D_{+}^I{D}_{-}^I=1$ would violate the first relation. A quantum implementation can nevertheless give such a coincidence. Real imperfect experiments require an inequality that accounts for their nonzero error probabilities. Lucien Hardy gave a two-particle inequality-free argument in 1992.^[ref]

For the normalized ground state of a reduced quantum harmonic oscillator, ${\varphi }_0(q)={\pi }^{-1/4}{e}^{-q^2/2}$ and $E_0=1/2$. Its classical turning points are $q=\pm 1$. The Born rule assigns probability $P=2{\pi }^{-1/2}{\int }_1^{\infty }{e}^{-q^2}dq=\mathrm{erfc}(1)\simeq 0.157299$ to the classically forbidden region. This is a stationary probability of detection outside the classical interval. It is not a transmitted flux or an escape rate: the real stationary wavefunction has zero probability current.

The percolation critical probability of independent bond percolation on the infinite square lattice is exactlyIn this model, $\theta (p)=0$ for $p\le 1/2$ and $\theta (p)>0$ for $p>1/2$. The particular graph, independent edge decisions, and distinction between bond percolation and site percolation matter: this value is not a universal threshold for arbitrary random networks. The equality of open and closed edge probabilities at $1/2$ suggests a relation to dual bond percolation, but that symmetry alone is not a proof of long-distance connectivity.

Harris established the lower bound, including absence of an infinite percolation cluster at $p=1/2$, in 1960. Kesten completed the equality in 1980. His original paper states the threshold result as Theorem 1 and the positive/zero percolation probability alternatives as Theorem 2: ^[ref]. These are claims about the infinite square lattice, rather than deductions from a simulated finite sample.

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]