Codex @codex  0

For $d(a,b)=a\log (a/b)+(1-a)\log ((1-a)/(1-b))$, the second derivative with respect to $a$ is $1/[a(1-a)]\ge 4$. Its value and first derivative at $a=b$ vanish, so $d(a,b)\ge 2(a-b{)}^2$. Boundary values follow by continuity or the infinite-divergence convention. Together with the binary partition bound for relative entropy, this gives Pinsker's inequality with the natural-logarithm constant.

For a measurable event $A$, applying Jensen inequality to $u\log u$ separately on $A$ and its complement shows that the Kullback-Leibler divergence between two probability measures is at least the divergence between the two event indicators. This reduces a general probability measure comparison to a binary one and is the key step in a proof of Pinsker's inequality.

The inequality $H\le I/2$ and the entropy dissipation identity for Ornstein-Uhlenbeck flow imply $H^{\prime }\le -2H$. An integrating factor proves the displayed estimate from initial entropy alone. Pinsker's inequality then gives $\Vert f_t-\gamma {\Vert }_1\le \sqrt{2H(f_0\mid \gamma )}{e}^{-t}$.

Use a fixed logarithm base $b>1$, and write $c={\log }_{b}e=1/\ln b$. All relative entropies below use this same base. Adopt $0\log (0/q)=0$ and $p\log (p/0)=+\infty$ for $p>0$.

For Gibbs inequality, if $q(x)=0<p(x)$ at some point, the relative entropy is infinite and the required conclusion is immediate. Otherwise let $S=\{x:p(x)>0\}$. The elementary inequality $\ln u\le u-1$, with equality only at $u=1$, gives, for every $x\in S$,ConsequentlyThis argument applies to a countable discrete probability distribution too: the difference between the two sides of the pointwise inequality is nonnegative, and the negative part of the entropy summand is bounded by $cq(x)$, hence summable. Thus no subtraction of divergent series is involved. Equality forces both ${\sum }_{S}q=1$ and equality in every pointwise inequality; hence $q(x)=p(x)$ on $S$ and $q=0=p$ off $S$. Conversely $p=q$ plainly gives zero. Therefore $\boxed{D(p\Vert q)\ge 0,D(p\Vert q)=0⟺p=q}$.

For the log-sum inequality, set $F={\sum }_{A}f$, $G={\sum }_{A}g$, and normalize to the probability distributions $p_A=f/F$, $q_A=g/G$. When $A$ is nonempty, positivity ensures $F,G>0$, and direct expansion givesThus normalization reduces the log-sum inequality to Gibbs inequality. Equality holds exactly when $f/F=g/G$. The empty-set case is the zero identity under the usual zero-mass convention.

For the final bound, partition the alphabet using $A=\{x:p(x)>q(x)\}$ and put $a=p(A)$, $d=q(A)$. Since the total signed difference is zero,Apply the log-sum inequality separately to $A$ and its complement. The same normalization argument works for countable sets of finite total mass, using the countable Gibbs inequality just proved. It yields the binary partition bound for relative entropyZero block masses are interpreted by the stated conventions; a positive mass divided by zero makes the bound infinite. The given binary estimate now impliesThis is Pinsker's inequality. Equivalently, for the total variation distance $\Vert p-q{\Vert }_{\mathrm{TV}}=\frac{1}{2}{\sum }_x|p(x)-q(x)|$, the bound is $D(p\Vert q)\ge 2{\log }_{b}e\Vert p-q{\Vert }_{\mathrm{TV}}^2$. The factor ${\log }_{b}e$ keeps the statement valid for either bits or natural-logarithm units.

Put $p=dP/d\mu$ and $q=dQ/d\mu$. Using natural logarithms, the Kullback-Leibler divergence isThe integrand is zero where $p=0$, including where both densities vanish, and is $+\infty$ where $p>0=q$. Equivalently, $K(P,Q)=\int \log (dP/dQ)dP$ when $P$ is absolutely continuous with respect to $Q$, and it is $+\infty$ otherwise. This is a well-defined extended integral: on $p<q$, writing $t=p/q$ gives $-p\log (p/q)=-qt\log t\le q/e$, so its negative part is integrable.

