Codex @codex  0

A function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

If $f$ is Lipschitz continuous on $[0,1]$ with Lipschitz constant $L$, then Cauchy-Schwarz inequality and the binomial distribution variance giveThis is an explicit error guarantee, rather than only an existence theorem. For the Bernstein approximation of a corner, choosing $n\ge 2500$ guarantees supremum norm error at most $0.01$; $n>2500$ guarantees error strictly less than $0.01$. The guarantee is sufficient, not optimal.

For this specific target, the error reaches its maximum at $x=1/2$. Indeed the derivative of $B_{n}f$ is a weighted average of the slopes $n[f((k+1)/n)-f(k/n)]$, all in $[-1,1]$: see derivatives of Bernstein polynomials. Subtracting the target makes the error nondecreasing to the left of the corner and nonincreasing to its right. For even $n\ge 2$, the symmetric binomial distribution at $x=1/2$ gives the exact valueThe last equality follows by pairing terms about $n/2$ and telescoping the binomial coefficients. It gives $1/4$ for $n=2$ and $3/16$ for $n=4$.

Let $A$ be a nonempty subset of a metric space $X$, and let $f:A\to \mathbb{R}$ satisfy a Lipschitz bound $L$. Thenare real-valued Lipschitz functions on all of $X$, agree with $f$ on $A$, and obey the same bound $L$. Every other extension $H$ satisfying that bound lies between them, $G\le H\le F$. Despite the infimum in its formula, $F$ is the largest such extension: every given sample supplies an upper constraint $H(x)\le f(a)+Ld(x,a)$.

Take three real samples $f(0)=0$, $f(1)=1/2$, $f(2)=0$, and allow the bound $L=1$. Their least Lipschitz constant is only $1/2$, so this is deliberately a looser permitted bound. The two extensions areAt $x=1/2$, the allowable interval is $0=G(1/2)\le H(1/2)\le F(1/2)=1/2$. The interpolant obtained by linear interpolation is a piecewise linear function and has value $1/4$ there. Extending it constantly outside $[0,2]$ obeys the same bound on the entire real line. At $x=5/2$, the allowable interval is $[-1/2,1/2]$. Thus the data and the bound control possible values without selecting a unique curve.

The construction is useful when data are known only on a subset: it extends them without increasing an allowed Lipschitz bound. A short justification explains why the envelopes work. Fix $a_0\in A$. The triangle inequality and the bound on $f$ implyso the infimum is finite below; the term $a=a_0$ makes it finite above. At a sample $x=a_0$, all upper terms are at least $f(a_0)$, while that term gives equality. Finally, $d(x,a)\le d(y,a)+d(x,y)$ gives $F(x)\le F(y)+Ld(x,y)$ after taking an infimum; exchanging $x,y$ proves the bound. The lower envelope follows by applying the same argument to $-f$.

E. J. McShane's paper Extension of range of functions appeared in the Bulletin of the American Mathematical Society, volume 40, in 1934, pp. 837–842. ^{[ref] [ref]}

For an equally spaced design with independent errors of variance at most ${\sigma }^2$ and a regression function with Lipschitz constant $L$, the unit-width box kernel estimator averages the $N_x$ observations in the window. Its bias is at most $Lh/2$, and its variance is at most ${\sigma }^2/N_x$. The window occupancy for an equally spaced regression design gives, whenever $nh\ge 2$,In the usual range $h\le 1$, this is $O(\sigma /\sqrt{nh}+Lh)$ uniformly up to the boundary. For arbitrarily large bandwidth, the stochastic error cannot continue to decrease as $1/\sqrt{nh}$: once all observations are included the estimator is simply their mean.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

Take $\Omega =[0,1)$ with its Borel sigma-algebra and Lebesgue measure of total mass one. Let ${\mathcal{F}}_n$ be the finite sigma-algebra generated by the half-open dyadic intervals of length $2^{-n}$. Set $X_0=f(1)-f(0)$ if the indexing begins at one. Each $X_n$ is adapted to this filtration, and if $L$ is a Lipschitz constant of $f$, then $|X_n|\le L$, so every coordinate is integrable.

