The negative partial-sum conjecture for normalization of aggregated Markov-chain distributions

The indexed conjecture holds, as do both other unproved normalization conjectures in the same source. In fact there is a sharp necessary-and-sufficient criterion, and the source's positive-coordinate constant $9/8$ is optimal.

Let $x\in\mathbb R^d\setminus\{0\}$, $a=\|x\|_1$, and let $p$ be an arbitrary probability vector. We ask when

$$\left\|\frac{x}{a}-p\right\|_1 \le \|x-p\|_1$$

holds for every such $p$.

For $a>1$, the exact criterion is

$$\boxed{ \text{There is no }S\subseteq\{i:x_i>0\} \text{ satisfying } \frac a2 < \sum_{i\in S}x_i < \frac{a(3-a)}2. }$$

To prove this, put $\ell_i=x_i/a$ and $c_i=(a-1)\ell_i$ for $x_i>0$. Direct coordinatewise evaluation gives

$$\|x-p\|_1- \left\|\frac{x}{a}-p\right\|_1 = a-1 - 2\sum_{i:x_i>0} \min\bigl((p_i-\ell_i)_+,c_i\bigr).$$

For $S\subseteq\{i:x_i>0\}$, let $L_S=\sum_{i\in S}\ell_i$. Optimizing over the probability simplex gives exactly

$$\sup_p \sum_{i:x_i>0} \min\bigl((p_i-\ell_i)_+,c_i\bigr) = \max_{S:L_S\le1} \min\{1-L_S,(a-1)L_S\}.$$

Indeed, for each active set the summand is bounded by both available probability mass and total capacity; conversely, first allocate its baseline masses $\ell_i$, then distribute the remaining mass up to these capacities. Therefore the normalization fails for some $p$ precisely when

$$\frac12<L_S<\frac{3-a}{2},$$

equivalently when the boxed forbidden subset exists. In particular, $a\ge2$ always implies improvement.

Now set

$$N_-=\sum_{x_i<0}(-x_i), \qquad P_+=\sum_{x_i>0}x_i, \qquad a=P_++N_-.$$

If $N_-\ge1$, the cases $a=1$ and $a\ge2$ are immediate. For $1<a<2$, every positive-coordinate subset satisfies

$$\sum_{i\in S}x_i\le P_+=a-N_-\le a-1<\frac a2.$$

Thus normalization improves the error universally whenever total negative mass is at least $1$. In particular:

• A coordinate $x_i\le-1$ proves Conjecture 4.1.3.
• A sum of $d-1$ distinct coordinates at most $-1$ implies $N_-\ge1$, proving the indexed Conjecture 4.1.5.

For the remaining source conjecture, suppose some $x_j=v\ge9/8$. Again only $1<a<2$ needs consideration. Any subset containing $j$ has sum at least

$$v\ge\frac98\ge\frac{a(3-a)}2,$$

since the last quadratic has maximum $9/8$. Any positive-coordinate subset omitting $j$ has sum at most

$$a-v<\frac a2.$$

Hence no forbidden subset exists, proving Conjecture 4.1.4.

The constant is sharp: for every $1<v<9/8$, take

$$x=(v-3/2,v),\qquad p=(0,1).$$

Then $a=3/2$, but

$$\|x-p\|_1=\frac12, \qquad \left\|\frac xa-p\right\|_1 = 2-\frac{4v}{3} > \frac12.$$

For completeness, $a=1$ gives equality identically. If $0<a<1$, universal improvement occurs only for $d=1,x=(a)$, or $d=2,x=(a/2,a/2)$: testing $p=e_j$ first forces all coordinates positive and then $x_j\ge a/2$ for every $j$; the two-dimensional equal-coordinate case follows from the triangle inequality.

Source: P. Sonnentag, “Finding the Smallest Possible Exact Aggregation of a Markov Chain,” arXiv:2507.11157, equation (4.1) and Conjectures 4.1.3–4.1.5.