On a certain discrepancy measure between probability distributions on the symmetric group of permutation S n Let S n be the symmetric group of permutations on n objects and let P and Q be a probability distributions on S n (i.e P and Q are points on the n!-simplex). For 1 ≤ i &lt; j ≤ n, let p i j be the probability that a random permutation σ drawn from P ranks j ahead of i, i.e satisfies σ ( i ) &lt; σ ( j ). Consider the quantity Δ ( P , Q ) := ∑ 1 ≤ i &lt; j ≤ n | p i j − q i j | .Is it possible to reasonably upper-bound Δ ( P , Q ) in terms of some distance (e.g total variation) between P and Q ?

Question

On a certain discrepancy measure between probability distributions on the symmetric group of permutation             S        n  Let             S        n   be the symmetric group of permutations on n objects and let P and Q be a probability distributions on             S        n   (i.e P and Q are points on the n!-simplex). For   1  ≤  i  &amp;lt;  j  ≤  n, let       p          i      j       be the probability that a random permutation   σ drawn from P ranks j ahead of i, i.e satisfies   σ  (  i  )  &amp;lt;  σ  (  j  ). Consider the quantity   Δ  (  P  ,  Q  )  :=      ∑          1      ≤      i      &amp;lt;      j      ≤      n            |        p          i      j        −      q          i      j            |  .Is it possible to reasonably upper-bound   Δ  (  P  ,  Q  ) in terms of some distance (e.g total variation) between P and Q ?

mangoslush27fig · Accepted Answer

Step 1I&#039;ve managed to obtain the bound speculated by E-A in the comments section, namely   Δ  (  P  ,  Q  )  ≤  C      n    2    T  V  (  P  ,  Q  ). The main difference is that my method is very direct.Step 2So, let       E          i      j        :=  {  σ  ∈            S        n    ∣  σ  (  i  )  &amp;lt;  σ  (  j  )  }. This is the set of permutations which rank j ahead of i. One can then rewrite       p          i      j        =            P              σ      ∼      P        [  σ  ∈      E          i      j        ]  =      ∑          σ      ∈                        S                n              P  (  σ  )      1          σ      ∈              E                  i          j                    . Thus                    Δ        (        P        ,        Q        )                            :=                  ∑                      i            &amp;lt;            j                                    |                          p                      i            j                          −                  q                      i            j                                    |                =                  ∑                      i            &amp;lt;            j                                    |                      ∑                          σ              ∈                              E                                  i                  j                                                              (          P          (          σ          )          −          Q          (          σ          )          )          |                ≤                  ∑                      i            &amp;lt;            j                                    ∑                      σ            ∈                          E                              i                j                                                              |          P          (          σ          )          −          Q          (          σ          )          |                                                           ≤                  ∑                      i            &amp;lt;            j                                    ∑                      σ            ∈                                          S                            n                                                |          P          (          σ          )          −          Q          (          σ          )          |                =                              n            (            n            −            1            )                    2                          ∑                      σ            ∈                                          S                            n                                                |          P          (          σ          )          −          Q          (          σ          )          |                                                  =        n        (        n        −        1        )        T        V        (        P        ,        Q        )        &amp;lt;                  n          2                T        V        (        P        ,        Q        )        ,            where the first inequality is Cauchy-Schwarz.

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

Answered question

Answer & Explanation

New Questions in High school geometry