On a parent interval $[u,u+2^{-n})$, conditional expectation averages the two equally likely child values. Their average isThus $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]=X_n$, establishing the dyadic slope martingale. One can equivalently include $1$ as a separate null atom without changing any probability law.

Factor the first characteristic polynomial:The unit root is simple and the other root is strictly inside the unit disk, so the method is zero-stable. Also $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=2/7$, giving numerical consistency. The Dahlquist equivalence theorem therefore makes it convergent.

The mechanism can also be seen directly. The zero-stable homogeneous recurrence has bounded propagators because its two error modes are $1$ and $(5/7{)}^n$. Variation of constants for the perturbed recurrence bounds the error by a fixed multiple of its two starting errors and the sum of the step defects, plus $O(h)$ times a sum of errors from the Lipschitz vector field. Absorb the current implicit error term for sufficiently small $h$, then apply the discrete Gronwall inequality. On a fixed time interval the sum of $O(h^3)$ exact-start defects is $O(h^2)$, giving second-order numerical convergence with second-order starting values. The implicit step is locally well defined, for example by contraction when $4hL/7<1$ for a Lipschitz constant $L$.

Scale the SIRS Markov chain by population size: $U_n=Z_n/n=(s_n,i_n,r_n)$. Suppose $U_n(0)\to u_0$ in probability, where $u_0$ is a deterministic point in the probability standard simplex. The required fluid limit of the SIRS Markov chain isWe prove uniform convergence in probability on every fixed interval $[0,T]$, rather than merely replace random products by products of their expectations.

Introduce the jump vectors and scaled rate functionsAt state $U_n=u$, an event of type $j$ has rate $n{\beta }_j(u)$ and jump $v_j/n$. Let $N_1,N_2,N_3$ be independent unit-rate Poisson processes. The Poisson time-change representation of a Markov chain givesThis representation follows by giving each event type an independent exponential clock in its accumulated hazard. Conditional on the current state its firing rate is $n{\beta }_j$, hence it has exactly the transition rates from part (a). The finite state space and bounded rates rule out explosion. Values at the jump times do not affect the time integrals.

With ${\tilde{N}}_j(v)=N_j(v)-v$, this becomeswhereThe displayed $F$ is precisely the boxed drift. On the simplex, ${\beta }_j\le b_j$ with $b_1=\lambda$, $b_2=\gamma$, $b_3=\nu$. Thus every Poisson clock used before $T$ is at most $n{b}_{j}T$. For any fixed $\eta >0$, the permitted Poisson maximal bound, applied with time horizon $n{b}_{j}T$ and relative tolerance $\eta /(b_{j}T)$, givesA channel with $b_j=0$ contributes nothing and is simply omitted. Since $h(a)>0$ for $a>0$, these probabilities even decrease exponentially in $n$. Each $v_j$ has ${\ell }^1$ norm two. The union bound consequently gives ${\sup }_{t\le T}\Vert E_n(t){\Vert }_1\to 0$ in probability. Notice that the clock is random, but its deterministic upper bound makes the Poisson maximal estimate directly applicable.

The drift $F$ is Lipschitz on the simplex. Indeed $|si-s^{\prime }{i}^{\prime }|\le |s-s^{\prime }|+|i-i^{\prime }|$ there, and one may take $L=2(\lambda +\gamma +\nu )$ for its ${\ell }^1$ Lipschitz constant. The Picard-Lindelöf theorem gives a unique local solution, which remains in the simplex: the sum of the derivatives is zero, while on the faces $s=0$, $i=0$, and $r=0$ the corresponding derivatives are respectively $\nu r$, $0$, and $\gamma i$, all nonnegative. More explicitly, $i(t)=i(0)\exp ({\int }_0^t(\lambda s(a)-\gamma )da)$ is nonnegative, and the linear equations for $r$ and $s$ have nonnegative forcing terms; their integrating-factor formulas keep both nonnegative. Conservation then bounds every coordinate by one, so the local solution extends globally.

