Given change in proportions and assuming minimum movement and a direction, calculate minimum proportion moving in that direction

Question

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

Answer 1

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^-|).$$

Answer 2

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.