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.
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}. $$