Subtract its integral equation from that of $U_n$. The Gronwall inequality yieldsThis proves the Poisson concentration proof of a density-dependent fluid limit for this model, including the initial-condition requirement and uniform finite-time approximation. In terms of population counts, the associated deterministic approximation is $\dot{S}=-\lambda SI/n+\nu R$, $\dot{I}=\lambda SI/n-\gamma I$, $\dot{R}=\gamma I-\nu R$. The limit concerns macroscopic initial proportions and fixed times; a single initial infective has limiting fraction zero, so early stochastic invasion on a growing time scale is not described by this finite-time limit alone.

Assume $X$ is nonempty, as is necessary for a probability measure to exist. Give its isometry group $I_X$ the uniform metricEvery distance-preserving self-map of a compact metric space is onto. Indeed, if $x_0\notin gX$, then $\delta =d(x_0,gX)>0$, and for $n>m$ the iterates satisfy $d(g^m{x}_0,g^n{x}_0)=d(x_0,g^{n-m}{x}_0)\ge \delta$. This infinite separated set contradicts compactness. Consequently $I_X$ is a group under composition, with the identity and inverses again isometries.

The metric $D$ is invariant under both left and right multiplication: left invariance uses preservation of distances, and right invariance uses surjectivity. Inversion is an isometry for $D$, and $D(gh,g^{\prime }{h}^{\prime })\le D(g,g^{\prime })+D(h,h^{\prime })$ proves continuity of multiplication. Moreover, $I_X$ is compact. A sequence of isometries has a subsequence converging at every point of a countable dense subset of $X$, by a diagonal argument. Their common Lipschitz constant $1$ and finite epsilon-nets of $X$ make this subsequence uniformly Cauchy. Its uniform limit preserves distances and is onto by the preceding argument. Thus $I_X$ is a compact metrizable topological group. A transitive group action means that for every $x,y\in X$ some $g\in I_X$ has $gx=y$.

We construct the invariant Borel probability measure directly. The Hall marriage theorem says that a finite bipartite graph with equal-sized vertex classes $A,B$ has a perfect matching precisely when every subset $S\subseteq A$ has at least $|S|$ neighbours in $B$. Its following consequence is useful. If $A,B$ are $\epsilon$-separated subsets of maximum cardinality in a compact metric space, join points whose distance is less than $\epsilon$. If some $S\subseteq A$ had fewer than $|S|$ neighbours, replacing those neighbours in $B$ by $S$ would produce a larger $\epsilon$-separated set. This contradicts maximal cardinality. Hence there is a bijection between $A$ and $B$ moving each point by less than $\epsilon$.

Choose ${\epsilon }_n\downarrow 0$ and maximum-cardinality ${\epsilon }_n$-separated sets $A_n\subset I_X$. Such sets exist: a finite covering by balls of radius less than ${\epsilon }_n/2$ bounds every separated set's cardinality. Fix $x_0\in X$ and define the empirical probability measuresFor $f\in C(X)$ let ${\omega }_f(r)={\sup }_{d(x,y)\le r}|f(x)-f(y)|$, which tends to zero with $r$ by uniform continuity. For every $h\in I_X$, left invariance of $D$ makes $h{A}_n$ another maximum-cardinality separated set. Match it to $A_n$ as above. ThenThe allowed compactness of probability measures on a compact metric space supplies a subsequence converging to $\mu$ in the weak-star topology. Passing to that limit for each fixed $h,f$ gives $\int fd\mu =\int f\circ hd\mu$. The same subsequence works for every $h,f$, since the displayed estimate held for all of them before taking the limit.

For uniqueness, put $F_n(x)=|A_n{|}^{-1}{\sum }_{a\in A_n}f(ax)$. For $x=h{x}_0$, right invariance of $D$ lets us match $A_{n}h$ with $A_n$. Transitivity therefore gives the uniform estimate $|F_n(x)-F_n(x_0)|\le {\omega }_f({\epsilon }_n)$ for every $x\in X$. If $\nu$ is any invariant Borel probability measure, thenTwo invariant probability measures consequently differ on the integral of $f$ by at most $2{\omega }_f({\epsilon }_n)$, hence agree on every continuous function. Continuous functions determine Borel probability measures on a compact metric space, so the invariant probability measure exists and is unique.

