zbMATH — the first resource for mathematics

Inconsistent marginal problem on finite sets. (English) Zbl 0907.60003
Beneš, Viktor (ed.) et al., Distributions with given marginals and moment problems. Proceedings of the 1996 conference, Prague, Czech Republic. Dordrecht: Kluwer Academic Publishers. 235-242 (1997).
Summary: An algorithm (Tetris) for finding a joint distribution \(P\) (on a finite set) whose marginals are identical to given less-dimensional distributions (oligodistributions) was presented by the author [in: IPMU ‘96. Proc. 6th Int. IPMU Conf., Vol. II, 763-768 (1996)]. The problem, in a more general setting, is known as marginal problem [see H. G. Kellerer, Z. Wahrscheinlichkeitstheorie Verw. Geb. 3, 247-270 (1964; Zbl 0126.34003)]. The Tetris algorithm ends in a finite number of steps \((O(nmK))\) if the set of less-dimensional distributions is strongly consistent, i.e. at least one such \(P\) exists. If it is not the case, i.e. the given distributions are not consistent, the fact is found in a finite number of steps, too. A new algorithm (Pentis), suggested in this paper, can be applied in this situation solving thus inconsistent marginal problem. It generates a distribution whose marginals differ a little (in absolute values) from the given oligodistributions. Being exponential in number of variables, both algorithms are effective for small-size marginal problems only.
For the entire collection see [Zbl 0885.00054].

60A10 Probabilistic measure theory
Zbl 0126.34003