Given change in proportions and assuming minimum movement and a direction, calculate minimum proportion moving in that direction Let $x_1, \dots, x_n$ with $\sum x_i = 1$ be proportions of a discrete distribution. Suppose the distribution changes and let $y_1, \dots, y_n$ be the subsequent proportions (and so $\sum y_i = 1$ too). Let $d_i = y_i - x_i$ be given. 
For example consider that the distribution is the distribution of grades A-F of a cohort of school children over two years. 
Assuming that a student can move at most one grade in a year (i.e. an A student in year 1 can only be an A student or a B student in year 2), and given the changes $d_i$, what is the minimum proportion of the distribution to have moved up (or down)?
Consider $d' = (0.1, 0, 0, -0.1)$ then the answer is 30% have moved down (and 0% have moved up). That is, I want a function $f(d') = (0.3, 0)$.
 A: Let
$$s_j = \sum^j_{i=1} d_i \quad s_j' = \sum^n_{i=j} d_i$$
(i.e. the cumulative sums ascending and descending) and then
$$f = (\sum s_j', \sum s_j)$$
I believe
$$-\sum_{j=1}^{n-1} (n-j-1)d_{j}$$ 
gives the (signed) movement, though I can't prove it.
A: This feels like a minimum-cost flow problem, but the exact correspondence with a standard formulation escapes me. Anyway, let the minimum total flow be $g(d_1,\ldots,d_n)$.
The $d_1$ extra students in grade $1$ have to have come from grade $2$, so
$$g(d_1,d_2,\ldots,d_n) = |d_1| + g(0,d_1+d_2,\ldots,d_n).$$
Furthermore, if the first component is zero, then there is no need for any flow between grades $1$ and $2$, so
$$g(0,d_2,\ldots,d_n) = g(d_2,\ldots,d_n).$$
Therefore,
$$\begin{align}
g(d_1,d_2,\ldots,d_n) &= |d_1| + g(d_1+d_2,\ldots,d_n) \\
&\vdots \\
&= |d_1| + |d_1+d_2| + \cdots + |d_1+d_2+\cdots+d_n|.
\end{align}$$
The last term has to be zero, of course; I've just left it there to show how the recursion terminates.
In short, compute the running sums $s_i := \sum_{j=1}^id_j$, and then you have $g(d_1,\ldots,d_n)=\sum_{i=1}^n|s_i|$.

Actually, this procedure fully characterizes the minimum flow, and from it you can compute any other quantity you need.
The value of $s_i$ is the signed flow to grade $i$ from grade $i+1$. The minimum downward flow between those two grades is therefore $s_i^+:=\max(s_i,0)$, and the minimum upward flow is the absolute value of $s_i^-:=\min(s_i,0)$. So the total downward and upward flows are
$$f(d_1,\ldots,d_n) = \sum_{i=1}^n(|s_i^+|,|s_i^-|).$$
