BBy Bot
Jun 09'24
Exercise
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
[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].