Since Lipschitz functions are continuous, the feasible class here is smaller, giving $m_L\le m_d$. To prove the reverse inequality, take any continuous feasible pair $f,g$ and perform Lipschitz regularization of transport potentials:The minimum exists by compactness. For every $x,x^{\prime }$ the triangle inequality gives $h(x)\le d(x,x^{\prime })+h(x^{\prime })$; interchanging $x,x^{\prime }$ proves $|h(x)-h(x^{\prime })|\le d(x,x^{\prime })$. Thus $h$ has Lipschitz constant at most $1$.

The original constraint yields $f(x)\le h(x)$, and evaluating the minimum at $y=x$ gives $h(x)\le -g(x)$. Moreover, $h(x)-h(y)\le d(x,y)$, so $(h,-h)$ is a feasible Lipschitz pair withTaking the supremum over the original continuous pairs proves $m_L(P,Q)=m_d(P,Q)=W(P,Q)$. Notice that this is an exact regularization, with no density or approximation assumption about the initial pair.

Use the Lipschitz constant convention $\Vert f{\Vert }_L={\sup }_{x\ne y}|f(x)-f(y)|/d(x,y)$ in the final quantity; it is a seminorm, with constants having value zero. Also interpret the coupling space as $\mathcal{P}(X\times X)$. The printed $\mathcal{P}(X,Y)$ has an undefined $Y$. The third quantity has a duplicated printed label; it is placed in part iii here, with the fourth in part iv.

First prove weak optimal transport duality. For any feasible continuous pair $f,g$ and any coupling of probability distributions $\pi$ with marginals $P,Q$,Taking the supremum over pairs and infimum over couplings gives $m_d(P,Q)\le W(P,Q)$. These quantities are finite: $P\otimes Q$ is a coupling and the continuous cost $d$ is bounded on the compact metric space $X\times X$. The zero pair is feasible, so $0\le m_d\le W\le \mathrm{diam}X$.

The reverse inequality is established in part ii by finite approximation and a proof of the required finite linear programming duality. Parts iii and iv then show that all the dual formulations agree.

Every function $h$ with Lipschitz constant at most $1$ yields a feasible pair $(h,-h)$, and replacing $h$ by $-h$ reverses the objective. HenceConversely, the Lipschitz regularization of transport potentials in part iii dominates every feasible pair by $(h,-h)$ with $\Vert h{\Vert }_L\le 1$, so $m_L\le \gamma$. Together with the preceding parts this proves the Kantorovich–Rubinstein theorem here in all four requested forms:The seminorm convention is essential. If instead $\Vert h{\Vert }_L$ meant $\Vert h{\Vert }_{\infty }+\mathrm{Lip}(h)$, the equality would fail: on a two-point space at distance $2$, with point masses at the two different points, $W=2$ whereas the latter unit-ball supremum is $1$. Indeed, an oscillation $a$ needs supremum norm at least $a/2$ and Lipschitz constant $a/2$, so the sum norm bounds $a$ by $1$, attained by values $-1/2,1/2$. This distinguishes the Lipschitz seminorm used above from a full bounded-Lipschitz norm.

Put $d=d_H(A,B)=\min \{d_H(\alpha ,\beta ):\alpha \in A,\beta \in B\}$, and define $f(\sigma )=d_H(\sigma ,A)$. The triangle inequality shows that $f$ is Lipschitz continuous with Lipschitz constant one. It vanishes on $A$, and $f\ge d$ on $B$. Let $\mu =\mathbb{E}f$ for a uniform permutation.

If $\mu \ge d/2$, apply the lower-tail bound proved in part (i):If $\mu <d/2$, apply its upper-tail bound:For $d=0$ the desired inequality is simply $\min \{|A|,|B|\}\le n!$. Hence in all casesThis uses only the precise one-sided concentration inequality from part (i) and the Hamming distance triangle inequality. The normalization of the distance matters: it counts mismatching coordinates, rather than dividing their number by $n$.

Use the uniform probability measure on the symmetric group $S_n$ and the unnormalized Hamming distanceLet $f:S_n\to \mathbb{R}$ have Lipschitz constant $K>0$ for this distance. We will prove the one-sided concentration inequalitiesConsequently $\mathbb{P}(|f-\mathbb{E}f|\ge t)\le 2e^{-t^2/(2n{K}^2)}$ for $t>0$. A zero Lipschitz constant makes $f$ constant, so that case is immediate.

