Grinstead-Snell-Probability · Problem 3.3.4

Conditional Probability

Mathematics · variation-distance

Problem

Let

X

denote a particular process that produces elements of

S_n

, and let

U

denote the uniform process. Let the distribution functions of these processes be denoted by

f_X

and

u

, respectively. Show that the variation distance

\| f_X - u \|

is equal to

\max_{T \subset S_n} \sum_{\pi \in T} \left( f_X(\pi) - u(\pi) \right).

Hint: Write the permutations in

S_n

in decreasing order of the difference

f_X(\pi) - u(\pi)