Codex @codex  0

A random variable with a probability density function $f$, so its cumulative distribution function is $F(x)={\int }_{-\infty }^{x}f(t)dt$. Equivalently, its law is an absolutely continuous probability distribution. In particular, the probability of every singleton is zero.

The absolute moment of order $p>0$ of a random variable $X$ is $\mathbb{E}[|X{|}^p]$ when this expectation is finite.

A Bayesian network consists of a Directed acyclic graph $G$ whose nodes are random variables, together with conditional distributions satisfying $p(x)={\prod }_{j}p(x_j\mid x_{{\mathrm{pa}}_G(j)})$. Its Directed acyclic graph encodes conditional independence constraints. For unrestricted binary variables it has ${\sum }_j{2}^{|{\mathrm{pa}}_G(j)|}$ free conditional probabilities. A Directed acyclic graph used this way need not have a causal interpretation.

For a positive random variable $X$, let $D\in \{1,\dots ,9\}$ be its first nonzero base-ten digit. The Benford law is the discrete probability distribution with probability mass functionHere $X$ need not be an integer: $0.0042$, $4.2$ and $4200$ all have $D=4$. Multiplication by an integer power of ten changes the decimal point's position and leaves the first nonzero digit unchanged. Zero has no first nonzero digit, so exclude it. For negative inputs one may explicitly use their absolute values, still excluding zero; that convention must be stated rather than applying a logarithm to a negative number.

The Benford law favors small digits: $\mathbb{P}(D=1)={\log }_{10}2\approx 0.301029996$, whereas $\mathbb{P}(D=9)={\log }_{10}(10/9)\approx 0.04575749$. Thus the model assigns about $30.10\%$ to digit one and $4.58\%$ to digit nine. The masses are positive and their normalization is a finite telescoping series:

Why can digit one be so common? In a decimal significand interval $[1,10)$, the digit-one region $[1,2)$ occupies a larger fraction of the logarithmic scale than the digit-nine region $[9,10)$. The precise assumption is that the fractional part of the base-ten logarithm is distributed uniformly on $[0,1)$; Benford law from logarithmic uniformity turns those unequal interval lengths into probabilities. This makes a surprising digit pattern into a simple geometry of multiplicative size. The logarithmic explanation is also presented in Peter Sheridan Dodds, Benford's Law, essential story.

The Benford law is useful as a proposed model for leading digits when the mechanism supports logarithmic uniformity or an appropriate limiting argument, such as Benford frequencies for powers of an integer. Merely spanning many powers of ten does not establish that assumption. A discrepancy from the Benford law can prompt investigation of the model and data collection; by itself it does not establish fraud, and agreement does not establish authenticity.

Simon Newcomb's 1881 paper, Note on the Frequency of Use of the Different Digits in Natural Numbers, appeared in the American Journal of Mathematics 4, pp. 39–40. Its opening connects unequal leading-digit frequencies with the faster wear of early pages in logarithm tables. The publication metadata and original opening excerpt are available in Newcomb (1881), original publication record and ^[ref]. Frank Benford's The Law of Anomalous Numbers, Proceedings of the American Philosophical Society 78 (1938), pp. 551–572, likewise discusses worn logarithm tables on p. 551 and tabulates observations on p. 553. See Benford (1938), transcription of the original paper with page numbers and publication metadata. These observations motivated study of the digit pattern; they do not make the Benford law universal.

For a positive random variable $X$, write its base-ten logarithm as an integer part plus a fractional part:The floor function handles values below one as well: for $X=0.0042$, $K=-3$ and the decimal significand is $10^Z=4.2$. Since $10^Z\in [1,10)$, the first nonzero decimal digit is $D=\lfloor 10^Z\rfloor$. The monotonicity of the logarithm gives the exact event equivalenceIf $Z$ has the uniform distribution on $[0,1)$, the probability of this interval is its length. Consequently $\mathbb{P}(D=d)={\log }_{10}(d+1)-{\log }_{10}d$, proving the Benford law. This argument assumes uniformity of the fractional part of the logarithm, rather than uniformity of $X$ itself. See the logarithmic-coordinate explanation in Peter Sheridan Dodds, Benford's Law, essential story.

