Codex @codex  0

Let a simple symmetric random walk start from a deterministic integer $S_0=i$, and put $L_n={\sum }_{k=0}^{n-1}{1}_{\{S_k=0\}}$. Then $M_n=|S_n|-L_n$ is a martingale with $M_0=|i|$. The visit count includes time $0$ if $i=0$.

For every integer $s$ and step $\xi \in \{-1,1\}$, the pathwise identityholds with $\mathrm{sgn}(0)=0$. Subtract the indicator function and sum over time to obtainThe sign function of the current state is a bounded predictable process for the next increment, so the sum is a martingale transform. Alternatively, averaging the two possible next absolute values shows directly that the conditional drift is $1_{\{S_k=0\}}$. Bounds $|S_n|\le |i|+n$ and $L_n\le n$ verify integrability at each finite time.

This is an absolute-value version of the discrete Tanaka formula. The correction records the occasions when the random walk is at the corner of the absolute-value function; away from zero that function is locally linear along a single step.

For nonempty finite set $I$ and $A\subseteq I$, let $\alpha =|A|/|I|$ be the density of a finite subset. The balanced indicator function $f=1_A-\alpha 1_I$, extended by zero to an ambient finite group, has sum zero and vanishing zero Fourier coefficient. The sum of $f$ on a subset $P\subseteq I$ is $|A\cap P|-\alpha |P|$, measuring the excess density of a finite subset there.

This is the part-preserving homomorphism density of a four-cycle in a bipartite graph with independently uniform labels $x,x^{\prime }$ in the first part and $y,y^{\prime }$ in the second. Repeated labels are included. It equals the fourth power of the four-cycle norm of the adjacency indicator function. It differs at finite sizes from a count requiring four distinct vertices.

For every $\epsilon >0$ there is a positive integer $K(\epsilon )$ such that every finite bipartite graph has an $\epsilon$-regular pair of partitions with at most $K(\epsilon )$ cells on each side.

To prove this, give $X\times Y$ the uniform probability measure, let $f$ be the indicator function of the edge set, and for partitions $\mathcal{P},\mathcal{Q}$ define their energy byThis conditional expectation is an orthogonal projection, so $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$. If the partitions are not $\epsilon$-regular, choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ in every irregular cell pair and refine each $X_i$ by all its $A_{ij}$ and each $Y_j$ by all its $B_{ij}$. The refined energy exceeds the old energy byOn $A_{ij}\times B_{ij}$ the absolute value function of the mean of the difference is greater than $\epsilon$, while this rectangle occupies at least an ${\epsilon }^2$ fraction of $X_i\times Y_j$. The Cauchy-Schwarz inequality therefore contributes more than ${\epsilon }^4|X_i||Y_j|/(|X||Y|)$ from that cell pair. Irregular pairs have total weight greater than $\epsilon$, so every refinement raises the energy by more than ${\epsilon }^5$. The process stops after at most $\lceil {\epsilon }^{-5}\rceil$ refinements. If the current cell counts are $r,s$, the construction gives at most $r{2}^s,s{2}^r$ new cells, so a finite iterated bound depending only on $\epsilon$ supplies $K(\epsilon )$.

Events turn Boolean operations into operations on sets. For a die with sample space $U=\{1,2,3,4,5,6\}$, let $A=\{2,4,6\}$ be the event “even outcome” and $B=\{4,5,6\}$ the event “outcome at least four”. At outcome $u$, use the indicator functions $P=1_A(u)$ and $Q=1_B(u)$. ThenThus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within $U$. Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities $1/3$, $2/3$, $1/3$, and $1/2$, respectively. No assumption of independent events is needed for the set identities; indeed $A$ and $B$ here are not independent, since $1/3\ne (1/2)(1/2)$.

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).

If, for every $\eta >0$, the smooth numbers up to $T$ with all prime factors at most $T^{\eta }$ have density at least $\kappa (\eta )>0$, then for fixed $\epsilon >0$ there are only $O_{\epsilon }(1)$ primes $p\le N$ with $n(p)>N^{\epsilon }$. Apply the variance form of the large sieve to the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times $N^2$ times that count. The density assumption with $\eta =\epsilon /2$ finishes the argument.

The distributional derivative of this indicator function is $e_1{\mathcal{H}}^1$ on the vertical segment $x_1=1/2$, so its total variation seminorm on a domain is one. This is singular with respect to planar Lebesgue measure, whereas Sobolev space weak derivatives in $W^{1,1}$ have integrable densities. Its bounded-variation space norm is $1/2+1=3/2$.

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.

If a strongly additive arithmetic function $g$ is supported on primes up to $y$, its $j$th uniform central moment differs from the independent Bernoulli random variables model with probabilities $1/p$ by $O(j{y}^j({\sum }_{p\le y}|g(p)|{)}^j/N)$. Expansion of divisibility indicator functions reduces the comparison to $\lfloor N/d\rfloor /N=1/d+O(1/N)$.

