# Variance Bounds: Some Old and Some New

Clément Deslandes111C.M.A.P. École Polytechnique, Palaiseau, 91120, France &
Georgia Institute of Technology, Atlanta, GA, 30332, USA
(clement.deslandes@poytechnique.edu). Christian Houdré222School of
Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA
(houdre@math.gatech.edu). 333Research supported in part by the awards $524678$
and ${\rm MP\\!\\!-\\!\\!TSM-}\\!00002660$ from the Simons Foundation.
Keywords: Jackknife, Noise Sensitivity, Variance Bounds, Longest Common
Subsequences.
MSC 2010: 60B20, 60F05.

###### Abstract

For functions of independent random variables, various upper and lower
variance bounds are revisited in diverse settings. These are then specialized
to the Bernoulli, Gaussian, infinitely divisible cases and to Banach space
valued random variables. Frameworks and techniques vary from jackknives
through semigroups and beyond. Some new applications are presented,
recovering, in particular, all the known estimates on the variance of the
length of the longest common subsequences of two random words.

##  1 Introduction and preliminary results

We revisit below various lower and upper bounds on the variance of functions
of independent random variables. Throughout and unless otherwise noted,
$X_{1},\dots,X_{n},X^{\prime}_{1},\dots,X^{\prime}_{n}$ are independent random
variables such that for all $k\in\\{1,\dots,n\\}$, $X_{k}$ and
$X^{\prime}_{k}$ are identically distributed, while
$S:\mathbb{R}^{n}\to\mathbb{R}$ is a Borel function such that
$\mathds{E}S(X_{1},\dots,X_{n})^{2}<+\infty$. Next, and if $S$ is short for
$S(X_{1},\dots,X_{n})$, for any $k\in\\{1,\dots,n\\}$, let
$S^{k}:=S(X_{1},\dots,X_{k-1},X^{\prime}_{k},X_{k+1},\dots,X_{n})$ and more
generally if $\alpha\subset\\{1,\dots,n\\}$, let $S^{\alpha}$ be defined as
$S(X_{1},\dots,X_{n})$ but with $X_{k}$ replaced by $X^{\prime}_{k}$ for all
$k\in\alpha$. With these preliminary notations, we next recall the definitions
of various quantities which will play an important role in the sequel.

Following [1], for $k\in\\{1,\dots,n\\}$, let

$B_{k}:=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(S^{i_{1},\dots,i_{k-1}}-S^{i_{1},\dots,i_{k}}),$
(1.1)

where $\mathfrak{S}_{n}$ is the symmetric group of degree $n$ and where for
$k=1,S^{i_{1},\dots,i_{k-1}}=S$. As the following sum is telescopic:

$\sum_{k=1}^{n}B_{k}=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(S-S^{i_{1},\dots,i_{n}})={\textrm{Var}}\,S.$

One key fact motivating the definition of the $B_{k}$’s is that they can be
rewritten as:

$B_{k}=\mathds{E}\frac{1}{2n!}\sum_{i\in\mathfrak{S}_{n}}(S-S^{i_{k}})(S^{i_{1},\dots,i_{k-1}}-S^{i_{1},\dots,i_{k}}).$
(1.2)

Indeed, if $\alpha,\beta\subset\\{1,\dots,n\\}$,

$\mathds{E}\left(S^{\alpha}S^{\beta}\right)=\mathds{E}\left(SS^{\alpha\Delta\beta}\right),$
(1.3)

where $\Delta$ denotes the symmetric difference operator, so

$\mathds{E}(S-S^{i_{k}})(S^{i_{1},\dots,i_{k-1}}-S^{i_{1},\dots,i_{k}})=2\mathds{E}\left(SS^{i_{1},\dots,i_{k-1}}-SS^{i_{1},\dots,i_{k}}\right).$
(1.4)

Next, for all $k\in\\{1,\dots,n\\}$, let $\Delta_{k}S:=S-S^{k}$, and iterating
this operator: for $k\neq{\ell}$, let
$\Delta_{k,{\ell}}S:=\Delta_{k}(\Delta_{\ell}S)=S-S^{k}-S^{\ell}+S^{k,{\ell}}$
(note the commutativity property:
$\Delta_{k}(\Delta_{\ell}S)=\Delta_{\ell}(\Delta_{k}S)$). Iterating this
process, let
$\Delta_{i_{1},\dots,i_{k}}S:=\Delta_{k}(\Delta_{i_{1},\dots,i_{k-1}}S)$.
Using this notation, we have

$B_{k}=\mathds{E}\frac{1}{2n!}\sum_{i\in\mathfrak{S}_{n}}(\Delta_{i_{k}}S)(\Delta_{i_{k}}S)^{i_{1},\dots,i_{k-1}},$
(1.5)

and so $B_{k}\geq 0$ since if $U,U^{\prime}$ and $V$ are independent with $U$
and $U^{\prime}$ identically distributed, then for any function $F$ such that
$F(U,V)$ is integrable,
$\mathbb{E}\left(F(U,V)F(U^{\prime},V)\right)=\mathbb{E}\left(\mathbb{E}\left(F(U,V)|V\right)^{2}\right)\geq
0$. We are now ready to generalize the approach used to go from (1.1) to
(1.5), leading to novel properties of the $B_{k}^{\prime}s$.

######  Lemma 1.1.

Let $\alpha,\beta$ be two disjoint subsets of $\\{1,\dots,n\\}$. Then

$\mathbb{E}\left(S(\Delta_{\alpha}S)^{\beta}\right)=\frac{1}{2^{|\alpha|}}\mathbb{E}\left(\Delta_{\alpha}S(\Delta_{\alpha}S)^{\beta}\right).$
(1.6)

###### Proof.

Firstly, by a straightforward induction on $k:=|\alpha|$, note that
$\Delta_{\alpha}S=\sum_{\alpha^{\prime}\subset\alpha}(-1)^{|\alpha^{\prime}|}S^{\alpha^{\prime}}$.
Then, for any $\alpha^{\prime}\subset\alpha$,

$(-1)^{|\alpha^{\prime}|}S^{\alpha^{\prime}}(\Delta_{\alpha}S)^{\beta}=\sum_{\alpha^{\prime\prime}\subset\alpha}(-1)^{|\alpha^{\prime}|+|\alpha^{\prime\prime}|}S^{\alpha^{\prime}}S^{\alpha^{\prime\prime}\cup\beta},$

and so using (1.3) ($\alpha$ and $\beta$ are disjoint and
$\alpha^{\prime}\subset\alpha$ so
$\alpha^{\prime}\Delta(\alpha\cup\beta)=(\alpha^{\prime}\Delta\alpha)\cup\beta$),

$\mathds{E}\left((-1)^{|\alpha^{\prime}|}S^{\alpha^{\prime}}(\Delta_{\alpha}S)^{\beta}\right)=\mathds{E}\left(\sum_{\alpha^{\prime\prime}\subset\alpha}(-1)^{|\alpha^{\prime}|+|\alpha^{\prime\prime}|}SS^{(\alpha^{\prime}\Delta\alpha^{\prime\prime})\cup\beta}\right).$

Since $\alpha^{\prime\prime}\mapsto\alpha^{\prime}\Delta\alpha^{\prime\prime}$
is just a permutation of the subsets of $\alpha$ and
$(-1)^{\alpha^{\prime}\Delta\alpha^{\prime\prime}}=(-1)^{|\alpha^{\prime}|+|\alpha^{\prime\prime}|}$,

$\displaystyle\mathds{E}\left((-1)^{|\alpha^{\prime}|}S^{\alpha^{\prime}}(\Delta_{\alpha}S)^{\beta}\right)$
$\displaystyle=\mathds{E}\left(\sum_{\alpha^{\prime\prime}\subset\alpha}(-1)^{|\alpha^{\prime\prime}|}SS^{\alpha^{\prime\prime}\cup\beta}\right)=\mathbb{E}\left(S(\Delta_{\alpha}S)^{\beta}\right),$

and so

$\displaystyle\frac{1}{2^{|\alpha|}}\mathbb{E}\left(\Delta_{\alpha}S(\Delta_{\alpha}S)^{\beta}\right)$
$\displaystyle=\frac{1}{2^{|\alpha|}}\sum_{\alpha^{\prime}\subset\alpha}\mathds{E}\left((-1)^{|\alpha^{\prime}|}S^{\alpha^{\prime}}(\Delta_{\alpha}S)^{\beta}\right)=\mathbb{E}\left(S(\Delta_{\alpha}S)^{\beta}\right).$

∎

Let $T$ be the forward shift operator, i.e., for $k\in\\{1,\dots,n-1\\}$, let
$TB_{k}:=B_{k+1}$ and let $D$ be the backward discrete derivative: $D:=Id-T$
(so for $k\in\\{1,\dots,n-1\\}$, $DB_{k}=B_{k}-B_{k+1}$), and denote by
$D^{\ell}$ ($\ell\geq 0$) its $\ell$-th iteration. It is known (see [1]) that
the finite sequence $(B_{k})_{1\leq k\leq n}$ is non-increasing. More can be
said.

######  Theorem 1.2.

For all $\ell\geq 0$ and $k\in\\{1,\dots,n-\ell\\}$,

$D^{\ell}B_{k}=\mathds{E}\frac{1}{2^{\ell+1}n!}\sum_{i\in\mathfrak{S}_{n}}(\Delta_{i_{1},\dots,i_{\ell+1}}S)(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+2},\dots,i_{k+\ell}}.$
(1.7)

In particular, $D^{\ell}B_{k}\geq 0$, i.e., $(B_{k})_{1\leq k\leq n}$ is
completely monotone (recall that $D=Id-T$).

###### Proof.

With the previous lemma, it is enough to prove that for all
$\ell\in\\{0,\dots,n-1\\}$ and $k\in\\{1,\dots,n-\ell\\}$,

$D^{\ell}B_{k}=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+2},\dots,i_{k+\ell}}.$
(1.8)

This is done by induction on $\ell$. When $\ell=0$, (1.8) is just the very
definition of $B_{k}$. Assume next that (1.8) holds for
$\ell\in\\{0,\dots,n-2\\}$. Let $k\in\\{1,\dots,n-(\ell+1)\\}$. Then,

$\displaystyle D^{\ell+1}B_{k}$
$\displaystyle=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+2},\dots,i_{k+\ell}}-\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+2},\dots,i_{k+1+\ell}}$
$\displaystyle=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+3},\dots,i_{k+1+\ell}}-\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+1}}S)^{i_{\ell+2},\dots,i_{k+1+\ell}}$
$\displaystyle=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}S(\Delta_{i_{1},\dots,i_{\ell+2}}S)^{i_{\ell+3},\dots,i_{k+1+\ell}},$

where in getting the second equality, the terms are reindexed. ∎

We wish now to study potential connections between the $B_{k}$’s and
jackknives operators $J_{k}$ and $K_{k}$ previously studied in [3]. For
$Y\in\sigma(X_{1},\dots,X_{n})$, i.e., Y measurable with respect to the
$\sigma$-field generated by $X_{1},\dots,X_{n}$ and $i\in\\{1,\dots,n\\}$, let
$\mathds{E}^{(i)}Y:=\mathds{E}(Y|X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n})$ and
more generally for a subset $\alpha$ of $\\{1,\dots,n\\}$, let

$\mathds{E}^{\alpha}Y:=\mathds{E}(Y|(X_{i})_{i\notin\alpha}).$

For $i\in\\{1,\dots,n\\}$, let

${\textrm{Var}}\,^{(i)}Y:=\mathds{E}^{(i)}Y^{2}-(\mathds{E}^{(i)}Y)^{2}$

and iterating, for $i\in\mathfrak{S}_{n}$, let

${\textrm{Var}}\,^{(i_{1},\dots,i_{k})}Y:=\mathds{E}^{(i_{1})}({\textrm{Var}}\,^{(i_{2},\dots,i_{k})}Y)-{\textrm{Var}}\,^{(i_{2},\dots,i_{k})}(\mathds{E}^{(i_{1})}Y).$

For $k\in\\{1,\dots,n\\}$, let

$J_{k}:=\sum_{i_{1}\neq i_{2}\dots\neq
i_{k}}{\textrm{Var}}\,^{(i_{1},\dots,i_{k})}S,$ (1.9)

and

$K_{k}:=\sum_{i_{1}\neq i_{2}\dots\neq
i_{k}}{\textrm{Var}}\,^{i_{1},\dots,i_{k}}\mathds{E}^{\overline{(i_{1},\dots,i_{k})}}S,$
(1.10)

where $\overline{(i_{1},\dots,i_{k})}=(i_{k+1},\dots,i_{n})$. For ease of
notation, set also $J^{\prime}_{k}:=J_{k}/k!$ and $K^{\prime}_{k}:=K_{k}/k!$.
The next lemma provides relationships between these quantities and the
$B_{k}$’s, it will allow us to get easily, and in a unified fashion, many of
the known expressions involving the variance, along with some new ones.

######  Lemma 1.3.

Let $\alpha,\beta$ be two disjoint subsets of $\\{1,\dots,n\\}$. Then

$\mathds{E}\left({\textrm{Var}}\,^{\alpha}\mathds{E}^{\beta}S\right)=\mathds{E}\left(S(\Delta_{\alpha}S)^{\beta}\right).$
(1.11)

###### Proof.

This is straightforward by induction on the cardinality of $\alpha$. ∎

Recalling (1.8), we get from (1.11) that for all $k\in\\{1,\dots,n\\}$,

$J^{\prime}_{k}={n\choose k}D^{k-1}B_{1}\quad\text{and}\quad
K^{\prime}_{k}={n\choose k}D^{k-1}B_{n-k+1}.$ (1.12)

It is easy to check that for any finite sequence $(a_{k})_{1\leq k\leq n}$ and
any positive integers $k\in\\{1,\dots,n\\}$,

$a_{k}=\sum_{j=0}^{k-1}(-1)^{j}{k-1\choose
j}D^{j}a_{1}=\sum_{j=0}^{n-k}{n-k\choose j}D^{j}a_{n-j}.$ (1.13)

In particular, for all $k\in\\{1,\dots,n\\}$,

$\displaystyle B_{k}$ $\displaystyle=\sum_{j=0}^{k-1}(-1)^{j}\frac{{k-1\choose
j}}{{n\choose j+1}}J^{\prime}_{j+1},$ (1.14) $\displaystyle B_{k}$
$\displaystyle=\sum_{j=0}^{n-k}\frac{{n-k\choose j}}{{n\choose
j+1}}K^{\prime}_{j+1}.$ (1.15)

We can now connect the $J^{\prime}_{k}$’s and $K^{\prime}_{k}$’s to the
variance.

######  Lemma 1.4.

For all $k\in\\{1,\dots,n\\}$,

${\textrm{Var}}\,S-J^{\prime}_{1}+J^{\prime}_{2}-\dots+(-1)^{k}J^{\prime}_{k}=(-1)^{k}\sum_{1\leq
i_{1}<\dots<i_{k+1}\leq n}D^{k}B_{i_{1}},$ (1.16)
${\textrm{Var}}\,S-K^{\prime}_{1}-K^{\prime}_{2}-\dots-K^{\prime}_{k}=\sum_{1\leq
i_{1}<\dots<i_{k+1}\leq n}D^{k}B_{i_{k+1}}.$ (1.17)

###### Proof.

Let us prove (1.16) by induction on $k\in\\{1,\dots,n\\}$. For the base case:

${\textrm{Var}}\,S-J^{\prime}_{1}=B_{1}+\dots+B_{n}-nB_{1}=\sum_{j=2}^{n}(B_{j}-B_{1})=-\sum_{j=2}^{n}\sum_{i=1}^{j-1}DB_{i}.$

For the inductive step: assume it is true for $k\in\\{1,\dots,n\\}$. Then,

$\displaystyle{\textrm{Var}}\,S-J^{\prime}_{1}+J^{\prime}_{2}-\dots+(-1)^{k}J^{\prime}_{k}+(-1)^{k+1}J^{\prime}_{k+1}$
$\displaystyle=(-1)^{k}\left(\left(\sum_{1\leq i_{1}<\dots<i_{k+1}\leq
n}D^{k}B_{i_{1}}\right)-J^{\prime}_{k+1}\right)$
$\displaystyle=(-1)^{k}\sum_{1\leq i_{1}<\dots<i_{k+1}\leq
n}\left(D^{k}B_{i_{1}}-D^{k}B_{1}\right)$ $\displaystyle=(-1)^{k}\sum_{1\leq
i_{1}<\dots<i_{k+1}\leq n}\sum_{1\leq i_{0}<i_{1}}-D^{k+1}B_{i_{0}}$
$\displaystyle=(-1)^{k+1}\sum_{1\leq i_{0}<i_{1}<\dots<i_{k+1}\leq
n}D^{k+1}B_{i_{0}}.$

The proof of (1.17) is very similar and so it is omitted. The following
proposition recovers and extends some of the results obtained in [3]. ∎

######  Proposition 1.5.

${\textrm{Var}}\,S=J^{\prime}_{1}-J^{\prime}_{2}+\dots+(-1)^{n-1}J^{\prime}_{n},$
(1.18) ${\textrm{Var}}\,S=K^{\prime}_{1}+K^{\prime}_{2}+\dots+K^{\prime}_{n},$
(1.19)

and for all $k\in\\{1,\dots,n\\}$,

$K^{\prime}_{k+1}\leq(-1)^{k}\left({\textrm{Var}}\,S-J^{\prime}_{1}+J^{\prime}_{2}-\dots+(-1)^{k}J^{\prime}_{k}\right)\leq
J^{\prime}_{k+1},$ (1.20)
$K^{\prime}_{k+1}\leq{\textrm{Var}}\,S-K^{\prime}_{1}-K^{\prime}_{2}-\dots-K^{\prime}_{k}\leq
J^{\prime}_{k+1}.$ (1.21)
${\textrm{Var}}\,S=J^{\prime}_{1}-J^{\prime}_{2}+\dots+(-1)^{k-1}J^{\prime}_{k}+(-1)^{k}\sum_{j=k+1}^{n}{j-1\choose
k}K^{\prime}_{j}.$ (1.22) ${\textrm{Var}}\,S=\frac{{k\choose 1}}{{n\choose
1}}J^{\prime}_{1}-\frac{{k\choose 2}}{{n\choose
2}}J^{\prime}_{2}+\dots+(-1)^{k-1}\frac{{k\choose k}}{{n\choose
k}}J^{\prime}_{k}+\frac{{n-k\choose 1}}{{n\choose
1}}K^{\prime}_{1}+\frac{{n-k\choose 2}}{{n\choose
2}}K^{\prime}_{2}+\dots+\frac{{n-k\choose n-k}}{{n\choose
n-k}}K^{\prime}_{n-k}.$ (1.23)