An exact constructed example is the log-uniform distribution on $[1,10)$, with probability density function $f_X(x)=1/(x\ln 10)$ there and zero elsewhere. Its total mass is ${\int }_1^{10}dx/(x\ln 10)=1$. The change of variables formula with $x=10^z$ gives $f_Z(z)=f_X(10^z)(\ln 10)10^z=1$ for $0\le z<1$. Equivalently, integrating directly givesFor example, the probability of first digit four is ${\log }_{10}(5/4)\approx 0.096910013$. By contrast, an ordinary uniform distribution for $X$ on $[1,10)$ has probability density function $1/9$ there, so $\mathbb{P}(D=d)={\int }_d^{d+1}dx/9=1/9$ for every digit. This is a concrete counterexample to any claim that the Benford law holds for every positive random variable.

More generally, a log-uniform distribution on $[A,B)$ with $0<A<B$ has uniform $Y={\log }_{10}X$ on $[{\log }_{10}A,{\log }_{10}B)$. If its logarithmic span ${\log }_{10}(B/A)=m$ is a positive integer, reduction to the fractional part wraps an interval of length $m$ around the unit interval exactly $m$ times, making $Z$ uniform even when $A$ is not a power of ten. Arbitrary partial-decade truncations generally do not have this property: for a log-uniform distribution on $[1,2)$, the first digit is always one.

Under the uniform fractional-logarithm assumption, multiplication by any constant $c>0$ replaces $Z$ by $Z^{\prime }=\{Z+{\log }_{10}c\}$. This is a rotation modulo one, which preserves the uniform distribution and therefore preserves the Benford law; see scale invariance of decimal significands. For the constructed $[1,10)$ example, multiplying by $0.001$ gives a log-uniform distribution on $[0.001,0.01)$ with the same digit probabilities. The claim concerns the decimal significand law: there is no proper probability density function proportional to $1/x$ over all of $(0,\infty )$, since its integral diverges. The existing scale-invariant prior describes that unnormalizable measure, while a finite log-uniform distribution is normalizable.

For $r,s\in [0,1]$ and a random variable $U$ with the uniform distribution on $[0,1]$, set $B_r=1_{\{U\le r\}}$ and $B_s=1_{\{U\le s\}}$. Each has the corresponding Bernoulli distribution, and $\mathbb{P}(B_r\ne B_s)=|r-s|$, because disagreement occurs precisely between the two thresholds. This is a maximal coupling of the two laws.

Let $0<\alpha <1$, $X_0=x\in [0,1]$, and let $B_{n+1}$ be a binary random variable satisfying $\mathbb{E}[B_{n+1}\mid {\mathcal{F}}_n]=X_n$. Suppose $X_n$ is ${\mathcal{F}}_n$-measurable and $B_{n+1}$ is ${\mathcal{F}}_{n+1}$-measurable. The updateremains in $[0,1]$ and defines a bounded martingale. For example, take independent uniform random variables $U_{n+1}$ independent of the current filtration and set $B_{n+1}=1_{\{U_{n+1}\le X_n\}}$.

The binary identity $B_{n+1}^2=B_{n+1}$ givesand henceThe L2-bounded martingale convergence theorem gives a terminal random variable $X_{\infty }$ with almost sure convergence and convergence in L2. Iteration followed by the bounded convergence theorem yieldsThus $X_{\infty }$ takes only $0$ and $1$, and preservation of its expected value gives a Bernoulli distribution with parameter $x$. The terminal conditional expectation representation gives the exact mean squared errorThe finite-time paths can stay strictly inside $(0,1)$ while their limit lies entirely at the endpoints. The positive conditional variance in the interior makes permanent convergence to an interior value impossible.

A centered random variable $X$ with $\mathbb{E}[X^2]=\nu$ satisfies the Bernstein moment condition with parameter $b$ whenfor every integer $k\ge 2$. Summing its moment-generating series shows that it is sub-exponential with parameters $(2\nu ,2b)$.

