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$ ?

Motivation. The question arises from a statistical learning-theoretic study of rankings (of say, user-based google search results or movies on Neflix). Think of $P$ and $Q$ as datasets of such rankings. Quantities of the form $\Delta (P,\hat{P}_N)$ appear in bounds on the rate of learning an optimal ranking from empirical samples from some unknown oracle distribution $P$. Here $\hat{P}_N$ is the empirical version of $P$ based on $N$ iid samples.

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$

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$

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$ ?

Motivation. The question arises from a statistical learning-theoretic study of rankings (of say, user-based google search results or movies on Neflix). Think of $P$ and $Q$ as datasets of such rankings. Quantities of the form $\Delta (P,\hat{P}_N)$ appear in bounds on the rate of learning an optimal ranking from empirical samples from some unknown oracle distribution $P$. Here $\hat{P}_N$ is the empirical version of $P$ based on $N$ iid samples.

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(n-1)/4 = o(n^2)$. $\quad\quad\quad\Box$

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$ ?

Motivation. The question arises from a statistical learning-theoretic study of rankings (of say, user-based google search results or movies on Neflix). Think of $P$ and $Q$ as datasets of such rankings. Quantities of the form $\Delta (P,\hat{P}_N)$ appear in bounds on the rate of learning an optimal ranking from empirical samples from some unknown oracle distribution $P$. Here $\hat{P}_N$ is the empirical version of $P$ based on $N$ iid samples.

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$

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

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

Motivation. The question arises from a statistical learning-theoretic study of rankings (of say, user-based google search results or movies on Neflix). Think of $P$ and $Q$ as datasets of such rankings. Quantities of the form $\Delta (P,\hat{P}_N)$ appear in bounds on the rate of learning an optimal ranking from empirical samples from some unknown oracle distribution $P$. Here $\hat{P}_N$ is the empirical version of $P$ based on $N$ iid samples.

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(n-1)/4 = o(n^2)$. $\quad\quad\quad\Box$

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$ ?

Motivation. The question arises from a statistical learning-theoretic study of rankings (of say, user-based google search results or movies on Neflix). Think of $P$ and $Q$ as datasets of such rankings. Quantities of the form $\Delta (P,\hat{P}_N)$ appear in bounds on the rate of learning an optimal ranking from empirical samples from some unknown oracle distribution $P$. Here $\hat{P}_N$ is the empirical version of $P$ based on $N$ iid samples.

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(n-1)/4 = o(n^2)$. $\quad\quad\quad\Box$