###### Proof.

Above, the first two equalities simply follow from the fact that the right-
hand terms in Lemma 1.4 are zero when $k=n$. Then, the first two inequalities
follow from Lemma 1.4 and the complete monotonicity of the $B_{k}$’s: for
$1\leq i_{1}\leq n-k$, $D^{k}B_{n-k}\leq D^{k}B_{i_{1}}\leq D^{k}B_{1}$. Let
us turn to the identity (1.22).

Applying the inversion formula (1.13) to $(D^{k}B_{i})_{1\leq i\leq n-k}$,
with $i\leq n-k$, we get

$\displaystyle\sum_{1\leq i_{1}<\dots<i_{k+1}\leq n}D^{k}B_{i_{1}}$
$\displaystyle=\sum_{i=1}^{n-k}{n-i\choose k}D^{k}B_{i}$
$\displaystyle=\sum_{i=1}^{n-k}\sum_{j=0}^{n-k-i}{n-i\choose k}{n-k-i\choose
j}D^{k+j}B_{n-k-j}$
$\displaystyle=\sum_{i=1}^{n-k}\sum_{j=0}^{n-k-i}{n-i\choose k}{n-k-i\choose
j}\frac{K^{\prime}_{k+j+1}}{{n\choose k+j+1}}$
$\displaystyle=\sum_{j=0}^{n-1}\sum_{i=1}^{n-k-j}{n-i\choose k+j}{k+j\choose
k}\frac{K^{\prime}_{k+j+1}}{{n\choose k+j+1}}$
$\displaystyle=\sum_{j=0}^{n-1}{k+j\choose k}K^{\prime}_{k+j+1},$

where the last equality stems from the hockey-stick formula and reindexing.

To finish, let us prove (1.23) which will follow from
${\textrm{Var}}\,S=B_{1}+\dots+B_{k}+B_{k+1}+\dots+B_{n}$. Indeed, the
equality (1.18) remains valid for any sequence $(a_{n})_{n\geq 1}$, namely,
the same proof shows that

$a_{1}+\dots+a_{n}={n\choose 1}D^{0}a_{1}-{n\choose
2}D^{1}a_{1}+\dots+(-1)^{n-1}{n\choose n}D^{n-1}a_{1}.$ (1.24)

In particular,

$\displaystyle B_{1}+\dots+B_{k}$ $\displaystyle={k\choose
1}D^{0}B_{1}-{k\choose 2}D^{1}B_{1}+\dots+(-1)^{k-1}{k\choose k}D^{k-1}B_{1}$
$\displaystyle=\frac{{k\choose 1}}{{n\choose 1}}J^{\prime}_{1}-\frac{{k\choose
2}}{{n\choose 2}}J^{\prime}_{2}+\dots+(-1)^{k-1}\frac{{k\choose k}}{{n\choose
k}}J^{\prime}_{k}.$

The second part, $B_{k+1}+\dots+B_{n}$, is treated similarly. ∎

The equality (1.23) could be of use to find the order of ${\textrm{Var}}\,S$
as $n$ tends to infinity. For example, if there is a constant $C>1$
(independent of $n$) such that $J^{\prime}_{2}(n)\leq CJ^{\prime}_{1}(n)$,
then, taking $k=\lfloor\frac{n}{2C}\rfloor$ will lead to

$\liminf_{n\to\infty}\frac{{\textrm{Var}}\,S(n)}{J^{\prime}_{1}(n)}\geq\frac{1}{4C}.$

We have proved that the finite sequence $(B_{k})_{1\leq k\leq n}$ is
completely monotone and we already knew from [1] that it is non-increasing, so
it is natural to wonder if one could find further properties of the $B_{k}$’s.
On the other hand, one may also wonder whether or not $(K_{k})_{1\leq k\leq
n}$ does satisfy any further property except, of course, from being non-
negative. Both answers appear to be negative:

######  Proposition 1.6.

For any $a_{1},\dots,a_{n}\geq 0$, there exists
$S:\mathbb{R}^{n}\to\mathbb{R}$ a Borel function such that for all
$k\in\\{1,\dots,n\\}$, $K_{k}=a_{k}$.

######  Corollary 1.7.

If $(b_{k})_{1\leq k\leq n}$ is completely monotone, then there exists
$S:\mathbb{R}^{n}\to\mathbb{R}$ a Borel function such that for all
$k\in\\{1,\dots,n\\}$, $B_{k}=b_{k}$.

###### Proof of the Corollary.

It is easy to see that $(b_{k})_{1\leq k\leq n}$ is completely monotone if and
only if for all $k\in\\{1,\dots,n\\}$, $D^{k-1}b_{n-k+1}\geq 0$. From the
statement of the proposition, there exists $S:\mathbb{R}^{n}\to\mathbb{R}$ a
Borel function such that for all $k\in\\{1,\dots,n\\}$,
$K_{k}=\frac{n!}{(n-k)!}D^{k-1}b_{n-k+1}$, and, recalling (1.12), since there
is no choice for the $B_{k}$’s knowing the $K_{k}$’s, $B_{k}=b_{k}$. ∎

###### Proof of the proposition.

This follows from using the link with the Hoeffding decomposition observed in
[3]. Consider for example $A_{1},\dots,A_{n}\geq 0$ and
$S(X_{1},\dots,X_{n}):=A_{1}\sum_{1\leq i_{1}\leq
n}(X_{i_{1}}-\mathds{E}X_{i_{1}})+A_{2}\sum_{1\leq i_{1}<i_{2}\leq
n}(X_{i_{1}}-\mathds{E}X_{i_{1}})(X_{i_{2}}-\mathds{E}X_{i_{2}})+\dots+A_{n}\sum_{1\leq
i_{1}<\dots<i_{n}\leq
n}(X_{i_{1}}-\mathds{E}X_{i_{1}})\dots(X_{i_{n}}-\mathds{E}X_{i_{n}})$. Then,
from [3],

$\displaystyle K_{k}$ $\displaystyle=A_{k}^{2}\,k!\sum_{1\leq
i_{1}<\dots<i_{k}\leq
n}{\textrm{Var}}\,(X_{i_{1}}-\mathds{E}X_{i_{1}})\dots(X_{i_{n}}-\mathds{E}X_{i_{k}})$
$\displaystyle=A_{k}^{2}\,k!\sum_{1\leq i_{1}<\dots<i_{k}\leq
n}{\textrm{Var}}\,(X_{i_{1}})\dots\textrm{Var}\,(X_{i_{k}}),$

so it is possible to adjust the $A_{k}$’s to have the $K_{k}$’s as wanted. ∎

One could expect the $J_{k}$’s to behave like the $K_{k}$’s and to also be
able to take any values, but this is unfortunately not the case, for example
${2}J_{2}/n=(n-1)(B_{1}-B_{2})\leq nB_{1}=J_{1}$.

To conclude this section, we connect the $B_{k}$’s and the quantities $T_{A}$
introduced in [4]. For any subset $A$ of $\\{1,\dots,n\\}$, $T_{A}$ is defined
as

$T_{A}=\sum_{j\notin A}\Delta_{j}S(\Delta_{j}S)^{A},$ (1.25)

and then $T$ is defined as

$T=\sum_{A\subsetneq\\{1,\dots,n\\}}\frac{T_{A}}{2(n-|A|){n\choose|A|}}.$
(1.26)

It is easy to check that for all $k\in\\{1,\dots,n\\}$,

$B_{k}=\sum_{A:|A|=k-1}\frac{T_{A}}{2(n-|A|){n\choose|A|}},$

hence $\mathds{E}T=\sum_{k=1}^{n}B_{k}={\textrm{Var}}\,S$ (as expected).

######  Remark 1.8.

  1. (i)

One might wonder if the above variance results can be transferred to the
$\Phi$-entropy. Let $\Phi$ be a convex function of the real variable such that
$\mathds{E}|\Phi(S)|<+\infty$, and let the $\Phi$-entropy $H_{\Phi}$ of $S$
(e.g., see [2]) be defined as:

$H_{\Phi}(S)=\mathds{E}\Phi(S)-\Phi(\mathds{E}S).$

Following [3], for $i\in\\{1,\dots,n\\}$, let

$H^{(i)}_{\Phi}(S)=\mathds{E}^{(i)}\Phi(S)-\Phi(\mathds{E}^{(i)}(S)),$

while for $i\neq j\in\\{1,\dots,n\\}$,

$H^{(j,i)}_{\Phi}(S):=\mathds{E}^{(j)}H^{(i)}_{\Phi}(S)-H^{(i)}_{\Phi}(\mathds{E}^{(j)}S)=H^{(i,j)}_{\Phi}(S).$

Still iterating, for $i_{1}\neq\dots\neq i_{k}\in\\{1,\dots,n\\}$,

$H^{(i_{1},\dots,i_{k})}_{\Phi}(S):=\mathds{E}^{(i_{1})}H^{(i_{2},\dots,i_{k})}_{\Phi}(S)-H^{(i_{2},\dots,i_{k})}_{\Phi}(\mathds{E}^{(i_{1})}S).$

Define the corresponding $B_{k}$’s as,

$B_{k}:=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}H^{(i_{k})}_{\Phi}(\mathds{E}^{(i_{1},\dots,i_{k-1})}S),$

for all $k\in\\{1,\dots,n\\}$. Once again the sum is telescopic:

$\sum_{k=1}^{n}B_{k}=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}\mathds{E}^{(i_{k})}\Phi(\mathds{E}^{(i_{1},\dots,i_{k-1})}S)-\Phi(\mathds{E}^{(i_{1},\dots,i_{k})}S)=H_{\Phi}S.$

By the conditional Jensen inequality, the $B_{k}$’s are non-negative. Just
like in the variance case, it is clear by induction that for all
$\ell\in\\{0,\dots,n-1\\}$,

$D^{\ell}B_{k}=\mathds{E}\frac{1}{n!}\sum_{i\in\mathfrak{S}_{n}}H^{(i_{1},\dots,i_{\ell+1})}_{\Phi}(\mathds{E}^{(i_{\ell+2},\dots,i_{k+\ell})}S).$

Let us now look for the class of convex functions $\Phi$ such that for any $S$
and $X_{1},\dots,X_{n}$ satisfying the basic independence and integrability
assumptions, $(B_{k})_{1\leq k\leq n}$ is non-increasing. In particular, for
any random variable $Z$ defined on a product space
$\Omega_{1}\times\Omega_{2}$ satisfying the integrability conditions, choosing
$S$ and $X_{1},\dots,X_{n}$ such that $S=Z$ ($S=f(X_{1},X_{2})$ for some
function $f$), we have that

$\displaystyle D^{1}B_{k}$
$\displaystyle=\frac{1}{n!}\mathds{E}\sum_{i\in\mathfrak{S}_{n}}H^{(i_{1},i_{2})}_{\Phi}(\mathds{E}^{(i_{3},\dots,i_{k+1})}S)$
$\displaystyle=\frac{2}{n!}\mathds{E}H^{(1,2)}_{\Phi}(S)$
$\displaystyle=\frac{2}{n!}\mathds{E}\left(\Phi(Z)-\Phi(\mathds{E}^{(1)}Z)-\Phi(\mathds{E}^{(2)}Z)+\Phi(\mathds{E}^{(1,2)}Z)\right),$

so
$\mathds{E}\left(\Phi(Z)-\Phi(\mathds{E}^{(1)}Z)-\Phi(\mathds{E}^{(2)}Z)+\Phi(\mathds{E}^{(1,2)}Z)\right)\geq
0$. Reciprocally, if for any random variable $Y$ defined on a product space
$\Omega_{1}\times\Omega_{2}$ satisfying the integrability conditions,

$\mathds{E}\left(\Phi(Y)-\Phi(\mathds{E}^{(1)}Y)-\Phi(\mathds{E}^{(2)}Y)+\Phi(\mathds{E}^{(1,2)}Y)\right)\geq
0,$

then clearly $D^{1}B_{k}\geq 0$ for all $k\in\\{1,\dots,n-1\\}$. Theorem 1 in
[20] tells us that this happens if and only if $\Phi$ is affine or is twice
differentiable with $\Phi^{\prime\prime}>0$ and $1/\Phi^{\prime\prime}$
concave.

  2. (ii)

One may further wonder what conditions on $\Phi$ would guarantee
$(B_{k})_{1\leq k\leq n}$ to be completely monotone, or, at least, to have
$D^{2}B_{k}\geq 0$ for all $k\in\\{1,\dots,n-2\\}$. Unfortunately, the
variance is basically the only case for which this holds true. Indeed, if the
condition $D^{2}B_{k}\geq 0$ is satisfied for all $S$, then, as before,
choosing $S=f(X_{1},X_{2},X_{3})$, we get

$\displaystyle D^{1}B_{k}$
$\displaystyle=\frac{1}{n!}\mathds{E}\sum_{i\in\mathfrak{S}_{n}}H^{(i_{1},i_{2},i_{3})}_{\Phi}(\mathds{E}^{(i_{3},\dots,i_{k+2})}S)$
$\displaystyle=\frac{6}{n!}\mathds{E}H^{(1,2,3)}_{\Phi}(S)$
$\displaystyle=\frac{6}{n!}\mathds{E}\sum_{\alpha\subset\\{1,2,3\\}}(-1)^{|\alpha|}\Phi(\mathds{E}^{\alpha}S).$

Therefore, for any random variable $Y$ defined on a product space
$\Omega_{1}\times\Omega_{2}\times\Omega_{3}$ satisfying the integrability
conditions,
$\sum_{\alpha\subset\\{1,2,3\\}}(-1)^{|\alpha|}\Phi(\mathds{E}^{\alpha}Y)\geq
0$. Reciprocally, this guarantees the non-negativity of $D^{2}B_{k}$, for any
$k\in\\{1,\dots,n-2\\}$ and any $S$. According to [20, Theorem 2], this
happens if and only if there exist $a,b,c\in\mathbb{R}$ with $a\geq 0$ and
$\Phi:x\mapsto ax^{2}+bx+c$. So for any function $\Phi$ that is not of this
form, the $K_{k}$’s and the $J_{k}$’s (defined as the variations of $B_{k}$’s)
are not always non-negative: for some functions $S$ they are negative.

  3. (iii)

It is tempting to use the representation of completely monotone functions for
the $B_{k}^{\prime}s$. Unfortunately, a completely monotone finite sequence
may not be the restriction of a completely monotone function.

##  2 Connection with a more general decomposition of the variance

Let $U_{1},\dots,U_{n}$ be random variables taking values in $(0,1)$ and
independent of $X_{1},\dots,X_{n},X^{\prime}_{1},\dots,X^{\prime}_{n}$. For
any $\alpha\in[0,1]$, let $X^{(\alpha)}$ be the vector with coordinates,
$X^{(\alpha)}_{i}:=\mathds{1}_{\alpha\leq
U_{i}}X_{i}+\mathds{1}_{\alpha>U_{i}}X^{\prime}_{i}$, $1\leq i\leq n$. Then,

${\textrm{Var}}\,S=\mathds{E}\left(S(X^{(0)})\left(S(X^{(0)})-S(X^{(1)})\right)\right),$
(2.1)

and it is tempting to rewrite this last term as an integral. Let us assume
that each $U_{i}$ has a density $\nu_{i}$. For any
$0\leq\alpha<\alpha^{\prime}\leq 1$, denote by $A_{\alpha,\alpha^{\prime}}$
the random set of indices $i\in\\{1,\dots,n\\}$ such that $\alpha\leq
U_{i}<\alpha^{\prime}$. By the Cauchy-Schwarz inequality,

$\displaystyle\left|\mathds{E}\left(S(X^{(0)})S(X^{(\alpha^{\prime})})\right)-\mathds{E}\left(S(X^{(0)})S(X^{(\alpha)})\right)\right|$
$\displaystyle\leq
2\mathds{E}(S^{2})\mathds{P}\left(|A_{\alpha,\alpha^{\prime}}|>0\right)$
$\displaystyle\leq 2\mathds{E}(S^{2})\mathds{E}|A_{\alpha,\alpha^{\prime}}|$
$\displaystyle\leq
2\mathds{E}(S^{2})\sum_{i=1}^{n}\int_{\alpha}^{\alpha^{\prime}}\mathrm{d}\nu_{i},$

hence $\alpha\mapsto\mathds{E}\left(S(X^{(0)})S(X^{(\alpha)})\right)$ is
absolutely continuous, its derivative is well defined almost everywhere,
integrable, and

$\displaystyle{\textrm{Var}}\,S=\mathds{E}\left(S(X^{(0)})S(X^{(0)})\right)-\mathds{E}\left(S(X^{(0)})S(X^{(1)})\right)=-\int_{0}^{1}\frac{\mathrm{d}}{\mathrm{d}\alpha}\mathds{E}\left(S(X^{(0)})S(X^{(\alpha)})\right)\mathrm{d}\alpha.$
(2.2)

In order to compute the derivative in (2.2), fix $\alpha\in(0,1)$ and
$\varepsilon\in(0,1-\alpha)$. Conditioning on $A_{\alpha,\alpha+\varepsilon}$
and letting

$\Delta_{\alpha,\varepsilon}:=\frac{\mathds{E}\left(S(X^{(0)})S(X^{(\alpha+\varepsilon)})\right)-\mathds{E}\left(S(X^{(0)})S(X^{(\alpha)})\right)}{\varepsilon},$

we get

so for almost every $\alpha$,

$\Delta_{\alpha,\varepsilon}\xrightarrow[\varepsilon\to
0]{}\sum_{i=1}^{n}\mathds{E}\left(S(X^{(0)})(S(X^{(\alpha),\hat{i}})-S(X^{(\alpha),i}))\right)\nu_{i}(\alpha),$

where $X^{(\alpha),i}$ is defined like $X^{(\alpha)}$ but with $X_{i}$ for its
$i$-th coordinate, and $X^{(\alpha),\hat{i}}$ is defined like $X^{(\alpha)}$
but with $X^{\prime}_{i}$ for its $i$-th coordinate. So we get finally:

