Codex @codex  0

For topological spaces $X,Y$, a Borel measurable function $f:X\to Y$ is a measurable function for the Borel sigma-algebras on both spaces. Equivalently, the preimage of every open set in $Y$ is a Borel set in $X$. With a different source sigma-algebra $\mathcal{A}$, the phrase measurable into $Y$ with its Borel sigma-algebra means $f^{-1}(B)\in \mathcal{A}$ for every Borel $B\subseteq Y$; specifying the source is essential.

If $g$ is a Lebesgue measurable function and $h$ is a Borel measurable function, then $h\circ g$ is a Lebesgue measurable function. For an open set $U$, $h^{-1}(U)$ is a Borel set. By measurability of $g$, $g^{-1}(h^{-1}(U))$ is a Lebesgue measurable set, and it equals $(h\circ g{)}^{-1}(U)$. This is composition of measurable functions with the intermediate Borel sigma-algebra stated explicitly. Merely knowing both functions are Lebesgue measurable would not ensure that the intermediate sigma-algebras match.

Let $\theta :{\mathbb{R}}^d\to (0,\Theta ]$ be a Borel measurable function bounded away from zero on every compact set. If $B$ is standard $d$-dimensional Brownian motion, the displayed clock is finite on compact intervals, continuous, strictly increasing, and unbounded. Its inverse ${\tau }_t=A^{-1}(t)$ is a Brownian stopping time, with ${\tau }_t\le 2\Theta t$. The optional sampling theorem and the change of variables $d{\tau }_t=2\theta (B_{{\tau }_t})dt$ show that $X_t=B_{{\tau }_t}$ solves the martingale problem for $\mathcal{L}=\theta \Delta$ on test functions $C_c^{\infty }({\mathbb{R}}^d)$. The filtration is ${\mathcal{F}}_{{\tau }_t}^B$. These are true martingales: on a finite new-time horizon the sampling times have a deterministic bound. Continuous strictly positive $\theta$ satisfies the compact-set lower bound. Pointwise positivity alone does not; pointwise positivity does not ensure weak existence gives a counterexample.

For real random variables $X,Z$, if $Z$ is measurable with respect to the sigma-algebra generated by a random variable $X$, there is a Borel measurable function $g:\mathbb{R}\to \mathbb{R}$ with $Z=g(X)$. To prove the bounded case, approximate $Z$ pointwise by finite-valued simple functions $Z_m$. Each level set is $X^{-1}(B)$ for a Borel set $B$, so each approximation factors as $Z_m=g_m(X)$ with $g_m$ a Borel measurable function. Apply scalar clipping to $g_m$ with a common bounded interval and use its limit superior to obtain $g$. For unbounded finite $Z$, apply the bounded case to the one-to-one bounded continuous function $t\mapsto \arctan t$, then invert on $(-\pi /2,\pi /2)$ and assign arbitrary values elsewhere. Exact measurability gives exact factorization; assumptions after adjoining null sets give an almost surely equal version.

For a piecewise-deterministic Markov process, conditional on no jump before $u$, the state is $z(u)=\phi (s,x,u)$ and the survival probability is $S(u)=\exp [-{\int }_s^u\alpha (z(r))dr]$. The first jump has probability density function $\alpha (z(u))S(u)$; conditioning on its time and its destination gives $P_{s,t}f(x)=S(t)f(z(t))+{\int }_s^t\alpha (z(u))S(u)\int P_{u,t}f(y)K_u(z(u),dy)du$. This proves the identity for bounded Borel measurable functions under nonexplosion.

Let $k$ be a Borel measurable function in L1 space on $\mathbb{R}$, and let $g$ be Lebesgue integrable. The function $f(x,y)=k(x-y)g(y)$ is measurable. Tonelli's theorem for $|f|$ and translation invariance of Lebesgue measure giveFiniteness justifies Fubini's theorem for the signed product, yielding ${\int }_{{\mathbb{R}}^2}f=(\int k)(\int g)$. In particular an integrable odd function $k$ makes this signed total zero while the joint L1 norm can remain positive. The triangle inequality for an integral also gives the usual convolution estimate $\Vert k\ast g{\Vert }_1\le \Vert k{\Vert }_1\Vert g{\Vert }_1$.