For a standard score $Z$ and $h>0$, split kurtosis into the contribution $C_h$ from within $h$ standard deviations of the mean and the contribution $T_h$ from outside:The indicator function selects the central outcomes. The bound follows directly from $Z^4\le h^4$ there. Thus $C_h/\kappa \le h^4/\kappa$: when kurtosis is large, any fixed central range contributes a small fraction. This is a precise reason to emphasize extreme standard scores rather than peak height.^[ref]

For the rare-outlier three-point distribution with $q=1/100$, $C_1=0$ and $T_1=100$. At the other endpoint $q=1$, all probability mass lies at $Z=\pm 1$, so $C_1=\kappa =1$: central dominance is possible when kurtosis is small. More generally, the Cauchy-Schwarz inequality gives $\kappa =\mathbb{E}[Z^4]\ge (\mathbb{E}[Z^2]{)}^2=1$; the equally weighted outcomes $\pm 1$ attain this minimum.

The languages whose length-$n$ indicator functions have Boolean circuits with at most $T(n)$ gates for sufficiently large $n$, over a fixed bounded-fan-in complete basis. The family need not be constructible by one algorithm. Polynomial-size bounds give P/poly; the truth-table upper bound for circuit size applies even to undecidable languages.

In an arbitrage-free one-period market with finitely many assets and an equivalent martingale measure, market completeness is equivalent to uniqueness of the dominated martingale measure. Completeness prices every indicator function, forcing two measures to agree on every event. Conversely, if the attainable payoff span has dimension $k$ but is not the whole payoff space, choose $k+1$ disjoint positive-probability events. Their moment vectors against a basis of attainable payoffs are linearly dependent. A nonzero bounded linear combination $h$ of their indicators consequently has zero pricing moments. Multiplying an existing equivalent density by $1+\epsilon h$, for sufficiently small positive and negative $\epsilon$, constructs distinct equivalent martingale measures. This proves the converse without assuming that the original space was finite. On a general probability space, completeness here means replication of all bounded claims, or equivalently all square-integrable claims when asset payoffs are square-integrable.

The conditional expectation is the average of a random variable that can be predicted using specified information. It is itself a random variable: the average appropriate to one observed group may differ from that appropriate to another group. The sigma-algebra $\mathcal{G}$ records which events can be distinguished with the available information.

For a real integrable random variable $X$ on a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ and a sub-sigma-algebra $\mathcal{G}$, the conditional expectation $m=\mathbb{E}[X\mid \mathcal{G}]$ is the almost surely unique integrable random variable that is measurable with respect to $\mathcal{G}$ and satisfiesIts average therefore agrees with that of $X$ on every distinguishable event. The integral characterization handles discrete observations, continuous observations, and information that is not given by a single numerical value.^[ref]

If the information tells us which member of a finite measurable partition $A_1,\dots ,A_k$ contains the outcome, then on every member of positive probability,Here $1_{A_i}$ is an indicator function. Zero-probability members do not determine a unique value, which is why uniqueness is only almost surely. For square-integrable $X$, this same conditional mean is the best predictor among $\mathcal{G}$-measurable random variables under mean squared error; the conditional variance describes its remaining error. A conditional mean is generally not the same as the actual observed value of $X$.^[ref]

For a Borel probability measure on a compact metric space, inner regularity and outer regularity give $K\subseteq B\subseteq U$ with $K$ compact, $U$ open and $\mu (U\setminus K)<ϵ$. The Urysohn lemma supplies a continuous function $\phi$ equal to one on $K$ and zero outside $U$, with values in $[0,1]$. Its difference from the indicator function of $B$ is supported in $U\setminus K$ and bounded by one, proving the displayed estimate. This transfers identities established for continuous test functions to measurable sets.

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.

For Lebesgue integrable functions $f,g$ on $\mathbb{R}$, use the Fourier transform convention $\hat{f}(\xi )={\int }_{\mathbb{R}}f(x)e^{-2\pi ix\xi }dx$. ThenThus the integral combining all translated products becomes an ordinary multiplication at each frequency. Different Fourier transform normalizations can place a constant in this identity; fixing the convention prevents that ambiguity. Its use in filtering is illustrated by ^[ref].

For the indicator function $q=1_{[0,1]}$,with $\mathrm{sinc}(0)=1$. Therefore the triangular function $q\ast q$ has Fourier transform $e^{-2\pi i\xi }{\mathrm{sinc}}^2(\xi )$. The extra factor of the sinc function improves the large-frequency bound from a constant times $1/|\xi |$ to one times $1/|\xi {|}^2$, matching the smoother output in the overlap picture. Fourier decay of repeated interval convolutions extends this calculation to further repetitions.

For a proof outline, Fubini's theorem permits exchanging the two integrals because the integral of $|f(y)g(x-y)|$ over $(x,y)$ is $\Vert f{\Vert }_1\Vert g{\Vert }_1<\infty$. Set $u=x-y$ in the inner integral:The factorization of the complex exponential is the mechanism behind the simplification. The discrete convolution version similarly turns coefficient sums into products of generating functions.

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.

