Codex @codex  0

Let $\mathcal{T}$ be the set of three-vertex subsets and let $I_A$ indicate that $A$ forms a triangle. ThenIn particular $p\sim (6\alpha {)}^{1/3}/n$. We will use the Stein-Chen method with edge-sharing dependency neighborhoods, rather than wrongly treating triangle indicators as mutually independent.

Here is the needed Poisson approximation with dependency neighborhoods, together with its proof. For indicators $I_A$ with means $p_A$, let $B_A$ contain $A$ and suppose $I_A$ is independent of the entire family of indicators outside $B_A$. With $\mu ={\sum }_A{p}_A$ and $W={\sum }_A{I}_A$, defineThe total variation distance convention is $d_{TV}(P,Q)={\sup }_E|P(E)-Q(E)|$. We claimFor an indicator test function $g$ on the nonnegative integers, solve the Poisson Stein equationwith $\Vert \Delta f{\Vert }_{\infty }\le 1$. This elementary Stein factor can be proved as follows. Take the immigration--death process with immigration rate $\mu$ and per-particle death rate one. Starting at $k$, its time-$t$ distribution iswith independent summands. Its stationary law is that of $Z$. Coupling the initial particles with a stationary Poisson initial population makes the centered expectations decay at least as a constant times $(k+\mu )e^{-t}$, sois finite. Its generator equation is $\mu (u(k+1)-u(k))+k(u(k-1)-u(k))=g(k)-\mathbb{E}g(Z)$, obtained by integrating the semigroup derivative. Set $f(k)=u(k)-u(k-1)$ for $k\ge 1$; choose $f(0)=f(1)$, which does not affect the equation. To bound $\Delta f(k)$, couple the processes starting at $k-1,k,k+1$ by adding two independent initial particles. Both survive to time $t$ with probability $e^{-2t}$, and otherwise their second difference cancels in expectation. Since $|g(j+2)-2g(j+1)+g(j)|\le 2$,This proves the Stein factor for $k\ge 1$, and the chosen $f(0)$ handles $k=0$.

Put $W_A=W-{\sum }_{C\in B_A}{I}_C$. Independence gives $\mathbb{E}[I_{A}f(W_A+1)]=p_A\mathbb{E}f(W_A+1)$. Inserting this identity into the Stein equation yieldsThe first sum in absolute value is at most $b_1$, since the two arguments differ by ${\sum }_{C\in B_A}{I}_C$. In the second sum, on $I_A=1$ the arguments differ by ${\sum }_{C\in B_A\setminus \{A\}}{I}_C$, giving bound $b_2$. Taking the supremum over event indicators $g$ proves the claimed total variation distance bound.

For triangle $A$, choose $B_A$ to consist of $A$ itself and all triangles sharing an edge with $A$. There are exactly $1+3(n-3)$ such triangles. Every outside triangle uses none of the three edges of $A$, even if it shares one vertex, so $I_A$ is independent of their entire indicator family. For distinct neighboring triangles, their union has five edges and $\mathbb{E}(I_A{I}_C)=p^5$. ThereforeThe Stein-Chen method gives $d_{TV}(\mathcal{L}(X),\mathrm{Poisson}({\mu }_n))\to 0$. Coupling Poisson distributions of two means by adding an independent Poisson variable givesThis proves the Poisson limit for triangles in a binomial random graph:Applying the same bound to the event $\{1,2,\dots \}$ givesFor finite $n$ this is an approximation, not an exact formula: the error from $1-e^{-{\mu }_n}$ is at most $b_1+b_2$, and the error from $1-e^{-\alpha }$ is at most $b_1+b_2+|{\mu }_n-\alpha |$.

Apply the preceding argument to the two product observation laws and the real-valued estimator $T={\hat{\psi }}_n$. Alternatively, directly useThe average of the two mean squared errors is at least $(\theta -\tau {)}^2/4$ times the overlap of the two joint probability density functions. Their overlap equalsTaking the infimum over estimators therefore yieldsHere $R_n^{\ast }$ is the minimax risk for this functional. The factor $\frac{1}{2}\Vert P_f^{(n)}-P_g^{(n)}{\Vert }_1$ is the total variation distance, so the same metric squared-loss two-point bound applies to a functional even when distinct density parameters have the same functional value.

For fixed-design nonparametric regression, let $x_i=i/n$ and $K_h(u)=h^{-1}K(u/h)$. The degree-$p$ local polynomial estimator takes the fitted intercept ${\hat{m}}_h(x;p)={\hat{\beta }}_0$, whereUse a nonnegative regression kernel and an invertible local polynomial Gram matrix to obtain a unique fit. For $p=0$, solving the single weighted least squares normal equation gives the local constant estimator:At the interior point $x_0$, use the standard unit-integral regression kernel convention ${\mu }_0(K)=1$. Otherwise the leading variance below is $R(K)/(nh{\mu }_0(K{)}^2)$; unlike a kernel density estimator, the local constant estimator itself is unchanged by rescaling $K$.

