The claim
Fix a measurement scenario with incidence matrix M. Its rows are the pairs (context C, joint outcome of C), and its columns are the global assignments g. The entry is 1 when g restricted to C gives that outcome. An empirical model e is the vector v_e ≥ 0 of its context-wise probabilities. As in LIT-265, Eq. 3,
NCF(e) = max { 1·b : Mb ≤ v_e, b ≥ 0 }, CF(e) = 1 − NCF(e).
Let y₁, …, y_K be the vertices of the dual polyhedron P = { y ≥ 0 : Mᵀy ≥ 1 }. Then:
- NCF(e) = min_k y_k·v_e, so NCF is concave and piecewise linear in v_e, and CF is convex and piecewise linear.
- |CF(e) − CF(e′)| ≤ (max_k ‖y_k‖₁)·‖v_e − v_e′‖_∞ for any two empirical models on the scenario.
Proof
The primal is feasible and bounded. b = 0 is feasible. Each column of M has exactly one 1 among the rows of any one context C, because a global assignment gives one outcome on C. So summing the rows of C in Mb ≤ v_e gives 1·b ≤ Σ_(rows of C) v_e = 1. A feasible, bounded linear programme has a dual that attains the same value: NCF(e) = min { y·v_e : y ∈ P }.
The dual minimum is at a vertex. P is nonempty. Take the indicator y of the rows of one context: each column has exactly one 1 there, so Mᵀy = 1. P lies in the nonnegative orthant, so it contains no line. It is therefore the convex hull of its finitely many vertices plus its recession cone, and the recession cone is nonnegative. Since v_e ≥ 0, moving along a recession direction does not lower y·v_e. So the minimum is attained at a vertex, and NCF(e) = min_k y_k·v_e.
Piecewise linearity and the bound. A minimum of finitely many linear functions is concave and piecewise linear, which gives (1). For (2), |min_k a_k − min_k b_k| ≤ max_k |a_k − b_k|, and |y_k·(v_e − v_e′)| ≤ ‖y_k‖₁ ‖v_e − v_e′‖_∞.
Convexity under mixing also follows from (1). It agrees with LIT-265’s Theorem 2, which THEORY-165 holds.
What it does not say
- How large the constant is. It is the largest ℓ₁ norm of a dual vertex, a property of the scenario that this does not bound. In a sample of 300 random mixtures on CHSH, the largest ‖y*‖₁ seen was 8 (THEORY-165’s check), and that is not the constant.
- Anything about the underlying states or chains. The bound is in the empirical table. A drift result must first bound the change in every context’s distribution.
- Anything across scenarios, or for signalling data, where CF is undefined.
- That the decomposition varies continuously. Only its weight does.