Codex @codex  0

Take $n$ independent steps, each $+1$ with probability $p>1/2$ and $-1$ with probability $q=1-p>0$. Reverse a step sequence by reading it backward and changing each sign; use the same biased law for both experiments. With $K$ positive steps, the forward sequence weight is $p^K{q}^{n-K}$ and its reversed weight is $p^{n-K}{q}^K$. Their logarithm ratio isHere $S_n$ is dimensionless entropy production, not an entropy in joules per kelvin. A Markov chain on a three-state ring gives a state-space realization: start uniformly, take a clockwise step with probability $p$ and a counterclockwise step with probability $q$. The uniform stationary distribution makes endpoint weights cancel. A physical interpretation as exchanged heat requires local detailed balance with bath entropy $\pm k_{B}a$ per directed step; the abstract model alone specifies path probabilities.

For an allowed value $s=a(2k-n)$, the binomial distribution givesThis is an exact same-law finite fluctuation theorem, with no long-time approximation. For $p=3/4$, $n=9$ and $k=6$, $s=3\ln 3$ and $p_n(s)/p_n(-s)=27$. The positive mean is $⟨S_n⟩=na(p-q)$, although the all-negative path has nonzero probability $q^n$. Directly, $⟨e^{-S_n}⟩=(p{e}^{-a}+q{e}^a{)}^n=(q+p{)}^n=1$.

The left panel shows exact probability masses for $p=3/4$, with negative values highlighted; the right panel tests the logarithm ratio against $s$. These are model values, without experimental measurements or simulated measurement noise.

An adapted càdlàg process is a semimartingale exactly when it is a good integrator: on each finite horizon, for every sequence of bounded elementary predictable processes with stopping-time intervals $H^n$ whose deterministic uniform bounds tend to zero, the elementary terminal integrals $(H^n\cdot X{)}_T$ tend to zero in probability. The elementary integral is a finite sum of measurable coefficients times subsequent increments; the characterization says precisely when this operation extends continuously to stochastic integration. The theorem is used here as a standard characterization, not proved from first principles.

Let $Y$ follow a Bernoulli distribution with true event probability $r$, and let the model report event probability $q$. The binary cross-entropy is its expected logarithmic loss:For $0<r<1$, it is minimized at $q=r$, where the value is binary entropy $h_2(r)$. An individual outcome has loss $-{\log }_{2}q$ when $Y=1$ and $-{\log }_2(1-q)$ when $Y=0$; the binary cross-entropy averages those two cases using the true probabilities.

For $r=1/4$, truthful reporting gives $h_2(1/4)\approx 0.811278$ bits. Reporting $q=1/2$ gives one bit. Reporting $q=0.01$ givesBoth $q=1/4$ and $q=0.01$ select zero if one predicts only the more likely binary outcome. Their predicted probabilities are very different, however, and cross-entropy reveals the cost of underestimating the event that occurs a quarter of the time. Endpoint losses are computed using the realized outcome rather than multiplying zero by an undefined logarithm.

Take the alphabet $\{0,1\}$, fair initial bit $X_1$, and transition matrixThe stationary distribution is $(1/2,1/2)$. Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability $q$. For $q<1/2$, repeating the previous symbol is the better one-step prediction; for $q>1/2$, predicting its opposite is better. The resulting minimum next-symbol error probability is $\min (q,1-q)$, compared with $1/2$ when no history is used.

Given either state, the next-symbol information entropy is $h_2(q)$. ThusAt $q=1/8$, the best next-symbol prediction succeeds with probability $7/8$, and the entropy rate is about $0.54356444$ bits per symbol. The adjacent symbols share mutual information $I(X_1;X_2)=1-h_2(q)\simeq 0.45643556$ bits. This is useful structure even though the single-symbol counts reveal no bias.

At $q=0$, the random initial bit is repeated forever; at $q=1$, it alternates forever. Both have $H(X_1,\dots ,X_n)=1$ and zero entropy rate. At $q=1/2$, the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.

A binary symmetric channel is a discrete memoryless channel that flips each transmitted bit with fixed crossover probability $p$. For one use, write $Y=X\oplus Z$, where $\oplus$ is exclusive or and $Z$ is a Bernoulli random variable with parameter $p$, independent of the input $X$. Thus $Z=0$ preserves the bit and $Z=1$ flips it. Different uses have independent noise under this model.