${\textrm{Var}}\,S=\sum_{i=1}^{n}\int_{0}^{1}\mathds{E}\left(S(X^{(0)})(S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}}))\right)\mathrm{d}\nu_{i}(\alpha).$
(2.3)

Let us further define, for $i\in\\{1,\dots,n\\}$ and any
$x_{1},\dots,x_{n}\in\mathbb{R}^{n}$, $d_{i}S$ via,

$d_{i}S(x_{1},\dots,x_{n}):=S(x_{1},\dots,x_{n})-\mathds{E}S(x_{1},\dots,x_{i-1},X_{i},x_{i+1},\dots,x_{n}).$
(2.4)

Note that if $Z_{i}$ is independent of all the other random variables and has
same distribution as $X_{i}$, we have

$d_{i}S(X)=\mathds{E}_{Z_{i}}\left(S(X)-S(X_{1},\dots,X_{i-1},Z_{i},X_{i+1},\dots,X_{n})\right).$
(2.5)

Therefore we notice, conditioning on $U_{i}$, that

$\mathds{E}\left(d_{i}S(X^{(0)})d_{i}S(X^{(\alpha)})\right)=\mathds{P}(\alpha\leq
U_{i})\mathds{E}\left(S(X^{(0)})(S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}}))\right).$
(2.6)

We can rewrite the variance as

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\sum_{i=1}^{n}\int_{0}^{1}\mathds{E}\left(d_{i}S(X^{(0)})d_{i}S(X^{(\alpha)})\right)\frac{1}{\int_{\alpha}^{1}\mathrm{d}\nu_{i}(\alpha)}\mathrm{d}\nu_{i}(\alpha).$
(2.7)

Note that in the special case where $U_{i}$ are uniformly distributed on
$[0,1]$,

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\sum_{i=1}^{n}\int_{0}^{1}\mathds{E}\left(d_{i}S(X^{(0)})d_{i}S(X^{(\alpha)})\right)\frac{1}{1-\alpha}\mathrm{d}\alpha,$
(2.8)

and a simple change of variables allows us to recover again (2.7). Therefore,
we will focus on the uniformly distributed case.

###  2.1 Connection with the $B_{k}$’s

From (2.3),

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\sum_{i=1}^{n}\int_{0}^{1}\mathds{E}\left(S(X^{(0)})(S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}}))\right)\mathrm{d}\alpha$
$\displaystyle=\sum_{i=1}^{n}\int_{0}^{1}\sum_{k=0}^{n-1}\mathds{E}\left(S(X^{(0)})(S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}}))\right)\mathds{1}_{|A_{0,\alpha}\setminus\\{i\\}|=k}\mathrm{d}\alpha$
$\displaystyle=\int_{0}^{1}n\sum_{k=0}^{n-1}\frac{1}{n}\sum_{i=1}^{n}\mathds{E}\left(S\left(\Delta_{i}S\right)^{\beta_{k,i}}\right)\mathds{P}\left(|A_{0,\alpha}\setminus\\{i\\}|=k\right)\mathrm{d}\alpha,$

where $\beta_{k,i}$ is a random set of $k$ elements chosen in
$\\{1,\dots,n\\}\setminus\\{i\\}$. Clearly
$\mathds{P}\left(|A_{0,\alpha}\setminus\\{i\\}|=k\right)={n-1\choose
k}\alpha^{k}(1-\alpha)^{n-1-k}$, and from the representations (1.5) and (1.6),
we get

$\sum_{k=0}^{n-1}\frac{1}{n}\sum_{i=1}^{n}\mathds{E}\left(S\left(\Delta_{i}S\right)^{\beta_{k,i}}\right)=B_{k+1},$

hence

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\sum_{k=0}^{n-1}\int_{0}^{1}n{n-1\choose
k}\alpha^{k}(1-\alpha)^{n-1-k}B_{k+1}\mathrm{d}\alpha=\sum_{k=0}^{n-1}B_{k+1}.$

###  2.2 Connection with a semigroup approach

The semigroup approach, as developed in [15] for the hypercube, boils down to
the same integration trick along $\alpha$. We need first to rewrite our
results in a more general setup: we assume the $X_{i}$’s are i.i.d. discrete
variables, taking a finite number of values and this time, $S$ takes values in
a Banach space $(E,\|\cdot\|_{E})$. We also consider a continuous convex
function $\Phi:E\rightarrow\mathbb{R}^{+}$, so instead of considering
${\textrm{Var}}\,S=\mathds{E}\|S-\mathds{E}S\|_{E}^{2}=\|S-\mathds{E}S\|_{E,2}^{2}$,
we consider $\mathds{E}\left(\Phi(S-\mathds{E}S)\right)$. The price to pay is
a suboptimal constant, as seen next, and the lack of connection with the
$B_{k}$’s, which do not seem to have any equivalent in this setup. We hope
that making this connection casts a new light on the breakthrough [15], but
also gives prospects to generalize it: indeed, while it is not clear what
would be the adequate semigroup when the $X_{i}$’s are not binary variables,
our theorem works for all discrete distributions with finite support (and it
is straightforward to generalize to all discrete distributions or even bounded
continuous distributions).

######  Theorem 2.1.

For any $\alpha\in(0,1)$, let
$\varepsilon_{1}(\alpha),\dots,\varepsilon_{n}(\alpha)$ be i.i.d. random
variable such that
$\mathds{P}(\xi_{i}(\alpha)=1)=1-\alpha,\mathds{P}(\xi_{i}(\alpha)=-1)=\alpha$,
and let
$\delta_{i}(\alpha)=\frac{\xi_{i}(\alpha)-\mathds{E}\xi_{i}(\alpha)}{\sqrt{{\textrm{Var}}\,\xi_{i}(\alpha)}}$.
Then, with the notations above,

$\displaystyle\mathds{E}(\Phi(S-\mathds{E}S))$
$\displaystyle\leq\int_{0}^{1}\mathds{E}\Phi\left(\pi\sum_{i=1}^{n}\delta_{i}(\alpha)d_{i}S(X)\right)\frac{\mathrm{d}\alpha}{\pi\sqrt{\alpha(1-\alpha)}}.$
(2.9)

###### Proof.

Firstly, without loss of generality, we may assume $\mathds{E}S=0$ (one may
check all the following results are true when one adds a constant to $S$).
Following [15], denoting by $\Phi^{*}$ the convex conjugate of $\Phi$, we note
that for any $x\in E$,

$\Phi(x)=\sup_{y\in E^{*}}\left(\langle y,x\rangle-\Phi^{*}(y)\right),$ (2.10)

and therefore, since the $X_{i}$’s only take a finite number of values,

$\mathds{E}(\Phi(S-\mathds{E}S))=\sup_{T\text{ is
}\sigma(X_{1},\dots,X_{n})-\text{measureable, taking values in }\in
E^{*}}\mathds{E}(\langle T,S\rangle-\Phi^{*}(T)).$ (2.11)

Now we bound the term $\mathds{E}(\langle T,S\rangle-\Phi^{*}(T))$. We write,
as in (2.2),

$\displaystyle\mathds{E}(\langle
T,S\rangle-\Phi^{*}(T))=-\int_{0}^{1}\frac{\mathrm{d}}{\mathrm{d}\alpha}\left(\mathds{E}(\langle
T,S(X^{(\alpha)})\rangle\right)\mathrm{d}\alpha-\mathds{E}\Phi^{*}(T)),$
(2.12)

and just like we obtained (2.3), we get

$\mathds{E}(\langle T,S\rangle-\Phi^{*}(T))=\int_{0}^{1}\mathds{E}(\langle
T,\sum_{i=1}^{n}S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}}))\rangle\mathrm{d}\alpha-\mathds{E}\Phi^{*}(T).$
(2.13)

Note that

$S(X^{(\alpha),i})-S(X^{(\alpha),\hat{i}})=d_{i}S(X^{(\alpha),i})-d_{i}S(X^{(\alpha),\hat{i}}),$
(2.14)

and by independence,

$\displaystyle\mathds{E}(\langle T,d_{i}S(X^{(\alpha),\hat{i}})\rangle)$
$\displaystyle=0,$ (2.15)

so