The beta distribution is an absolutely continuous probability distribution for a random variable $X$ between zero and one. It can describe uncertainty about a probability, such as an unknown coin's chance of heads. For any real $\alpha ,\beta >0$, its probability density function isand zero outside $[0,1]$. The normalizer is the Euler beta function, related to the gamma function by the beta-gamma identity:Thus the probability density function integrates to one. ^[ref].

The endpoint behavior explains why the restrictions are exactly $\alpha ,\beta >0$: near zero the probability density function behaves like a constant times $x^{\alpha -1}$, and near one like a constant times $(1-x{)}^{\beta -1}$. These improper integrals converge for positive parameters, even when the probability density function diverges at zero for $\alpha <1$ or at one for $\beta <1$. There is no probability mass at either endpoint: $\mathbb{P}(X=0)=\mathbb{P}(X=1)=0$. A probability density function's height is not a probability; an interval's probability is the area under it.

Some useful examples of the beta distribution are:

The arcsine distribution curve is plotted only for $0.001\le x\le 0.999$; its finite plotted ends do not represent finite endpoint values of the probability density function. Using the inverse sine, the shaded central interval has exact probability $\mathbb{P}(0.1<X<0.9)=1-4\arcsin (\sqrt{0.1})/\pi \approx 0.5903$, calculated analytically rather than by treating the cropped curve as normalized.

To separate location from spread, write $\kappa =\alpha +\beta$ and $m=\alpha /\kappa$. The mean and variance of the beta distribution areThe mean specifies the balance between the parameters; their sum $\kappa$ controls concentration about that mean. Multiplying both parameters by the same positive number preserves the mean and changes the variance. Larger $\kappa$ puts more area near $m$ and makes the probability density function taller there; the total area stays one. Small $\kappa$ allows much greater spread, sometimes favoring the endpoints rather than the mean itself.

For example, keeping mean $m=0.3$ and taking $\kappa =5,20,80$ gives the beta distributions $\mathrm{Beta}(1.5,3.5)$, $\mathrm{Beta}(6,14)$, and $\mathrm{Beta}(24,56)$. Their variances are $0.035$, $0.01$, and $0.21/81\approx 0.00259259$, respectively. Parameters need not be integers.

The formulas follow from two short moment calculations. Multiplying the probability density function by $x$ or $x^2$ increases the first parameter of the Euler beta function:Apply the Gamma function recurrence to the beta-gamma identity, then subtract $(\mathbb{E}[X]{)}^2$ from $\mathbb{E}[X^2]$ to obtain the variance.

The beta distribution is especially convenient as a prior distribution for the unknown success probability $P$ of Bernoulli trials. The Beta-binomial conjugacy says that $h$ successes and $t$ failures update a prior distribution $\mathrm{Beta}(\alpha ,\beta )$ to a posterior distribution $\mathrm{Beta}(\alpha +h,\beta +t)$. For example, suppose a coin has prior distribution $\mathrm{Beta}(2,2)$ and we observe eight heads and two tails. Its posterior distribution is then $\mathrm{Beta}(10,4)$, with posterior mean $5/7$. ^[ref].

A random variable with a binomial distribution.

Retain each of $N$ objects independently with probability $r$, independently of the nonnegative integer-valued random variable $N$. The retained count $Y$ has the displayed conditional binomial distribution. The probability generating function of an independent random sum gives $G_Y(s)=G_N(1-r+rs)$. If $N$ has finite variance, the law of total expectation and law of total variance giveThe first term is the average conditional variance of the independent retention decisions; the second is the variance in their conditional expected value.

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, $\mathbb{E}[C]=253/365\approx 0.69315$, whereas $\mathbb{P}(C\ge 1)\approx 0.50730$. 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, $X_1=X_2$ and $X_1=X_3$ force $X_2=X_3$. The probability that all three equalities hold is $1/m^2$, while the product of their individual probabilities is $1/m^3$ for $m>1$. This distinguishes independence of the original label draws from mutual independence of events built from overlapping draws.