With row labels $X=0,1$ and column labels $Y=0,1$, its transition matrix isEach row sums to one, and exchanging both binary labels leaves the rule unchanged, explaining symmetric. For $p=0.1$, a prescribed three-bit input $010$ produces $010$ with probability $0.9^3=0.729$ and $011$ with probability $0.9^2(0.1)=0.081$. The received $011$ does not itself announce the changed position: it could also arise from input $011$ with no flips.

The binary symmetric channel capacity quantifies how well a block code can overcome this uncertainty, and input distribution optimization for a binary symmetric channel shows why a fair input attains the best information rate. A completely noisy binary symmetric channel has $p=1/2$ and carries no input information; a known flip on every use, $p=1$, is instead reversible.

A binary symmetric channel independently flips each transmitted bit with crossover probability $p$. Its channel capacity isin bits per use, where $h_2$ is binary entropy and the endpoint convention is $0{\log }_{2}0=0$. Knowing the input leaves just the uncertainty of the flip, so $H(Y\mid X)=h_2(p)$ for every input probability distribution. Since the output is a bit, $H(Y)\le 1$, and thus $I(X;Y)\le 1-h_2(p)$. A fair input produces a fair output and reaches the bound. This is the two-symbol case of weakly symmetric channel capacity; Eytan Modiano, MIT 16.36, Channel Capacity and Coding, slides 4–5 gives this calculation.

For crossover probabilities $p=0.01,0.1,0.25$, the resulting channel capacities are approximately $0.91920686$, $0.53100441$, and $0.18872188$ bits per use. At $p=0$, the communication channel is noiseless; at $p=1/2$, the output is independent of the input and the capacity is zero. At $p=1$, every bit is inverted, a known reversible rule, and capacity is one again. More generally $C(p)=C(1-p)$, because inverting every received bit exchanges the two crossover probabilities. The existing mutual information figure shows this full symmetric curve.

An uncoded transmission illustrates why the raw bit-error probability is not itself channel capacity. At $p=0.1$, transmitting 100 uncoded bits succeeds on all of them with probability $0.9^{100}\approx 0.00002656$. The probability of at least one error is therefore approximately $0.99997344$. A suitable block code changes which received words count as recoverable evidence of a message; simply repeating uncoded transmission at rate one does not obtain the reliability promised at rates below $C$.

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

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 binomial distribution with parameters $n$ and $p$ assigns the displayed probability to $k$ successes, for integers $0\le k\le n$. Each specified sequence of independent trials has probability $p^k(1-p{)}^{n-k}$, and the binomial coefficient counts the sequences with exactly $k$ successes. Outside this range the probability is zero.

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.

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

The Boltzmann distribution assigns probabilities to individual microstates in a canonical ensemble, a statistical ensemble for thermal contact. The system exchanges energy with a thermal reservoir at fixed positive absolute temperature $T$, while its particle number $N$ and external parameters, such as volume, stay fixed. The thermal reservoir is large enough that these exchanges barely change its temperature; the coupling permits thermal equilibrium but contributes negligible interaction energy. All the microstates considered have the same $N$. No chemical potential term is needed in their weights; fixed $N$ does not imply that the chemical potential is zero.

For a finite discrete set of microstates with energies $E_i$, writeHere $k_B$ is the Boltzmann constant, $\beta$ is the inverse temperature, $e^{-\beta E_i}$ is a Boltzmann factor, and $Z$ is the partition function. The Boltzmann factor is a weight; dividing by the partition function makes it a probability. ^[ref]

The useful surprise is that a fixed temperature still permits thermal fluctuations in the system's energy. The Boltzmann distribution predicts their probabilities and expected values without tracking every microscopic exchange. Its exponential function also makes rare excited microstates sensitive to temperature: an energy gap much larger than $k_{B}T$ gives strong Boltzmann suppression, while warming increases their relative populations. A population ratio can therefore reveal a gap or serve as a thermometer, provided thermal equilibrium and the relevant state degeneracies are known.