$\mathds{E}(\langle
T,S\rangle-\Phi^{*}(T))=\sum_{i=1}^{n}\int_{0}^{1}\mathds{E}(\langle
T,d_{i}S(X^{(\alpha),i})\rangle\mathrm{d}\alpha-\mathds{E}\Phi^{*}(T).$ (2.16)

Now, let

$\delta_{i}(\alpha):=\frac{\mathds{1}_{U_{i}\geq\alpha}-(1-\alpha)}{\sqrt{\alpha(1-\alpha)}}=\frac{2(\mathds{1}_{U_{i}\geq\alpha}-1/2)-(1-2\alpha)}{2\sqrt{\alpha(1-\alpha)}},$
(2.17)

where the last equality is here to show that this is just a renormalized
random variable taking values in $\\{-1,1\\}$, much like the $\xi_{i}(t)$’s,
random variables with $\mathds{P}(\xi_{i}(t)=1)=(1+\mathrm{e}^{-t})/2$ and
$\mathds{P}(\xi_{i}(t)=-1)=(1-\mathrm{e}^{-t})/2$ introduced in [15]. We have:

$\displaystyle\mathds{E}(\langle
T,\delta_{i}(\alpha)d_{i}S(X^{(\alpha)})\rangle)$
$\displaystyle=\mathds{E}\left(\langle
T,\frac{\mathds{1}_{U_{i}\geq\alpha}d_{i}S(X^{(\alpha),i})-(1-\alpha)(\mathds{1}_{U_{i}\geq\alpha}d_{i}S(X^{(\alpha),i})+\mathds{1}_{U_{i}<\alpha}d_{i}S(X^{(\alpha),\hat{i}}))}{\sqrt{\alpha(1-\alpha)}}\rangle\right)$
(2.18) $\displaystyle=\mathds{E}\left(\langle
T,\frac{\alpha\mathds{1}_{U_{i}\geq\alpha}d_{i}S(X^{(\alpha),i})}{\sqrt{\alpha(1-\alpha)}}\rangle\right)$
(2.19) $\displaystyle=\mathds{E}\left(\langle
T,\sqrt{\alpha(1-\alpha)}d_{i}S(X^{(\alpha),i})\rangle\right),$ (2.20)

hence, with (2.16) we get:

$\displaystyle\mathds{E}(\langle T,S\rangle-\Phi^{*}(T))$
$\displaystyle=\sum_{i=1}^{n}\int_{0}^{1}\frac{\mathds{E}(\langle
T,\delta_{i}(\alpha)d_{i}S(X^{(\alpha)})\rangle)}{\sqrt{\alpha(1-\alpha)}}\mathrm{d}\alpha-\mathds{E}\Phi^{*}(T)$
(2.21) $\displaystyle=\int_{0}^{1}\mathds{E}(\langle
T,\pi\sum_{i=1}^{n}\delta_{i}(\alpha)d_{i}S(X^{(\alpha)})\rangle)-\mathds{E}\Phi^{*}(T)\frac{\mathrm{d}\alpha}{\pi\sqrt{\alpha(1-\alpha)}}$
(2.22)
$\displaystyle\leq\int_{0}^{1}\mathds{E}\Phi\left(\pi\sum_{i=1}^{n}\delta_{i}(\alpha)d_{i}S(X^{(\alpha)})\right)\frac{\mathrm{d}\alpha}{\pi\sqrt{\alpha(1-\alpha)}}.$
(2.23)

Note that $(U_{1},\dots,U_{n},X^{(\alpha)}_{1},\dots,X^{(\alpha)}_{n})$ has
the same distribution as $(U_{1},\dots,U_{n},X_{1},\dots,X_{n})$, so

$\displaystyle\mathds{E}(\langle T,S\rangle-\Phi^{*}(T))$
$\displaystyle\leq\int_{0}^{1}\mathds{E}\Phi\left(\pi\sum_{i=1}^{n}\delta_{i}(\alpha)d_{i}S(X)\right)\frac{\mathrm{d}\alpha}{\pi\sqrt{\alpha(1-\alpha)}}.$
(2.24)

Recalling (2.11), the result follows. ∎

Let us see how the above allows us to recover the main results of [15], for
Rademacher random variables. We recall the notation in use in [15]: for
$x\in\\{-1,1\\}^{n}$, let

$D_{i}S(x):=\frac{S(x_{1},\dots,x_{i},\dots,x_{n})-S(x_{1},\dots,-x_{i},\dots,x_{n})}{2}.$
(2.25)

We may now state the corollary, in the Rademacher case:

######  Corollary 2.2.

In particular, if $X_{i}$’s follow a Rademacher distribution,

$\displaystyle\mathds{E}(\Phi(S-\mathds{E}S))$
$\displaystyle\leq\int_{0}^{1}\mathds{E}\Phi\left(\pi\sum_{i=1}^{n}\delta_{i}(\alpha)D_{i}S(X)\right)\frac{\mathrm{d}\alpha}{\pi\sqrt{\alpha(1-\alpha)}},$
(2.26)

so with a change of variable we get [15, Theorem 1.2], with a different $\xi$
and the constant $\pi$ instead of $\pi/2$ in $\Phi$:

$\displaystyle\mathds{E}(\Phi(S-\mathds{E}S))$
$\displaystyle\leq\int_{0}^{+\infty}\mathds{E}\Phi\left(\pi\sum_{i=1}^{n}\delta_{i}(\mathrm{e}^{-2t})D_{i}S(X)\right)\frac{2\mathrm{d}t}{\pi\sqrt{\mathrm{e}^{2t}-1}}.$
(2.27)

###### Proof.

Since $\mathds{E}^{(i)}S$ does not depend on $x_{i}$,

$\displaystyle D_{i}S(x)$
$\displaystyle=\frac{(S-\mathds{E}^{(i)}S)(x_{1},\dots,x_{i},\dots,x_{n})-(S-\mathds{E}^{(i)}S)(x_{1},\dots,-x_{i},\dots,x_{n})}{2}$
$\displaystyle=\frac{d_{i}S(x_{1},\dots,x_{i},\dots,x_{n})-d_{i}S(x_{1},\dots,-x_{i},\dots,x_{n})}{2}$
$\displaystyle=d_{i}S(x),$

the last equality coming from the fact that
$d_{i}S(x_{1},\dots,1,\dots,x_{n})=-d_{i}S(x_{1},\dots,-1,\dots,x_{n})$ since
$\mathds{E}^{(i)}(d_{i}S(X))=0$.

∎

The above implies a slightly weaker [15, Theorem 1.2], i.e., with a different
absolute constant, but the fact that Enflo type and Rademacher type coincide
still follows from Theorem 2.1 just as it follows from [15, Theorem 1.4] with,
as indicated there, a routine symmetrization argument.

To make the connection complete, recall the additional notations in [15]: the
operator $\Delta$ is defined by

$\Delta:=\sum_{i=1}^{n}D^{i},$ (2.28)

and the semigroup $P_{t}$ is defined as

$P_{t}:=\mathrm{e}^{-t\Delta}.$ (2.29)

In the case where the $X_{i}$’s are Rademacher random variables, the crucial
observation in [15] is that (we denote by $\xi^{\prime}$, $\delta^{\prime}$
the variables $\xi$, $\delta$ introduced there, to avoid any confusion with
$\delta$ previously defined):

$-\frac{\mathrm{d}P_{t}S}{\mathrm{d}t}=\frac{1}{\sqrt{\mathrm{e}^{2t}-1}}\mathds{E}_{\xi^{\prime}(t)}\left(\sum_{i=1}^{n}\delta^{\prime}_{i}(t)D_{i}S(\xi^{\prime}(t)X)\right),$
(2.30)

where $\xi^{\prime}(t)X$ is defined as
$(\xi^{\prime}_{1}(t)X_{1},\dots,\xi^{\prime}_{n}(t)X_{n})$.

Something similar holds in a more general framework (when the
$X_{i}^{\prime}s$ are random variables taking a finite number of values):

######  Theorem 2.3.

With the same assumptions as in Theorem 2.1,

$-\frac{\mathrm{d}\mathds{E}_{X^{\prime},U}S(X^{(\alpha)})}{\mathrm{d}\alpha}=\frac{1}{\sqrt{\alpha(1-\alpha)}}\mathds{E}_{X^{\prime},U}\left(\sum_{i=1}^{n}\delta_{i}(\alpha)d_{i}S(X^{(\alpha)})\right).$
(2.31)

###### Proof.

This is essentially the same proof as Theorem 2.1. ∎

We conclude this section with a remark on the Talagrand $L_{1}-L_{2}$
inequality in Banach spaces of Rademacher type 2.

As noted in [5], it is natural, to try and understand for which Banach spaces
$(E,\|\cdot\|_{E})$ there exists $C=C(E)>0$ such that for any function
function $S$ of Rademacher random variables $X_{1},\dots,X_{n}$ taking values
in $E$,

$\|S-\mathds{E}S\|_{E,2}^{2}\leq
C\sigma(S)\sum_{i=1}^{n}\frac{\|D_{i}S\|_{E,2}^{2}}{1+\log\left(\frac{\|D_{i}S\|_{E,2}}{\|D_{i}S\|_{E,1}}\right)},$
(2.32)

where $\|\cdot\|_{E,k}=\left(\mathds{E}\|\cdot\|_{E}^{k}\right)^{1/k}$, which
is a generalization of Talagrand’s $L_{1}-L_{2}$ inequality (see Theorem 3.7)
to Banach spaces.

Clearly, if a Banach space satisfies (2.32), it must be Rademacher type 2. It
is still unknown whether or not the converse is true. The best result, to
date, is:

######  Theorem 2.4 ([5, Theorem 1]).

Let $(E,\|\cdot\|_{E})$ be a Banach space with Rademacher type 2. Then there
there exists $C=C(E)>0$ such that for any function function $S$ of Rademacher
random variables $X_{1},\dots,X_{n}$ taking values in $E$,

$\|S-\mathds{E}S\|_{E,2}^{2}\leq
C\sigma(S)\sum_{i=1}^{n}\frac{\|D_{i}S\|_{E,2}^{2}}{1+\log\left(\frac{\|D_{i}S\|_{E,2}}{\|D_{i}S\|_{E,1}}\right)},$

where
$\sigma(S)=\max_{i\in\\{1,\dots,n\\}}\log\left(1+\log\left(\frac{\|D_{i}S\|_{E,2}}{\|D_{i}S\|_{E,1}}\right)\right)$.

It is still unclear whether or not the logarithmic term $\sigma(S)$ is needed
or not, but we now show how hypercontractivity comes short to removing it.

As noted in [5], one may apply (2.30) to $P_{t}S$ instead of $S$ (for a fixed
$t$), while the chain rule and semigroup property give:

$-\frac{\mathrm{d}P_{2t}S}{\mathrm{d}t}=\frac{2}{\sqrt{\mathrm{e}^{2t}-1}}\mathds{E}_{\xi^{\prime}(t)}\left(\sum_{i=1}^{n}\delta^{\prime}_{i}(t)D_{i}P_{t}S(\xi^{\prime}(t)X)\right).$
(2.33)

Hence, using the fact that $E$ is Rademacher type 2, if we denote by $K$ its
constant, we get (see e.g. [5, (57)]):

$\|S-\mathds{E}S\|_{E,2}\leq
4K\int_{0}^{+\infty}\left(\sum_{i=1}^{n}\|D_{i}P_{t}S\|_{E,2}^{2}\right)^{1/2}\frac{\mathrm{d}t}{\sqrt{\mathrm{e}^{2t}-1}}.$
(2.34)

We now show that in some cases hypercontractivity may not be enough to get rid
of the factor $\sigma(S)$. More precisely, let

$I=\int_{0}^{+\infty}\left(\sum_{i=1}^{n}\|D_{i}S\|_{E,2}^{2}\left(\frac{\|D_{i}S\|_{E,1}}{\|D_{i}S\|_{E,2}}\right)^{2\frac{1-\mathrm{e}^{-2t}}{1+\mathrm{e}^{-2t}}}\right)^{1/2}\frac{\mathrm{d}t}{\sqrt{\mathrm{e}^{2t}-1}},$
(2.35)

which is the upper bound on the right term of (2.34) one gets using
hypercontractivity.

We let
$L_{i}=\log\left(\mathrm{e}\frac{\|D_{i}S\|_{E,2}}{\|D_{i}S\|_{E,1}}\right)$,
$d_{i}=\|D_{i}S\|_{E,2}$ and
$\theta(t)=\frac{1-\mathrm{e}^{-2t}}{1+\mathrm{e}^{-2t}}$, so

$I\sim\int_{0}^{+\infty}\left(\sum_{i=1}^{n}d_{i}^{2}\mathrm{e}^{-2L_{i}\theta(t)}\right)^{1/2}\frac{\mathrm{d}t}{\sqrt{\mathrm{e}^{2t}-1}}.$
(2.36)

With a change of variable,

$\displaystyle I$
$\displaystyle\sim\int_{0}^{1}\left(\sum_{i=1}^{n}d_{i}^{2}\mathrm{e}^{-2L_{i}\theta}\right)^{1/2}\frac{\mathrm{d}\theta}{\sqrt{\theta(1-\theta)}}$
$\displaystyle\sim\int_{0}^{1/2}\left(\sum_{i=1}^{n}d_{i}^{2}\mathrm{e}^{-2L_{i}\theta}\right)^{1/2}\frac{\mathrm{d}\theta}{\sqrt{\theta}}+\frac{\mathrm{e}^{-1}}{\sqrt{2}}\int_{1/2}^{1}\frac{\mathrm{d}\theta}{\sqrt{1-\theta}}\sqrt{\sum_{i=1}^{n}\frac{d_{i}^{2}}{L_{i}}},$

so bounding $\frac{I^{2}}{\sum_{i=1}^{n}d_{i}^{2}/L_{i}}$ (we already know it
is bounded by $\sigma(S)$) is equivalent to bounding

$R:=\frac{\int_{0}^{1/2}\left(\sum_{i=1}^{n}d_{i}^{2}\mathrm{e}^{-2L_{i}\theta}\right)^{1/2}\frac{\mathrm{d}\theta}{\sqrt{\theta}}}{\sqrt{\sum_{i=1}^{n}d_{i}^{2}/L_{i}}}.$
(2.37)

Letting $\lambda_{i}:=\frac{d_{i}^{2}/L_{i}}{\sum_{i=1}^{n}d_{i}^{2}/L_{i}}$,
we get

$R=\sqrt{2}\int_{0}^{1/2}\left(\sum_{i=1}^{n}\lambda_{i}L_{i}\mathrm{e}^{-L_{i}\theta}\right)^{1/2}\frac{\mathrm{d}\theta}{\sqrt{\theta}}.$
(2.38)

Assume $L_{i}=2^{i-1}$, $\lambda_{i}=1/n$. Then for any
$\theta\in(1/2^{n},1)$, there exists $i_{0}\in\\{1,\dots,n\\}$ such that
$1/2^{i_{0}}\leq\theta\leq 1/2^{i_{0}-1}$, and

$\displaystyle\left(\sum_{i=1}^{n}\lambda_{i}L_{i}\mathrm{e}^{-L_{i}\theta}\right)^{1/2}\geq\left(\lambda_{i_{0}}L_{i_{0}}\mathrm{e}^{-L_{i_{0}}\theta}\right)^{1/2}\geq\left(\frac{L_{i_{0}}\theta\mathrm{e}^{-L_{i_{0}}\theta}}{n\theta}\right)^{1/2}\geq\frac{\sqrt{2\mathrm{e}^{-2}}}{\sqrt{n\theta}},$

so

$\displaystyle
R\geq\frac{2\sqrt{\mathrm{e}^{-2}}}{\sqrt{n}}\int_{1/2^{n}}^{1}\frac{\mathrm{d}\theta}{\theta}\geq
2\sqrt{\mathrm{e}^{-2}}\log(2)\sqrt{n}\geq\frac{2\sqrt{\mathrm{e}^{-2}}}{\log(2)}\sqrt{\max_{i\in\\{1,\dots,n\\}}L_{i}}.$

Thus in this case, $\frac{I^{2}}{\sum_{i=1}^{n}d_{i}^{2}/L_{i}}$ is lower
bounded by $C\sigma(S)$, for some constant $C>0$.

##  3 Some applications

To finish these notes, we present some applications of the above inequalities
to various contexts, in particular to lower-bounding the variance of the
length of the longest common subsequences between two random words. For
$(x_{1},\dots,x_{s})$, $(y_{1},\dots,y_{t})$ two sequences taking values in a
finite set $\mathcal{A}$, we denote by $LCS(x_{1}\dots x_{s};y_{1}\dots
y_{t})$ the largest integer $k$ such that there exists $1\leq
i_{1}<\dots<i_{k}\leq s$, $1\leq j_{1}<\dots<j_{k}\leq t$ satisfying
$a_{i_{1}}=b_{j_{1}},\dots,a_{i_{k}}=b_{j_{k}}$, or $0$ if there is no such
integer. For example, $LCS(01001;01011)=4$ because one subsequence with
maximal length is $0101$. In the sequel, we take $\mathcal{A}=\\{1,\dots,m\\}$
(for some $m$ we specify in each case), $X_{1},\dots,X_{n},Y_{1},\dots,Y_{n}$
i.i.d. random variables taking values in $\mathcal{A}$ (according to a
distribution we specify), and consider the length of the longest common
subsequences of these two random words, $LCS(X_{1}\dots X_{n};Y_{1}\dots
Y_{n})$, written simply $LC_{n}$.

###  3.1 Iterated gradients and Gaussian (in)equalities

It is well known that one can transfer the finite samples results of the
previous section to functions of normal random variables, somehow reversing
the analogies between iterated jackknives and iterated gradients first
unveiled in [7]. This transfer is then followed by a study of the infinitely
divisible framework and by the semigroup approach to these inequalities.

Let $Z$ be a standard random variable and $G$ be an absolutely continuous
function. As well known, the Gaussian Poincaré inequality asserts that

${\textrm{Var}}\,G(Z)\leq\mathds{E}\left(G^{\prime}(Z)^{2}\right),$ (3.1)

while in [9], this inequality is generalized with higher order gradients.

Lemma 1.4 and Proposition 1.5 allows us to quickly recover Gaussian results.
Indeed, e.g., see [2] in the case $k=1$, one can infer from the discrete
decomposition of the variance a decomposition for ${\textrm{Var}}\,G(Z)$.

######  Lemma 3.1.

Let $G$ be a real-valued $m$-times continuously differentiable function, such
that $\mathds{E}\left(G^{(k)}(Z)^{2}\right)<+\infty$, $k=0,\dots,m$. Let
$X_{1},\dots,X_{n},X^{\prime}_{1},\dots,X^{\prime}_{n}$ be independent
Rademacher random variables and let
$S(X_{1},\dots,X_{n})\\!:=G\left(\frac{X_{1}+\dots+X_{n}}{\sqrt{n}}\right)$.
Then for all $k\in\\{1,\dots,m\\}$,

$J_{k}(n)\xrightarrow[n\to+\infty]{}\mathds{E}\left(G^{(k)}(Z)^{2}\right)\quad\text{and}\quad
K_{k}(n)\xrightarrow[n\to+\infty]{}\left(\mathds{E}\left(G^{(k)}(Z)\right)\right)^{2}.$
(3.2)

###### Proof.

It is enough to prove the theorem for $G$ $m+1$-times continuously
differentiable with compact support. From (1.8), we have

$J_{k}=k!{n\choose k}D^{k-1}B_{1},$

so (using (1.7)),

$J_{k}=k!{n\choose
k}\mathds{E}\frac{1}{2^{k}n!}\sum_{i\in\mathfrak{S}_{n}}\left(\Delta_{i_{1},\dots,i_{k}}S\right)^{2}.$

By symmetry of the function
$S(X_{1},\dots,X_{n})=G\left(\frac{X_{1}+\dots+X_{n}}{\sqrt{n}}\right)$, this
simplifies to

$J_{k}=k!{n\choose
k}\mathds{E}\frac{1}{2^{k}}\left(\Delta_{1,\dots,k}S\right)^{2}.$ (3.3)

For any $i\in\\{1,\dots,k\\}$,

$\Delta_{i}S=(D_{i}S)2\mathds{1}_{X_{i}=X^{\prime}_{i}}$

with

$D_{i}S(x):=\frac{S(x_{1},\dots,x_{i},\dots,x_{n})-S(x_{1},\dots,-x_{i},\dots,x_{n})}{2}.$

Iterating,

$\Delta_{1,\dots,k}S=(D_{1,\dots,k}S)2^{k}\mathds{1}_{X_{1}=X^{\prime}_{1},\dots,X_{k}=X^{\prime}_{k}},$

hence

$\mathds{E}\frac{1}{2^{k}}\left(\Delta_{1,\dots,k}S\right)^{2}=\mathds{E}\left(D_{1,\dots,k}S\right)^{2}.$
(3.4)

We now expand, for any $x\in\\{-1,1\\}^{n}$, $D_{1,\dots,k}S(x)$. Let us
denote for $A\subset\\{1,\dots,k\\}$,

$x^{A}:=(2\mathds{1}_{1\in A}-1,\dots,2\mathds{1}_{k\in
A}-1,x_{k+1},\dots,x_{n}).$

It is straightforward to prove by induction that

$D_{1,\dots,k}S(x)=(-1)^{|i\in\\{1,\dots,k\\}:x_{i}=1|}\frac{1}{2^{k}}\sum_{A\subset\\{1,\dots,k\\}}(-1)^{|A|}S(x^{A}),$

which simplifies to

$D_{1,\dots,k}S(x)=(-1)^{|i\in\\{1,\dots,k\\}:x_{i}=1|}\frac{1}{2^{k}}\sum_{i=0}^{k}{k\choose
i}(-1)^{i}G\left(\frac{2i-k+x_{k+1}+\dots+x_{n}}{\sqrt{n}}\right).$

By Taylor’s formula, and using the fact that $\sum_{i=0}^{k}{k\choose
i}(-1)^{i}i^{\ell}/\ell!=(-1)^{k}\mathds{1}_{\ell=k}$ for any
$\ell\in\\{0,\dots,k\\}$, we get that

$\left|D_{1,\dots,k}S(x)\right|=\left|\frac{1}{\sqrt{n}^{k}}G^{(k)}\left(\frac{-k+x_{k+1}+\dots+x_{n}}{\sqrt{n}}\right)\right|+\mathcal{O}\left(\frac{1}{\sqrt{n}^{k+1}}\right),$

with $\mathcal{O}$ uniform in $x$ (thanks to the compact support assumption).
This leads to

$\mathds{E}n^{k}\left(D_{1,\dots,k}S\right)^{2}\xrightarrow[n\to\infty]{}\mathds{E}\left(G^{(k)}(Z)\right)^{2},$

and using (3.3) and (3.4), we get the desired result

$\mathds{E}J_{k}(n)\xrightarrow[n\to\infty]{}\mathds{E}\left(G^{(k)}(Z)\right)^{2}.$

The other limit in the theorem is obtained in a very similar fashion. ∎

We now see, using (1.14) and (1.15), that for any fixed $k\geq 1$,

$B_{k}(n)\sim_{n\to+\infty}\frac{1}{n}\mathds{E}\left(G^{\prime}(Z)^{2}\right)\quad\text{and}\quad
B_{n-k}(n)\sim_{n\to+\infty}\frac{1}{n}\left(\mathds{E}\left(G^{\prime}(Z)\right)\right)^{2}.$

More generally, for any $a\in(0,1)$,

$B_{\lfloor
an\rfloor}(n)\sim_{n\to+\infty}\frac{1}{n}\sum_{i=0}^{\infty}\frac{a^{j}(-1)^{j}}{j!}\mathds{E}\left(G^{(j+1)}(Z)^{2}\right).$

Note that

$\int_{0}^{1}B_{\lfloor
an\rfloor}(n)\mathrm{d}a\xrightarrow[n\to+\infty]{}\sum_{i=0}^{\infty}\frac{(-1)^{j}}{(j+1)!}\mathds{E}\left(G^{(j+1)}(Z)^{2}\right)={\textrm{Var}}\,G(Z),$

as one could expect.

######  Proposition 3.2.

Under the same assumptions on $G$, for all $k\in\\{1,\dots,m-1\\}$,

$\frac{\left(\mathds{E}\left(G^{(k+1)}(Z)\right)\right)^{2}}{(k+1)!}\leq(-1)^{k}\left({\textrm{Var}}\,G(Z)-\mathds{E}\left(G^{\prime}(Z)^{2}\right)+\dots+(-1)^{k}\frac{\mathds{E}\left(G^{(k)}(Z)^{2}\right)}{k!}\right)\leq\frac{\mathds{E}\left(G^{(k+1)}(Z)^{2}\right)}{(k+1)!}.$
$\frac{\left(\mathds{E}\left(G^{(k+1)}(Z)\right)\right)^{2}}{(k+1)!}\leq{\textrm{Var}}\,G(Z)-\left(\mathds{E}\left(G^{\prime}(Z)\right)\right)^{2}-\frac{\left(\mathds{E}\left(G^{\prime\prime}(Z)\right)\right)^{2}}{2}-\dots-\frac{\left(\mathds{E}\left(G^{(k)}(Z)\right)\right)^{2}}{k!}\leq\frac{\mathds{E}\left(G^{(k+1)}(Z)^{2}\right)}{(k+1)!}.$

The above indicates that the difference between the variance and each partial
sum is squeezed between the Cauchy-Schwarz inequality. We may also get
equalities, when $G$ is infinitely differentiable, with additional conditions.
Indeed,

######  Corollary 3.3.

Let $G$ be a real-valued infinitely-differentiable function, such that, for
all $k\geq 0$, $\mathds{E}(G^{(k)}(Z))^{2}<+\infty$. Then,

${\textrm{Var}}\,G(Z)=\sum_{i=1}^{+\infty}(-1)^{i-1}\frac{\mathds{E}\left(G^{(i)}(Z)^{2}\right)}{i!},$

if and only if $\lim_{k\to\infty}\mathds{E}(G^{(k)}(Z))^{2}/k!=0$, and under
such a condition,

${\textrm{Var}}\,G(Z)=\sum_{i=1}^{+\infty}\frac{\left(\mathds{E}\left(G^{(i)}(Z)\right)\right)^{2}}{i!}.$

For any $k\geq 1$,

$VarG(Z)=\mathds{E}\left(G^{\prime}(Z)^{2}\right)-\frac{\mathds{E}\left(G^{\prime\prime}(Z)^{2}\right)}{2}+\dots+(-1)^{k-1}\frac{\mathds{E}\left(G^{(k)}(Z)^{2}\right)}{k!}+(-1)^{k}\sum_{j=k+1}^{\infty}{j-1\choose
k}\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!}.$ (3.5)

For any $a\in[0,1]$,

${\textrm{Var}}\,G(Z)=\sum_{i=1}^{+\infty}\left((-1)^{i-1}a^{i}\frac{\mathds{E}\left(G^{(i)}(Z)^{2}\right)}{i!}+(1-a)^{i}\frac{\left(\mathds{E}\left(G^{(i)}(Z)\right)\right)^{2}}{i!}\right).$
(3.6)

###### Proof.

This is nothing but Lemma 3.1 together with Proposition 1.5. To get the last
equality, apply (1.23) to $k=\lfloor an\rfloor$. ∎

The equality (3.5) is a generalization of the equality in [3], where $k=1$.
Note that (3.6) can be rewritten as

${\textrm{Var}}\,G(Z)=\sum_{i=1}^{+\infty}\frac{\left(\mathds{E}\left(G^{(i)}(Z)\right)\right)^{2}}{i!}+\sum_{i=1}^{+\infty}\left((-1)^{i-1}\frac{\mathds{E}\left(G^{(i)}(Z)^{2}\right)}{i!}+\sum_{j\geq
i}(-1)^{i}{j\choose
i}\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!}\right)a^{i},$

which gives us the additional equality: for all $i\geq 1$,

$\frac{\mathds{E}\left(G^{(i)}(Z)^{2}\right)}{i!}=\sum_{j\geq i}{j\choose
i}\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!}.$

This gives an alternative way to find (3.1) again:

$\displaystyle\sum_{i=k+1}^{+\infty}(-1)^{i-1}\frac{\mathds{E}\left(G^{(i)}(Z)^{2}\right)}{i!}$
$\displaystyle=\sum_{j\geq i\geq k+1}(-1)^{i-1}{j\choose
i}\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!}$
$\displaystyle=\sum_{j=k+1}^{+\infty}\left(\sum_{i=k+1}^{j}(-1)^{i-1}{j\choose
i}\right)\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!}$
$\displaystyle=\sum_{j=k+1}^{+\infty}{j-1\choose
k}\frac{\left(\mathds{E}\left(G^{(j)}(Z)\right)\right)^{2}}{j!},$