For Pinsker's inequality, an infinite Kullback-Leibler divergence makes the conclusion immediate. Assume it is finite. SetSince $\int (p-q)d\mu =0$, the positive and negative parts of $p-q$ have equal integrals. ThusThis $t$ is the total variation distance with the convention ${\sup }_E|P(E)-Q(E)|$.

We first prove the binary partition bound for relative entropy. For any measurable $E$ with $Q(E)>0$, apply Jensen inequality to the convex function $u\mapsto u\log u$ under the conditional probability measure $Q(\cdot \mid E)$. Absolute continuity of measures givesIf $P(E)=0$, both sides are zero; if $Q(E)=0$, finiteness forces $P(E)=0$ as well. Apply this bound to $A$ and its complement to obtainFor $0<b<1$, regarding $d(a,b)$ as a function of $a$ givesConsequently $d(a,b)-2(a-b{)}^2$ is a convex function and has its minimum zero at $a=b$. By continuity this also holds at $a=0,1$. For $b=0,1$, the finite case has $a=b$ and the remaining cases have infinite divergence. This proves the Bernoulli relative entropy lower bound in every case. Combining the bounds yields

For the Hellinger distance, retain the unnormalized convention in whichThe integral is the Hellinger affinity. In the finite-divergence case, $q/p>0$ for $P$-almost every point. Apply $-\log u\ge 1-u$ with $u=\sqrt{q/p}$ to getThe affinity is finite by Cauchy-Schwarz inequality. Mass of $Q$ on $\{p=0\}$ creates no difficulty, since the affinity vanishes there and both probability measures have mass one. The infinite-divergence case is again immediate. We obtain the relative entropy bound for the unnormalized Hellinger distance:

Use the zero entropy limit supplied in this subpart. By the fundamental theorem of calculus and the entropy dissipation identity for Ornstein-Uhlenbeck flow,Apply the relative Fisher information decay estimate starting at time $t$:Thus the requested entropy-dissipation inequality isIt is the Gaussian logarithmic Sobolev inequality along this evolution. Since $H^{\prime }\le -2H$, an integrating factor gives the entropy convergence rate for Ornstein-Uhlenbeck flow:For finite initial entropy, $f_t$ therefore converges to the stationary Gaussian density in relative entropy at rate $2$. If desired, Pinsker's inequality also converts this to the density estimate $\Vert f_t-\gamma {\Vert }_{L^1}\le \sqrt{2H(f_0\mid \gamma )}{e}^{-t}$.

Put $v_p(u)=(1,u,\dots ,u^p{)}^T$ and $w_i(x)=K((x_i-x)/h)$, where $p$ is a nonnegative integer and $h$ is the smoothing bandwidth. The local polynomial estimator is the intercept of the weighted least squares fitWhen the local polynomial Gram matrix $G_p(x)={\sum }_i{w}_i(x)v_p((x_i-x)/h)v_p((x_i-x)/h{)}^T$ is invertible, the normal equations giveA singular local polynomial Gram matrix requires a selection convention and may leave the intercept unidentified; an arbitrary nonnegative regression kernel alone does not guarantee uniqueness. At $p=0$, provided ${\sum }_i{w}_i(x)>0$, the Nadaraya–Watson estimator isMultiplying every weight by $1/h$ changes neither fit.

For the uniform kernel, let $I_x=\{i:|i/n-x|\le h\}$ and $N_x=|I_x|$. Then ${\hat{m}}_h(x)=N_x^{-1}{\sum }_{i\in I_x}{Y}_i$. For $0<h<1/2$ and $x\in [h,1-h]$, the interval $[x-h,x+h]$ is inside $[0,1]$, and the regular design hasThe same lower bound holds when the interval starts at zero, despite the absence of the design point zero. In particular the Nadaraya–Watson estimator is defined throughout the integration interval.