The local constant estimator is a linear estimator in nonparametric regression with weights $W_i=K_h(x_i-x_0)/(n{s}_{0,h})$. The independent unit-variance errors implyTo control the bias of an estimator, differentiability at this one point is enough. WriteSymmetry makes ${\mu }_1(K)=0$, and the supplied moment approximation gives $s_{1,h}=o(h)$. Therefore the linear contribution to the bias of an estimator is $m^{\prime }(x_0)s_{1,h}/s_{0,h}=o(h)$. The remaining contribution has absolute value at most $\eta (h)h$, because only $|x_i-x_0|\le h$ receive positive weight. This is the interior first-order bias cancellation for local constant regression, and gives squared bias of an estimator $o(h^2)$. Combining with the variance provesFor fixed $\epsilon >0$, take $h_{\epsilon }={\epsilon }^{-1/3}{n}^{-1/3}$. It satisfies both asymptotic smoothing bandwidth conditions, and the displayed remainder, multiplied by $n^{2/3}$, tends to zero for this fixed $\epsilon$. ThusLetting $\epsilon \downarrow 0$ proves the optimized scaled pointwise error tends to zero. The order of these limits matters: no remainder uniform in $\epsilon$ has been assumed.

For the lower bound over the whole function class, the absence of a uniform bound on derivatives permits a particularly direct argument. It also avoids assuming a normal distribution for errors when the model only supplies their first two moments. Fix $n$ and $x_0$. Choose a smooth bump function $b$ on the interval, with $b(x_0)=1$, whose support contains no design point except possibly $x_0$. Such a bump exists because the design is finite; at an endpoint use the restriction of a smooth bump on the real line. Every $m_a=ab$, $a\in \mathbb{R}$, belongs to the differentiability class.

If $x_0$ is not a design point, all observation means are zero for every $a$. The Le Cam two-point lemma applied to $a=\pm A$ has total variation distance zero and gives a lower bound tending to infinity with $A$. In fact, the supremum of the mean squared error is infinite at every such $x_0$.

If $x_0$ is a design point, only its response depends on $a$. The resulting location family is the single observation $Y=a+ϵ$; all remaining observations are independent of $a$ and give no extra information. The single-observation location minimax bound isHere is a proof covering discrete as well as continuous errors. Give $a$ the prior distribution $U[-A,A]$, independently of the noise. Put $p_M=\mathbb{P}(|ϵ|\le M)$ and $v_M=\mathrm{Var}(ϵ\mid |ϵ|\le M)$. Consider an easier experiment in which an oracle also reveals whether $|ϵ|\le M$, and reveals $a$ itself on the complementary event. On the event $|ϵ|\le M$ and $|Y|\le A-M$, every possible truncated noise value places $a=Y-ϵ$ within $[-A,A]$. The flat prior distribution then makes the Bayesian posterior noise law exactly its truncated original law. The smallest conditional squared-error loss is its conditional variance $v_M$, attained by the posterior mean.

The probability of that event is at least $p_M(1-2M/A)$ for $A>2M$, by restricting further to $|a|\le A-2M$. Thus every rule's supremum risk function is at least the original Bayes risk, which is at least the easier experiment's Bayes risk, and therefore at least $p_M(1-2M/A)v_M$. Let $A\to \infty$ and then $M\to \infty$. Finite second moment and zero mean give $p_M{v}_M\to 1$. The rule $T(Y)=Y$ has constant mean squared error one, proving the equality.

Consequently, at every $x_0\in [0,1]$, the unrestricted differentiability class satisfies the stronger conclusionThus $c=1$ works for every $n\ge 1$. There is no conflict with the preceding fixed-function limit: the worst functions, including arbitrarily narrow bumps, can vary with $n$. This is the pointwise versus uniform risk distinction. A smoothness ball with a common derivative bound would pose a different minimax risk problem.

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:

Two independent cyclic intervals intersect with probability at most $\min \{1,(2k-1)/d\}\le 2k/d$. For $k\le d/2$, precisely the $2k-1$ starting-point offsets $-(k-1),\dots ,k-1$ can overlap; for larger $k$, the upper bound is automatic. The cyclic interval overlap bound and the preceding chi-squared divergence estimate therefore giveAs in 1(e), the square-root hypothesis is meaningful when $\alpha d\ge 1$. The chi-squared testing lower bound bounds the total variation distance by $\sqrt{2{\alpha }^{\epsilon }}/2$. The worst individual Type II error dominates the error under the uniform mixture model. ThusTaking $\alpha$ small makes this lower bound informative. This argument uses the actual cyclic-interval alternative, without substituting a different family of subsets.

Let $p=dP/d\nu$ and $q=dQ/d\nu$ be Radon-Nikodym derivatives. Use the following normalizations of the Kullback-Leibler divergence, total variation distance and unnormalized Hellinger distance:We use $0\log (0/q)=0$ and assign infinite Kullback-Leibler divergence if $Pot\ll Q$, where $\ll$ denotes absolute continuity of measures. Common domination alone also suffices for the inequalities with the extended-value convention. The negative part of the logarithmic integral is integrable: on $p<q$, $p\log (q/p)\le q-p\le q$. Thus the extended-value integral defining the Kullback-Leibler divergence is well-defined. These expressions do not depend on which common dominating measure is chosen. The Kullback-Leibler divergence is generally asymmetric and therefore fails a defining property of a metric.

