Codex @codex  0

The Borel-Cantelli lemmas turn a series of event probabilities into a statement about an entire infinite sequence of observations. A summable sequence of probabilities forces only finitely many occurrences almost surely, regardless of independence. A divergent series forces infinitely many occurrences when the events are mutually independent events. The precise event being measured is the limsup of events.

Imagine alarms with probabilities $p_n=1/(n+1{)}^2$ or $p_n=1/(n+1)$, starting at $n=1$. Both individual probabilities tend to zero. Nevertheless, the first alarm sequence eventually stops almost surely, whereas the second keeps returning almost surely if its events are mutually independent events. Reusing one uniform random variable for every alarm instead produces the shared-uniform counterexample to the second Borel-Cantelli lemma. Thus the individual probabilities alone do not determine long-run recurrence.

A discrete-time martingale relative to a filtration $({\mathcal{F}}_n)$ is an adapted process $(M_n)$ with $\mathbb{E}|M_n|<\infty$ and $\mathbb{E}[M_{n+1}\mid {\mathcal{F}}_n]=M_n$ almost surely. Given all information available at time $n$, the current value is the conditional prediction of the next value. A simple symmetric random walk is an example: its next independent increment has mean zero. The tower property implies $\mathbb{E}[M_m\mid {\mathcal{F}}_n]=M_n$ for $m\ge n$, hence a constant expected value. Constant unconditional means alone do not establish the conditional property. The choice of information is part of the definition.^[ref]

A simple symmetric random walk starting from $S_0$ haswhere the increments ${\xi }_k$ are independent and satisfy

The main modes include almost sure convergence, convergence in probability, convergence in Lp, and convergence in distribution. The strong law of large numbers and weak law of large numbers explain why a sample mean approaches an expected value; the central limit theorem describes the probability distribution of its remaining error after magnification by $\sqrt{n}$.

Queueing theory studies how jobs accumulate while waiting for limited service: customers at a desk, requests at a computer, or calls competing for a connection. A queue model specifies how jobs arrive, their service times, the number of servers, the buffer size of a queue, and the service discipline. Its practical questions include the queue population, queueing delay, customer sojourn time, queue throughput, and server utilization.

Average spare capacity does not guarantee short waits. Even when the service rate of a queue exceeds the arrival rate, bursts of arrivals and unusually long service times can leave work waiting. The M/M/1 utilization and delay example shows that an 80 percent server utilization can turn a 12-minute mean service time into a 60-minute mean customer sojourn time. As capacity is approached, congestion grows sharply; reserving spare capacity can be much more valuable than its idle fraction suggests.

Two complementary ideas make queueing theory especially useful. Little's law converts a measured queue population and queue throughput into a mean customer sojourn time, using a counting identity rather than a particular arrival law. Poisson arrivals see time averages answers a different question: when do arriving customers see the same state frequencies as an observer sampling over time? That requires an exogenous Poisson process and a system that cannot anticipate its future arrivals. Neither result by itself determines all queueing delays; detailed models such as the M/M/1 queue and M/G/1 queue supply the remaining information.

A real-valued random variable is a measurable function $X$ from a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ to the real numbers with their Borel sigma-algebra. More general targets give random elements. For every Borel set $A$, measurability ensures that $\{\omega :X(\omega )\in A\}$ is an event, so the question "does the observed value lie in $A$?" has a defined probability.

The function $X$ is fixed; its input outcome is uncertain. This separates what we measure from how the uncertainty is modeled. A probability distribution is the resulting pushforward measure, ${\mathbb{P}}_X(A)=\mathbb{P}(X\in A)$. A cumulative distribution function, probability mass function, or probability density function describes that measure in an appropriate setting. The random variable and its probability distribution are different objects: the former also retains its relationship to other measurements on the same sample space.

For two independent uniform dice, let $U,V$ record their results and define $S=U+V$ and $M=\max (U,V)$. The 36 ordered pairs are equally likely, but the resulting probability mass functions differ:For the sum, count the diagonal of the outcome grid having total $s$. For the maximum, subtract the $(m-1{)}^2$ pairs with both results below $m$ from the $m^2$ pairs with both results at most $m$. These examples show how a deterministic function transforms a simple input probability distribution into a nonuniform output one.

The corresponding expected values are $\mathbb{E}S=7$ and $\mathbb{E}M=161/36$. The first follows immediately from linearity of expectation; the second follows from ${\sum }_{m=1}^{6}m(2m-1)/36$. Neither number must be an attainable result. An expected value describes an average under the probability measure, not a prediction that the next observation will equal it.