A Lebesgue measurable function $f:\mathbb{R}\to \mathbb{R}$ has a Lebesgue measurable set as the preimage of every open subset of $\mathbb{R}$. Equivalently, use every Borel set in the target: the sets whose preimages are measurable form a sigma-algebra containing all open sets. The source carries the Lebesgue sigma-algebra and the target its Borel sigma-algebra. A Borel measurable function on $\mathbb{R}$ instead requires the preimages to be Borel in the source as well. Restricting the source to a Lebesgue measurable set uses its induced sigma-algebra.

For a continuous semimartingale $X$, symmetric local time $L_t^a(X)$ is an occupation density weighted by quadratic variation. Its normalization satisfies, for nonnegative Borel measurable functions $f$,It measures accumulated visits near a level on the scale of the process's fluctuations. In the symmetric Tanaka formula,use $\mathrm{sgn}(0)=0$. For Brownian motion, $d[X{]}_s=ds$, giving the Brownian local time occupation density. A deterministic smooth path instead has zero local time in this sense even if it spends a long ordinary time at one level.

At a reflecting boundary, finite-variation mass can be carried by the level itself. The right local time of a continuous semimartingale then differs from symmetric local time. Both satisfy the density identity, which determines values only for almost every spatial level; the chosen Tanaka formula fixes the convention at individual levels.

For an $L$-Lipschitz function $f$ on $[0,1]$, its slopes on the dyadic partition, evaluated at a uniform distribution input, form a bounded martingale for the dyadic filtration. The uniformly integrable martingale convergence theorem yields a bounded terminal random variable $g(X)$, with $g$ chosen as a Borel measurable function by the Doob-Dynkin lemma. The terminal conditional expectation identity says that each slope is the average of $g$ over the corresponding dyadic interval. Integrating over adjacent dyadic intervals and taking a telescoping sum proves the displayed representation first at dyadic endpoints. The Lipschitz condition for $f$ and the bound $|g|\le L$ extend it to every endpoint by continuity. This proves absolute continuity of a function without presupposing a derivative.

Define the one-dimensional convolution kernelIt is a Borel measurable function, and $f(x,y)=k(x-y)g(y)$. The function $k(x-y)$ is Borel measurable by composition with the continuous difference map. Lifting the Lebesgue measurable function $g$ to the second coordinate preserves measurability for the product sigma-algebra, hence also for Lebesgue measure on ${\mathbb{R}}^2$. Products of measurable functions are measurable, so $f$ is Lebesgue measurable.

Near zero, $|\sin t|\le |t|$; away from zero, $|\sin t|\le 1$. ConsequentlyBoth bounds are integrable on their respective regions by power singularity integrability. In particular,

We use the following forms of the two product-integration theorems. On the product of measure spaces equipped with sigma-finite measures, Tonelli's theorem says that a nonnegative measurable function has equal product and iterated integrals, with infinity allowed. Fubini's theorem says that for an absolutely integrable measurable function, its sections are integrable for almost every fixed coordinate, and both orders of iterated integration equal the finite product integral. The Lebesgue measure on each factor is a sigma-finite measure, because the real line is a countable union of finite-length intervals.

Apply Tonelli's theorem first to $|f|$, before presuming finiteness. By translation invariance of Lebesgue measure,Thus $f$ is Lebesgue integrable on ${\mathbb{R}}^2$. The triangle inequality for an integral now gives the requested estimate:This is the L1 norm identity for a translated kernel product followed by a simple bound on the convolution kernel.

