A re-examination of the Diaconis-Graham inequality

Abstract

In this paper, we give an alternative and more intuitive proof to one of two classic inequalities given by Diaconis and Graham in 1977. The inequality involves three metrics on the symmetric group, i.e., the set of all permutations of the first $n$ positive integers. Our technique for the proof of the inequality allows us to resolve an open problem posed in that paper: When does equality hold? It also allows us to estimate how often equality holds. In addition, our technique can sometimes be applied for the proof of other inequalities between metrics or pseudo-metrics on the symmetric group.