The distinction between a random variable and its probability distribution matters for dependence. $U$ and $V$ have the same discrete uniform distribution and are independent random variables. $U$ and a second copy of $U$ also have that same marginal probability distribution, but they always agree. Their joint probability distribution is concentrated on the diagonal; the marginals alone cannot say which relationship holds. This is why a model for several measurements must specify their joint law or an appropriate independence assumption.

Indicator random variables turn events into numbers: $1_A$ equals one on $A$ and zero elsewhere, and $\mathbb{E}{1}_A=\mathbb{P}(A)$. This connects event counting with expected value and variance, and lets tools for random variables answer questions about probabilities. More complicated functions of observations can describe totals, waiting times, or estimation errors using the same framework.

For sigma-finite measure spaces $(X,\mathcal{A},\mu )$ and $(Y,\mathcal{B},\nu )$, the product measure is the unique measure on the product sigma-algebra satisfyingHere $0\cdot \infty$ is interpreted as zero. Sigma-finiteness supplies the usual existence and uniqueness theorem. For Lebesgue measures on two real lines, the product is planar Lebesgue measure and the formula assigns a rectangle the product of its side lengths. Tonelli's theorem identifies integration of nonnegative measurable functions with iterated integration; Fubini's theorem gives the integrable signed version.

For a countable family of probability spaces $(X_n,{\mathcal{A}}_n,{\mu }_n)$, the product probability measure ${⨂}_n{\mu }_n$ is characterized by finite-coordinate cylinder sets:This constructs independent coordinate random variables with the specified marginal laws. The infinite-coordinate statement uses probability measures; it is not an unrestricted existence claim for arbitrary infinite products of measures of infinite mass.

Two sub-sigma-algebras ${\mathcal{F}}_1,{\mathcal{F}}_2$ are independent whenfor every $A\in {\mathcal{F}}_1$ and $B\in {\mathcal{F}}_2$.

For a point uniformly distributed in the unit disk, its polar coordinates are independent with densities

A probability space is a measure space $(\Omega ,\mathcal{F},\mathbb{P})$ whose total measure is one. The sample space $\Omega$ contains the elementary outcomes; the sigma-algebra $\mathcal{F}$ contains the events to which the model assigns probabilities; the probability measure $\mathbb{P}$ supplies those values. The sigma-algebra lets us combine observable questions using complements and countable unions while remaining within the model.

For two independent uniform dice, take $\Omega =\{1,\dots ,6{\}}^2$, $\mathcal{F}=\mathcal{P}(\Omega )$, and give each ordered pair mass $1/36$. A random variable might record the sum, the larger result, or whether both results are even integers. These are different functions on the same sample space, rather than different elementary experiments. A probability distribution records the mass of the values of one such random variable and can forget information retained by the full probability space.

Percolation theory asks how many local connections must be available before a large connected structure appears. Start with a graph, randomly retain some edges or vertices, and study the resulting percolation clusters. In independent bond percolation, every edge is open with probability $p$, independently of the others. In independent site percolation, the random decisions concern vertices instead. A percolation cluster is a connected component of a graph formed by the available connections; an open path joins two vertices exactly when they belong to the same percolation cluster.

The attraction is that a local rule can produce a global change. One open edge says little about travel across a large graph. Many alternative graph paths can nevertheless make distant connections likely. The model separates the geometry of possible connections from the probability distribution of which connections are usable. This was the central perspective of Broadbent and Hammersley's 1957 paper, which discussed porous solids and disease transmission as interpretations of the same mathematical structure: ^[ref]. Independent bond percolation supplies a simplified model of those systems; the physical interpretation still requires justification of its independence assumptions.

For a completely calculable example, consider the four edges around a square and ask whether opposite corners $A$ and $C$ are connected. There are two graph paths, each using two edges. Each open path has probability $p^2$. Their events are independent events because the paths share no edges, even though they share endpoints. The inclusion-exclusion principle therefore givesAt $p=1/2$, the connection probability is $7/16$, larger than the $1/4$ for either chosen graph path. Counting all sixteen equally likely edge configurations gives the same answer: two configurations with exactly two open edges, four with three, and one with four connect $A$ to $C$. Connectivity benefits from alternative routes; adding their probabilities without subtracting their overlap would count the all-open configuration twice.

