**Disclaimer.** This is a follow up to a question I asked and answered on SE <https://math.stackexchange.com/q/3579311/168758>. The question was about upper-bounds. Here I'm interested in lower bounds, and they seem harder to get...


Question
========


So, let $\mathfrak S\_n$ be the symmetric group of permutations on $n$ objects and let $P$ and $Q$ be a probability distributions on $\mathfrak S\_n$ (i.e $P$ and $Q$ are points on the $n!$-simplex). Let $p\_{ij}$ be the probability that a random permutation $\sigma$ drawn from $P$ ranks $j$ ahead of $i$, i.e satisfies $\sigma(i) < \sigma(j)$. Note that $p\_{ii} = 0$ and $p\_{ji} = 1-p\_{ij}$ for every $i,j \in \{1,\ldots,n\}$ with $i \ne j$. Consider the quantity $\Delta(P,Q) := \sum\_{1 \le i < j \le n}|p\_{ij}-q\_{ij}|$.



> 
> What is a reasonable lower-bound for $\Delta(P,Q)$ in terms of some standard measure of distance (e.g total variation) between $P$ and $Q$ ?
> 
> 
> 




---


Partial answer: an upper bound via total variation
==================================================



> 
> **Claim.** $\Delta(P,Q) \le n(n-1)TV(P,Q)$. Moreover, the $n^2$ factor in the bound is tight.
> 
> 
> 


**Proof.** let $E\_{ij} := \{\sigma \in \mathfrak S\_n \mid \sigma(i) < \sigma(j)\}$. This is the set of permutations which rank $j$ ahead of $i$. One can then rewrite
$p\_{ij} = \mathbb P\_{\sigma \sim P}[\sigma \in E\_{ij}] = \sum\_{\sigma \in \mathfrak S\_n}P(\sigma)1\_{\sigma \in E\_{ij}}$. Thus


$$
\begin{split}
\Delta(P,Q) &:= \sum\_{i < j}|p\_{ij}-q\_{ij}| = \sum\_{i < j}\left|\sum\_{\sigma \in E\_{ij}}(P(\sigma)-Q(\sigma))\right| \le \sum\_{i < j}\sum\_{\sigma \in E\_{ij}}\left|P(\sigma)-Q(\sigma)\right|\
 \\
&\le \sum\_{i < j}\sum\_{\sigma \in \mathfrak S\_n}\left|P(\sigma)-Q(\sigma)\right| = \frac{n(n-1)}{2}\sum\_{\sigma \in \mathfrak S\_n}\left|P(\sigma)-Q(\sigma)\right|\\
&= n(n-1)TV(P,Q),
\end{split}
$$
where the first inequality is Cauchy-Schwarz.


We now show that the $n^2$ factor in the bound is optimal. Indeed if $P$ is a dirac and $Q$ is uniform, then $p\_{ij} \in \{0,1\}$ and $q\_{ij}=1/2$ if $i \ne j$. Thus, $\Delta(P,Q) = {n\choose 2}(1/2) = n(n-1)/4 = o(n^2)$. $\quad\quad\quad\Box$



On bounding a certain discrepancy between probability distributions on the symmetric group
There is no non-trivial lower bound as it is well possible that $P\neq Q$, whereas $p\_{ij}=q\_{ij}$ for all pairs of $i$ and $j$. The reason is that (as you point out), these numbers are nothing but the values of the measure $P$ (resp., $Q$) on the sets $E\_{ij}$, and the collection of the sets $\{E\_{ij}\}$ is just not big enough to separate measures on the symmetric group. For instance, let $P$ be the uniform measure, and let $Q$ be the uniform measure on the union of the cycle $(1,2,\dots,n)$ and of its product with the involution $\sigma(i)=n-i$. Then $p\_{ij}=q\_{ij}=1/2$ for all $i,j$.


By the way, your upper bound immediately follows from the inequality 
$$|P(A)-Q(A)| \le \|P-Q\|/2$$ 
(the RHS of which is what probabilists erroneously like to call the total variation) satisfied for any subset of the symmetric group (in particular, for $A=E\_{ij}$).