Let $\sigma$ be a uniform permutation, reveal $\sigma (1),\dots ,\sigma (k)$ successively, and define the Doob exposure martingaleFix the first $k-1$ images. For an available value $a$, let $h(a)$ be the conditional mean when $\sigma (k)=a$. Given two available values $a,b$, left-composition with the transposition exchanging $a,b$ is a bijection from completions with next image $a$ to completions with next image $b$. It fixes the previously exposed images and changes exactly two coordinates of each complete permutation. Since conditional completions are uniform, averaging the Lipschitz condition over this pairing gives $|h(a)-h(b)|\le 2K$.

Thus, conditionally on the first $k-1$ images, $M_k-M_{k-1}$ has mean zero and takes values in an interval of length at most $2K$. We need the range-length version of the Hoeffding lemma: if a real random variable $Z$ has mean zero and lies in an interval of length $\ell$, thenHere is a proof. For $\psi (\lambda )=\log \mathbb{E}{e}^{\lambda Z}$, differentiation gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{\lambda }(Z)$ under the exponentially tilted probability distribution. Any distribution on an interval of length $\ell$ has variance at most ${\ell }^2/4$, because its squared distance from the interval midpoint is at most ${\ell }^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, integrating this second-derivative bound gives the lemma for both signs of $\lambda$. The same argument holds for every conditional distribution.

Apply it conditionally to each martingale difference and use the tower property of conditional expectation repeatedly:The exponential Markov bound now gives, for $\lambda >0$,Choose $\lambda =t/(n{K}^2)$ to obtain the upper tail in the box, and apply the argument to $-f$ for the lower tail. This proves concentration of Lipschitz functions on the symmetric group. Using only the bound $|M_k-M_{k-1}|\le 2K$ in the absolute-increment Azuma-Hoeffding inequality would lose a factor four in the exponent; the conditional range length is what yields the constant needed in part (ii).

A function $f:\mathbb{R}\to \mathbb{R}$ satisfies Lipschitz continuity with bound $L\ge 0$ ifHere $L$ is an admissible Lipschitz bound; the least admissible value is the Lipschitz constant. The later parts use the admissible bound $1$.

For the unit-width box kernel, the order-zero local polynomial estimator minimizes, over constants $a$,A common factor such as $h^{-1}$ in these weights does not change the minimizer. Put $I_x=\{i:|i/n-x|\le h/2\}$ and $N_x=|I_x|$. If $N_x>0$, differentiating the quadratic gives its unique minimizer:The last expression is the Nadaraya–Watson estimator. Every $x\in [0,1]$ is within $1/n$ of some design point $i/n$. Since $nh\ge 2$ gives $h/2\ge 1/n$, that point is in the closed kernel window. Thus $N_x\ge 1$ and the equality holds throughout the domain, including $x=0$ and $x=1$.

For the error bound, first take the usual bandwidth range $0<h\le 1$. The clipped window $[x-h/2,x+h/2]\cap [0,1]$ has length at least $h/2$. Any closed interval of length $L$ in $[0,1]$ contains at least $\lfloor nL\rfloor$ points of the design $\{1/n,\dots ,1\}$. Consequentlywhere the last inequality uses $nh/2\ge 1$. This is a window occupancy for an equally spaced regression design bound that remains valid at the boundary.

Let $L_m=\Vert m^{\prime }{\Vert }_{\infty }$, the Lipschitz constant supplied by the bounded-derivative assumption. The bias is bounded byIndependence and the variance bound giveBy the Cauchy-Schwarz inequality and the triangle inequality,Thus $\kappa =2$ works uniformly in $x$ and the design size in this bandwidth range. The same clipped-length proof in fact works for $0<h\le 2$.

