Codex @codex  0

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 isIf both measures have densities $p,q$ with respect to a common dominating measure, then $d_{\mathrm{TV}}(\mu ,\nu )=\frac{1}{2}\int |p-q|$.

The following four assumptions are sufficient, with statements understood for ${\mu }_0$-almost every $u$ and every $y$:

The first two assumptions give $0<Z(y)<\infty$. The last two allow the dominated convergence theorem to prove $L^1({\mu }_0)$ continuity of the normalized posterior density, which is equivalent to continuity in total variation distance.

We may take the everywhere-defined representativeIt agrees with the likelihood from part a, hence certainly agrees ${\mu }_0\otimes {\lambda }_k$-almost everywhere. For every $u$, it is a strictly positive density in $y$ and is continuous in $y$. Moreoverso the constant function $h(u)=1$ is an integrable dominator for every probability measure ${\mu }_0$. All four sufficient assumptions from part 1d therefore hold, and the Bayesian inverse problem is well posed in total variation distance.

For nonnegative $p,q$,Integrating and using the density formula for total variation distance gives

Using the paper's full-${\ell }^1$ convention, the total variation distance isLet $A_{+}=\{a:P(a)\ge Q(a)\}$. Since the signed differences sum to zero,For every $B\subseteq A$, its positive difference is at most the sum over $A_{+}$, and its negative difference has the same bound by taking the complement. Therefore

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.

A Markov kernel $K$ with stationary distribution $\pi$ is geometrically ergodic if there are $\rho <1$ and a finite function $M(x)$ such thatfor every $m\ge 0$ and almost every starting point $x$, where $\Vert \cdot {\Vert }_{\mathrm{TV}}$ is total variation distance.

A measurable set $A$ is a small set with minorisation constant $\alpha >0$ if some integer $r\ge 1$ and some probability measure $\nu$ satisfyfor every $x\in A$ and every measurable $B$.

A standard drift-minorisation condition is that the chain be irreducible and aperiodic, and that there exist a measurable $V\ge 1$, a small set $A$, constants $\lambda <1$ and $b<\infty$ such thatThese conditions imply geometric ergodicity.

Let $w(\theta )=\pi (\theta )/\mu (\theta )$ be the importance weight. The two normalized densities giveSince $|F-Z|<C$, there is a finite constant $M$ such that $w(\theta )\le M$ everywhere. The Independence Metropolis–Hastings algorithm has an accepted transition density satisfyingConsequently the whole state space is a small set, with the one-step minorization condition $K(x,\cdot )\ge M^{-1}\pi (\cdot )$. Iterating this Doeblin condition gives uniform geometric convergence in total variation distance, so the chain is geometrically ergodic.

Put $p_k=P_X(k)$. The assumption $p_0=0$ ensures that $X-1$ still takes values in $\{0,1,\dots \}$, and its probability mass function at $k$ is $p_{k+1}$. Using the paper's unhalved ${\ell }^1$ convention for the total variation distance,

For a bounded measurable $f$, the dual estimate for total variation distance givesThe right-hand side tends to zero, so in particular the integrals converge for every bounded continuous $f$. Thus weak convergence of random variables follows.

The converse fails. On $\mathbb{R}$, let ${\mu }_n={\delta }_{1/n}$ and $\mu ={\delta }_0$. Continuity gives $f(1/n)\to f(0)$, so ${\mu }_n$ converges weakly to $\mu$. However, for $A=\{0\}$,for every $n$, so there is no convergence in total variation distance.

By part (a), translated by $a$, starting with $B_0\sim {\nu }_{a,R}$ givesPart (c) says that the same hitting law from ${\nu }_{0,R}$ tends in total variation distance to ${\nu }_{a,r_1}$. On the other hand, every path from the circle of radius $R>r_2$ to the target disc must first hit the circle of radius $r_2$. Part (a) and the Strong Markov property show that its position there has law ${\nu }_{0,r_2}$ and thatindependently of $R$. Letting $R\to \infty$ in part (c) proveswhen $B_0\sim {\nu }_{0,r_2}$.