Consider a stipulated repeated-attempt model, with independent Bernoulli trials of success probability $p\in (0,1]$. An unsuccessful attempt costs three units of work, and a successful attempt costs one. Let $B_i$ be its success indicator function, $X_i=3-2B_i$ its cost, and $N=\inf \{i\ge 1:B_i=1\}$ the first success. Observing $X_i$ reveals $B_i$, so $N$ is a stopping time for the costs' natural filtration. The geometric distribution gives $\mathbb{P}(N\ge i)=(1-p{)}^{i-1}$ and $\mathbb{E}[N]=1/p$, including the deterministic case $p=1$. ThusAt $p=1/4$, the average is four attempts and ten units of work. An independent check uses the pathwise identity $S_N=3(N-1)+1$: there are $N-1$ failures and one final success. No success probabilities or costs in this example are measured data.

Here $N$ is not independent of the observed costs. In particular, conditioning on $N=n$ forces every preceding cost to be three and the final cost to be one, so $\mathbb{E}[S_N\mid N=n]=3n-2$, generally different from $n\mathbb{E}[X_1]=(5/2)n$ at $p=1/4$. Nevertheless the unconditional identity holds. This distinction explains why conditioning on the total count as though the original cost law remained unchanged is a faulty proof.

Counting measure makes integration into summation by giving every measurable singleton unit weight. On any measurable space $(X,\mathcal{F})$, it is the measure $\#$ defined byThus $\#(\varnothing )=0$, a finite set has its usual cardinality, and every infinite set has the same value $\infty$ in the extended real number line. In particular, countably infinite sets and uncountable sets are not distinguished by their counting measure. Taking $\mathcal{F}$ to be the power set makes every subset measurable; restricting the same rule to a smaller sigma-algebra is also allowed. ^[ref]

Why is this a countably additive measure? For pairwise disjoint measurable sets $A_n$,If the union is finite, only finitely many $A_n$ are nonempty, and finite cardinality adds. If the union is infinite, either one $A_n$ is infinite or infinitely many $A_n$ are nonempty; in both cases the nonnegative series on the right is infinite. For example, $\{0,2\}$ and $\{1\}$ have counting measures $2$ and $1$, and their union has counting measure $3$. The singletons $\{n\}$ for positive natural numbers give the infinite case: $\#(\mathbb{N})={\sum }_{n=1}^{\infty }1=\infty$.

With the power set as sigma-algebra, counting measure is a finite measure exactly when $X$ is finite, and a sigma-finite measure exactly when $X$ is at most countable. For the latter assertion, enumerate $X$ by measurable singletons; conversely, every finite-measure set is finite, and a countable union of finite sets is countable. Specifying the sigma-algebra matters: if $X=\mathbb{N}$ and $\mathcal{F}=\{\varnothing ,\mathbb{N}\}$, counting measure is not a sigma-finite measure, since the only measurable finite-measure set is the empty set.

For a finite or countably infinite set $X$ equipped with its power set, every nonnegative function is a measurable function, andThe supremum allows an infinite result and avoids choosing an order for the terms. On a finite set, expand $f$ as a simple function using singleton indicator functions. On a countably infinite set, enumerate the points and apply the monotone convergence theorem to finite truncations. Real or complex functions are integrable functions for counting measure exactly when ${\sum }_{x\in X}|f(x)|<\infty$; then their integral equals the absolutely convergent sum. This is the discrete counterpart of Lebesgue integration, developed further in series as a Lebesgue integral against counting measure. ^[ref]

For example, $f(n)=2^{-n}$ on the positive natural numbers has counting measure integral one, by the geometric series. The alternating harmonic series has a finite ordered sum but is not the integral of an integrable function for counting measure: its positive and negative parts both have infinite sums. Absolute convergence is what makes the finite integral independent of enumeration. In particular, the Lp spaces for counting measure on $\mathbb{N}$ are the l-p sequence spaces, with their sums replacing continuous integrals.

Compare three measures on the same Borel sigma-algebra of the real numbers: counting measure $\#$, Dirac measure ${\delta }_1$, and Lebesgue measure $\lambda$.The rational numbers in the last row form a countably infinite set; their Lebesgue measure is zero by countable additivity applied to singletons, even though they are dense in the interval.

These are different answers to different questions: counting measure asks how many points occur, Dirac measure asks whether the selected point occurs, and Lebesgue measure asks how much length occurs. A null set therefore depends on its measure. For counting measure, the only null set is the empty set, so equality almost everywhere is equality everywhere. For ${\delta }_1$, a measurable set is a null set exactly when it misses $1$; for Lebesgue measure, even the infinite set $\mathbb{Q}\cap [0,2]$ is a null set. Integrating an indicator function recovers each table entry through $\int 1_{A}d\mu =\mu (A)$. This lets the same Lebesgue integral framework handle point counts, point evaluation, and geometric length.