On a certain discrepancy measure between probability distributions on the symmetric group of permutation $\mathfrak S_n$ 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). For $1 \le i < j \le n$, 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)$. Consider the quantity $\Delta(P,Q) := \sum_{1 \le i < j \le n}|p_{ij}-q_{ij}|$.

Question. Is it possible to reasonably upper-bound $\Delta(P,Q)$ in terms of some distance (e.g total variation) between $P$ and $Q$ ?

 A: I've managed to obtain the bound speculated by E-A in the comments section, namely $\Delta(P,Q) \le Cn^2TV(P,Q)$. The main difference is that my method is very direct.

So, 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) < n^2TV(P,Q),
\end{split}
$$
where the first inequality is Cauchy-Schwarz.

Edit 1: $n^2$ constant is actually tight!
Indeed if $P$ is a dirac and $Q$ is uniform, then $TV(P,Q) = (n!-1)/n! \sim 1$ and $\Delta(P,Q) = n(n-1)/4 = o(n^2)$.