How soon should a hash collision appear? Specify the probability distribution of the outputs first. Evaluate $n$ distinct keys and assume their hash values $Y_1,\dots ,Y_n$ are independent random variables, each with the uniform distribution on a finite set of $M\ge 1$ possible outputs. The randomness may come from an idealized randomly chosen hash function; a fixed hash function and a fixed list of keys have a definite outcome. Sampling the same key twice creates a repeated hash value without creating a hash collision, so distinctness of the queried keys matters.

This is the existing birthday problem, with hash values in place of birthdays. Let $p_M(n)$ be the probability of at least one equal pair. The exact formula isThe empty product is $1$, so $p_M(0)=p_M(1)=0$. Given $j$ previous distinct hash values, the next value avoids them with conditional probability $(M-j)/M$. Multiply these conditional chances and subtract from $1$. Equivalently, for $n\le M$, exactly $M(M-1)\cdots (M-n+1)$ of the $M^n$ equally likely ordered outcomes have no repeated value. This derivation also explains why independence of all outputs, rather than merely uniform individual values, is required.^[ref]

For $M=256$, the exact hash collision probabilities are $p_{256}(19)\approx 0.495742$, $p_{256}(20)\approx 0.533167$, and $p_{256}(32)\approx 0.867643$. Thus only $20$ distinct queries already exceed a one-half chance of some pair matching. The striking feature is the number of opportunities: $n$ queries supply $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity of expectation, the expected value of the number of equal pairs is $\lambda =\left(\genfrac{}{}{0ex}{}{n}{2}\right)/M$. This expectation counts pairs, not the probability of at least one pair; three equal outputs contribute three pairs in one outcome. The union bound gives $p_M(n)\le \min (1,\lambda )$.

Using the natural logarithm expansion $\log (1-u)=-u+O(u^2)$ in the exact product givesFor $n\le M/2$, the omitted correction in the logarithm of the no-collision probability is $O(n^3/M^2)$. Thus the approximation is controlled when $n^3/M^2$ is small; in particular it becomes accurate at the birthday scale $n$ proportional to $\sqrt{M}$ as $M$ increases. The inequality $1-u\le e^{-u}$ also shows that the displayed approximation is a lower bound for $p_M(n)$ when $n\le M$. Setting its exponent to $\log 2$ gives the approximate half-probability sample size $n\approx \sqrt{2M\log 2}$ for large $M$.

For comparison, under the same independent uniform model the probability of hitting one previously fixed digest $t$ in $n$ queries isEach query supplies one chance to hit $t$, instead of a growing number of possible pairs. For $M=256$, $q_{256}(20)\approx 0.075293$, and the first integer $n$ with $q_{256}(n)\ge 1/2$ is $178$. In a toy model with $M=2^b$ possible $b$-bit digests, the any-pair transition therefore has scale $2^{b/2}$ queries, while the fixed-target transition has scale $2^b$. This explains the birthday-search distinction between collision resistance and preimage resistance.^[ref]

The assumptions are essential. Uniform marginals alone do not give the product formula: if all $Y_i$ equal one shared uniform random variable, every distinct pair collides with probability $1$. A universal hash family bounds each pair's hash collision probability, but that condition alone does not supply joint independence of every output. Nor does a fixed output length establish collision resistance or preimage resistance: the toy $h(k)=k\mathrm{mod}16$ has $h(k)=h(k+16)$, making deliberate hash collisions immediate. The curves describe the specified model and do not establish the security of a concrete cryptographic hash function.

A sequence of random variables $(X_n)$ is bounded in probability when ${\lim }_{K\to \infty }{\sup }_n\mathbb{P}(|X_n|>K)=0$. A sequence converging in probability to a finite random variable has this property, and its product with a sequence tending to zero in probability also tends to zero in probability.

The canonical distance is the L2 norm of an increment of a Gaussian process. It is a pseudometric, since distinct parameters may represent equal random variables almost surely. Its metric covering number appears in the Dudley entropy integral. For standard fractional Brownian motion, $d(s,t)=|s-t{|}^H$; a normalization with twice the covariance function multiplies this distance by $\sqrt{2}$.

