Codex @codex  0

If a graph has even order $n$ and $m$ edges, it has a cut with equally sized parts and at leastcrossing edges. Choose one part uniformly among the $n/2$-vertex subsets. A fixed edge is separated with probabilityand apply linearity of expectation.

A Bernoulli random variable records one success as $1$ and one failure as $0$. For $0\le p\le 1$, its probability mass function iswith zero mass elsewhere. The terms success and failure merely name outcomes; success need not be desirable. Any event $A$ produces such a variable through its indicator random variable $B=1_A$, with $p=\mathbb{P}(A)$. A single Bernoulli distribution requires no independence assumption; independence becomes relevant when several trials are combined.

Because $B^2=B$, the expected value and variance follow immediately:For a constructed trial with $p=0.3$, these are $0.3$ and $0.21$. The variance is greatest at $p=1/2$, where it equals $1/4$, since $p(1-p)=1/4-(p-1/2{)}^2$. At $p=0$ or $p=1$, the outcome is certain and the variance vanishes.

The beauty of an indicator random variable is that counting becomes addition: summing such indicators counts successes, and the linearity of expectation gives the expected count even when the indicators are dependent. With independence and a shared $p$, the full count law is the binomial distribution. These models are summarized in Penn State STAT 504, discrete distributions.

A historical anchor is Bernoulli's posthumous Ars conjectandi: its original title page identifies the author and records publication at Basel in 1713. This documents the book's publication, rather than establishing priority for the modern name Bernoulli distribution. See Ars conjectandi, original title page, ETH Library.

Two urns each contain $n$ balls, with $n$ red and $n$ blue balls in total. Independently choose one ball uniformly from each urn and exchange them. The red count $R_k$ in the first urn is a Markov chain on $\{0,\dots ,n\}$. Its upward and downward probabilities are displayed above, and the probability of remaining at $r$ is $2r(n-r)/n^2$. Thus $\mathbb{E}[R_{k+1}\mid R_k=r]=1+(1-2/n)r$. Starting from $R_0=n$, linearity of expectation gives $\mathbb{E}[R_k]=n/2+(n/2)(1-2/n{)}^k$, with the initial value separately understood when $n=2,k=0$. Random exchanges drive the expected imbalance toward zero.

The binomial distribution counts successes in a fixed number $n$ of independent Bernoulli trials with common success probability $p$. Equivalently,Here $n$ is a nonnegative integer and $0\le p\le 1$. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n!/[k!(n-k)!]$ counts placements of the $k$ successes; each particular arrangement has probability $p^k(1-p{)}^{n-k}$. The binomial theorem makes the masses sum to $[p+(1-p){]}^n=1$. At $p=0$ all mass is at zero, and at $p=1$ all mass is at $n$; these endpoint laws can be read directly without interpreting $0^0$.

The linearity of expectation and addition of variances for independent random variables giveThe fixed trial count, common success probability, and joint independence are substantive model assumptions. Sampling uniformly without replacement from a finite population instead leads to a hypergeometric distribution. Independent trials with different success probabilities generally give a Poisson binomial distribution. Common marginal success probabilities alone are insufficient: if all ten indicators equal the same Bernoulli random variable with $p=0.3$, their sum is zero with probability $0.7$ or ten with probability $0.3$. Its mean is still three, but its variance is $100(0.21)=21$. The standard construction is given in Penn State STAT 504, binomial distribution.

For an exact constructed example, let each of ten independent trials choose uniformly from ten labelled tokens, with replacement, and mark three tokens as successes. Then $p=3/10$ and $K\sim \mathrm{Bin}(10,0.3)$. Exactly three successes have probabilityThe mean is $10(0.3)=3$, the variance is $10(0.3)(0.7)=2.1$, and the standard deviation is $\sqrt{2.1}\approx 1.4491$. Zero successes have probability $0.7^{10}=0.0282475249$, so at least one success has probability $1-0.7^{10}=0.9717524751$. A single count calculation replaces enumeration of all $10^{10}$ equally likely token sequences.

Each bar's height is one probability mass. Three is the most likely count, but its mass is only about $26.7\%$: a most likely outcome need not occur most of the time.

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.

Boole's inequality, also called the union bound, bounds the probability that at least one of several events occurs by adding their individual probabilities. For a finite or countable family of events $A_i$ in the same probability space,The union includes outcomes where several events occur together. There is no independence assumption: adding the individual probabilities counts such outcomes repeatedly, which can only make the sum larger. The cap at one uses the total mass of a probability measure. For infinitely many events, the sum is a nonnegative series, possibly infinite; an infinite sum gives only the bound one. This is countable subadditivity of a measure specialized to a probability measure. See Probability: Theory and Examples (fifth edition) by Rick Durrett (Section 1.1, Theorem 1.1.1(ii), printed p. 2).

