On bounding a certain discrepancy between probability distributions on the symmetric group

Question

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$

Answer 1

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}$).