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


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

| cite | improve this answer | |
  • $\begingroup$ I see how you've interpreted the question, but what I meant was the minimum proportion moving in a given direction, not the minimum proportion who move (in either direction). $\endgroup$ – Hugh Jan 15 '15 at 1:03
  • $\begingroup$ Well, you can understand why I interpreted the question that way, because your original proposed solution also gave a single scalar. I've updated my answer now. $\endgroup$ – user856 Jan 15 '15 at 6:59
  • $\begingroup$ The absolute values are redundant, are they not? (Because $s_i^\pm \geq 0$.) $\endgroup$ – Hugh Jan 15 '15 at 7:18
  • $\begingroup$ Well, not quite, it would have to be $s_i^+$ and $-s_i^-$, so I stuck absolute values on both of them for symmetry. $\endgroup$ – user856 Jan 15 '15 at 7:47


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

  • $\begingroup$ I'm guessing that the $n=3$ case provides sufficient generality. $\endgroup$ – Hugh Jan 14 '15 at 5:03
  • $\begingroup$ That can't be right, because it gives zero for $d=(-0.1,0.2,-0.1,0)$. $\endgroup$ – user856 Jan 14 '15 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.