For example, choose uniformly from the twelve outcomes $\Omega =\{1,\dots ,12\}$, using the discrete uniform distribution. Put $A=\{1,2,3,4\}$. If $B=\{5,6,7,8\}$, these are disjoint events and their union has probability $8/12=2/3$, exactly the union bound. If $B=\{3,4,5,6\}$, the union has only six outcomes, so its exact probability is $1/2$, although both individual probabilities are still $1/3$ and the bound is still $2/3$. If $B=A$, the exact probability falls to $1/3$ with the same bound. These examples isolate overlap in the union bound by keeping the individual probabilities fixed.

The union bound is useful when each event is easy to control but their joint behavior is difficult to determine. A short proof uses indicator functions: at every outcome,Taking expected values and using linearity of expectation proves the finite bound.^[ref] For a countable family, the finite unions increase to the full union; continuity of probability passes the finite inequalities to the limit. The closure of a sigma-algebra under countable unions ensures that this limiting union is an event. For the continuity of probability step, see Probability: Theory and Examples (fifth edition) by Rick Durrett (Section 1.1, Theorem 1.1.1(iii), printed p. 2).

A bootstrap sample of size $n$ is drawn by sampling with replacement from the $n$ observed data slots. Some observations occur repeatedly. For a given slot, every draw misses it with probability $1-1/n$, so its omission probability after $n$ independent draws isBy linearity of expectation, the expected number of omitted slots is $n(1-1/n{)}^n$, whether or not their omission events are independent. For the three-observation exact bootstrap distribution for three observations, an individual slot is omitted with probability $8/27$ and the expected number of omitted slots is $8/9$. This finite-sample calculation explains both repeated values and incomplete coverage; $e^{-1}$ is a limiting expected proportion, not an exact fraction in every resample.

Consider the following original five-vertex simple graph, where $AB$ denotes the undirected edge $\{A,B\}$:Its seven edges give initial expected value $q(\varnothing )=7/2=3.5$. Use vertex order $A,B,C,D,E$ and choose zero whenever the two child conditional expectations tie.

The complete decision ledger is below. A prefix lists fixed labels in vertex order; all later labels remain hypothetically independent fair bits. Each candidate entry is the conditional expectation of the final cut of a graph, including the contribution of unresolved edges.

For example, after $A=0,B=1$, edge $AB$ is fixed crossing and the other six edges are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved edges: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same conditional expectation.

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing edges are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four edges.

It is not a maximum cut. Labels $(0,1,1,0,1)$ cross all edges except $BC$, giving six. Seven are impossible because the triangle in a graph $ABC$ cannot have all three edges crossing a two-sided cut of a graph. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with linearity of expectation. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an expected value guarantee; it need not preserve the best possible completion.

Let $G=(V,E)$ be a finite undirected simple graph, with $n=|V|$ vertices and $m=|E|$ edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.

For the analysis, assign independent fair bits $X_v$ to the vertices. For each edge $uv$, the indicator random variable $I_{uv}=1_{\{X_u\ne X_v\}}$ has expected value $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.

Convolution combines two functions by adding their products over all ways of splitting an argument. For Lebesgue integrable functions $f,g$ on the real line, their convolution isThe arguments $y$ and $x-y$ always add to $x$. For $f,g$ in the L1 space, the integral exists almost everywhere and defines another element of the L1 space, with $\Vert f\ast g{\Vert }_1\le \Vert f{\Vert }_1\Vert g{\Vert }_1$ by Young's convolution inequality. Particular examples below have a value at every $x$.

To see what the integral counts, take the indicator function $q=1_{[0,1]}$. The product $q(y)q(x-y)$ equals one exactly when $y$ belongs to both intervals $[0,1]$ and $[x-1,x]$. Its integral is their overlap length, soAt $x=1/2$, the overlap is $[0,1/2]$ and the output is $1/2$; at $x=1$, the two intervals coincide and the output is one. The result is the shifted triangular function $\mathrm{tri}(x-1)$. As $x$ changes, $q(x-y)$ is a reflected and translated copy of $q(y)$: the moving overlap makes the entire graph visible without a difficult integration.

The same calculation gives the probability distribution of a sum of two independent random variables. If $X,Y$ are independent random variables with the continuous uniform distribution on $[0,1]$, each has probability density function $q$. Their sum has probability density function $q\ast q$ by convolution of probability densities. The probability density function at one is larger than near zero or two because there are more combinations of the two inputs giving that sum. Its total integral is one; its expected value is one and its variance is $1/6$. These follow equally from integrating the triangular function or from linearity of expectation and variance additivity for independent random variables.