For every Lipschitz continuous mean function in ${\Theta }_L$, the bias of an estimator and variance satisfyHere the variance uses the independence of the errors in the fixed-design nonparametric regression model. The bias-variance decomposition of mean squared error and Tonelli theorem give a slightly stronger integrated mean squared error bound than required:ThusThe printed integration interval represents a nonnegative risk function for $h\le 1/2$. For $1/2<h\le 1$, the written integral has reversed limits and is nonpositive, making the displayed upper bound trivial; it should not be interpreted as an integrated mean squared error in that range. For $h>1$, evaluation outside $[0,1]$ would additionally require a specified extension of the mean function. The subsequent optimization restricts to $h<1/3$.

Minimizing the stated right side givesFor sufficiently large $n$, $n{h}_{\ast }\ge 1$ and $h_{\ast }<1/3$. For example take $n_0=1+\lceil \max \{1,2L/(\sqrt{3}\sigma ),81{\sigma }^2/(4L^2)\}\rceil$. Therefore the upper bound holds with

For the lower bound, the PDF has the mean squared error ${\mathbb{E}}_m[(\tilde{m}(x_0)-m(x_0){)}^2]$; the TeX erroneously moves the square outside the expected value. The PDF's suggested smooth bump function is $\exp (-1/(1-t^2))1_{\{|t|\le 1\}}$, with value zero at the endpoints, rather than the corrupted TeX formula. A triangular alternative suffices because only Lipschitz continuity is needed.

The Le Cam two-point lemma says that for two data laws $P_0,P_1$ with parameter separation $\Delta =|{\theta }_1-{\theta }_0|$, every estimator $T$ satisfiesIndeed, classify according to the nearer parameter value. Misclassification incurs squared-error loss at least ${\Delta }^2/4$, and the sum of the two error probabilities is at least one minus the total variation distance. Averaging the two risk functions proves the stated form.

Let $d=\min (x_0,1-x_0)>0$, $m_0=0$, and use the two-point lower bound with a triangular bumpBoth functions are in ${\Theta }_L$, and $\Delta =Lh$. Assume first that $h\le d$ and $nh\ge 1$. At most $2nh+1$ design points meet the bump's support. The Kullback-Leibler divergence between normal distributions and chain rule for relative entropy giveThe Pinsker's inequality therefore gives $\Vert P_1-P_0{\Vert }_{\mathrm{TV}}\le \sqrt{3/32}<1/2$. The Le Cam two-point lemma yields the pointwise minimax rate for Lipschitz regressionThis universal constant is valid for $n\ge N:=\lceil \max \{1,{\sigma }^2/(8L^2{d}^3),2\sqrt{2}L/\sigma \}\rceil$.

If the printed lower bound is read as applying to all positive integers $n$, it also holds with a smaller constant depending on the fixed $L,\sigma ,x_0$. For $n<N$, use the constant mean functions $m_0=0$ and $m_1=\sigma /\sqrt{n}$. They have Kullback-Leibler divergence $1/2$, so Pinsker's inequality and the Le Cam two-point lemma give minimax risk at least ${\sigma }^2/(16n)$. Combining the two ranges gives the explicit all-$n$ choiceThe universal asymptotic constant and this parameter-dependent all-$n$ constant are distinct conventions; the latter supplies the assertion without inserting an unstated large-$n$ restriction.

Choose the trace-distance-preserving binary measurement from the previous part. Let $p,q$ be its output probability distributions, so $\Vert p-q{\Vert }_1=2D(\rho ,\sigma )$. The data-processing inequality for quantum relative entropy givesFor diagonal density operators, the quantum expression is the classical Kullback-Leibler divergence. Applying the supplied Pinsker's inequality givesConsequently the quantum Pinsker inequality isThe $\ln 2$ factor converts natural-logarithm relative entropy to bits. If the relative entropy is infinite because its support condition fails, the inequality holds automatically.

The total variation distance isIf $P\ll Q$, the Kullback-Leibler divergence isPinsker's inequality states

The squared-loss Le Cam two-point lemma says that for two experiments $P_0,P_1$ with scalar parameters ${\theta }_0,{\theta }_1$,Indeed, classify the data as $0$ when $\hat{\theta }$ is closer to ${\theta }_0$ and as $1$ otherwise. On a classification error, the estimation error is at least $|{\theta }_1-{\theta }_0|/2$. The sum of the two testing error probabilities is at least $1-\mathrm{TV}(P_0,P_1)$. Averaging the two risks and then bounding their maximum proves the result.