There is also a stronger signed conclusion. The integrable convolution kernel $k$ is an odd function, so ${\int }_{\mathbb{R}}k(t)dt=0$. Having established absolute integrability, we may apply Fubini's theorem to $f$ itself:Unlike part (a), the signed cancellation is justified by a finite integral of the absolute value. The constant eight is useful as an L1 norm bound even though this particular signed total vanishes.

For a Lebesgue measurable function $f:\mathbb{R}\to \mathbb{R}$, the preimage $f^{-1}(U)$ of every open set $U$ is a Lebesgue measurable set. For a Borel measurable function, each such preimage must instead be a Borel set. Equivalently, both definitions can test all Borel target sets: the collectionis a sigma-algebra, since preimages preserve complements and countable unions. Containing all open sets therefore makes it contain the Borel sigma-algebra.

Now let $U$ be open. Since $h$ is a Borel measurable function, $h^{-1}(U)$ is Borel. Since $g$ is a Lebesgue measurable function, $g^{-1}(h^{-1}(U))$ is a Lebesgue measurable set. ButThus $h\circ g$ is a Lebesgue measurable function. The intermediate sigma-algebra is Borel; this is why Borel postcomposition preserves Lebesgue measurability.

A map between the measurable spaces is measurable whenA real-valued function $f$ on $S$ is $\Sigma$-measurable when it is measurable from $(S,\Sigma )$ to $(\mathbb{R},\mathcal{B}(\mathbb{R}))$. Equivalently each set $\{f<a\}$ is in $\Sigma$, since open half-lines generate the Borel sigma-algebra.

A Borel measurable function on the real line is a function measurable with respect to the Borel sigma-algebra on both its domain and range. Continuity is sufficient for this property, but is not required.

Every open interval is Borel, since $(a,b)={\bigcup }_{m\ge 1}(a,b-1/m]$, omitting empty pieces. Open subsets of the line are countable unions of open intervals and hence Borel. Conversely, each half-open interval is obtained from open sets by sigma-algebra operations, so this is the usual Borel sigma-algebra.

A continuous function has open, and therefore Borel, inverse images of open sets. Since open sets generate the target Borel sigma-algebra, it is a Borel measurable function. A discontinuous example is $1_{[0,\infty )}$, whose only level sets are built from the Borel half-lines; it jumps at zero.

A Borel measurable function has $f^{-1}(B)\in \mathcal{B}$ for every Borel set $B$. Thus the upper-ray condition is necessary.

For sufficiency, note that the rays generate the stipulated sigma-algebra: $(a,b]=(a,\infty )\setminus (b,\infty )$, and $(y,\infty )={\bigcup }_{m>y}(y,m]$, with integer $m$. The familyis a sigma-algebra because inverse images preserve complements and countable unions. If it contains all upper rays, it contains their generated Borel sigma-algebra. Therefore upper-ray preimages suffice to prove Borel measurability.

Let $K=\sigma (T)$ for a bounded normal operator on a nonzero complex Hilbert space. The zero Hilbert space has the trivial calculus. Take the inner product linear in its first argument. The continuous functional calculus is an isometric unital star-representation $\pi :C(K)\to \mathcal{B}(H)$ with $\pi (z)=T$. The Borel calculus will act on $B_b(K)$, the algebra of actual bounded Borel measurable functions. A quotient by null functions is introduced only after specifying the spectral measure; there is no preferred scalar measure such as plane area on $K$.

Here is a construction that also covers a nonseparable Hilbert space. For $v\in H$, the positive functional $f\mapsto ⟨\pi (f)v,v⟩$ has a finite regular Borel measure ${\mu }_v$ by the Riesz-Markov-Kakutani representation theorem. On continuous functions,Continuous functions are dense in $L^2(K,{\mu }_v)$. Hence $f\mapsto \pi (f)v$ extends to a unitary map from that space onto $H_v=\overline{\pi (C(K))v}$. This subspace reduces $T$ and $T^{\ast }$, which correspond to multiplication by $z$ and $\overline{z}$. Decompose $H$ as an orthogonal direct sum of such cyclic reducing subspaces, using maximality: a nonzero vector in the remaining orthogonal complement would generate another summand. The family need not be countable. This is the cyclic multiplication model for a normal operator.