Convolution also gives a useful averaging operation. For $\epsilon >0$, let $k_{\epsilon }(y)=1_{[-\epsilon ,\epsilon ]}(y)/(2\epsilon )$. Thenthe mean of $f$ in a neighborhood of $x$. A smaller $\epsilon$ examines a smaller neighborhood. For a continuous function $f$, this mean tends to $f(x)$ as $\epsilon \to 0$, an example of an approximate identity. Integrating a sharp input against a distributed convolution kernel can produce a smoother output; the triangular example turns two discontinuous inputs into a continuous output.

In signal processing, a linear time-invariant system combines shifted copies of its impulse response by the same rule. In discrete time, an input value at index $m$ contributes a scaled response $a_m{h}_{n-m}$ at index $n$, and discrete convolution sums these contributions. This is the superposition interpretation developed in Oppenheim, MIT Signals and Systems, Lecture 4, convolution sums and integrals. The convolution theorem then gives another description: transform both inputs with a Fourier transform and multiply their transforms. Combining shifts, combining independent quantities and multiplying frequency descriptions are three faces of the same operation.

The coordinate revealment of coordinate $i$ for a decision tree $T$ under input probability distribution $\mu$ isIt depends on the chosen decision tree and the probability distribution, not just on the Boolean function. Since no coordinate is queried twice on a graph path, indicator functions giveThe second equality uses linearity of expectation; it does not require independence of random variables or a product measure. The cited paper defines these inspection probabilities and their sum for product measures; the displayed indicator function argument extends the identity to any input probability distribution.^[ref]

For the three-bit majority decision tree under the discrete uniform distribution, $({\delta }_1,{\delta }_2,{\delta }_3)=(1,1,1/2)$, whose sum is $2.5$. Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same majority function, depth and expected query cost, but coordinate revealments $(1,1/2,1)$. The asymmetry belongs to the chosen query order. Parity gives $(1,1,1)$ for every exact decision tree without repeated queries. If repeated queries were charged, inspection probabilities would count distinct coordinates; total query count would instead require expected multiplicities.

If $U,V$ are independent random variables, each with the uniform distribution on $[0,a]$ for $a>0$, then $T=U-V$ has the symmetric triangular distributionThe convolution of probability densities gives $q(t)=a^{-2}\int 1_{[0,a]}(s)1_{[0,a]}(s+t)ds$. The overlap of these two intervals has length $a-|t|$ for $|t|<a$ and is empty otherwise, proving the formula. By linearity of expectation and the variance of a sum,For $0\le b\le a$, its upper-tail probability is $(a-b{)}^2/(2a^2)$.

A useful model for elapsed time measured from two independently truncated clock readings uses $a$ as the display resolution and $T$ as the endpoint-offset difference. Independence is essential: uniform marginal probability distributions alone do not imply this triangular distribution. For example $U=V$ gives $T=0$ with certainty. In general, with the same uniform marginals, $\mathrm{Var}(U-V)=a^2/6-2\mathrm{Cov}(U,V)$.

For $X$ with Poisson distribution of mean one, every factorial moment satisfies $\mathbb{E}[(X{)}_k]=1$. The polynomial identityexpresses powers in terms of falling factorials, where $S(n,k)$ are Stirling numbers of the second kind. Substituting $X$ and using linearity of expectation provesOn the other hand, the probability mass function gives $\mathbb{E}[X^n]=e^{-1}{\sum }_{j=0}^{\infty }{j}^n/j!$. This proves Dobiński's formula and explains why a count of set partitions is a moment of a Poisson distribution. For example, $\mathbb{E}[X^3]=\mathbb{E}[(X{)}_3+3(X{)}_2+X]=1+3+1=5=B_3$. At $n=0$, take $j^0=1$ also for $j=0$, obtaining $B_0=1$. For each fixed $n$, the ratio test proves convergence of the displayed infinite sum.

A simple random walk on a cycle graph of $n\ge 3$ vertices has expected value of its cover time equal to $n(n-1)/2$, from any starting vertex. Lift the walk to the integers using the same $\pm 1$ increments. Its contiguous visited interval covers all residues precisely when it reaches length $n$. Sum the expected time to expand a random-walk range, $1+2+\cdots +(n-1)$, using linearity of expectation; no independence of expansion times is needed.

The expected value of the number of observations in a category under a specified statistical model. For $n$ observations with common category probability $p_j$, linearity of expectation gives $E_j=n{p}_j$; the calculation does not itself require independence. In a contingency table, fitting independence gives $E_{ij}=n_{i+}{n}_{+j}/n$. These are model-based counts, which may be fractional, rather than an additional set of observed responses. Pearson's chi-squared test compares observed counts with their corresponding expected frequencies.