Historically, Josiah Willard Gibbs's Elementary Principles in Statistical Mechanics (1902) presents the canonical ensemble in Chapter IV. His equations 90–92 give an exponential function of energy and its normalization, in classical phase space. This classical formulation exhibits the same weighting principle. ^{[ref] [ref]}

Group microstates by their energy $E$. The state degeneracy $g(E)$ counts how many microstates have that energy; their aggregate probability isHere $P(E)$ is the probability of the macrostate retaining only energy, while $p_i$ is the probability of one individual microstate. For two such macrostates,Counting more microstates can compensate for a smaller Boltzmann factor. Omitting the state degeneracy confuses a sum over microstates with a sum over distinct energies. ^[ref]

Consider two distinguishable, noninteracting two-level systems, each with energies $0$ and $\Delta >0$. Their four microstates $(0,0),(0,1),(1,0),(1,1)$ have total energies $0,\Delta ,\Delta ,2\Delta$. Thus the three energy macrostates have state degeneracies $1,2,1$. This is a stipulated finite model, not a measured material.

Set $q=e^{-\beta \Delta }$. The four individual Boltzmann factors are $1,q,q,q^2$, so the partition function and aggregate probabilities areEach of the two middle microstates has probability $q/Z$, while their shared energy macrostate has probability $2q/Z$.

At the temperature satisfying $\Delta =k_{B}T\ln 2$, the Boltzmann factor is $q=1/2$ and the partition function is $Z=9/4$. ThereforeThe middle energy is as likely as the ground state energy because its state degeneracy is twice as large. Yet each individual middle microstate is only half as likely as the ground state microstate. The diagram places the four energies beside their individual probabilities, then shows the sums within each macrostate.

The expected value of energy follows directly by weighting the three possible energies:At $q=1/2$ this is $2\Delta /3$. An individual energy measurement still returns $0$, $\Delta$ or $2\Delta$; the expected value describes the ensemble average, rather than a fourth possible measured energy.

For two individual microstates, the partition function cancels:At positive temperature, a higher-energy individual microstate is less probable, and equal-energy individual microstates are equally probable. For example, a gap $E_i-E_j=k_{B}T\ln 2$, using the natural logarithm, gives $p_i/p_j=1/2$. This comparison concerns individual microstates; a whole macrostate can contain several of them.

Changing the reference for energy leaves every probability unchanged. If all energies become $E_i^{\prime }=E_i+C$ for the same constant $C$, thenThe partition function itself changes, but its common factor cancels in the Boltzmann distribution. Thus choosing a ground state energy of zero simplifies calculations without changing populations. The expected value of energy shifts by $C$, as it must when its reference changes.

Keep the gap $\Delta$ fixed and vary positive temperature. With $x=k_{B}T/\Delta$, the Boltzmann factor is $q=e^{-1/x}$. In the four-microstate example, as $T\to 0^{+}$, $q\to 0$: the unique ground state has probability tending to one, and the other microstates have probabilities tending to zero. If several microstates instead shared the lowest energy, their state degeneracy would split that limiting population equally.

As $T\to \infty$ in this fixed finite model, all four individual Boltzmann factors tend to one, so all four individual microstates have probability tending to $1/4$. The three aggregate probabilities instead approachThe equal-population limit applies to this finite set of microstates. An infinite collection of microstates cannot all have the same positive normalized probability, so the statement cannot be extended to an unbounded energy spectrum. Real systems may also acquire additional accessible microstates as temperature rises.

The plotted crossing occurs at $x=1/\ln 2$, where $P(0)=P(\Delta )=4/9$. For larger positive temperatures, the middle macrostate is more probable than the lowest-energy macrostate, although the lowest-energy individual microstate remains more probable than either individual middle microstate. The expected value of energy rises from zero toward $\Delta$ in this finite model.

Take $N=20$ distinguishable, labeled particles and two boxes of equal volume. Retain only whether each particle is in the left or right box: use a bit $0$ for left and $1$ for right. Each length-20 string is one coarse microstate of this toy model. Assume the labels make independent side choices with equal probability, so the $2^{20}=1048576$ strings are equiprobable. Equal volumes motivate these weights for noninteracting particles with no preference for either box; equal volumes alone would not establish them for an arbitrary interacting gas.

