[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Let [math]X[/math] denote a particular process that produces elements of

[math]S_n[/math], and let [math]U[/math] denote the uniform process. Let the distribution functions of these processes be denoted by [math]f_X[/math] and [math]u[/math], respectively. Show that the variation distance \newline [math]\parallel f_X - u\parallel[/math] is equal to

[[math]] \max_{T \subset S_n} \sum_{\pi \in T} \Bigl(f_X(\pi) - u(\pi)\Bigr)\ . [[/math]]

Hint: Write the permutations in [math]S_n[/math] in decreasing order of the difference [math]f_X(\pi) - u(\pi)[/math].