where the last equality comes from a simple formula for the partial alternate
sum of binomial coefficients.

Multivariable versions of the above results remain true, and in fact, so do
infinite-dimensional ones on Wiener space or Poisson space or even Fock space.
In each case, what is needed is a proper definition of the gradient, e.g., see
[13] for some infinite dimensional setting (Wiener and Poisson spaces). In the
multivariate setting here is a small sample of results which can be easily
obtained via the techniques developed to this point: Let $m\geq 1$, let
$G:\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a smooth function (for the sake of
simplicity, just assume differentiability up to the correct order, as above),
and let $Z_{1},\dots,Z_{m}$ be i.i.d. standard normal random variables. Now,
for $k\geq 1$, let

$\theta_{k}=\sum_{1\leq i_{1},\dots,i_{k}\leq
m}\left(\mathds{E}\left(\frac{\partial^{k}G}{\partial x_{i_{1}}\dots
x_{i_{k}}}(Z_{1},\dots,Z_{m})\right)\right)^{2},$

and let

$\eta_{k}=\sum_{1\leq i_{1},\dots,i_{k}\leq
m}\left(\mathds{E}\left(\frac{\partial^{k}G}{\partial x_{i_{1}}\dots
x_{i_{k}}}(Z_{1},\dots,Z_{m})\right)^{2}\right).$

Let further $(X_{i,j})_{i\in\\{1,\dots,m\\},j\in\\{1,\dots,n\\}}$ be
independent Rademacher random variables and let

$S(X_{1,1},\dots,X_{m,n}):=G\left(\frac{X_{1,1}+\dots+X_{1,n}}{\sqrt{n}},\dots,\frac{X_{m,1}+\dots+X_{m,n}}{\sqrt{n}}\right).$

Then for all $k\geq 1$,

$J_{k}(n)\xrightarrow[n\to+\infty]{}\eta_{k}\quad\text{and}\quad
K_{k}(n)\xrightarrow[n\to+\infty]{}\theta_{k}.$

Moreover, for all $k\geq 1$,

$\frac{\theta_{k+1}}{(k+1)!}\leq(-1)^{k}\left({\textrm{Var}}\,G(Z_{1},\dots,Z_{m})-\eta_{1}+\frac{\eta_{2}}{2}-\dots+(-1)^{k}\frac{\eta_{k}}{k!}\right)\leq\frac{\eta_{k+1}}{(k+1)!}.$
$\frac{\theta_{k+1}}{(k+1)!}\leq{\textrm{Var}}\,G(Z_{1},\dots,Z_{m})-\theta_{1}-\frac{\theta_{2}}{2}-\dots-\frac{\theta_{k}}{k!}\leq\frac{\eta_{k+1}}{(k+1)!}.$

######  Remark 3.4.

It is well known that if $Z_{1},Z_{2},\dots,Z_{m}$ are iid standard normal
random variables, and if $\|Z\|_{2}^{2}:=\sum_{k=1}^{m}Z_{k}^{2}$, then
$\left(Z_{1}/\|Z\|_{2},\dots,Z_{m}/\|Z\|_{2}\right)$ is uniformly distributed
on the $m-1$-dimensional unit sphere. Therefore, the above multivariate
Gaussian case allows to recover and extend various variance bounds and
covariance representations on the high-dimensional sphere.

###  3.2 The Infinitely divisible case

Let $Y$ be an infinitely divisible real-valued random variable, and
$G:\mathbb{R}\rightarrow\mathbb{R}$ be a smooth function such that its
derivatives of all order are well defined and
$\mathds{E}\left(G^{(k)}(Y)\right)^{2}<+\infty$ for all $k\geq 0$. We are
interested in the decomposition of the variance of $G(Y)$.

We let $(Y_{t})_{t\geq 1}$ be the corresponding Lévy process (i.e. $Y_{1}$ has
the same distribution as $Y$), we denote by $(b,\sigma,\nu)$ its generator
(from the Lévy–Khintchine representation), and let $(Y^{\prime}_{t})_{t\geq
0}$,$(Y^{\prime\prime}_{t})_{t\geq 0}$ be independent copies of
$(Y_{t})_{t\geq 0}$. For $1\leq{\ell},m$, let

$\displaystyle X_{{\ell},m}$ $\displaystyle=Y_{{\ell}/m}-Y_{({\ell}-1)/m},$
(3.7) $\displaystyle X^{\prime}_{{\ell},m}$
$\displaystyle=Y^{\prime}_{{\ell}/m}-Y^{\prime}_{({\ell}-1)/m},$ (3.8)

and let

$S_{n}=G(X_{1,n}+\dots+X_{n,n}).$ (3.9)

We now study, for any fixed $\alpha\in(0,1)$, the limit when $m$ goes to
infinity of $nB_{\lfloor\alpha n\rfloor}$ (the $B_{k}$’s of $S_{n}$) where
$n=2^{m}+1$, which allows us to recover in another way the representation of
the variance from [14].

######  Theorem 3.5.

Let $\alpha\in(0,1)$. Then with the notations above,

$2^{m}B_{\lfloor\alpha(2^{m})\rfloor+1}\xrightarrow[m\to\infty]{}\mathds{E}\left(\sigma
G^{\prime}(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})G^{\prime}(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})+\int_{\mathbb{R}}\Delta_{u}G(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})\Delta_{u}G(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\mathrm{d}\nu\right),$
(3.10)

where $\Delta_{u}G(x)=G(x+u)-G(x)$.

###### Proof.

We first prove this fact for $\alpha$ a dyadic rational number,
$\alpha=a/2^{b}\in(0,1)$. Let $m\geq b$ and $n=2^{m}$, with $m\geq b$. The
proof is more convenient to write for a slightly different function: instead
of computing the $B_{k}$’s of $S_{n}$ ($n=2^{m}$), we compute the $B_{k}$’s of

$T_{n}:=G(X_{1,n}+\dots+X_{n,n}+X_{n+1,n}).$ (3.11)

Since the difference between the former and latest has order
$\mathcal{O}(1/n)$, this is enough to get the desired result. We have

$\displaystyle B_{\lfloor\alpha n\rfloor+1}$
$\displaystyle=\mathds{E}\leavevmode\resizebox{390.25534pt}{}{$\left(G\left(\sum_{i=1}^{n+1}X_{i,n}\right)\left(G\left(X_{1}+\sum_{i=2}^{2^{m-b}a+1}X^{\prime}_{i,n}+\sum_{i=2^{m-b}a+2}^{n+1}X_{i,n}\right)-G\left(\sum_{i=1}^{2^{m-b}a+1}X^{\prime}_{i,n}+\sum_{i=2^{m-b}a+2}^{n+1}X_{i,n}\right)\right)\right)$}$
$\displaystyle=\mathds{E}\left(G(Z_{1/n}+Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\left(G(Z_{1/n}+Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})-G(Z^{\prime}_{1/n}+Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\right)\right),$

where $Z$ and $Z^{\prime}$ are two independent copies of $Y$, since
$(Z_{1/n},Z^{\prime}_{1/n},Y_{\alpha},Y^{\prime}_{\alpha},Y^{\prime\prime}_{1-\alpha})$
has the same distribution as
$(X_{1},X^{\prime}_{1},\sum_{i=2}^{2^{m-b}a+1}X_{i,n},\sum_{i=2}^{2^{m-b}a+1}X^{\prime}_{i,n},\sum_{i=2^{m-b}a+2}^{n+1}X_{i,n})$.

Let
$G_{\alpha,1}(\cdot)=\mathds{E}(G(\cdot+Y_{\alpha}+Y^{\prime\prime}_{\alpha})|Y_{\alpha},Y^{\prime\prime}_{1-\alpha})$
and
$G_{\alpha,2}(\cdot)=\mathds{E}(G(\cdot+Y_{\alpha}+Y^{\prime\prime}_{\alpha})|Y^{\prime}_{\alpha},Y^{\prime\prime}_{1-\alpha})$,
we then have

$\displaystyle B_{\lfloor\alpha n\rfloor+1}$
$\displaystyle=\mathds{E}\left(G_{\alpha,1}(Z_{1/n})G_{\alpha,2}(Z_{1/n})-G_{\alpha,1}(0)G_{\alpha,2}(0)-(G_{\alpha,1}(Z_{1/n})G_{\alpha,2}(Z^{\prime}_{1/n})-G_{\alpha,1}(0)G_{\alpha,2}(0))\right),$

so if $A_{1}$ be the infinitesimal generator of $(Y_{t},Y_{t})_{t\geq 0}$ and
$A_{0}$ is the infinitesimal generator of $(Y_{t},Y^{\prime}_{t})_{t\geq 0}$,
then

$\displaystyle nB_{\lfloor\alpha n\rfloor+1}\xrightarrow[n\to\infty]{}$
$\displaystyle\,\mathds{E}\left((A_{1}-A_{0})G_{\alpha,1}\otimes
G_{\alpha,2}(0,0)\right)$ (3.12) $\displaystyle=\mathds{E}\left(\sigma
G^{\prime}(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})G^{\prime}(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})+\int_{\mathbb{R}}\Delta_{u}G(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})\Delta_{u}G(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\mathrm{d}\nu\right),$
(3.13)

since $(A_{1}-A_{0})(f\otimes g)(0,0)=\sigma
f^{\prime}(0)g^{\prime}(0)+\int_{\mathbb{R}}\Delta_{u}f(0)\Delta_{u}g(0)\mathrm{d}\nu$.
(This computation is in [14, Proposition 2].)

Since the finite sequence $B_{k}$ is non-decreasing, a routine density
argument shows that for any $\alpha\in(0,1)$, $nB_{\lfloor\alpha n\rfloor}$
has limit (3.13), which is the desired result. ∎

######  Corollary 3.6.

${\textrm{Var}}\,G(Y)=\int_{0}^{1}\mathds{E}\left(\sigma
G^{\prime}(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})G^{\prime}(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})+\int_{\mathbb{R}}\Delta_{u}G(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})\Delta_{u}G(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\mathrm{d}\nu\right)\mathrm{d}\alpha.$
(3.14)

This above representation of the variance stems from the decomposition
${\textrm{Var}}\,G(Y)=\sum_{k=1}^{n}B_{k}$ and it can also be found, with a
different approach, in [14]. Although we have only been concerned with
representations of the variance, similar representations continue to hold for
covariances in the spirit of the work just cited.

For example, we note that in the Poisson case, the limit (3.13) is simply

$\mathds{E}\left(DG(Y_{\alpha}+Y^{\prime\prime}_{1-\alpha})DG(Y^{\prime}_{\alpha}+Y^{\prime\prime}_{1-\alpha})\right),$
(3.15)

where $DG(x)=G(x+1)-G(x)$,
$Y_{\alpha},Y^{\prime}_{\alpha},Y^{\prime\prime}_{1-\alpha}$ are Poisson
distributed independent random variables (with respective parameter $\alpha$,
$\alpha$, and $1-\alpha$). In the Gaussian case, it is

$\mathds{E}\left(G^{\prime}(Z_{1,\alpha})G^{\prime}(Z_{2,\alpha})\right),$
(3.16)

where $Z_{1,\alpha}$, $Z_{2,\alpha}$ are Gaussian random variables centered
with variance one and covariance $1-\alpha$.

###  3.3 A weaker Talagrand $L_{1}-L_{2}$ inequality

Let us focus on the special case where the $X_{i}$’s are Bernoulli with
parameter $1/2$. For $i\in\\{1,\dots,n\\}$, let

$\tau_{i}S(X_{1},\dots,X_{n}):=S(X_{1},\dots,X_{i-1},0,X_{i+1},\dots,X_{n})-S(X_{1},\dots,X_{i-1},1,X_{i+1},\dots,X_{n})$

(so this does not depend on $X_{i}$). Then, Talagrand’s $L_{1}-L_{2}$
inequality can be stated as follows:

######  Theorem 3.7 ([19, Theorem 1.5]).

There exists $C>0$ such that for any function
$f:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, the following inequality holds

${\textrm{Var}}\,S\leq
C\sum_{i=1}^{n}\frac{\|\tau_{i}S\|_{2}^{2}}{1+\log\left(\frac{\|\tau_{i}S\|_{2}}{\|\tau_{i}S\|_{1}}\right)},$
(3.17)

where $S=f(X_{1},\dots,X_{n})$.

We now prove a weaker form of this inequality using the $B_{k}^{\prime}s$, in
the special case where there exists $a>0$ such that for all
$i\in\\{1,\dots,n\\}$, $|\tau_{i}S|\in\\{0,a\\}$. We can further assume
without loss of generality by rescaling that $a=1$. Note that this particular
case includes $LC_{n}$ (changing a letter can only change $LC_{n}$ by at most
one).

Firstly, conditioning on whether $X_{i_{k}}=X^{\prime}_{i_{k}}$ or
$X_{i_{k}}\neq X^{\prime}_{i_{k}}$, we can rewrite (1.5) as

$B_{k}=\mathds{E}\frac{1}{4n!}\sum_{i\in\mathfrak{S}_{n}}(\tau_{i_{k}}S)(\tau_{i_{k}}S)^{i_{1},\dots,i_{k-1}},$
(3.18)

so

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\sum_{k=1}^{n}\mathds{E}\frac{1}{4n!}\sum_{i\in\mathfrak{S}_{n}}(\tau_{i_{k}}S)(\tau_{i_{k}}S)^{i_{1},\dots,i_{k-1}}$
$\displaystyle=\frac{1}{4n!}\sum_{i\in\mathfrak{S}_{n}}\sum_{k=1}^{n}\mathds{E}(\tau_{i_{1}}S)(\tau_{i_{1}}S)^{i_{2},\dots,i_{k}}.$

Let us fix $i\in\mathfrak{S}_{n}$ and bound
$\sum_{k=1}^{n}\mathds{E}(\tau_{i_{1}}S)(\tau_{i_{1}}S)^{i_{2},\dots,i_{k}}$.
For ease of notation, by reindexing the $X_{i}$’s, we may assume $i=Id$, also,
let us write $X:=(X_{2},\dots,X_{n})$. Since, by assumption, $\tau_{1}S$ is
boolean, there exists $m\leq 2^{n-1}$ and
$x^{1},\dots,x^{m}\in\\{0,1\\}^{n-1}$ pairwise distinct such that
$|\tau_{1}S|=\sum_{i=1}^{m}\mathds{1}_{X=x^{i}}$. Let, for
$\alpha\subset\\{2,\dots,n\\}$,
$N(\alpha):=|\\{(i,j)\in\\{1,\dots,m\\}^{2}:\forall
k\in\alpha,x^{i}_{k}=x^{j}_{k}\\}|$. We have

$\mathds{E}(\tau_{1}S)(\tau_{1}S)^{2,\dots,k}\leq\mathds{E}|\tau_{1}S||\tau_{1}S|^{2,\dots,k}=\frac{N(\\{k+1,\dots,n\\})}{2^{n+k-2}}.$
(3.19)

Let ${\ell}\in\\{1,\dots,n-1\\}$ be such that $2^{{\ell}-1}\leq m\leq
2^{\ell}$ (we may exclude the trivial case $m=0$). Using that for any
$k\in\\{1,\dots,{\ell}\\}$, $N(\\{k+1,\dots,n\\})\leq m2^{k-1}$, and the
trivial bound $N(\\{k+1,\dots,n\\})\leq m^{2}$ when $k>{\ell}$, we get

$\displaystyle\sum_{k=1}^{n}\mathds{E}(\tau_{1}S)(\tau_{1}S)^{2,\dots,k}$
$\displaystyle\leq\sum_{k=1}^{\ell}\frac{m}{2^{n-1}}+\sum_{k=1+1}^{n}\frac{m^{2}}{2^{n+k-2}}$
$\displaystyle\leq{\ell}\frac{m}{2^{n-1}}+2\frac{m^{2}}{2^{n-1+{\ell}}}$
$\displaystyle\leq({\ell}+2)\frac{m}{2^{n-1}}=({\ell}+2)\|\tau_{1}S\|_{2}^{2}.$

Note that
$\log\left(\frac{\|\tau_{1}S\|_{2}}{\|\tau_{1}S\|_{1}}\right)=\log\left(\sqrt{\frac{2^{n-1}}{m}}\right)={\log(2)}(n-1-\log_{2}(m))/2$
so ${\ell}+2\leq
n+2-\frac{2}{\log(2)}\log\left(\frac{\|\tau_{1}S\|_{2}}{\|\tau_{1}S\|_{1}}\right)$
hence

$\sum_{k=1}^{n}\mathds{E}(\tau_{1}S)(\tau_{1}S)^{2,\dots,k}\leq\left(n+2-\frac{2}{\log(2)}\log\left(\frac{\|\tau_{1}S\|_{2}}{\|\tau_{1}S\|_{1}}\right)\right)\|\tau_{1}S\|_{2}^{2}.$
(3.20)

Finally,

$\displaystyle{\textrm{Var}}\,S$
$\displaystyle=\frac{1}{4n!}\sum_{i\in\mathfrak{S}_{n}}\sum_{k=1}^{n}\mathds{E}(\tau_{i_{1}}S)(\tau_{i_{1}}S)^{i_{2},\dots,i_{k}}$
$\displaystyle\leq\frac{1}{4n!}\sum_{i\in\mathfrak{S}_{n}}\left(n+2-\frac{2}{\log(2)}\log\left(\frac{\|\tau_{i_{1}}S\|_{2}}{\|\tau_{i_{1}}S\|_{1}}\right)\right)\|\tau_{i_{1}}S\|_{2}^{2}$
$\displaystyle\leq\sum_{j=1}^{n}\left(1+\frac{2}{n}-\frac{2}{n\log(2)}\log\left(\frac{\|\tau_{j}S\|_{2}}{\|\tau_{j}S\|_{1}}\right)\right)\|\tau_{j}S\|_{2}^{2}.$