On each summand define $f(T)$ to be multiplication by $f$, for $f\in B_b(K)$, and take their bounded direct sum. It defines a unital star-homomorphismThus $(fg)(T)=f(T)g(T)$, $\overline{f}(T)=f(T{)}^{\ast }$, and positivity of $f$ gives positivity of $f(T)$. The continuous functional calculus is recovered on $C(K)$.

Set $E(S)=\Phi (1_S)$ for a Borel subset $S$ of $K$. Then $E(S)$ is an orthogonal projection, $E(K)=I$, $E(S)E(R)=E(S\cap R)$, and disjoint countable unions add in the strong operator topology. Indeed on every multiplication summand the indicators add pointwise, and the tail squared norm is the measure of a decreasing sequence of sets tending to the empty set. Thus $E$ is a projection-valued measure, andFor $v,w\in H$, polarization gives scalar measures ${\mu }_{v,w}(S)=⟨E(S)v,w⟩$ satisfying $⟨f(T)v,w⟩=\int fd{\mu }_{v,w}$. Regularity of these finite scalar measures and uniqueness in the Riesz-Markov-Kakutani representation theorem make the projection-valued measure unique: its values on continuous functions determine all scalar measures and hence every projection. This also makes the calculus independent of the chosen cyclic decomposition.

The correct convergence assertion is bounded pointwise convergence in the strong operator topology. If $f_n\to f$ pointwise and ${\sup }_n\Vert f_n{\Vert }_{\infty }<\infty$, thenby the dominated convergence theorem. This need not be convergence in operator norm. For multiplication by $t$ on $L^2[0,1]$, the functions $1_{[0,1/n]}$ converge pointwise to $1_{\{0\}}$, their operators converge strongly to zero, but their operator norms are all one.

A Borel measurable function can vanish spectrally without vanishing pointwise. Precisely, $f(T)=0$ if and only if $E(\{|f|>\epsilon \})=0$ for every $\epsilon >0$, andThe upper norm bound follows by integrating $|f{|}^2$ against vector measures; a unit vector in any nonzero projection $E(\{|f|>C\})$ gives $\Vert f(T)\Vert \ge C$. The induced map on the quotient by these spectral-null Borel measurable functions is isometric. Every nonempty relatively open subset of $K$ has nonzero spectral projection, since otherwise a nonzero continuous function supported there would contradict faithfulness of the continuous functional calculus. This full support gives the usual continuous spectral mapping theorem, but for a Borel measurable function the exact statement is insteadIf an indicated neighborhood has zero projection, define a bounded reciprocal of $f-\lambda$ off it and zero on it; the calculus supplies an inverse. Conversely unit vectors in the nonzero projections for arbitrarily small neighborhoods give $\Vert (f(T)-\lambda )v\Vert$ arbitrarily small, contradicting invertibility. This is spectral essential range in Borel functional calculus. For example $1_{\{0\}}(T)=0$ in the multiplication model on $[0,1]$, although the pointwise range of that function is $\{0,1\}$.

Spectral projections provide reducing subspaces, and $E(\{\lambda \})H=\ker (T-\lambda I)$: the squared norm of $(T-\lambda )v$ is $\int |z-\lambda {|}^{2}d{\mu }_v$. In finite dimension the calculus is simply $f(T)={\sum }_{j}f({\lambda }_j)P_j$, the sum over eigenspaces. In general it also permits discontinuous cuts and Borel choices of square roots, such as $s(z)=|z{|}^{1/2}{e}^{i\mathrm{Arg}(z)/2}$ with $s(0)=0$, giving a normal operator $s(T)$ with $s(T{)}^2=T$ even when a continuous scalar branch is unavailable.