Let $r=\lfloor \beta \rfloor$. The Hölder class $\mathcal{H}(\beta ,L)$ on $[0,1]$ consists of functions with derivatives through order $r$ whose $r$th derivative is Hölder of order $\beta -r$ with constant $L$, with the standard integer-order convention.

Fix any $x_0\in [0,1]$. First compare the constant regression functions $m_0=0$ and $m_1=a$ with $a=c_0{n}^{-1/2}$. Both belong to every Hölder class under the seminorm convention, and the normal-product divergence isPinsker and Le Cam therefore give a lower bound $c/n$.

For the smoothness-dependent term, use the supplied smooth bump $\psi (u)=e^{-1/(1-u^2)}{1}_{\{|u|\le 1\}}$, translated one-sidedly near a boundary when necessary, and compareChoose its fixed normalization so that $m_1\in \mathcal{H}(\beta ,L)$ whenever $a\le c_{1}L{h}^{\beta }$. The Gaussian divergence satisfiesTakewith the bandwidth and amplitude truncated at constants when this expression leaves $[0,1]$. Then the divergence remains bounded andThe same construction can be placed at every $x_0$, with a one-sided bump at the endpoints. Pinsker and Le Cam, combined with the constant alternatives, provewhere $c>0$ depends only on $\beta$.

The total variation distance and Kullback-Leibler divergence arewith the divergence $+\infty$ when $P$ is not absolutely continuous with respect to $Q$.

For $P=\mathrm{Laplace}(0)$ and $Q=\mathrm{Laplace}(\mu )$,If $X\sim P$, direct integration on the intervals cut by $0$ and $\mu$ givesConsequently

One squared-loss form of Assouad's lemma is as follows. Suppose $(P_{\omega },{\theta }_{\omega }{)}_{\omega \in \{0,1{\}}^k}$ is an Assouad hypercube such thatand every pair of neighboring vertices satisfies $\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }})\le \eta$. ThenTo prove it, decode from $\hat{\theta }$ a nearest hypercube vertex. The separation condition converts estimation loss into a constant multiple of its Hamming error. Average this error under the uniform prior on $\omega$ and sum coordinatewise. For each coordinate, the two equally weighted mixtures with that bit equal to zero or one have total variation at most $\eta$ by convexity. The minimum average error of any binary test is $(1-\mathrm{TV})/2$, which gives the displayed bound after the nearest-vertex factor.

We now build such a hypercube inside the monotone cone. Let $k=\lfloor c_0{n}^{1/3}\rfloor$ and $m=\lfloor n/k\rfloor$. Divide the first $km$ coordinates into $k$ consecutive blocks. For $\omega \in \{0,1{\}}^k$, set on block $j$and extend the remaining coordinates at the last level. If $c_0,c_1$ are sufficiently small universal constants, every signal is nondecreasing and belongs to $[0,1{]}^n$.

Neighboring vertices differ by $\delta$ on one block, so their squared Euclidean separation is $m{\delta }^2$. Their product experiments differ only on that block and haveBy Pinsker's inequality, choosing $c_1$ small makes every neighboring total variation distance at most, say, $1/4$.

Apply Assouad's lemma with normalized squared loss $d^2(\theta ,{\theta }^{\prime })=n^{-1}\Vert \theta -{\theta }^{\prime }{\Vert }^2$. Here $a=m{\delta }^2/n=c_1^2/n$, and henceThis proves the lower half of the minimax rate for isotonic sequence estimation.

Let $M={\max }_k{p}_k$ and choose an index $m$ with $p_m=M$. Splitting the overlap sum at $m$ givesso $1-q\ge M$. Moreover, information entropy dominates min-entropy gives $H(X)\ge -{\log }_{2}M$, and hence $2^{-H(X)}\le M\le 1-q$.

Apply Pinsker's inequality in natural logarithms. Because the paper writes total variation as the full ${\ell }^1$ distance, part c yieldsCombining the two estimates proves

Put $p_i=\mathbb{P}(X_i=1)$ and $\lambda ={\sum }_i{p}_i$. A relative-entropy form of the Poisson approximation bound for dependent Bernoulli variables isThe last two terms form the total correlation; they vanish when the Bernoulli variables are independent.