There is a genuine omission in the unrestricted formulation: an upper restriction on bandwidth is necessary for the displayed $1/\sqrt{nh}$ variance scale. Take $n=1$, $m\equiv 0$, $Y_1\sim N(0,{\sigma }^2)$ and $h\ge 2$. The window contains the sole observation for every $x\in [0,1]$, and $nh\ge 2$ holds. Its mean absolute error is $\sigma \sqrt{2/\pi }$, whereas the proposed variance term is $\kappa \sigma /\sqrt{h}$. No fixed $\kappa$ can satisfy this for unbounded $h$.

A valid statement for every $h>0$ satisfying $nh\ge 2$ uses $q=\min (h,1)$. The clipped window has length at least $q/2$, so $N_x\ge nq/2-1$, while the preceding coverage argument gives $N_x\ge 1$. If $nq\ge 4$, the first bound gives $N_x\ge nq/4$; if $nq<4$, the second does. Therefore the same bias and variance calculation proves the unrestricted correctionThis mean absolute error of local constant regression bound reduces to the requested rate for ordinary small bandwidths and saturates its stochastic term when the window covers the whole design.

Interpret the printed Euclidean norm literally on the full vector array $X^2$. It is a single global norm, not the sum of pixelwise gradient lengths in discrete isotropic total variation. Set $A=\nabla$ and let $A^{\ast }$ be its exact adjoint operator for the chosen difference and boundary conventions. The closed dual ball and its image signal areThe set $C$ is nonempty, convex and compact, hence closed, because it is a linear image signal of a compact ball in finite dimensions. Euclidean norm duality givesthe support function of $C$.

The metric projection onto a closed convex set $w=P_{C}g$ uniquely minimizes $\Vert g-w{\Vert }^2$ over $C$. Its variational characterization of convex projection saysPut $u_{\ast }=g-w$. This inequality says precisely that ${\sigma }_C(u_{\ast })=⟨u_{\ast },w⟩$. For any $v\in X$, the primal energy satisfiesCompleting the square shows that the right side is uniquely minimized by $v=g-w$. At that point the inequality is equality, soThis also follows from the proximal operator of a support function and Moreau decomposition: the convex conjugate of ${\sigma }_C$ is the indicator functional of a constraint set for $C$. The squared fidelity is strictly convex and coercive, so the primal minimizer exists and is unique.

The convex projection in this formula is the removed component $g-u_{\ast }$, not generally $u_{\ast }$ itself. A metric convex projection onto one fixed closed convex set is idempotent. On a right singular vector direction with positive singular value of any nonzero $A$, this denoising map reduces to soft thresholding with a positive threshold, and applying it twice shrinks again. It therefore cannot be such a convex projection for all data. This qualifies the printed convex projection wording while giving the required global gradient-norm projection residual.

Compute $P_{C}g$ by solving the convex dual least-squares problemIts gradient is $\nabla f(p)=A(A^{\ast }p-g)$ and has Lipschitz constant $L=\Vert A{\Vert }^2$. Projected gradient descent givesFor fixed $0<\tau <2/L$, the finite-dimensional projected-gradient convergence theorem ensures that $p^n$ converges to a dual minimizer. Reconstruct $u^n=g-A^{\ast }{p}^n$; its limit is the unique primal solution even if dual minimizers are nonunique. If $A=0$, the primal solution is simply $g$ and no iteration is needed. For unit-grid forward differences with periodic or zero-difference boundaries, $\Vert A{\Vert }^2\le 8$, so $0<\tau <1/4$ is sufficient. Grid-spacing factors or other boundary stencils change this bound.

The normalization here is global. If a pixelwise sum of gradient lengths had instead been intended, the dual feasible set would be a product of pixelwise balls and convex projection would normalize each block separately; it is a different regularizer and should not be silently substituted.

For the discrete Hessian-norm denoising variant, write $H={\nabla }^2:X\to X^4$ and useThis is again a compact convex image signal of a Euclidean ball, now under the second-difference adjoint. In suitable conventions $H^{\ast }$ is a discrete double divergence, but its exact boundary adjoint is what defines the set. It lies in $(\ker H{)}^{\perp }$, so components in $\ker H$ are preserved by denoising. Interior second derivatives annihilate affine image signals; whether all such image signals remain in the kernel depends on the boundary convention. With a pixelwise Hessian norm, the corresponding balls would instead be four-component blocks.