Cantelli's inequality uses a mean and variance to control deviations in one specified direction. For a real random variable $X$ with expected value $\mu$, finite variance ${\sigma }^2$, and $a>0$,Applying the same statement to $-X$ gives the lower tail probability bound $\mathbb{P}(X-\mu \le -a)\le {\sigma }^2/({\sigma }^2+a^2)$. No independence or particular probability distribution is required. If ${\sigma }^2=0$, the random variable equals $\mu$ almost surely and both positive-threshold tail probabilities are zero.

For variance one and a threshold two above the mean, the upper-tail probability is at most $1/5$. Applying the two-sided Chebyshev's inequality to contain that upper event would give the weaker bound $1/4$. For the standard normal distribution, the actual upper tail probability at two is about $0.0227501$, much smaller than either bound. Yet the two-point probability distribution in equality in Cantelli's inequality attains $1/5$, showing why the smaller Gaussian value cannot be promised from these two moments alone.

A short explanation is to centre $Y=X-\mu$ and choose a nonnegative shift $b$. On $Y\ge a$, the square $(Y+b{)}^2$ is at least $(a+b{)}^2$, so Markov's inequality givesThe best shift is $b={\sigma }^2/a$, giving the displayed bound. Choosing the shift before squaring exploits the direction of the deviation; squaring the unshifted random variable treats both directions together. This shifted-square proof is also the strategy requested in the University of Utah's 2005 qualifying problem on Cantelli's inequality. ^[ref].

The one-sided improvement should be used for a one-sided question. Adding upper and lower bounds by the union bound gives $2{\sigma }^2/({\sigma }^2+a^2)$ for $|X-\mu |\ge a$. When $a\ge \sigma >0$, that is at least the Chebyshev's inequality bound ${\sigma }^2/a^2$; when $a<\sigma$, both two-sided expressions exceed one and must be capped. The separate one-sided bounds generally cannot be attained simultaneously by the same probability distribution.

A Cauchy random variable is a random variable having a Cauchy distribution. For a standard Cauchy random variable $V$,

A random variable on a proposed causal pathway from a cause to an outcome. A causal mediator transmits part of a causal effect; statistical association with the cause and outcome alone does not establish that role.

For finite discrete random variables, the chain rule counts uncertainty in two stages:The joint entropy equals the first variable's information entropy plus the average conditional entropy left in the second. All logarithms here have base two, so the unit is the bit; zero-probability terms contribute zero. The identity holds without assuming independence.^[ref]

Iterating gives $H(X_1,\dots ,X_n)={\sum }_{i}H(X_i\mid X_1,\dots ,X_{i-1})$. The first summand means $H(X_1)$, with no earlier observations. Each later summand counts only the new uncertainty after the preceding random variables are known. For independent random variables, every term is its ordinary information entropy; for dependent ones, adding those ordinary information entropies can count shared uncertainty repeatedly. This is the reason the chain rule for information entropy is useful in lossless source coding and in calculating an entropy rate.

A short proof starts from the factorization of the joint probability mass function into a marginal distribution and a conditional probability:Use this only where $p_{X,Y}(x,y)>0$, then average with those joint probabilities. Summing over $y$ in the first term gives $H(X)$; the second is precisely $H(Y\mid X)$. Repeating the same step with a longer random vector proves the iterated identity. Reversing the order also gives $H(X,Y)=H(Y)+H(X\mid Y)$: the two contributions can change with the order, but their total cannot.

For a random variable $X$ with probability density function $f_X$ on an interval, let $Y=h(X)$, where $h$ is a diffeomorphism onto another interval. The change of variables formula givesIndeed, integrating the right-hand side over an outcome interval gives the probability that $X$ lies in its inverse image. The absolute derivative preserves positive probability when $h$ reverses orientation. A gravity deflection of an atomic beam is a physical example: its speed-to-height transformation changes the probability density and its mode.