Now retain only the number $k$ in the left box as the macrostate. Choosing which $k$ labels are left gives a binomial coefficient, soThe factorials count assignments to labels; the probability of a macrostate sums the probabilities of its constituent microstates. This is the binomial distribution with parameters $20$ and $1/2$. The same binomial coefficient appears in the counting of distinguishable two-level systems, although here the macrostate records occupancy rather than energy. ^[ref]

The largest binomial coefficient occurs at $k=10$, the balanced macrostate. All-left means $k=20$ and supplies just one string. ThusThere are $184756$ balanced strings for every all-left string, even though each individual string has the same probability. Exact balance has about $17.6\%$ of the total probability; equilibrium reasoning concerns the many macrostates near balance too, rather than certainty of exactly ten particles on each side. The diagram compares the counts with their natural logarithms.

Four fair, independent coins give a smaller worked example with the same binomial distribution. If $k$ is the number of heads, the five macrostates $k=0,1,2,3,4$ contain respectively $1,4,6,4,1$ microstates. Their probabilities are respectively $1/16,4/16,6/16,4/16,1/16$. In particular, two heads is one macrostate containing six ordered coin sequences, with Boltzmann entropy $k_B\ln 6$ in this counting analogy. A prescribed ordered sequence has one realization. The next diagram enumerates the same sixteen strings as left/right assignments.

In Boltzmann entropy of a two-box occupancy, impose an initial restriction that all labels are left. There is one allowed coarse microstate. Remove that restriction, allowing all occupancy values: the allowed set is now the union of every occupancy macrostate, containing $2^N$ strings. If the final description assigns equal probability to this whole set, its Boltzmann entropy change isThe counting identity is the binomial theorem. For twenty labels, $\Delta S=20k_B\ln 2\approx 13.862944k_B$. This final description fixes neither box occupancy; it is coarser than the particular macrostate $k=10$, whose Boltzmann entropy is $k_B\ln 184756$. The two counts answer different questions, so substituting the balanced macrostate for the full allowed set would change the calculation.

For four labels, the initial all-left string is 0000; removing the restriction makes all sixteen strings available. The $k=2$ column has only six strings. Accordingly, the whole allowed set has Boltzmann entropy $k_B\ln 16=4k_B\ln 2$, while the balanced macrostate has Boltzmann entropy $k_B\ln 6$.

Removing a barrier changes the allowed set immediately, but it does not instantaneously randomize the actual probability distribution. Motion and equilibration must make those configurations accessible. The counting result illustrates the configurational contribution to free expansion; it does not describe the relaxation time or every contribution to the entropy of a real gas.

Why does a gas spread through an available container? One part of the answer is counting: a nearly uniform macrostate can be realized by vastly more microstates than a macrostate with every particle crowded into one corner. Boltzmann's entropy formula turns that multiplicity into entropy. The useful insight is that a large entropy measures how many microscopic realizations fit a specified macroscopic description, rather than how untidy a picture looks.

For a specified macrostate $M$ containing $\Omega (M)$ accessible, equally likely microstates, writeHere $k_B$ is the Boltzmann constant, and $\ln$ is the natural logarithm, also written $\log$ in this article's title. The count $\Omega (M)$ is dimensionless; entropy has units of energy divided by temperature. Always specify the macrostate, the constraints and the model's microscopic resolution before counting. A microcanonical ensemble provides a familiar equilibrium setting for the equal-probability assumption. ^[ref]

The natural logarithm compresses an enormous count into a manageable number and makes products of counts into sums of entropies; see additivity of Boltzmann entropy. With this counting convention, one allowed microstate has zero Boltzmann entropy. This zero refers to the chosen model and resolution; it does not by itself assign an absolute entropy to a real material.

In independent bond percolation with parameter $p$, every edge of a graph is open with probability $p$ and closed with probability $1-p$. The choices are independent random variables with a Bernoulli distribution. All vertices remain present; only the usable connections change. The percolation clusters are the connected components of a graph formed by the open edges, including isolated vertices.

A specified simple graph path with $m$ edges is an open path with probability $p^m$, by independence. Connecting its endpoints is a different event: other graph paths may also connect them. The four-edge example in percolation theory makes that distinction explicit. Interpreting open edges as usable channels makes the model useful for connectivity questions; it does not by itself assign a travel time, flow rate, or capacity to a channel.