On multistochastic Monge–Kantorovich problem, bitwise operations, and fractals

Calculus of Variations and Partial Differential Equations. 2019. Vol. 58. No. 173. P. 1–33.

Gladkov N., Kolesnikov A., Zimin A.

The multistochastic (n, k)-Monge–Kantorovich problem on a product space ∏ni=1Xi∏i=1nXi is an extension of the classical Monge–Kantorovich problem. This problem is considered on the space of measures with fixed projections onto Xi1×⋯×XikXi1×⋯×Xik for all k-tuples {i1,…,ik}⊂{1,…,n}{i1,…,ik}⊂{1,…,n} for a given 1≤k<n1≤k<n. In our paper we study well-posedness of the primal and the corresponding dual problem. Our central result describes a solution ππ to the following important model case: n=3,k=2,Xi=[0,1]n=3,k=2,Xi=[0,1], the cost function c(x,y,z)=xyzc(x,y,z)=xyz, and the corresponding two-dimensional projections are Lebesgue measures on [0,1]2[0,1]2. We prove, in particular, that the mapping (x,y)→x⊕y(x,y)→x⊕y, where ⊕⊕ is the bitwise addition (xor- or Nim-addition) on [0,1]≅Z∞2[0,1]≅Z2∞, is the corresponding optimal transportation. In particular, the support of ππ is the Sierpiński tetrahedron. In addition, we describe a solution to the corresponding dual problem.

Keywords: fractals, фракталы, Optimal transportation, оптимальная транспортировка

Publication based on the results of: ­­­Uncertainty quantification in high-dimensional statistics (2019)