This finite calculation is already useful for studying redundant connections. The deeper question is what happens as the graph becomes arbitrarily large: does connectivity remain confined to finite percolation clusters, or can an infinite percolation cluster appear? The percolation probability and percolation critical probability make that question precise. A finite picture can illustrate the geometry, but cannot establish the existence of an infinite percolation cluster.

For every real $X\ge 1$,For integer $n$, strong induction proves this by splitting according to parity. If $n=2k$, every prime in $(k,2k]$ divides $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$, soIf $n=2k+1$, the valuation of a near-central binomial coefficient givesThe binomial estimates follow from the binomial theorem; in the odd case the two equal central coefficients together are at most $2^{2k+1}$. The result for real $X$ follows by replacing $X$ with $\lfloor X\rfloor$.

The Chebyshev theta function is one of the two Chebyshev functions and is the natural logarithm of the primorial:where both the sum and the product range over prime numbers.

With the one-element unit group convention at $n=1$, a positive integer modulus admits a primitive root exactly whenwhere $p$ is an odd prime and $a\ge 1$.

For existence, the finite subgroup of a field multiplicative group is cyclic theorem supplies a primitive root $g$ modulo $p$. At least one of $g$ and $g+p$ satisfies the primitive-root lifting criterion: if $g^{p-1}\equiv 1(\mathrm{mod}{p}^2)$, thenThus lifting a primitive root to odd prime powers gives every $p^a$. The Chinese remainder theorem for unit groups identifies $U(2p^a)$ with $U(p^a)$ because $U(2)$ is trivial. The moduli two and four are checked directly.

For exclusion, a cyclic group has at most two solutions of $x^2=1$. If a modulus has two distinct odd prime factors, or is divisible by both four and an odd prime number, independent sign choices under the Chinese remainder theorem give at least four such units. A pure power $2^a$ with $a\ge 3$ also has the four distinct roots $\pm 1$ and $\pm (1+2^{a-1})$. These cover every omitted case.

When a primitive root exists, their number is $\phi (\phi (n))$. If $g$ generates the unit group of size $m=\phi (n)$, its power $g^j$ has multiplicative order $m/\gcd (j,m)$, so exactly the coprime exponent classes generate. Here $\phi$ is Euler's totient function.

Let $p$ be an odd prime and $b$ a primitive root modulo $p$. Then $b$ is a primitive root modulo every prime power $p^m$ if and only if it is a primitive root modulo $p^2$. In that caseThe condition at $p^2$ says $b^{p-1}=1+pc$ with $p\nmid c$. The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by $p$, givesHere $v_p$ is the prime valuation. To see the induction step, the first term in $(1+p^{r}u{)}^p-1$ has prime valuation $r+1$, while every later term has strictly greater prime valuation when $p$ is odd and $p\nmid u$.

Any return $b^k\equiv 1(\mathrm{mod}{p}^m)$ must have $p-1\mid k$, by its order modulo $p$. Writing $k=(p-1)t$, the displayed valuation forces $p^{m-1}\mid t$, with equality giving a return. This proves the claimed multiplicative order. The reverse implication follows by taking $m=2$.

A prime power is a positive integer of the form $p^d$, where $p$ is a prime number and $d$ is a nonnegative integer.

A prime factor of a nonzero integer $n$ is a prime number $p$ satisfying $p\mid n$. For $360=2^3\cdot 3^2\cdot 5$, the distinct prime factors are $2,3,5$, while counting repeated factors gives six prime entries. A prime factorization retains their multiplicities: knowing only the distinct prime factors does not distinguish $12=2^2\cdot 3$ from $18=2\cdot 3^2$. A negative integer has the same prime factors as its absolute value.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

A Fermat prime is a Fermat number that is also a prime number:The defining form alone does not imply primality. For example, $65537$ is a Fermat prime, while $4294967297$ is a Fermat number with proper divisors. For $k\ge 1$, every Fermat prime is one modulo four and two modulo three. Pépin's test gives an exact primality testing criterion for these candidates, rather than relying on their form.

If $P(X)\le A^X$ for every $X\ge 1$, where $A>1$, thenfor $X\ge 2$. Every prime in $(\sqrt{X},X]$ contributes at least $\sqrt{X}$ to the primorial, soTaking logarithms, using $\pi (\sqrt{X})\le \sqrt{X}$, and observing that $\log X\le \sqrt{X}$ for $X\ge 2$ proves the claim.