To see that it is weaker than $L_{1}-L_{2}$ Talagrand’s inequality, consider
for example $X_{1},\dots,X_{n}$ independent Bernoulli variables of parameter
$1/2$, and $S$ defined on $\\{0,1\\}^{n}$ by $S(x_{1},\dots,x_{n}):=x_{1}\dots
x_{n/2}$ (assuming $n$ is even). Then, for any $j\in\\{1,\dots,n/2\\}$,
$\|\tau_{j}S\|_{1}=(1/2)^{\frac{n}{2}-1}$ and
$\|\tau_{j}S\|_{2}=\sqrt{\|\tau_{j}S\|_{1}}$. So on the one hand, Talagrand’s
inequality gives a bound of order $(1/2)^{\frac{n}{2}-1}$, which is optimal,
while on the other hand, our weaker bound gives an upper bound of order
$n(1/2)^{\frac{n}{2}-1}$.

###  3.4 An upper bound on the variance of the length of the longest common
subsequences

We got the upper bound for the variance ${\textrm{Var}}\,S\leq nB_{1}$, which
was already known in [18]. Let us apply it to $LC_{n}$, and then improve it.

Let $Z_{1},\dots,Z_{2n}$ be $i.i.d.$ Bernoulli random variables of parameter
$1/2$, and consider the $B_{k}$’s of the function
$S(Z_{1},\dots,Z_{2n}):=LCS(Z)=LC_{n}$. We know that
${\textrm{Var}}\,LC_{n}\leq 2nB_{1}(2n)$. Using (3.18), $B_{1}(2n)\leq 1/4$ so
${\textrm{Var}}\,LC_{n}\leq n/2$ (see also [11]). But this bound can be
improved: note that by symmetry of the zeros and ones in $LC_{n}$ (that is, if
$\bar{Z}_{i}:=1-Z_{i},i\in\\{1,\dots,2n\\}$, $S(Z)=S(\bar{Z})$),
$\mathds{E}\tau_{i}S$=0 so $B_{2n}(2n)=0$. By convexity of $B$,
$B_{1}(2n)+\dots+B_{2n}(2n)\leq 2n\frac{B_{1}(2n)+B_{2n}(2n)}{2}$, so
${\textrm{Var}}\,LC_{n}\leq n/4$.

More generally, in the case of an alphabet $\\{1,\dots,m\\}$, conditioning on
$X_{i}\neq X^{\prime}_{i}$ we get
$B_{1}(2n)\leq\left(1-\sum_{k=1}^{m}p_{k}^{2}\right)/2$, and when additionally
$B_{2n}(2n)=0$, then
${\textrm{Var}}\,LC_{n}\leq\left(1-\sum_{k=1}^{m}p_{k}^{2}\right)n/2$, which
improves, by a factor of two, on Steele’s bound [18],
${\textrm{Var}}\,LC_{n}\leq\left(1-\sum_{k=1}^{m}p_{k}^{2}\right)n$. The
condition $B_{2n}(2n)=0$ is realized when $p_{1}=\dots=p_{m}=1/m$, for
instance (by symmetry).

In the remaining part of this section, we focus on lower bounds for the
variance of $LC_{n}$. By Theorem 1.2, $(B_{k})_{1\leq k\leq 2n}$ is, in
particular, non-decreasing, so

${\textrm{Var}}\,LC_{n}\geq 2nB_{2n},$ (3.21)

which we will use throughout this section to lower bound the variance. [16,
Theorem 2.1] provides a lower bound on the variance of $LC_{n}$, proving that
when $p$ is smaller than some universal (but extremely small) constant, the
variance has order $n$, see also [11] for more explicit bounds (we already
know by Efron-Stein that the variance is less than $n$). To obtain this bound,
the authors first show Theorem 2.2 there, and then prove that it implies that
the variance has order $n$. The proof of this implication is long and we aim
to show that the jackknives tools we developed greatly simplifies it. We also
generalize the case where one letter is omitted, and then proceed to prove, in
the binary case, another slightly weaker bound: for some $p_{1}\in(0.096,0.5)$
(so not as small as in [16] or [11]), the limit superior of the variance over
$n$ is not zero. Finally, we give further partial results on the order of the
variance in the uniform case.

###  3.5 On the order of the variance under a hypothesis on a modification of
$LC_{n}$

In this section we prove how Theorem 2.2 in [16] or Theorem 2.1 in [11] imply
their main theorem, namely the linear order of the variance. This shows how
the use of the $B_{k}$’s greatly simplify some proofs, and it is of interest
to infer, more generally, a lower bound on the variance from a random
perturbation that has an effect on the expectation. More specifically, here,
the random perturbation is to pick a random $1$ from the letters (if there is
at least one), and turn it into a $0$. The original letters are denoted by
$Z_{1},\dots,Z_{2n}$, the new letters (with a $1$ turned into a $0$) by
$\tilde{Z_{1}},\dots,\tilde{Z_{2}n}$. We refer to [16] and [11] for a more
formal definition of $\tilde{Z}$. Theorem 2.2/Theorem 2.1 there implies, in
particular, that for any $\delta\in(0,\alpha_{1}-\alpha_{2})$, where
$\alpha_{1}$, $\alpha_{2}$ are constants defined there such that
$\alpha_{1}>\alpha_{2}$, for $n$ large enough,

$\mathds{E}\left(LCS(Z)-LCS(\tilde{Z})\right)\geq\delta.$

From this, it is natural to try to prove that $B_{2n}(2n)$ is greater than
some absolute constant, to infer that the variance has linear order. Let, for
all $z\in\\{0,1\\}^{2n}$, $x\in\\{0,1\\}$ and $k\in\\{1,\dots,2n\\}$,
$z^{k,x}:=(z_{1},\dots,z_{k-1},x,z_{k+1},\dots,z_{2n})$. Consider the
modifications of $Z$, $Z^{N,1}$ and $Z^{N,0}$, with $N$ picked in
$\\{1,\dots,n\\}$ uniformly. Intuitively, this is "almost" like the previous
pair $(Z,\tilde{Z})$. But it is easier to write $B_{2n}(2n)$ in terms of
$\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0}\right)$. Indeed, we have

$\displaystyle B_{2n}(2n)$
$\displaystyle=\mathds{E}\frac{1}{2(2n)!}\sum_{i\in\mathfrak{S}_{2n}}(S-S^{i_{2n}})(S^{i_{1},\dots,i_{2n-1}}-S^{i_{1},\dots,i_{2n}})$
$\displaystyle=\mathds{E}\frac{1}{2(2n)}\sum_{k=1}^{2n}(S-S^{k})(S^{\\{1,\dots,2n\\}\setminus\\{k\\}}-S^{\\{1,\dots,2n\\}}),$

conditioning on $(Z_{i_{2n}},Z^{\prime}_{i_{2n}})$ (first term when its
$(0,1)$, second term $(1,0)$, the other terms are null) we get

$\displaystyle B_{2n}(2n)$
$\displaystyle=\mathds{E}\frac{1}{2(2n)}\sum_{k=1}^{2n}\left(LCS(Z^{k,0})-LCS(Z^{k,1})\right)\left(LCS(Z^{\prime
k,0})-LCS(Z^{\prime k,1})\right)p(1-p)+$
$\displaystyle\quad\quad\quad\mathds{E}\frac{1}{2(2n)}\sum_{k=1}^{2n}\left(LCS(Z^{k,1})-LCS(Z^{k,0})\right)\left(LCS(Z^{\prime
k,1})-LCS(Z^{\prime k,0})\right)p(1-p),$

and by independence,

$\displaystyle B_{2n}(2n)$
$\displaystyle=\frac{1}{2n}\sum_{k=1}^{2n}\left(\mathds{E}\left(LCS(Z^{k,1})-LCS(Z^{k,0})\right)\right)^{2}p(1-p),$

so by the Cauchy-Schwarz inequality,

$B_{2n}(2n)\geq\left(\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0})\right)\right)^{2}p(1-p).$
(3.22)

We now give a lower bound on
$\mathds{E}\left(LCS(Z^{N,0})-LCS(Z^{N,1})\right)$. First note that if $N_{1}$
denotes the number of ones, for any ${\ell}\in\\{1,\dots,2n\\}$,
$(Z^{N,1},Z^{N,0})$ conditionally on $N_{1}(Z^{N,1})={\ell}$ has the same
distribution as $(Z,\tilde{Z})$ conditionally on $N_{1}(Z)={\ell}$. Indeed,
this is the uniform distribution on all the possible pairs of $2n$ bits, the
first one having $k$ ones and the second one being identical except exactly
for a $1$ turned into a $0$. To simplify the notations, for
${\ell}\in\\{0,\dots,2n\\}$, let

$f({\ell}):=\mathds{E}\left(LCS(Z)-LCS(\tilde{Z})|N_{1}(Z)\right).$

We have

$\displaystyle\mathds{E}\left(LCS(Z)-LCS(\tilde{Z})\right)$
$\displaystyle=\sum_{{\ell}=1}^{2n}f({\ell})\mathds{P}(N_{1}(Z)={\ell})$
$\displaystyle=\mathds{E}\left(f(N_{1}(Z))\right),$

while, since $f(0)=0$,

$\displaystyle\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0})\right)$
$\displaystyle=\sum_{{\ell}=1}^{2n}\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0})|N_{1}(Z)\right)\mathds{P}(N_{1}(Z^{N,1})={\ell})$
$\displaystyle=\sum_{{\ell}=1}^{2n}f({\ell})p^{{\ell}-1}(1-p)^{n-{\ell}}{n-1\choose{\ell}-1}$
$\displaystyle=\sum_{{\ell}=1}^{2n}f({\ell})\frac{{\ell}}{pn}\mathds{P}(N_{1}(Z)={\ell})$
$\displaystyle=\mathds{E}\left(f(N_{1}(Z))\frac{N_{1}(Z)}{pn}\right),$

so by dominated convergence,

$\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0})\right)\xrightarrow[n\to\infty]{}\mathds{E}\left(LCS(Z)-LCS(\tilde{Z})\right)$

and so for any $\delta\in(0,\alpha_{1}-\alpha_{2})$, for $n$ large enough,

$\mathds{E}\left(LCS(Z^{N,1})-LCS(Z^{N,0})\right)\geq\delta$

so using (3.21) and (3.22),

$\frac{{\textrm{Var}}\,LC_{n}}{n}\geq 2p(1-p)\delta^{2}.$

###  3.6 On the order of the variance when one letter is omitted

As in [10], we consider the letters $X_{1},\dots,X_{n}$ drawn from an alphabet
$\alpha_{1},\dots,\alpha_{m+1}$ and the letters $Y_{1},\dots,Y_{n}$ drawn from
an alphabet $\alpha_{1},\dots,\alpha_{m}$: so $\alpha_{m+1}$ is an omitted
letter, not belonging to any longest common subsequence. We let
$p=\mathds{P}(X_{i}=\alpha_{m+1})$ and assume $p>0$, but in contrast to [10],
we only make minimal assumptions on
$p_{X,1}:=\mathds{P}(X_{i}=\alpha_{1}),\dots,p_{X,m}:=\mathds{P}(X_{i}=\alpha_{m}),p_{Y,1}:=\mathds{P}(Y_{i}=\alpha_{1}),\dots,p_{Y,m}:=\mathds{P}(Y_{i}=\alpha_{m})$:
we assume that there are all strictly positive, but these letters are no
longer equiprobable, and we assume $m>1$ (the case $m=1$ is trivial and may be
dealt with separately). Using

${\textrm{Var}}\,LC_{n}\geq 2nB_{2n}(2n),$ (3.23)

we see that it is enough to find a constant lower bound on $B_{2n}(2n)$.
Firstly, we write

$\displaystyle B_{2n}(2n)$
$\displaystyle=\frac{1}{4n}\sum_{j=1}^{2n}\mathds{E}\left(\Delta_{j}LC_{n}(\Delta_{j}LC_{n})^{1,\dots,j-1,j+1,\dots,n}\right)$
$\displaystyle=\frac{1}{4n}\sum_{j=1}^{2n}\sum_{i,i^{\prime}=1}^{m}\left(\mathds{E}\Delta_{j}LC_{n}^{Z_{j}=\alpha_{i},Z^{\prime}_{j}=\alpha_{i^{\prime}}}\right)^{2}\mathds{P}(Z_{j}=\alpha_{i})\mathds{P}(Z^{\prime}_{j}=\alpha_{i^{\prime}})\quad\text{conditioning}$
$\displaystyle\geq\frac{1}{4n}\sum_{j=1}^{n}\sum_{i=1}^{m}\left(\mathds{E}\Delta_{j}LC_{n}^{X_{j}=\alpha_{i},X^{\prime}_{j}=\alpha_{m+1}}\right)^{2}p_{X,i}p$
$\displaystyle\geq\frac{1}{4n}\sum_{j=1}^{n}\left(\sum_{i=1}^{m}\mathds{E}\Delta_{j}LC_{n}^{X_{j}=\alpha_{i},X^{\prime}_{j}=\alpha_{m+1}}p_{X,i}\right)^{2}p.$

Writing $LC_{n-1,n}:=LCS(X_{1}\dots X_{n-1};Y_{1}\dots Y_{n})$, we have for
any $j\in\\{1,\dots,n\\}$,

$\sum_{i=1}^{m}\mathds{E}\Delta_{j}LC_{n}^{X_{j}=\alpha_{i},X^{\prime}_{j}=\alpha_{m+1}}p_{X,i}=\mathds{E}(LC_{n})-\mathds{E}(LC_{n-1,n}),$

hence

$B_{2n}(2n)\geq\frac{1}{4}\left(\mathds{E}(LC_{n})-\mathds{E}(LC_{n-1,n})\right)p.$
(3.24)

Let $(\pi,\eta)$ be the alignment of
$(X_{1}\dots,X_{n-1}),(Y_{1},\dots,Y_{n})$ that is minimal for the
lexicographic order, so $(\pi,\eta)$ is well defined as a (measurable)
function of $X_{1}\dots,X_{n-1},Y_{1},\dots,Y_{n}$. Let $F_{n}$ be the event
"$\eta_{LC_{n}}<n$", in other words, $Y_{n}$ does not contribute to the
longest common subsequences, then
$\sum_{i=1}^{n}\Delta_{n}LC_{n}^{X_{n}=\alpha_{i},X^{\prime}_{n}=\alpha_{m+1}}\geq\mathds{1}_{F_{n}}$,
hence

$\mathds{E}(LC_{n})-\mathds{E}(LC_{n-1,n})\geq p_{X,\min}\mathds{P}(F_{n}),$
(3.25)

where $p_{X,\min}:=\min_{1\leq i\leq m}p_{X,i}$.

We are now going to combine this bound with another one with some elements
already present in [10]. Let
$V_{1}=\pi_{1}-1,V_{2}=\pi_{2}-\pi_{1}-1,\dots,V_{LC_{n}}=\pi_{LC_{n}}-\pi_{LC_{n}-1}-1$,
and let $M$ be the number of indices $i$ such that $V_{i}>0$. In terms of
[10], $M$ is the number of nonempty matches (except that there is also the
term $V_{1}$). We denote by $I_{i,j}$ the event: "inserting $\alpha_{i}$ at
the $j$-th position in $(X_{1}\dots,X_{n-1}),(Y_{1},\dots,Y_{n})$ increases
the longest common subsequence". Observe that

