majorization vs total variance Let $u=(u_1,\ldots, u_n)$ and $v=(v_1,\ldots, v_n)$ be two distributions. $u$ is majorized by $v$ and $v$ is weakly majorized by $(1+\epsilon) u$. Namely, for any $1\leq i\leq n$,
$\sum_{j\leq i} u_j\leq\sum_{j\leq i} v_j\leq(1+\epsilon)\sum_{j\leq i} u_j$.
What is the best upper bound on $\|u-v\|_{TV}$, where $\|\cdot\|_{TV}$ is the total variance. Can we have an upper bound independent of the size $n$? Thanks.
 A: I don't think that with only that sort of multplicative constraint on the cdf (or, more or less, on the Kolmogorov distance between $u$ and $v$), you can get any good bound -- i.e., anything better than constant. Indeed, assume $n = \omega\left(\frac{1}{\varepsilon}\right)$. Take $v_1 = u_1 = \frac{1}{2}$, and then, for $k \leq 2\cdot\frac{2}{3\varepsilon}$,
$$
u_{k+1} = \begin{cases}
\frac{\varepsilon}{2} &\text{ if } k \text{ odd}\\
\varepsilon &\text{ if } k \text{ even}\\
\end{cases}
$$
and
$$
v_{k+1} = \begin{cases}
\frac{\varepsilon}{2} &\text{ if } k \text{ even}\\
\varepsilon &\text{ if } k \text{ odd.}\\
\end{cases}
$$
and $v_k = u_k = 0$ for $2\cdot\frac{2}{3\varepsilon} +1 < k \leq n$. That is, the distributions look like
$$\begin{align}
u &= (\frac12, \frac{\varepsilon}{2}, \varepsilon, \frac{\varepsilon}{2}, \varepsilon, \dots, \frac{\varepsilon}{2}, \varepsilon, 0, \dots, 0) \\
v &= (\frac12, \varepsilon, \frac{\varepsilon}{2}, \varepsilon, \frac{\varepsilon}{2} \dots, \varepsilon, \frac{\varepsilon}{2} 0, \dots, 0)
\end{align}$$
Then we do have, if I'm not mistaken,
$$
\sum_{k=1}^i u_j\leq\sum_{k=1}^i v_j \leq (1+\varepsilon)\sum_{k=1}^i u_j 
$$
for all $i\in[n]$; yet you get
$$
\lVert u-v\rVert_{\rm TV} = \frac{1}{2}\lVert u-v\rVert_{1} = \frac{1}{2}\cdot\frac{2}{3\varepsilon}\cdot \varepsilon = \frac{1}{3}.
$$
