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].