TOPICS
Search

Multistochastic Optimal Transport


Multistochastic optimal transport optimizes the integral of a cost over probability measures on a product space whose marginals on every specified collection of k coordinates are fixed. For n coordinates and 1<=k<n, it is called the (n,k) problem; ordinary optimal transport corresponds to (n,k)=(2,1) (Gladkov et al. 2019). In the (3,2) case with all two-coordinate marginals equal to uniform distributions on [0,1]^2, the three coordinates are pairwise independent and uniform.

Write a binary expansion x=sum_(i>=1)2^(-i)x_i, x_i in {0,1}, and let

 f(x)=sum_(i>=1)a_ix_i, a_i>=0, sum_(i)a_i<infty, a_i>sum_(j>i)a_j.
(1)

For independent random variables X,Y with uniform distribution, Gvozdev and Kolesnikov (2026) proved that among all pairwise independent uniform triples, the choice Z=X direct sum Y minimizes E[f(X)f(Y)f(Z)], while Z=1-(X direct sum Y) maximizes it. The symbol  direct sum means exclusive OR of corresponding binary digits; ambiguities at numbers with two binary expansions have probability zero. The minimizing plan is supported on the tetrix with vertices (0,0,0), (0,1,1), (1,0,1), and (1,1,0). The maximizing plan lies on its reflection with vertices (0,0,1), (0,1,0), (1,0,0), and (1,1,1). The case f(x)=x, whose coefficients satisfy equality instead of the strict domination above, was established separately by Gladkov et al. (2019).

For the geometric coefficients a_i=a^(-i), a>=2, Gvozdev and Kolesnikov (2026) also constructed a dual certificate. Put C_a(x)=sum_(i)a^(-i)x_i, g(x)=2C_a(x)-1/(a-1), and phi(u,v)=uv+(u+v)/2+1/3. On sequences of binary digits, let T delete the first digit if it is 1, and delete the first digit and complement all remaining digits if it is 0. The bounded function

 H(x,y)=sum_(k>=1)a^(-3k)phi(g(T^kx),g(T^ky))
(2)

satisfies

 -H(x,y)-H(y,z)-H(z,x)<=g(x)g(y)g(z),
(3)

with equality for z=x direct sum y. Integrating the left side depends only on the fixed two-coordinate marginals, which certifies minimality for the centered cost. The authors report that GPT-6 Astra contributed to developing these dual solutions, whose arguments they checked.


See also

Optimal Transport, Probability Measure, Tetrix

Explore with Wolfram|Alpha

References

Gladkov, N. A.; Kolesnikov, A. V.; and Zimin, A. P. "On Multistochastic Monge-Kantorovich Problem, Bitwise Operations, and Fractals." Calc. Var. PDE 58, 173, 2019. https://doi.org/10.1007/s00526-019-1610-4.Gvozdev, D. and Kolesnikov, A. "On Pairwise Independent and Strongly Correlated Random Variables." 16 Nov 2026. https://arxiv.org/abs/2611.20365v1.

Cite this as:

Weisstein, Eric W. "Multistochastic Optimal Transport." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MultistochasticOptimalTransport.html

Subject classifications