For completeness, the integral formula for total variation distance follows by taking $A=\{p\ge q\}$: since $\int (p-q)d\nu =0$, the positive and negative parts of $p-q$ have the same integral, and this set attains the supremum.

Put $a=\int \sqrt{pq}d\nu \le 1$, by the Cauchy-Schwarz inequality. A second application givesThe logarithmic inequality in the hint implies $\log t\le t-1$ for $t>0$. Apply it to $t=\sqrt{q/p}$ on $\{p>0\}$:Multiplying by $p$ and integrating provesIf $q=0<p$ on a set of positive $P$-measure, the right side is finite but the Kullback-Leibler divergence is infinite, so the inequality is immediate. ThusThis total variation–Hellinger–relative entropy inequality requires the stated Hellinger distance normalization for its first constant. With the alternative convention ${\bar{h}}^2=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^2$, the correct comparison is $\mathrm{TV}\le \sqrt{2}\bar{h}$ and $\bar{h}\le \sqrt{\mathrm{KL}/2}$. In particular, $P=\mathrm{Bernoulli}(0.6)$ and $Q=\mathrm{Bernoulli}(0.4)$ have $\mathrm{TV}=0.2>\bar{h}\approx 0.1421$.

Here is a testing form of the Le Cam two-point lemma. Suppose two parameter values ${\theta }_0,{\theta }_1$ in a metric space have separation $\Delta =d({\theta }_0,{\theta }_1)>0$, and let $P_0,P_1$ be the corresponding observation laws. Every estimator $T$ satisfiesTo prove it, classify $T$ by the closer of the two parameters, breaking a tie in favour of one. Let $A=\{d(T,{\theta }_1)\le d(T,{\theta }_0)\}$. On $A$, the triangle inequality implies $d(T,{\theta }_0)\ge \Delta /2$, while on $A^c$ it implies $d(T,{\theta }_1)>\Delta /2$. Hence the sum of the two probabilities in the display is at leastAt least one is at least half the sum, proving the claim. It also gives a lower bound $\Delta (1-\mathrm{TV})/4$ for the maximum expected metric loss.

For absolute-error loss, or any loss given by a metric, there is a stronger expectation form. Take densities $p_0,p_1$ relative to $m=P_0+P_1$ and use the triangle inequality under their overlap:Therefore the Le Cam lower bound under absolute-error loss isBoth arguments are valid for randomized estimators as well, by adjoining the independent randomization to the observation; doing so does not change total variation distance.

For the normal distribution model, assume the usual nondegenerate convention $\sigma >0$ and use the full product observation laws. ChooseFor one observation, its Gaussian log likelihood ratio isUnder the first law, ${\mathbb{E}}_0(X-{\mu }_1{)}^2={\sigma }^2+({\mu }_1-{\mu }_0{)}^2$ and ${\mathbb{E}}_0(X-{\mu }_0{)}^2={\sigma }^2$. Thus the Kullback-Leibler divergence between normal distributions isFor the independent and identically distributed random variables, the joint log likelihood ratio is the sum of the individual ones, so the Kullback-Leibler divergence of the two full statistical samples is $n({\mu }_1-{\mu }_0{)}^2/(2{\sigma }^2)=1/4$. The comparison just proved implies $\mathrm{TV}(P_0,P_1)\le 1/2$. Applying the expectation form of the Le Cam two-point lemma givesThis is a Gaussian location minimax lower bound under absolute-error loss. The constant may depend on the fixed known $\sigma$, but neither on the estimator nor on $n$. If a signed nonzero scale were used, the same result holds with $|\sigma |$ in place of $\sigma$. If zero noise were allowed, $X_1=\mu$ would estimate $\mu$ exactly, so a positive lower bound would be false; positive variance is necessary.

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\pi }_n$ is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so $d_n(t)$ is nonincreasing and the minimum is finite.

Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed $0<\epsilon <1/2$,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha )/t_{\mathrm{mix}}^{(n)}(\beta )\to 1$ for any fixed $\alpha ,\beta \in (0,1)$.

Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.

Let $m\ge 2$ be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ${\gamma }_{\ast }$; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap $1-{\lambda }_2$. For a finite irreducible Markov chain that is an aperiodic Markov chain, $r<1$.

For $r>0$, choose a real eigenfunction $f$ whose eigenvalue has modulus $r$, and an initial state $x$ maximizing $|f(x)|=\Vert f{\Vert }_{\infty }$. It has $\pi (f)=0$, and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, $d(t)\ge r^t/2$. At $t=t_{\mathrm{mix}}(\epsilon )$, for $0<\epsilon <1/2$,The second inequality follows from $-r\log r\le 1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\epsilon \ge 1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention ${\gamma }_{\ast }=1$ the bound is again trivial.

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.