Hash function 2026-10-13
A hash function is a function assigning each key in an input set a value in an output set . Usually is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If , the pigeonhole principle makes some collisions unavoidable.
For example, modular arithmetic gives the hash function , with seven bucket indices . Store the seven keys : their values are respectively . In particular, although . A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket retains all four keys . Inserting must not overwrite merely because their hash function values agree.
Searching for computes bucket , then compares the actual keys until it reaches . Searching for absent key reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.
Hazard function Created 2026-09-24 Updated 2026-10-14
For a survival time with an absolutely continuous probability distribution, probability density function , and survival function , the hazard function iswhere , with the derivative identity holding almost everywhere. At points where the local limit exists, equivalentlyThe hazard function measures an instantaneous conditional rate. If time is in years, its units are inverse years, and its value can exceed one. A probability for a short interval is approximately , not ; for an absolutely continuous probability distribution, the probability of an occurrence at the single exact time is zero. The discrete hazard, by contrast, is a conditional probability at a possible event time.
The factorization distinguishes a probability density function for the original population from a hazard function for those still event-free. With an exponential distribution of rate per year, per year but per year: the latter also accounts for the probability of reaching year five. The exponential survival risk over an interval example computes finite-horizon probabilities from this rate.
Orient a degree- regular tree towards one end, and let height decrease along the unique parent edge and increase along the child edges. For , suppressing the occupied-target constraint only increases births, so its infinitesimal generator satisfies . For , choose . If , the expected weight and the infection probability at each fixed site decay exponentially. The expected number of recoveries there equals its expected total occupation time, which is finite. Each infection episode ends almost surely at a recovery, so infinitely late infection is impossible. For , take sufficiently close to one for each .
Helstrom measurement for the zero and plus states Created 2026-09-24 Updated 2026-10-14
Suppose one qubit is prepared in either of the known pure states and , with equal prior probabilities. Measuring in the computational basis seems natural, but a tilted projective measurement gives better quantum state discrimination. The two density operators and their difference areThe Pauli matrices give , and the eigenvalues of are . Their absolute sum gives trace distance , agreeing with trace distance between qubit states.
The positive spectral projector points along the unit Bloch vector :The outcome labels and here refer to the sign of the eigenvalue of ; they do not denote a Hadamard basis measurement. Guess after and after . This sign choice is the equal-prior Helstrom measurement for two pure states, a case of the Holevo–Helstrom theorem. [ref]
https://cs.uwaterloo.ca/~watrous/TQI/TQI.3.pdf. Watrous, The Theory of Quantum Information, Theorem 3.4, equation (3.17)
An explicit orthonormal basis for this projective measurement iswith . Thus the real coefficient rotation angle is relative to the computational basis, while the Bloch vector of is tilted by from the positive axis toward negative . State-vector and Bloch sphere angles differ by a factor of two.
Write and , so . The Born rule gives the conditional outcome probabilitiesThe event has probability gap , attaining the variational characterization of trace distance. Both preparations are identified correctly with conditional probability , so
For comparison, a projective measurement in the computational basis has conditional outcome probabilities on and on . Guess zero on outcome zero and plus on outcome one. The average success isand the measured total variation distance is only . The optimal tilted projective measurement gains about in absolute success probability by balancing the two conditional error rates instead of identifying perfectly at the expense of .
Conditional outcome probabilities and equal-prior success for Z and optimal Helstrom measurements of zero versus plus
. Details. These are statistics for alternative measurements on independently prepared copies. Applying first and then the tilted projective measurement is a different experiment, because the first measurement in quantum mechanics changes the density operator.
For a target pure state of a qubit, choose its orthogonal complement so thatMeasuring the sender's half of this singlet state in that basis leaves the receiver in when the sender obtains . The outcome has probability one half. One classical success flag heralds the exact preparation without conveying the target's classical description.
// Target: quantum-theory.bigb
High-speed charge and isotope scaling of electronic stopping Created 2026-10-18 Updated 2026-10-20
For a fast ion traversing a fixed material thickness with only a small fractional energy loss, the dipole excitation probability per atomic encounter scales as at fixed impact parameter. Summing transferred excitation energies and integrating the encounter measure gives the leading electronic stopping power scaling, with slower logarithmic dependence from the allowed excitation energies and impact-parameter range.
At fixed ion kinetic energy , a heavier isotope is slower, so the leading loss scales as . At fixed velocity, isotopes of the same element instead have approximately the same electronic loss; plotting against energy per nucleon removes the leading isotope mass dependence. The charge should be the effective projectile charge if its bound electrons screen the nucleus. At lower speeds, excitation thresholds, slow-passage suppression, charge exchange and nuclear energy transfer invalidate a simple extrapolation of the high-speed law.
Histogram 2026-10-14
A histogram groups numerical observations into adjacent intervals called bins and draws one rectangle per bin. Its attraction is that a long list of values becomes a visible pattern of concentration, gaps and skewness. Specify the bin edges, the treatment of values on those edges, and what the vertical axis means: count, proportion, or density. Those choices are part of the graphic. [ref]
https://www.itl.nist.gov/div898/handbook/eda/section3/histogra.htm. NIST/SEMATECH, Histogram, definition and normalization
Let observations be covered by disjoint bins with positive widths and counts , so . For example, use left-closed, right-open bins, closing the final right edge too. The three common height choices have different meanings:
For the density convention, a histogram is a piecewise constant probability density function estimate:Its normalization follows by adding rectangular areas:If the observations have units, density has reciprocal units; a density height is not a probability and can exceed . With equal bin widths, count heights and density heights differ only by a common scale factor. With unequal widths, count-height areas give wider bins extra visual weight unrelated to their counts. Dividing by width removes that distortion. R's histogram documentation explicitly describes area-one normalization for unequal bins. [ref]
https://stat.ethz.ch/R-manual/R-devel/library/graphics/html/hist.html. R graphics documentation, hist, frequency versus density
Reuse the twelve invented values under box plot, with bins . The counts are and the widths are . Hence the density heights and areas are exactlyThe second and third bars have equal density heights even though the third contains twice as many observations: it is also twice as wide. The last bar contains only two observations; its count-height area would be , larger than the six-observation bar's . Its correct density area is only .
Bin choice trades detail against stability. Broad bins merge distinctions: the toy bin hides the empty stretch between and . Narrow bins expose gaps but can make each individual observation dominate a bar. With one-unit bins starting at , the bins each contain two values and appear equally prominent; that apparent pattern depends on grouping the repeated integers together. Moving the bin origin also changes membership without changing the observations. For density estimation, this is a form of the bias-variance tradeoff: averaging over broad bins loses local detail, while narrow bins give more variable density estimates across repeated statistical samples. [ref]
https://www.stat.cmu.edu/~cshalizi/uADA/24/lectures/ch14.pdf. Cosma Rohilla Shalizi, Estimating Distributions and Densities, Section 14.1
A useful practice is to compare a few plausible widths and offsets, keeping common edges when comparing groups. Automatic bin selectors are starting points, rather than guarantees of a unique correct picture. [ref]https://numpy.org/doc/stable/reference/generated/numpy.histogram_bin_edges.html. NumPy documentation, histogram_bin_edges, Notes on bin selectors
A histogram retains only bin membership. Its density estimate spreads each bin's fraction uniformly across that bin, so our last bar assigns density throughout even though the only toy values there are and . It does not recover within-bin positions or observation order, and a visually convincing shape does not establish a population probability distribution. A box plot provides a complementary compact summary of quartiles; neither graphic replaces the original observations.
Hoeffding confidence interval 2026-10-14
For a fixed positive sample size of independent and identically distributed Bernoulli random variables, letThe Hoeffding inequality makes a conservative confidence interval for : for every . Indeed, exclusion from the closed interval implies , an event contained in the deviation event bounded by . Clipping to retains coverage because already lies there. For , , and an observed frequency , , giving approximately .
Coverage concerns repeated independent samples: the unknown is fixed and the confidence interval is random. This fixed- guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The Hoeffding sample size for Bernoulli frequencies chooses in advance; guarantees across repeated inspection times require separate control of the additional events, for example through a union bound with an allocated failure probability at each time.
Hoeffding inequality Created 2026-09-24 Updated 2026-10-14
The Hoeffding inequality turns finite interval bounds and independence into exponentially small tail probabilities for a sum. It requires neither a normal distribution nor identical probability distributions. Let be independent essentially bounded real random variables, with deterministic finite bounds almost surely. Define the centered sum and its squared-width budget byFor and ,The union bound therefore gives . If , every is constant almost surely, so and both positive-threshold tail probabilities vanish. The equal-width version is stated in the authored Stanford notes.[ref]
The quantity is a sum of squared interval widths, not the variance of . Centering changes the endpoints to and , leaving each width unchanged. For example, independent random variables in and have , whatever their expected values or probability distributions. A deviation at least three above their total expected value has probability at most . If all widths equal , the sample mean satisfies
Independence is essential to this general guarantee. Take one Bernoulli random variable with success probability and set every . Each lies in , but for every the sample mean is either zero or one. Thus , whereas incorrectly inserting these dependent observations into the formula would give , less than one for . Some special dependent models have their own valid concentration inequalities; arbitrary statistical dependence cannot be ignored.
For the short proof, apply Markov's inequality to with , factor the expectation using independence, and apply the Hoeffding lemma to each factor:Minimizing this quadratic polynomial at gives the upper tail probability; applying it to gives the lower one. This is the Chernoff bound method. The original 1963 article is Probability Inequalities for Sums of Bounded Random Variables by Wassily Hoeffding; its publisher record identifies the article, but its full text was unavailable during this source check. The argument above is a direct derivation rather than a claim to have inspected that article's proof.
Hoeffding lemma Created 2026-09-24 Updated 2026-10-14
The Hoeffding lemma controls the entire centered moment-generating function using only an interval width. For an essentially bounded real random variable with finite deterministic bounds almost surely, every real satisfiesEquivalently, . This single-random variable statement needs no independence assumption; independence enters when applying it to the factors for a sum in the Hoeffding inequality. Both signs of are allowed, and equality holds at or when .[ref]
In the convention for a centered sub-Gaussian random variable , the Hoeffding lemma supplies . This upper parameter need not equal the actual variance. For a Bernoulli random variable of success probability ,The actual variance is , whereas the supplied parameter is for every . This explains part of the conservatism visible in Hoeffding sample size for Bernoulli frequencies.
A short proof exposes why the constant is . Put and define exponential tilting byThe tilted probability measure has the same interval of possible values, and differentiating the cumulant-generating function gives . Boundedness justifies these derivatives for every finite . Under any such tilted law, Popoviciu's inequality on variances gives : the variance is no larger than the expected value of the squared distance from the interval midpoint, itself at most . Since , the integral form of Taylor's theorem yieldsThis expression handles either sign of without changing the argument.
The constant cannot be reduced uniformly over all essentially bounded real random variables. Equal endpoint probabilities at and give , a scaled Rademacher random variable, andThus the sharpness is already forced near zero by the variance; the bound need not be equality at nonzero parameters for a particular probability distribution.
Let be independent and identically distributed Bernoulli random variables with success probability , and let be their observed frequency, a sample mean. Since every interval width is one, . Substituting into the Hoeffding inequality givesFor tolerance and failure probability , solving yields the sufficient sample sizeHere is the natural logarithm. For and , guarantees an error smaller than with probability at least , for every . The two-sided bound at this sample size is approximately . A specified single direction instead needs , or for these choices. Halving the tolerance multiplies the unrounded sufficient sample size by four; reducing the failure probability tenfold adds before rounding.
This is a conservative sufficient sample size, not a necessary minimum. For a specified , the count has a binomial distribution, whose exact upper tail probability isFor , the Hoeffding inequality bounds this by . An arbitrary frequency threshold uses ; if , the event is impossible. The discreteness of the count and its variance can make the exact tail probability substantially smaller. At , , , the exact upper tail probability is about , while the bound is . At , , the same deviation gives the same bound but an exact upper tail probability about .
Exact binomial distribution tails compared with the Hoeffding inequality
. Two original specified models, each with independent Bernoulli trials. Each dot includes its integer threshold , with horizontal coordinate . Exact finite sums are evaluated with rational arithmetic before conversion for plotting. The Hoeffding inequality uses the width one in both panels; it does not use the smaller variance at . These are model probabilities, not measured frequencies. Details. Holley inequality 2026-10-07
On a finite distributive configuration lattice, probability weights satisfying for all pairs give stochastic domination . The result holds for nonnegative weights as well: apply the four functions theorem to for an increasing event , obtaining .
Hong-Ou-Mandel effect Created 2026-10-20 Updated 2026-10-20
Two indistinguishable bosons entering separate inputs of an ideal balanced beam splitter have zero probability of leaving one per output. The two alternatives for that occupancy interfere destructively. Distinguishability in temporal, spatial or internal modes weakens the cancellation.
Huffman coding Created 2026-09-24 Updated 2026-10-14
Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. [ref]
The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with and ; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.
For a concrete example, use probabilities , , , . First join and , creating weight . The remaining weights are for , for the subtree, and for . Join the two weights to make , then join with that subtree to make . The merge weights are therefore . Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.
The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.
Huffman sibling property Created 2026-09-24 Updated 2026-10-14
For a finite source alphabet of symbols with positive weights , choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.[ref]
A Method for the Construction of Minimum-Redundancy Codes by David A. Huffman. p. 1099: Derived Coding Requirements and Optimum Binary Code
An exchange makes the idea tangible. Take probabilities . The prefix code , , , has expected codeword length bits. Exchange only the symbols at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become . The new expected codeword length is bits, and the two least probabilities, those of , now occupy deepest sibling leaves in a code tree. The saving is bit per source symbol.
Exchanging two leaf labels reduces expected length from 2.5 to 1.9 bits; contracting the least-probability siblings leaves cost 1.6
. Details. Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight from leaf depth in a code tree to a deepest position , occupied by , changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. [ref]
The nonrelativistic hydrogen ground energy is . Requiring nonnegative classical kinetic energy restricts radius to . Integrating the quantum ground-state radial probability density beyond that radius instead gives . A bound-state tail can therefore have substantial integrated probability outside the classically allowed region without violating energy conservation.
Hypergeometric distribution Created 2026-09-24 Updated 2026-10-14
The hypergeometric distribution counts marked objects in a uniformly chosen sample of fixed size from a finite population, using sampling without replacement. Let be the population size, let objects be marked, and sample distinct objects. If counts the marked objects selected, its probability mass function isThe bounds describe the support of a probability distribution and must be an integer; the mass is zero elsewhere. The denominator counts all size- subsets, while the numerator counts choices of marked and unmarked objects using binomial coefficients. This counting argument requires every size- sample to have the same probability.[ref]
https://web.mit.edu/14.380/www/handouts/hypergeometric.pdf. MIT 14.30, hypergeometric distribution handout, §§1–4
For a constructed example, a box contains ten labelled objects, four red and six blue. Select five without replacement. There are possible samples. The probabilities for areIn particular, . Five red objects are impossible because the box only contains four. The expected value is , and the variance is .
Five draws from four red and six blue objects: replacement preserves the mean but changes the spread
. Details. The count law also answers a detection question: what is the chance that five draws find at least one red object? By the complement rule of probability, it is , approximately . This can model inspecting five distinct objects from a known finite collection, with a mark indicating the property we want to detect. If repeated inspections can select the same object again, the replacement model instead gives . Equal expected values therefore do not imply equal chances of detecting a marked object.
The corresponding binomial distribution counts red draws when each selected object is put back before the next independent draw: . It has the same expected value , but variance , and it permits five red draws. Without replacement, a red first draw leaves red probability for the next draw; a blue first draw leaves . This statistical dependence pulls the total toward the fixed composition of the population, producing the finite population correction.
The useful modelling question is whether previously selected objects remain available. A fixed-size sample of distinct items calls for a hypergeometric distribution; fresh independent trials with constant success probability call for a binomial distribution. When the population grows with while stays fixed, the hypergeometric masses tend to the corresponding binomial distribution masses: removing finitely many objects has an increasingly small effect on the next draw's probability.
IceCube starting-event veto 2026-10-18
The 2013 selection rejected early boundary light. Tagged muons checked leakage; air shower companion muons also vetoed downward atmospheric neutrinos.[ref]
Evidence for High-Energy Extraterrestrial Neutrinos at the IceCube Detector by IceCube Collaboration. Event Selection; Atmospheric Muon Background
Entering tracks, contained interactions and an accompanying-muon veto
. Original schematic, not to scale or measured data. Dots: optical modules. Dashed arrows: unseen neutrinos; solid arrows: muons. Details.A simple original conditional probability model explains why a veto changes the selected mixture. Let mean that an atmospheric neutrino interaction would pass all other cuts, that an accompanying muon reaches the veto, and that the veto fires. Set and , and neglect unrelated veto hits. The law of total probability givesFor chosen and , the passing fraction is . Neither this value nor either input is an IceCube measurement. With equal incident candidate populations, this mechanism alone reduces the atmospheric contribution relative to a hypothetical population having . It does not make every surviving event astronomical: or gives no suppression, while removes the entire chosen atmospheric population. If unrelated light vetoes a surviving event independently with probability , its passing fraction becomes ; independence is an additional assumption.
Importance sampling of a Cauchy tail 2026-10-14
For uniform on , has density on . The importance sampling weight for the standard Cauchy distribution tail is , and its expectation is the target tail probability. Writing gives and by integrating . The weight varies only between and , making its variance much smaller than that of a rare-event indicator. This is a comparison of sampling variances, not a deterministic ordering of every pair of empirical variance estimates.
Impulsive quantum kick 2026-10-14
An impulsive quantum kick is the limit of a pulse with finite integrated Hamiltonian operator, rather than a bounded finite step. For a bounded self-adjoint operator with units of action, a rectangular pulse lasting has exact unitary time evolution for every . In the limiting notation , is the Dirac delta function andThe integral estimate for quantum state continuity at a finite Hamiltonian step no longer tends to zero: the pulse height diverges. A bounded background Hamiltonian operator contributes vanishing evolution during this limit. A more general pulse with noncommuting generators can require time ordering; integrated area alone then need not specify the result.
For example, , with a Pauli matrix, sends a qubit in to . At , the Born rule predicts with probability one, however short the regularized pulse is. Its finite rotation is precisely what a bounded finite step cannot accomplish at the switching instant.








