exercise:12796432f4: Difference between revisions
From Stochiki
(Created page with "<div class="d-none"><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></div> 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>, res...") |
No edit summary |
||
| Line 1: | Line 1: | ||
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 | |||
<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 | distance | ||
<math>\parallel f_X - u\parallel</math> is equal to | <math>\parallel f_X - u\parallel</math> is equal to | ||
| Line 16: | Line 8: | ||
</math> | </math> | ||
'' Hint'': | ''Hint'': Write the permutations in <math>S_n</math> in decreasing order of the difference <math>f_X(\pi) - | ||
Write the permutations in <math>S_n</math> in decreasing order of the difference <math>f_X(\pi) - | |||
u(\pi)</math>. | u(\pi)</math>. | ||
Latest revision as of 23:30, 12 June 2024
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].