$\displaystyle\mathds{E}(LC_{n})-\mathds{E}(LC_{n-1,n})$
$\displaystyle=\mathds{E}\left(LCS(X_{1}\dots X_{j-1}X^{\prime}_{1}X_{j}\dots
X_{n-1};Y_{1}\dots,Y_{n})-\right.$ $\displaystyle\left.\quad\quad\quad
LCS((X_{1}\dots X_{n-1};Y_{1}\dots Y_{n})\right)$
$\displaystyle=\sum_{i=1}^{m}p_{X,i}\mathds{P}(I_{i,j})$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\sum_{i=1}^{m}p_{X,i}\mathds{P}(I_{i,j})$
$\displaystyle\geq\frac{p_{X,\min}}{n}\mathds{E}\sum_{j=1}^{n}\sum_{i=1}^{m}I_{i,j}$
$\displaystyle\geq p_{X,\min}\frac{\mathds{E}M}{n}.$ (3.26)

From (3.25) and (3.6), we get

$\mathds{E}(LC_{n})-\mathds{E}(LC_{n-1,n})\geq\frac{p_{X,\min}}{2}\left(\mathds{P}(F_{n})+\frac{\mathds{E}M}{n}\right).$
(3.27)

Let $\gamma^{*}$ be the limit of $\mathds{E}(LC_{n})/n$, we have
$\gamma^{*}\leq 1-p<1$. Fix $k_{0}>0$ such that

$\sum_{k>k_{0}}mk(1-p_{Y,\min})^{k}\leq\frac{1-\gamma^{*}}{2}.$

When $F_{n}$ does not hold, that is, $\pi_{n}=LC_{n}$, we have

$\sum_{i=1}^{LC_{n}}V_{i}=n-LC_{n},$

so

$\mathds{E}\left(\sum_{i=1}^{LC_{n}}V_{i}\right)\geq\mathds{E}\left((n-LC_{n})\mathds{1}_{F_{n}^{c}}\right)\geq\mathds{E}\left(n-LC_{n}\right)-\mathds{P}(F_{n})n\geq(1-\gamma^{*})n-\mathds{P}(F_{n})n.$

Furthermore,

$k_{0}\mathds{E}M\geq\mathds{E}\left(\sum_{i=1}^{LC_{n}}V_{i}\mathds{1}_{V_{i}\leq
k_{0}}\right).$

On the other hand, $(\pi,\eta)$ is minimal, so any unmatched gap has (at
least) one letter of the alphabet not used, namely, the letter used in the
next match. Therefore the average number of indices $i$ such that $V_{i}=k$ is
no more than $nm(1-p_{Y,\min})^{k}$, and

$\mathds{E}\left(\sum_{i=1}^{LC_{n}}V_{i}\mathds{1}_{V_{i}>k_{0}}\right)\leq
n\sum_{k>k_{0}}mk(1-p_{Y,\min})^{k}\leq\frac{1-\gamma^{*}}{2}n.$

Finally we get

$k_{0}\mathds{E}M\geq\frac{1-\gamma^{*}}{2}n-\mathds{P}(F_{n})n,$

and

$\mathds{P}(F_{n})+\frac{\mathds{E}M}{n}\geq\frac{k_{0}\mathds{E}M+\mathds{P}(F_{n})n}{k_{0}n}\geq\frac{1-\gamma^{*}}{2k_{0}},$

so putting it together with (3.23), (3.24) and (3.27), we get

${\textrm{Var}}\,LC_{n}\geq\frac{pp_{X,\min}(1-\gamma^{*})}{8k_{0}}n.$

###  3.7 A weaker kind of lower bound

Let us return to the Bernoulli framework with parameter $0<p<1$, and let
$\gamma_{n}(p)=\mathds{E}LC_{n}/n$ and
$\gamma(p)=\lim_{n\to\infty}\gamma_{n}(p)$. It seems reasonable to expect that
${\textrm{Var}}\,LC_{n}/n$ converges when $n$ tends to infinity, but
unfortunately a proof of this result has been elusive so far. Actually little
is known on the variance: to the best of our knowledge, it is still an open
problem to determine whether or not the variance tends to infinity in the
uniform case. The function $\gamma$ is clearly symmetric around $1/2$, and it
is expected to be strictly convex with a minimum at $1/2$, but besides
numerical simulations there is no proof of this fact yet. The goal of this
section is to prove:

######  Theorem 3.8.

Let $p_{0}\in(0,1/2)$ be such that $\gamma(p_{0})>\gamma(1/2)$. Then there
exists $p_{1}\in(p_{0},1/2)$ such that when $p=p_{1}$,

$\limsup_{n\to\infty}\frac{{\textrm{Var}}\,LC_{n}}{n}\geq
2p_{0}(1-p_{0})\left(\frac{\gamma(p_{0})-\gamma(1/2)}{1/2-p_{0}}\right)^{2}.$

######  Remark 3.9.

Using the bound $\gamma(1/2)<0.8263$ from [17], and since $\gamma(p)\geq
p^{2}+(1-p)^{2}$, we can apply the above theorem with $p_{0}=0.096$, to get
for some $p_{1}\in(0.096,0.5),\limsup_{n\to\infty}{\textrm{Var}}\,LC_{n}/n\geq
1.8/10^{8}$. Clearly, by symmetry, this limsup result is also valid for some
$p_{2}\in(0.5,0.904)$.

###### Proof.

We have

$\displaystyle\gamma_{n}(p_{0})-\gamma_{n}(1/2)=-\int_{p_{0}}^{1/2}\frac{\mathrm{d}\gamma_{n}}{\mathrm{d}p}(p)\mathrm{d}p=\int_{p_{0}}^{1/2}\frac{1}{2n}\sum_{k=1}^{2n}\mathds{E}_{p}\left(LC_{n}^{k,0}-LC_{n}^{k,1}\right)\mathrm{d}p,$

where we used a Russo-Margulis kind of formula. This is not strictly the
Russo-Margulis lemma since $LC_{n}$ is not monotone, but the proof of this
version is elementary: as in [6], we rewrite $\gamma_{n}$ as a function of
$2n$ parameters, the parameters of each letter (Bernoulli random variables):

$\displaystyle\frac{\mathrm{d}\gamma_{n}}{\mathrm{d}p}(p)=\frac{\mathrm{d}\gamma_{n}}{\mathrm{d}p}(p,p,\dots,p)=\sum_{k=1}^{2n}\frac{\mathrm{d}\gamma_{n}}{\mathrm{d}p_{k}}(p,p,\dots,p),$

which yields the result. Hence,

$\displaystyle\gamma(p_{0})-\gamma(1/2)$
$\displaystyle=\limsup_{n\to\infty}\gamma_{n}(p_{0})-\gamma_{n}(1/2)$
$\displaystyle\leq\int_{p_{0}}^{1/2}\limsup_{n\to\infty}\frac{1}{2n}\sum_{k=1}^{2n}\mathds{E}_{p}\left(LC_{n}^{k,0}-LC_{n}^{k,1}\right)\mathrm{d}p,$

so there exists $p_{1}\in(p_{0},1/2)$ such that

$\limsup_{n\to\infty}\frac{1}{2n}\sum_{k=1}^{2n}\mathds{E}_{p_{1}}\left(LC_{n}^{k,0}-LC_{n}^{k,1}\right)\geq\frac{\gamma(p_{0})-\gamma(1/2)}{1/2-p_{0}}.$

Let us fix $p=p_{1}$. As seen previously,

$\displaystyle B_{2n}(2n)$
$\displaystyle=\frac{1}{2n}\sum_{k=1}^{2n}\left(\mathds{E}\left(LC_{n}(Z^{k,0})-LC_{n}(Z^{k,1})\right)\right)^{2}p_{1}(1-p_{1}),$

so

$\displaystyle{\textrm{Var}}\,LC_{n}$
$\displaystyle\geq\sum_{k=1}^{2n}\left(\mathds{E}\left(LC_{n}(Z^{k,0})-LC_{n}(Z^{k,1})\right)\right)^{2}p_{0}(1-p_{0})$
$\displaystyle\geq
2n\left(\frac{1}{2n}\sum_{k=1}^{2n}\mathds{E}_{p_{1}}\left(LC_{n}^{k,0}-LC_{n}^{k,1}\right)\right)^{2}p_{0}(1-p_{0}),$

and finally

$\displaystyle\limsup_{n\to\infty}\frac{{\textrm{Var}}\,LC_{n}}{n}$
$\displaystyle\geq
2p_{0}(1-p_{0})\left(\frac{\gamma(p_{0})-\gamma(1/2)}{1/2-p_{0}}\right)^{2}.$

∎

######  Remark 3.10.

As already mentioned, it is expected that the function $\gamma$ is strictly
convex, but even proving that $\gamma$ is non-increasing on $[0,1/2]$ and non-
decreasing on $[1/2,1]$ seems to be lacking. It also seems reasonable that for
a fixed alphabet, say binary uniform, the sequence
$(\mathds{E}LC_{n}/n)_{n\geq 1}$ is non-decreasing, but again a proof is
lacking.

###  3.8 On the order of the variance in the uniform case

A long-standing open problem is to find the order of the variance of $LC_{n}$
when the distribution is uniform. In this section, we focus on the uniform
binary case, so $\lim_{n\to\infty}\mathds{E}LC_{n}/n=\gamma(1/2):=\gamma_{2}$.
We recall, from [12], the definition of the function $\widetilde{\gamma}$: for
any $p>0$,

$\widetilde{\gamma}(p):=\lim_{n\to\infty}\frac{\mathds{E}\left(LCS(X_{1}\dots
X_{n};Y_{1}\dots Y_{\lfloor np\rfloor})\right)}{n(1+p)/2}.$ (3.28)

By a superadditivity argument, this limit is well defined and
$\widetilde{\gamma}$ is concave, non-decreasing on $[0,1]$ and non-increasing
on $[1,+\infty)$ (for the details, and more properties, we refer to [12]).

By symmetry, in this case, $B_{2n}(2n)=0$. However, letting
$Z_{1}=(X_{1},Y_{1}),Z_{2}=(X_{2},Y_{2}),\dots,Z_{n}=(X_{n},Y_{n})$, then the
last $B_{k}$ is $B_{n}(n)$ which can also be written as

$B_{n}(n)=\frac{1}{n}\sum_{k=1}^{n}\frac{1}{4}\left(\mathds{E}\left(LCS(Z^{k,0,0})-LCS(Z^{k,0,1})\right)\right)^{2},$
(3.29)

with transparent notations (the proof is similar). So it is enough to find a
lower bound for this quantity, which is doable for the terms on the edge ($1$
or $n$) but seems tricky for the terms in the middle.

We may also fix $b\geq 2$ and let $Z_{1}=X_{1},\dots,X_{b}$,
$Z_{2}=X_{b+1},\dots,X_{2b}$, $\dots$. In this case, one gets that lower
bounding $B_{n}(n)$ amounts to finding $w_{1},w_{2}\in\\{0,1\\}^{b}$ and
$\delta>0$ such that for all $n\geq 1$,

$\frac{1}{n}\sum_{k=1}^{n}\left(\mathds{E}\left(LCS(Z^{k,w_{1}})-LCS(Z^{k,w_{2}})\right)\right)^{2}\geq\delta.$
(3.30)

For example, intuitively, it is likely to get a larger LCS with $w_{1}=(1,0)$
than with $w_{2}=(1,1)$, and with $w_{1}=(1,0,1,0,1)$ than with
$w_{2}=(1,1,1,1,1)$. Running simulations in Python, Figure 1 seems to indicate
that $B_{n}(n)$ is lower bounded by a strictly positive constant (which would
yield the linearity of the variance).

Figure 1: $B_{n}(n)$ for $w_{1}=(1,0),w_{2}=(1,1)$ (left), and
$w_{1}=(1,0,1,0,1)$, $w_{2}=(1,1,1,1,1)$ (right), with the empirical measure
over $1000$ simulations.

We now pick again $Z_{1}=X_{1},Z_{2}=X_{2},\dots,Z_{2n}=Y_{n}$, and study
$B_{1}(2n)$. Note that if $B_{1}(2n)$ was converging to zero, this would rule
out the possibility of a linear lower bound on the variance. In the following,
we study $B_{1}(2n)$, and find that it is lower bounded by a constant.

Let $X_{1},\dots,X_{n},Y_{1},\dots,Y_{n}$ be independent Bernoulli random
variables with parameter $1/2$, and let $\upsilon\leq n$. We may assume, for
ease of notations, that $n=\upsilon m$ is a multiple of $\upsilon$, but it is
not hard to adapt all the following proofs to the general case. Let
$\mathcal{R}:=\\{\overrightarrow{r}\in{\mathbb{N}}^{m}:1=r_{0}\leq
r_{1}\leq\dots\leq r_{m}=n\\}$, and, for any
$\overrightarrow{r}\in\mathcal{R}$, let

$LC_{n}(\overrightarrow{r})=\sum_{i=0}^{m-1}LCS\left(P_{i}\right),$ (3.31)

where $P_{i}:=\left((X_{\upsilon
i+1},\dots,X_{(\upsilon+1)i}),(Y_{r_{i}},\dots,Y_{r_{i+1}-1})\right)$ (with
the convention $(Y_{r_{i}},\dots,Y_{r_{i+1}-1})=()$ if $r_{i}=r_{i+1}$). For
any $\overrightarrow{r}\in\mathcal{R}$, call $\overrightarrow{r}$ an alignment
if $LC_{n}=LC_{n}(\overrightarrow{r})$.

Denote by $N_{i}$ the number of letters in the cell $P_{i}$, that is,
$\upsilon+r_{i+1}-r_{i}$. For any $\overrightarrow{r}\in\mathcal{R}$, let
$I_{p_{1},p_{2}}(\overrightarrow{r})=\\{i\in\\{0,\dots,m-1\\};r_{i+1}-r_{i}\in[\upsilon
p_{1},\upsilon p_{2}]\\}$, and
$\overline{I_{p_{1},p_{2}}(\overrightarrow{r})}$ its complementary in
$\\{0,\dots,m-1\\}$. Next, let $B^{n}_{\varepsilon,p_{1},p_{2}}$ be the event
that: for any alignment $\overrightarrow{r}$,

$\sum_{i\in
I_{p_{1},p_{2}}(\overrightarrow{r})}N_{i}\geq\left(1-\frac{\varepsilon}{2}\right)2n.$

Forgetting about the slight difference in notations for the alignments, as we
define them following [8] with non-strict inequalities $r_{0}\leq
r_{1}\leq\dots$ rather than the strict inequalities in [12], we have
$B^{n}_{\varepsilon,p_{1},p_{2}}\subset A^{n}_{\varepsilon,p_{1},p_{2}}$,
where this event is defined in [12]. Indeed, if
$B^{n}_{\varepsilon,p_{1},p_{2}}$ is not satisfied, there is an alignment
$\overrightarrow{r}$ such that

$\sum_{i\in\overline{I_{p_{1},p_{2}}(\overrightarrow{r})}}N_{i}>\varepsilon
n.$

which implies
$\text{Card}\left(I_{p_{1},p_{2}}(\overrightarrow{r})\right)>\varepsilon m$,
which means $A^{n}_{\varepsilon,p_{1},p_{2}}$ is not satisfied. Therefore, the
following is a strengthening of [12, Theorem 2.2].

######  Lemma 3.11.

Let $\varepsilon>0$. Let $0<p_{1}<1<p_{2}$ be such that
$\widetilde{\gamma}(p_{1})<\widetilde{\gamma}(1)={\gamma_{2}}$ and
$\widetilde{\gamma}(p_{2})<{\gamma_{2}}$ and let
$\delta\in\left(0,\min({\gamma_{2}}-\widetilde{\gamma}(p_{1}),{\gamma_{2}}-\widetilde{\gamma}(p_{2}))\right)$.

Fix the integer $\upsilon$ to be such that
$(1+\ln(1+\upsilon))/\upsilon\leq\delta^{2}\varepsilon^{2}/16$, then

$\mathds{P}\left(B^{n}_{\varepsilon,p_{1},p_{2}}\right)\geq
1-\exp\left(-n\left(\frac{\delta^{2}\varepsilon^{2}}{16}-\frac{1+\ln(1+\upsilon)}{\upsilon}\right)\right),$

for all $n$ large enough.

###### Proof.

Let $\overrightarrow{r}\in\mathcal{R}$ be such that
$\sum_{i\in\overline{I_{p_{1},p_{2}}(\overrightarrow{r})}}N_{i}>\varepsilon
n$. We first prove that

$\mathds{E}\left(LC_{n}(\overrightarrow{r})-LC_{n}\right)\leq-\frac{\delta\varepsilon
n}{2}$

for all $n$ large enough. We follow the proof of [12, Lemma 3.1]. Let
$\delta^{*}=\min({\gamma_{2}}-\widetilde{\gamma}(p_{1}),{\gamma_{2}}-\widetilde{\gamma}(p_{2}))$.
Using the superadditivity of $\widetilde{\gamma}$, we get

$\displaystyle\mathds{E}\left(LC_{n}(\overrightarrow{r})\right)$
$\displaystyle\leq{\gamma_{2}}\left(\sum_{i\in
I_{p_{1},p_{2}}(\overrightarrow{r})}\frac{N_{i}}{2}\right)+({\gamma_{2}}-\delta^{*})\left(\sum_{i\in\overline{I_{p_{1},p_{2}}(\overrightarrow{r})}}\frac{N_{i}}{2}\right)$
$\displaystyle\leq\left({\gamma_{2}}-\frac{\delta^{*}\varepsilon}{2}\right)n.$

Moreover, for $n$ is large enough,

$-\mathds{E}\left(LC_{n}\right)\leq-\left({\gamma_{2}}-\frac{(\delta^{*}-\delta)\varepsilon}{2}\right)n,$

so combining together these two inequalities, we get the desired result:

$\mathds{E}\left(LC_{n}(\overrightarrow{r})-LC_{n}\right)\leq-\frac{\delta\varepsilon
n}{2}.$

The end of the proof is exactly like in [12], the only difference is, as
pointed out in [8, Remark 2.2], that the cardinality of $\mathcal{R}$ is now
${n+\upsilon\choose\upsilon}$ instead of ${n\choose\upsilon}$ so $\ln\upsilon$
becomes $\ln(1+\upsilon)$.

∎

######  Theorem 3.12.

There exists $C>0$ such that for all $n$ large enough, $B_{1}(2n)\geq C$.

###### Proof.

For any $\overrightarrow{r}\in\mathcal{R}$, let
$S(\overrightarrow{r})=\\{i\in\\{0,\dots,m-1\\};LCS(P_{i})=\min(\upsilon,r_{i+1}-r_{i})\\}$
the set of the indices of "saturated" cells, meaning that $LCS(P_{i})$ is
maximal given the size of the cell. We first show that for some
$\varepsilon>0$, with high probability, for any alignment
$\overrightarrow{r}$,
$\text{Card}(S(\overrightarrow{r}))\leq(1-\varepsilon)m$. The idea behind is
that the $\varepsilon m$ non-saturated cells will guarantee the lower bound on
$B_{1}(2n)$, as changing their coordinates might increase $LC_{n}$.

Let $x=0.28,p_{1}=1-x,p_{2}=1/p_{1}$, we know from [12] that
$\widetilde{\gamma}(p_{1})<{\gamma_{2}}$ and
$\widetilde{\gamma}(p_{2})<{\gamma_{2}}$. Let
$\eta=\frac{2(1-x)}{2-x}-{\gamma_{2}}$, from the upper bound ${\gamma_{2}}\leq
0.8263$, see [17], it that $\eta>0$. Let
$\varepsilon\in\left(0,\frac{\eta}{2({\gamma_{2}}+\eta)}\right)$, and, lastly,
let
$\delta\in\left(0,\min({\gamma_{2}}-\widetilde{\gamma}(p_{1}),{\gamma_{2}}-\widetilde{\gamma}(p_{2}))\right)$
and fix $\upsilon$ to be such that
$(1+\ln(1+\upsilon))/\upsilon<\delta^{2}\varepsilon^{2}/16$.

Let $C^{n}_{\varepsilon}$ be the event: for any alignment
$\overrightarrow{r}$,
$\text{Card}(S(\overrightarrow{r}))\leq(1-\varepsilon)m$. If
$(C^{n}_{\varepsilon})^{c}\cap B^{n}_{\varepsilon,p_{1},p_{2}}$ is realized,
then there is some alignment $\overrightarrow{r}$ such that
$\text{Card}(S(\overrightarrow{r}))>(1-\varepsilon)m$, and

$LC_{n}\geq\sum_{i\in S(\overrightarrow{r})\cap
I_{p_{1},p_{2}}(\overrightarrow{r})}\frac{N_{i}}{2}\frac{\min(\upsilon,r_{i+1}-r_{i})}{\frac{N_{i}}{2}}.$
(3.32)

For any $i\in I_{p_{1},p_{2}}(\overrightarrow{r})$, $r_{i+1}-r_{i}\in[\upsilon
p_{1},\upsilon p_{2}]$ so

$\frac{\min(\upsilon,r_{i+1}-r_{i})}{\frac{N_{i}}{2}}\geq\frac{2}{1+p_{2}}=\frac{2p_{1}}{1+p_{1}}=\frac{2(1-x)}{2-x}={\gamma_{2}}+\eta$

so

$LC_{n}\geq\sum_{i\in S(\overrightarrow{r})\cap
I_{p_{1},p_{2}}(\overrightarrow{r})}\frac{N_{i}}{2}({\gamma_{2}}+\eta).$
(3.33)

Furthermore,

$\displaystyle\sum_{i\in\overline{S(\overrightarrow{r})\cap
I_{p_{1},p_{2}}(\overrightarrow{r})}}\frac{N_{i}}{2}$
$\displaystyle=\sum_{i\in\overline{S(\overrightarrow{r})}\cap
I_{p_{1},p_{2}}(\overrightarrow{r})}\frac{N_{i}}{2}+\sum_{i\in\overline{I_{p_{1},p_{2}}(\overrightarrow{r})}}\frac{N_{i}}{2}$
$\displaystyle\leq\upsilon\frac{1+p_{2}}{2}\varepsilon m+\frac{\varepsilon
n}{2}$ $\displaystyle\leq 2\varepsilon n,$

so we get

$LC_{n}\geq(1-2\varepsilon)({\gamma_{2}}+\eta)n,$ (3.34)

but given the choice of $\varepsilon$,
$(1-2\varepsilon)({\gamma_{2}}+\eta)>{\gamma_{2}}$, so by concentration, this
has probability exponentially small to happen. Therefore,
$\mathds{P}\left((C^{n}_{\varepsilon})^{c}\right)\leq\mathds{P}\left((C^{n}_{\varepsilon})^{c}\cap
B^{n}_{\varepsilon,p_{1},p_{2}}\right)+\mathds{P}\left((B^{n}_{\varepsilon,p_{1},p_{2}})^{c}\right)$
goes to zero (exponentially fast) as $n$ goes to infinity.

Now for $i\in\\{1,\dots,m\\}$, let

$V_{i}=\max_{x\in\\{0,1\\}^{\upsilon}}\left|LCS(X_{1}\dots
X_{\upsilon(i-1)}x_{1}\dots,x_{\upsilon}X_{\upsilon i+1}\dots X_{n};Y_{1}\dots
Y_{n})-LCS(X_{1}\dots X_{n};Y_{1}\dots Y_{n})\right|.$ (3.35)

For any $i\in\overline{S(\overrightarrow{r})}$, $V_{i}\geq 1$, hence

$\mathds{E}\left(\frac{1}{m}\sum_{i=1}^{m}V_{i}^{2}\right)>\varepsilon\mathds{P}(C^{n}_{\varepsilon}).$
(3.36)

Now let for $x\in\\{0,1\\}^{\upsilon}$ and
$j\in\\{\upsilon(i-1)+1,\dots,\upsilon i\\}$,

$\displaystyle\delta_{j}(x)=$ $\displaystyle LCS(X_{1}\dots
X_{\upsilon(i-1)}x_{1}\dots x_{j-\upsilon(i-1)}X_{j+1}\dots X_{n};Y_{1}\dots
Y_{n})$ $\displaystyle-$ $\displaystyle LCS(X_{1}\dots
X_{\upsilon(i-1)}x_{1}\dots,x_{j-\upsilon(i-1)-1}X_{j}\dots X_{n};Y_{1}\dots
Y_{n}),$

so that

$\displaystyle V_{i}^{2}$
$\displaystyle=\max_{x\in\\{0,1\\}^{\upsilon}}\left|\sum_{j=\upsilon(i-1)+1}^{\upsilon
i}\delta_{j}(x)\right|^{2}$
$\displaystyle\leq\max_{x\in\\{0,1\\}^{\upsilon}}\upsilon\sum_{j=\upsilon(i-1)+1}^{\upsilon
i}\delta_{j}(x)^{2}$
$\displaystyle\leq\upsilon\sum_{j=\upsilon(i-1)+1}^{\upsilon
i}\max_{x\in\\{0,1\\}^{\upsilon}}\delta_{j}(x)^{2}.$

Note that
$\mathds{E}\Delta_{j}^{2}=\mathds{E}\delta_{j}(X^{\prime}_{1},\dots,X^{\prime}_{\upsilon})^{2}$
(see the next section to recall the definition of $\Delta_{j}$), and

$\mathds{E}_{X^{\prime}_{1},\dots,X^{\prime}_{\upsilon}}\Delta_{j}^{2}\geq\frac{1}{2^{\upsilon}}\max_{x\in\\{0,1\\}^{\upsilon}}\delta_{j}(x)^{2}.$

Hence,

$\mathds{E}\Delta_{j}^{2}\geq\frac{1}{2^{\upsilon}}\mathds{E}\max_{x\in\\{0,1\\}^{\upsilon}}\delta_{j}(x)^{2},$

so

$\displaystyle V_{i}^{2}$ $\displaystyle\leq\upsilon
2^{\upsilon}\sum_{j=\upsilon(i-1)+1}^{\upsilon i}\mathds{E}\Delta_{j}^{2},$
$\displaystyle\mathds{E}\left(\frac{1}{m}\sum_{i=1}^{m}V_{i}^{2}\right)$
$\displaystyle\leq\frac{\upsilon
2^{\upsilon}}{m}\sum_{j=1}^{n}\mathds{E}\Delta_{j}^{2}$
$\displaystyle\varepsilon\mathds{P}(C^{n}_{\varepsilon})$
$\displaystyle<\upsilon^{2}2^{\upsilon}B_{1}(2n),$

and when $n$ is large enough,
$B_{1}(2n)>{\varepsilon}/{2\upsilon^{2}2^{\upsilon}}$. ∎

######  Remark 3.13.

The above result is a necessary condition (certainly not sufficient, though)
to have ${\textrm{Var}}\,LC_{n}$ asymptotically linear. This implies that
there exists $C^{\prime}>0$, such that for all $n$, $B_{1}(2n)\geq
C^{\prime}$, as for all $n$, $B_{1}(2n)>0$.

###  3.9 A note on a potential implication of [8]

In this section, $\alpha\in(0,1)$, $\upsilon=n^{\alpha}$, and
$\overrightarrow{r}$ is a random alignment. Let
$X^{\prime}_{1},\dots,X^{\prime}_{n},Y^{\prime}_{1},\dots,Y^{\prime}_{n}$ be
independent Bernoulli variables with parameter $1/2$, independent from all the
previous variables. As previously, we write
$Z=(Z_{1},\dots,Z_{2n}):=(X_{1},\dots,X_{n},Y_{1},\dots,Y_{n})$, and as in
[8], for $j\in\\{1,\dots,2n\\}$, let

$\displaystyle\Delta_{j}$ $\displaystyle:=LCS(Z)-LCS(Z_{1}\dots
Z^{\prime}_{j}\dots Z_{2n})$ $\displaystyle\widetilde{\Delta_{j}}$
$\displaystyle:=LCS\left(P_{i}\right)-LCS\left(P^{\prime}_{i}\right)$

where $P_{i}$ is the cell of length $\upsilon$ containing $Z_{j}$ and
$P^{\prime}_{i}$ is the same cell but with $Z^{\prime}_{j}$ instead of
$Z_{j}$. We also write for $j,k\in\\{1,\dots,m\\}$:

$\displaystyle LC_{n}^{j}$ $\displaystyle:=LCS(Z_{1}\dots Z^{\prime}_{j}\dots
Z_{2n})$ $\displaystyle LC_{n}^{j,k}$ $\displaystyle:=LCS(Z_{1}\dots
Z^{\prime}_{j}\dots Z^{\prime}_{k}\dots Z_{2n})$ $\displaystyle\Delta_{j,k}$
$\displaystyle:=LC_{n}-LC_{n}^{j}-LC_{n}^{j}+LC_{n}^{j,k}.$

It is claimed in [8] that
$\mathds{E}\left|\widetilde{\Delta_{j}}-\Delta_{j}\right|=\mathds{E}\left(\widetilde{\Delta_{j}}-\Delta_{j}\right)$
is exponentially small in $n$. The equality comes from the fact that
$\widetilde{\Delta_{j}}-\Delta_{j}\geq 0$ (as explained in [8]). Furthermore,
$\mathds{E}\Delta_{j}=0$, so the problem boils to controlling
$\mathds{E}\widetilde{\Delta_{j}}$. Let us assume, in this section, that
$\mathds{E}\widetilde{\Delta_{j}}\leq\exp(-tn)$ for some $t>0$ not depending
on $j,n$, and let us denote by $A_{j}$ the event
$\widetilde{\Delta_{j}}-\Delta_{j}=0$. Of course,
$\mathds{P}(A_{j}^{c})\leq\exp(-tn)$. Finally, let $C_{j,k}$ be the event
"$Z_{j}$ and $Z_{k}$ are not in the same cell". Let $j,k\in\\{1,\dots,n\\}$
and suppose $A_{j}$, $A_{k}$ and $C_{j,k}$ are all realized, then when $X_{j}$
is flipped to $X^{\prime}_{j}$, the alignment
$\overrightarrow{r}=\overrightarrow{r}(Z)$ is still an alignment for
$(Z_{1},\dots,Z^{\prime}_{j},\dots,Z_{2n})$, so

$LC_{n}^{j,k}-LC_{n}^{j}\geq-\widetilde{\Delta_{k}}=LC_{n}^{k}-LC_{n}$ (3.37)

so, in other terms,

$\Delta_{j,k}\mathds{1}_{A_{j}}\mathds{1}_{A_{k}}\mathds{1}_{C_{j,k}}\geq 0.$
(3.38)

Let us write $\Delta_{j,k}=\Delta_{j,k}^{+}-\Delta_{j,k}^{-}$ (the positive
and negative parts), using the bounds $|\Delta_{j,k}|\leq 2$ and (3.38) we get

$\Delta_{j,k}^{-}\leq
2(1-\mathds{1}_{A_{j}}\mathds{1}_{A_{k}}\mathds{1}_{C_{j,k}})$ (3.39)

so $(\Delta_{j,k}^{-})^{2}\leq
4(1-\mathds{1}_{A_{j}}\mathds{1}_{A_{k}}\mathds{1}_{C_{j,k}})$, and

$\mathds{E}(\Delta_{j,k}^{-})^{2}\leq
4\left(\mathds{P}(A_{j}^{c})+\mathds{P}(A_{k}^{c})+\mathds{P}(C_{j,k}^{c})\right),$
(3.40) $\mathds{E}(\Delta_{j,k}^{+})^{2}\leq
2\mathds{E}\Delta_{j,k}^{+}=2\mathds{E}\Delta_{j,k}^{-}\leq
4\left(\mathds{P}(A_{j}^{c})+\mathds{P}(A_{k}^{c})+\mathds{P}(C_{j,k}^{c})\right),$
(3.41)

hence

$\mathds{E}(\Delta_{j,k})^{2}\leq
8\left(\mathds{P}(A_{j}^{c})+\mathds{P}(A_{k}^{c})+\mathds{P}(C_{j,k}^{c})\right).$
(3.42)

We may now give an upper bound on $B_{1}(2n)-B_{2}(2n)$:

$\displaystyle B_{1}(2n)-B_{2}(2n)$
$\displaystyle=\frac{1}{4(2n)(2n-1)}\sum_{\begin{subarray}{c}j\neq k\\\
j,k\in\\{1,\dots,2n\\}\end{subarray}}\mathds{E}(\Delta_{j,k})^{2}$
$\displaystyle=\frac{2}{4(2n)(2n-1)}\sum_{\begin{subarray}{c}j\neq k\\\
j\in\\{1,\dots,n\\},k\in\\{1,\dots,2n\\}\end{subarray}}\mathds{E}(\Delta_{j,k})^{2}\quad\text{(by
symmetry)}$
$\displaystyle\leq\frac{2}{n(2n-1)}\mathds{E}\left(\sum_{\begin{subarray}{c}j\neq
k\\\
j\in\\{1,\dots,n\\}\end{subarray}}\mathds{1}_{C_{j,k}^{c}}\right)+\frac{2}{n(2n-1)}\sum_{\begin{subarray}{c}j\neq
k\\\
j\in\\{1,\dots,n\\}\end{subarray}}\mathds{P}(A_{j}^{c})+\mathds{P}(A_{k}^{c})$
$\displaystyle\leq\frac{2}{n(2n-1)}(2n\upsilon-n)+2\exp(-tn)$

So when $n$ is large enough,

$B_{1}(2n)-B_{2}(2n)\leq\frac{2\upsilon}{n}$ (3.43)

and by convexity of $B$, and using the lower bound $0<C\leq B_{1}(2n)$ (see
Theorem 3.12),

${\textrm{Var}}\,LC_{n}=B_{1}(2n)+\dots+B_{2n}(2n)\geq\sum_{i=1}^{\frac{Cn}{2\upsilon}}C-\frac{2\upsilon(i-1)}{n}$

which is equivalent to $C^{2}n/(4\upsilon)$. So for some constant
$C^{\prime}>0$,

${\textrm{Var}}\,LC_{n}\geq C^{\prime}n^{1-\alpha}.$ (3.44)

Once again, this is under the assumption that
$\mathds{E}\widetilde{\Delta_{j}}\leq\exp(-tn)$. If, additionally, this
assumption holds for some $\alpha<1/10$, then by [8] there is convergence of
the properly rescaled $LC_{n}$ to a Gaussian.

There is also a somewhat weaker assumption that would guarantee the linearity
of the variance. Recalling the percolation interpretation of the LCS, we
denote by Geo the (random) set of geodesics, and for any
$a,b\in\\{1,\dots,2n\\}$, $\text{Geo}^{a}$ the set of geodesics when the
$Z_{a}$ is turned into $Z^{\prime}_{a}$, and $\text{Geo}^{a,b}$ the set of
geodesics when $Z_{a}$ is turned into $Z^{\prime}_{a}$ and $Z_{b}$ is turned
into $Z^{\prime}_{b}$. For $j,k\in\\{1,\dots,m\\}$, let $A_{j,k}$ be the
event: there exists $(p,q)$ such that $j<p<k$ and there exist
$(g_{1},g_{2},g_{3},g_{4})\in\text{Geo}\cap\text{Geo}^{j}\cap\text{Geo}^{k}\cap\text{Geo}^{j,k}$
such that $(p,q)\in g_{1}\cap g_{2}\cap g_{3}\cap g_{4}$. In words, this is
the event that it is possible to find $X_{p}$ aligned with $Y_{q}$ no matter
the values of $X_{j}$ and $X_{k}$. Similarly, let $B_{j,k}$ be the event:
there exists $(p,q)$ such that $j<p$ and $k>q$ or $j>p$ and $k<q$ and there
exist
$(g_{1},g_{2},g_{3},g_{4})\in\text{Geo}\cap\text{Geo}^{j}\cap\text{Geo}^{k+n}\cap\text{Geo}^{j,k+n}$
such that $(p,q)\in g_{1}\cap g_{2}\cap g_{3}\cap g_{4}$. In words, this is
the event that it is possible to find $X_{p}$ aligned with $Y_{q}$ no matter
the values of $X_{j}$ and $X_{k}$, and such that $X_{j},Y_{k}$ are not both
"on the same side". Now suppose that
$\mathds{P}(A_{j,k}^{c}),\mathds{P}(B_{j,k}^{c})\leq\exp(\alpha|k-j|)$ for
some constant $\alpha>0$. Then an adaptation of the proof above shows that the
variance is lower bounded by $C^{\prime}n$ for some constant $C^{\prime}>0$.

Acknowledgements: Many thanks to the ICTS in Bengaluru as well as the GESDA
program at IHP in Paris for their hospitality and support while part of this
research was carried out and to R. van Handel for his comments on Theorem 2.1.

## References

  * [1] Charles Bordenave, Gábor Lugosi, and Nikita Zhivotovskiy.  Noise sensitivity of the top eigenvector of a Wigner matrix.  Probability Theory and Related Fields, pages 1–33, 2020.
  * [2] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press, 2013.
  * [3] Olivier Bousquet and Christian Houdré.  Iterated jackknives and two-sided variance inequalities.  In High Dimensional Probability VIII, pages 33–40. Springer, 2019\.
  * [4] Sourav Chatterjee.  A new method of normal approximation.  The Annals of Probability, 36(4):1584–1610, 2008.
  * [5] Dario Cordero-Erausquin and Alexandros Eskenazis.  Talagrand’s influence inequality revisited.  Analysis & PDE, 16(2):571–612, 2023.
  * [6] Christophe Garban and Jeffrey E Steif.  Noise sensitivity of Boolean functions and percolation, volume 5.  Cambridge University Press, 2014.
  * [7] Christian Houdré.  The iterated jackknife estimate of variance.  Statistics & probability letters, 35(2):197–201, 1997.
  * [8] Christian Houdré and Ümit Işlak.  A central limit theorem for the length of the longest common subsequences in random words.  Electronic Journal of Probability, 28:1–24, 2023.
  * [9] Christian Houdré and Abram Kagan.  Variance inequalities for functions of gaussian variables.  Journal of Theoretical Probability, 8(1):23–30, 1995.
  * [10] Christian Houdré and Qingqing Liu.  On the variance of the length of the longest common subsequences in random words with an omitted letter.  arXiv preprint arXiv:1812.09552, 2018.
  * [11] Christian Houdré and Jinyong Ma.  On the order of the central moments of the length of the longest common subsequences in random words.  In High dimensional probability VII, pages 105–136. Springer, 2016\.
  * [12] Christian Houdré and Heinrich Matzinger.  Closeness to the diagonal for longest common subsequences in random words.  Electronic Communications in Probability, 21, 2016.
  * [13] Christian Houdré and Victor Pérez-Abreu.  Covariance identities and inequalities for functionals on Wiener and Poisson spaces.  The Annals of Probability, pages 400–419, 1995.
  * [14] Christian Houdré, Victor Pérez-Abreu, and Donatas Surgailis.  Interpolation, correlation identities, and inequalities for infinitely divisible variables.  Journal of Fourier Analysis and Applications, 4(6):651–668, 1998\.
  * [15] Paata Ivanisvili, Ramon van Handel, and Alexander Volberg.  Rademacher type and Enflo type coincide.  Annals of Mathematics, 192(2):665–678, 2020.
  * [16] Jüri Lember and Heinrich Matzinger.  Standard deviation of the longest common subsequence.  The Annals of Probability, 37(3):1192–1235, 2009.
  * [17] George S. Lueker.  Improved bounds on the average length of longest common subsequences.  Journal of the ACM (JACM), 56(3):1–38, 2009.
  * [18] J Michael Steele.  An Efron-Stein inequality for nonsymmetric statistics.  The Annals of Statistics, 14(2):753–758, 1986.
  * [19] Michel Talagrand.  On Russo’s approximate zero-one law.  The Annals of Probability, pages 1576–1587, 1994.
  * [20] Paweł Wolff.  Some remarks on functionals with the tensorization property.  Bulletin of the Polish Academy of Sciences. Mathematics, 3(55):279–291, 2007.