Any bounded operator commuting with both $T$ and $T^{\ast }$ commutes with their continuous functional calculus and with all $E(S)$. To justify the latter, regularity approximates $1_S$ by uniformly bounded continuous functions in the $L^2$ norms of any finite list of vector measures; the resulting net converges strongly to $E(S)$. Thus the Borel calculus lies in the Von Neumann algebra generated by $T$. On a separable Hilbert space, a countable dense list of vectors gives a controlling measure $\mu ={\sum }_j{2}^{-j}{\mu }_{v_j}/(1+\Vert v_j{\Vert }^2)$; spectral-null sets are exactly its null sets, and the range is the represented $L^{\infty }(K,\mu )$, equal to that Von Neumann algebra. Without separability this last equality is not automatic: for the diagonal operator with one eigenvector for each $t\in [0,1]$, the generated Von Neumann algebra has arbitrary bounded diagonal functions, while the original Borel calculus has Borel diagonal functions. The spectral-measure construction and the strong convergence theorem themselves require no separability. This distinguishes the Borel functional calculus for a normal operator from its continuous predecessor without confusing pointwise functions, spectral equivalence classes and topological closure.

Put $K=\sigma (T)$ and use the continuous functional calculus $\pi :C(K)\to \mathcal{B}(H)$. It is a unital star-homomorphism taking the coordinate function to $T$. This follows from the commutative C-star theorem applied to $C^{\ast }(I,T,T^{\ast })$, together with spectral permanence for C-star subalgebras, which is among the permitted C-star results.

Take the Hilbert space inner product linear in its first variable. For a vector $\xi$, let $H_{\xi }=\overline{\{\pi (f)\xi :f\in C(K)\}}$. This cyclic subspace is invariant under every $\pi (f)$ and its adjoint, so it is reducing. The functional $f\mapsto ⟨\pi (f)\xi ,\xi ⟩$ is positive because $f\ge 0$ implies $\pi (f)=\pi (\sqrt{f}{)}^{\ast }\pi (\sqrt{f})$. It has, by the Riesz-Markov-Kakutani representation theorem, a finite regular positive Borel measure ${\mu }_{\xi }$ on $K$. The identitymakes $f\mapsto \pi (f)\xi$ an isometry on its quotient by the functions of zero $L^2$ norm. Density of continuous functions in $L^2({\mu }_{\xi })$ extends it to a unitary $U_{\xi }:L^2({\mu }_{\xi })\to H_{\xi }$. Multiplication by a continuous function intertwines with $\pi$ on this subspace.

Choose a maximal family of mutually orthogonal nonzero cyclic reducing subspaces. Their orthogonal sum is all of $H$: otherwise its reducing orthogonal complement contains a nonzero vector generating another such subspace. This argument does not require separability. For a bounded Borel measurable function $g$ on $K$, multiplication $M_g$ on every $L^2({\mu }_{\xi })$ is bounded with norm at most $\Vert g{\Vert }_{\infty }$. Define on that orthogonal sumMultiplication operators satisfy $M_{fg}=M_f{M}_g$, $M_{\overline{g}}=M_g^{\ast }$ and $M_1=I$. The same identities hold for their direct sums, and the norm bound is uniform in $\xi$. Thus ${\beta }_T$ is a norm-decreasing unital star-homomorphism on the algebra of actual bounded Borel measurable functions, and ${\beta }_T(Z)=T$ because it extends $\pi$. No quotient by a single unspecified measure is being substituted for that Borel algebra.

Choose the bounded Borel measurable square root $s(0)=0$ and $s(z)=|z{|}^{1/2}{e}^{i\mathrm{Arg}(z)/2}$ for $z\ne 0$, taking $\mathrm{Arg}\in [0,2\pi )$. Let $S={\beta }_T(s)$. ThenThus every bounded normal operator has a normal square root. The Borel branch is essential in general: on a circle winding about zero a continuous square-root branch need not exist.

Values at the endpoint one do not affect any of the conclusions, since $\mathbb{P}(U=1)=0$. Set $b_n(1)=1$ to define each random variable everywhere, and choose a Borel measurable function agreeing with $f$ almost everywhere if necessary. These choices leave all integrals and almost-sure assertions unchanged.

