Talagrand convex distance ($d_T(x,A)$)

For an event $A$ in a product of finitely many probability spaces with its product measure, take the closed convex hull of the mismatch vectors $(1_{x_i\ne y_i}{)}_i$, $y\in A$. The distance of this hull from zero is $d_T(x,A)$. Equivalently it is the supremum, over nonnegative coordinate weights of squared sum at most one, of their minimum mismatch sum. Averaging mismatch patterns is the feature that distinguishes this quantity from ordinary Hamming distance.

On a finite product of standard probability spaces, for any measurable event $A$ of positive probability,Consequently $\mathbb{P}(A)\mathbb{P}(d_T(X,A)\ge s)\le e^{-s^2/4}$. Here $d_T$ is the Talagrand convex distance. The distance-event conclusion can be read with outer probability when necessary.

Let the largest last-coordinate section have probability $a$, and another section probability $ar$. Mix mismatch vectors from these two sections with weights $\lambda ,1-\lambda$. Their squared norm is at most $\lambda d_1^2+(1-\lambda )d_2^2+(1-\lambda {)}^2$. Hölder's inequality and induction bound that section's exponential integral by $a^{-1}{\inf }_{\lambda }{r}^{-\lambda }{e}^{(1-\lambda {)}^2/4}$. The scalar estimate for Talagrand product induction makes it at most $(2-r)/a$. Average over sections and use $m(2-m)\le 1$ with $m=\mathrm{Pr}(A)/a$ to close the induction.

For $a\in [0,1]$,where the endpoint $t=1$ is used directly if $a=0$. Put $L=-\log a$. For $L\le 1/2$, choose $t=2L$ and set $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ and $h^{\prime \prime }(L)=2-2e^L/(2e^L-1{)}^2\ge 0$, proving the bound. For $L\ge 1/2$, take $t=1$; the result follows from the already proved boundary case and monotonicity of $2-a$. This estimate closes the section-by-section induction for the exponential Talagrand convex distance moment.