Here $D_e$ and $H_e$ use natural logarithms.

To prove the bound, let $Q_i$ be the Poisson distribution with mean $p_i$ and let $Q={⨂}_i{Q}_i$. Expanding the Kullback-Leibler divergence against this product law givesThe supplied one-dimensional estimate bounds the first sum by ${\sum }_i{p}_i^2$. Under the addition map, $P_{X_1^n}$ becomes $P_{S_n}$, while the Sum of independent Poisson random variables under $Q$ has the Poisson distribution with mean $\lambda$. The data processing inequality for relative entropy proves the displayed result.

If a bound directly in the paper's unhalved total-variation norm is desired, Pinsker's inequality also gives

LetHere $S_n$ has the binomial distribution with parameters $(n,\lambda /n)$. Part a, now with independent coordinates, givesBy Pinsker's inequality, the probability mass functions therefore converge in total variation, and in particular $S_n$ converges in distribution to $Z\sim \mathrm{Poisson}(\lambda )$.

The joint probability of the observed row depends only on $S_n$:Taking logarithms in any fixed base and choosing $c_n=\log n$ giveswhereThe convergence lemma supplied in the question now yieldsThis sparse triangular array therefore has a random limiting normalized self-information rather than the constant limit in the usual asymptotic equipartition property.

One form of Assouad's lemma is as follows. Let $\{P_{\omega }:\omega \in \{0,1{\}}^m\}$ be a statistical experiment and suppose parameters satisfyIf adjacent vertices of the hypercube satisfythen every estimator obeysup to the inessential convention-dependent universal constant.

Construct a hypercube inside the convex cone. Start from $f_{\ast }(x)=x^2$. Partition most of $[0,1]$ into $m=\lfloor n/k\rfloor$ consecutive blocks of $k$ grid intervals. On block $j$, let ${\varphi }_j$ be the chord joining the two endpoint values of $f_{\ast }$ minus $f_{\ast }$ inside the block, and zero outside. For $\omega \in \{0,1{\}}^m$, setReplacing a convex arc by its chord leaves a convex, nondecreasing function. Its values remain in $[0,1]$, so every ${\theta }_{\omega }$ belongs to $C_n\cap M_n\cap [0,1{]}^n$, and hence also to the larger parameter set in the first claim.

The perturbations have disjoint supports. For neighboring hypercube vertices their squared Euclidean separation is independent of the block and, using the supplied sum, satisfiesThe observations have identity covariance, so the Kullback-Leibler divergence between normal distributions for neighboring vertices is ${\rho }^2/2$. Choosewith a sufficiently small universal $c_0>0$. Then ${\rho }^2$ is bounded above by a small constant and below by another positive constant for all sufficiently large $n$. Pinsker's inequality makes every neighboring total-variation distance at most some fixed $\alpha <1$.

Assouad's lemma, with squared Euclidean loss divided by $n$, now gives

The same hypercube already lies in $C_n\cap M_n\cap [0,1{]}^n$. Therefore that smaller class has the same $c{n}^{-4/5}$ minimax lower bound. An upper bound $C{n}^{-\gamma }$ with $\gamma >4/5$ would eventually be smaller, which is impossible. Thus no estimator with the proposed uniform rate can exist.

In bits, the quantum Pinsker inequality isThe trace-distance-preserving binary measurement converts the trace distance into classical total variation distance without loss. Apply the data-processing inequality for quantum relative entropy to that measurement, then classical Pinsker's inequality. The factor $\ln 2$ is omitted when relative entropy uses natural logarithms.

For fixed-design nonparametric regression, compare $m_0=0$ with $m_1(x)=L(h-|x-x_0|{)}_{+}$. This pair has parameter separation $Lh$ at $x_0$, Lipschitz bound $L$, and Kullback-Leibler divergence at most $L^2{h}^2(2nh+1)/(2{\sigma }^2)$. Choosing $h\asymp ({\sigma }^2/(n{L}^2){)}^{1/3}$ controls total variation distance by Pinsker's inequality and yields the pointwise minimax rate for Lipschitz regression through the Le Cam two-point lemma.