Every dyadic interval at level $n+1$ lies in a dyadic interval at level $n$. Equivalently, $b_n(U)$ is a measurable function of $b_{n+1}(U)$, so ${\mathcal{F}}_n\subseteq {\mathcal{F}}_{n+1}$: these sigma-algebras form a filtration. Since the uniform distribution of $U$ gives $\mathbb{E}|f(U)|={\int }_0^1|f(u)|du<\infty$, the conditional expectations $X_n=\mathbb{E}[f(U)\mid {\mathcal{F}}_n]$ are integrable and adapted. The tower property of conditional expectation givesThus $(X_n)$ is a martingale, and part (a) proves that it is uniformly integrable.

For $I_{n,k}=[k{2}^{-n},(k+1)2^{-n})$, the event $\{U\in I_{n,k}\}$ is an atom of a sigma-algebra ${\mathcal{F}}_n$, with probability $2^{-n}$. The value of the conditional expectation there is thereforeConsequently $\boxed{X_n=f_n(U)\text{ almost surely}.}$ This also shows directly that ${\int }_0^1|f_n|\le {\int }_0^1|f|$.

By the uniformly integrable martingale convergence theorem, there is an integrable $Y$ such that $X_n\to Y$ almost surely and in the L1 norm. To identify this limit, put ${\mathcal{F}}_{\infty }=\sigma ({\bigcup }_n{\mathcal{F}}_n)$. Since $0\le U-b_n(U)<2^{-n}$ away from the harmless endpoint, $U={\lim }_n{b}_n(U)$, and $U$ is ${\mathcal{F}}_{\infty }$-measurable. Conversely every $b_n(U)$ is a measurable function of $U$. Thus ${\mathcal{F}}_{\infty }=\sigma (U)$, and both $Y$ and $f(U)$ have ${\mathcal{F}}_{\infty }$-measurable versions.

For $A\in {\mathcal{F}}_m$, the defining property of conditional expectation gives $\mathbb{E}[X_n{1}_A]=\mathbb{E}[f(U)1_A]$ whenever $n\ge m$. Passing to the limit in the L1 norm yieldsThe increasing union ${\bigcup }_m{\mathcal{F}}_m$ is an algebra of sets generating ${\mathcal{F}}_{\infty }$. The class of events for which this integral identity holds is a Dynkin system, so the pi-lambda theorem extends the identity to every $A\in {\mathcal{F}}_{\infty }$. Since both random variables are measurable there, uniqueness of conditional expectation gives $Y=f(U)$ almost surely. We have proved that the dyadic conditional averages recover integrable functions:because a probability-one assertion for $U$ is a full-Lebesgue measure assertion for $x$. Likewise, the uniform distribution of $U$ turns convergence in L1 intoNo pointwise continuity of $f$ is required.

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.

The Borel sigma-algebra $\mathcal{B}(\mathbb{R})$ is the smallest sigma-algebra containing all open subsets of $\mathbb{R}$. A real-valued Borel measurable function on $(E,\mathcal{E})$ is a map $f$ with $f^{-1}(B)\in \mathcal{E}$ for every $B\in \mathcal{B}(\mathbb{R})$. It suffices to test the sets $(a,\infty )$ for rational $a$, because these generate the Borel sigma-algebra.

Here “Borel function” describes measurability into the Borel structure of the target; the domain need not itself be a topological space.

Let $f_n$ be Borel measurable and converge pointwise to the finite real value $f$. For every real $a$,If $f(x)>a$, choose a rational $r$ strictly between them; convergence puts $f_n(x)>r$ eventually. Conversely eventual strict inequality $f_n(x)>r>a$ implies $f(x)\ge r>a$. The right side belongs to $\mathcal{E}$ by its countable union/intersection operations. Since these half-lines generate the Borel sigma-algebra, $f$ is a Borel measurable function.