For a Galton-Watson process starting with one ancestor and finite offspring mean $\mu$, the expected value of the generation size is $\mathbb{E}[Z_n]={\mu }^n$. At $n=0$ it is one, including when $\mu =0$; zero offspring mean forces every later generation to be empty. With $m$ initial ancestors, the expected value is $m{\mu }^n$.

For $p_0=p_1=1/4$, $p_2=1/2$, the offspring mean is $5/4$. The exact calculations used in the generation probability mass function figure under Galton-Watson process give:

Nearly half the families are already empty at generation six, yet the expected value exceeds three. Since empty families contribute zero,whenever $q_n<1$. At generation six this conditional expectation is about $7.092969$. Conditioning on being nonempty now differs from conditioning on eventual survival: some presently nonempty families will still die out. The eventual branching extinction probability is $1/2$, even as the unconditional expected value grows without bound.

The expected value is useful for computing average population counts and, in the subcritical case, the expected value of the total progeny of a branching process. Its simple formula comes from one local calculation: linearity of expectation and the independent and identically distributed offspring counts giveThe tower property of conditional expectation gives the second equality; starting from $\mathbb{E}[Z_0]=1$ gives the formula. It describes an average over the generation probability distribution, not deterministic growth of an individual family. ^[ref]

For $n$ independent uniform points in a rectangle, condition on one point with normalized coordinates $(x,y)$. It is a maximal external point if all others avoid the upper-right rectangle of area $(1-x)(1-y)$, giving conditional probability $[1-(1-x)(1-y){]}^{n-1}$. Integrating gives $H_n/n$, where $H_n$ is a harmonic number. Linearity of expectation over the $n$ indicator random variables gives $\mathbb{E}{K}_n=H_n$. The same answer holds for independent continuous coordinate distributions, by transforming each coordinate with its distribution function.

In $n$ independent trials with category probabilities $p_1,\dots ,p_m$, let $K_n$ count the distinct categories observed. Write it as the sum of indicator random variables for the categories' appearances. Category $j$ is absent with probability $(1-p_j{)}^n$, so linearity of expectation gives the displayed formula. The appearance indicators need not be independent. For equally likely categories the expression becomes $m(1-(1-1/m{)}^n)$; uneven probabilities can substantially delay observation of rare categories.

An expected value is the probability-weighted arithmetic mean of a real-valued random variable. On a probability space $(\Omega ,\mathcal{F},\mathbb{P})$, its general definition is the Lebesgue integralwhere ${\mu }_X$ is the probability distribution of $X$. For an integrable random variable, this is a finite real number. With a probability mass function $p_X$, use ${\sum }_{x}x{p}_X(x)$; with a probability density function $f_X$, use ${\int }_{\mathbb{R}}x{f}_X(x)dx$. These are two ways of computing the same weighted average, rather than different definitions for different experiments.

For example, suppose $X$ takes the values $-1,2,8$ with probabilities $1/2,3/10,1/5$. ThenThe most likely outcome is $-1$, and $1.7$ is not a possible outcome at all. The expected value summarizes all outcomes and their weights; it need not predict the result of one trial. Geometrically, placing masses equal to the probability masses at the outcome positions gives a center of mass at $1.7$, since ${\sum }_x{p}_X(x)(x-1.7)=0$. This balance-point interpretation also explains the connection to a weighted arithmetic mean. ^[ref].

For the dimensionless random variable $Y$ with probability density function $f_Y(y)=2y$ on $[0,1]$, the expected value is $\mathbb{E}[Y]={\int }_0^{1}y(2y)dy=2/3$. Integrating the probability density function itself gives one; to compute the expected value, multiply by the outcome first. ^[ref].

Why is this useful? Linearity of expectation lets us compute an average total by adding average contributions, even for dependent random variables. And for independent and identically distributed integrable random variables, the strong law of large numbers says their sample mean approaches their common expected value almost surely. The theorem supplies the link to repeated observations; the weighted-average definition itself does not promise that any particular finite run will be close to the expected value.

There is a useful historical connection to valuing uncertain rewards. In his 1657 De ratiociniis in ludo aleae, Christiaan Huygens assigns the value $(a+b)/2$ to equally likely rewards $a,b$, and $(pa+qb)/(p+q)$ when they have $p,q$ equally likely chances. These are the finite weighted-average formulas for expected value. His opening discussion asks how to divide the stakes when a game stops before completion, connecting probability to a concrete question about an unfinished contest. ^[ref].