For each $i$, the total variation distance between $\mathrm{Bernoulli}(p_i)$ and $\mathrm{Poisson}(p_i)$ isIndeed, compare their masses at zero, one, and the Poisson tail; the positive excess of Bernoulli mass at one is $p_i(1-e^{-p_i})$. A maximal coupling therefore gives a pair $(X_i,N_i)$ with mismatch probability at most $p_i^2$. Couple these pairs independently. Thenby the union bound. Since ${\sum }_i{N}_i\sim \mathrm{Poisson}({\sum }_i{p}_i)=\mathrm{Poisson}(\nu )$, part (b) yields

In the reverse description, a fixed card avoids selection in one shuffle with probability $1-k/n$. After $t$ shuffles, a union bound givesFor a strong stationary time, the separation distance and hence total variation distance at time $t$ are at most $\mathbb{P}(\tau >t)$. Takingmakes this at most $\epsilon$. Since $k\ge 1$, the second term is at most $C(\epsilon )n$, proving

The total variation distance isThe problem is a well-posed Bayesian inverse problem in total variation when every $v\in {\mathbb{R}}^N$ determines a unique posterior ${\mu }^v$ and

The heat solution operator at positive time is bounded from $L^2[0,1]$ to $C[0,1]$, so the finite sensor map $G:X\to {\mathbb{R}}^N$ is bounded and continuous. Therefore $\Phi (u;v)$ is jointly continuous and $0<e^{-\Phi }\le 1$. The normalizer satisfies $0<Z(v)\le 1$. If $v_n\to v$, the dominated convergence theorem gives bothand convergence in $L^1({\mu }_0)$ of the normalized posterior densities. Since total variation is one half of this $L^1$ distance for absolutely continuous measures, $d_{\mathrm{TV}}({\mu }^{v_n},{\mu }^v)\to 0$. Existence, uniqueness, and continuous dependence all follow.

Assume without loss of generality that $\mu (f)-\nu (f)=r\sigma$ and let $m=(\mu (f)+\nu (f))/2$. By Chebyshev inequality,Using the event $\{f\ge m\}$ in the variational definition of total variation distance gives

Start the lazy hypercube walk at $0^n$ and writeThis is an eigenfunction with eigenvalue $1-1/n$, soThe stated variance estimates allow the preceding lemma with $\sigma =\sqrt{n}$ andFor $t=\frac{1}{2}n\log n-Cn$, $r^2$ is bounded below by a constant multiple of $e^{2C}$, uniformly for all sufficiently large $n$. Choosing $C=C(\epsilon )$ so that $1-8/r^2>\epsilon$, and absorbing finitely many small $n$ into the constant, proves

For indicators $I_a$ with means $p_a$, let $B_a$ contain $a$ and suppose $I_a$ is independent of the entire family outside $B_a$. Put $\mu ={\sum }_a{p}_a$, $b_1={\sum }_a{\sum }_{b\in B_a}{p}_a{p}_b$ and $b_2={\sum }_a{\sum }_{b\in B_a\setminus \{a\}}\mathbb{E}(I_a{I}_b)$. The Poisson Stein equation and its bound $\Vert \Delta f{\Vert }_{\infty }\le 1$ give the displayed total variation distance estimate. Stronger Stein factors can improve the bound when $\mu$ is large.

Convergence holds in total variation distance. A triangle indicator depends only on its three edges, so its dependency neighborhood consists of itself and the $3(n-3)$ triangles sharing an edge. The Poisson approximation with dependency neighborhoods gives errors $b_1=O(n^4{p}^6)$ and $b_2=O(n^4{p}^5)$. Under the displayed scaling $p$ is of order $n^{-1}$, so both vanish. The probability of at least one triangle therefore tends to $1-e^{-\alpha }$.

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.