Document Open Access Logo

Nawrotzki’s Algorithm for the Countable Splitting Lemma, Constructively ((Co)algebraic pearls)

Authors Ana Sokolova, Harald Woracek

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2021.23.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Ana Sokolova
  • Department of Computer Sciences, University of Salzburg, Austria
Harald Woracek
  • Institute of Analysis and Scientific Computing, TU Wien, Austria

Acknowledgements

We are indebted to Paul Levy for bringing this topic to us by asking us several years ago to figure out some details of Nawrotzki’s algorithm, in particular its constructivity.

Cite As Get BibTex

Ana Sokolova and Harald Woracek. Nawrotzki’s Algorithm for the Countable Splitting Lemma, Constructively ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CALCO.2021.23

Abstract

We reprove the countable splitting lemma by adapting Nawrotzki’s algorithm which produces a sequence that converges to a solution. Our algorithm combines Nawrotzki’s approach with taking finite cuts. It is constructive in the sense that each term of the iteratively built approximating sequence as well as the error between the approximants and the solution is computable with finitely many algebraic operations.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Mathematical analysis
  • Mathematics of computing → Probability and statistics
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Semantics and reasoning
Keywords
  • countable splitting lemma
  • distributions with given marginals
  • couplings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. G. Barthe, T. Espitau, J. Hsu, T. Sato, and P.-Y. Strub. *-liftings for differential privacy. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 102:1-102:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.102.
  2. G. Barthe, T. Espitau, J. Hsu, T. Sato, and P.-Y. Strub. Relational ⋆⋆backslashstar-liftings for differential privacy. Log. Methods Comput. Sci., 15(4), 2019. URL: https://doi.org/10.23638/LMCS-15(4:18)2019.
  3. G. Barthe, M. Gaboardi, B. Grégoire, J. Hsu, and P.-Y. Strub. Proving differential privacy via probabilistic couplings. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 749-758. ACM, 2016. URL: https://doi.org/10.1145/2933575.2934554.
  4. M. Beiglböck and N. Juillet. On a problem of optimal transport under marginal martingale constraints. Ann. Probab., 44(1):42-106, 2016. URL: https://doi.org/10.1214/14-AOP966.
  5. P. Berti, L. Pratelli, P. Rigo, and F. Spizzichino. Equivalent or absolutely continuous probability measures with given marginals. Depend. Model., 3(1):47-58, 2015. URL: https://doi.org/10.1515/demo-2015-0004.
  6. E. D'Aniello and J.D.M. Wright. Finding measures with given marginals. Q. J. Math., 51(4):405-416, 2000. URL: https://doi.org/10.1093/qjmath/51.4.405.
  7. M.H.A. Davis and D.G. Hobson. The range of traded option prices. Math. Finance, 17(1):1-14, 2007. URL: https://doi.org/10.1111/j.1467-9965.2007.00291.x.
  8. S. Friedland, J. Ge, and L. Zhi. Quantum Strassen’s theorem. Infin. Dimens. Anal. Quantum Probab. Relat. Top., 23(3):2050020, 29, 2020. URL: https://doi.org/10.1142/S0219025720500204.
  9. N. Gaffke and L. Rüschendorf. On the existence of probability measures with given marginals. Statist. Decisions, 2(1-2):163-174, 1984. Google Scholar
  10. J. Hsu. Probabilistic couplings for probabilistic reasoning. Phd thesis, University of Pennsylvania, 2017. URL: https://repository.upenn.edu/edissertations/3017/.
  11. C. Jones. Probabilistic Non-determinism. Phd thesis, University of Edinburgh, 1989. Google Scholar
  12. A. Jung and R. Tix. The troublesome probabilistic powerdomain. In Third Workshop on Computation and Approximation (Comprox III) (Birmingham, 1997), volume 13 of Electron. Notes Theor. Comput. Sci., page 22. Elsevier Sci. B. V., Amsterdam, 1998. Google Scholar
  13. T. Kamae, U. Krengel, and G.L. O'Brien. Stochastic inequalities on partially ordered spaces. Ann. Probability, 5(6):899-912, 1977. URL: https://doi.org/10.1214/aop/1176995659.
  14. J. Kawabe. A type of Strassen’s theorem for positive vector measures with values in dual spaces. Proc. Amer. Math. Soc., 128(11):3291-3300, 2000. URL: https://doi.org/10.1090/S0002-9939-00-05384-3.
  15. H.G. Kellerer. Funktionen auf Produkträumen mit vorgegebenen Marginal-Funktionen. Math. Ann., 144:323-344, 1961. URL: https://doi.org/10.1007/BF01470505.
  16. H.G. Kellerer. Duality theorems for marginal problems. Z. Wahrsch. Verw. Gebiete, 67(4):399-432, 1984. URL: https://doi.org/10.1007/BF00532047.
  17. H. König. On the marginals of probability contents on lattices. Mathematika, 58(2):319-323, 2012. URL: https://doi.org/10.1112/S0025579311002427.
  18. V.T. Koperberg. Couplings and matchings. Bachelor thesis, Universiteit Leiden, 2016. URL: https://www.universiteitleiden.nl/binaries/content/assets/science/mi/scripties/koperbergbach.pdf.
  19. K. Nawrotzki. Eine Monotonieeigenschaft zufälliger Punktfolgen. Math. Nachr., 24:193-200, 1962. URL: https://doi.org/10.1002/mana.19620240305.
  20. H.J. Skala. The existence of probability measures with given marginals. Ann. Probab., 21(1):136-142, 1993. URL: http://links.jstor.org/sici?sici=0091-1798(199301)21:1<136:TEOPMW>2.0.CO;2-I&origin=MSN.
  21. V. Strassen. The existence of probability measures with given marginals. Ann. Math. Statist., 36:423-439, 1965. URL: https://doi.org/10.1214/aoms/1177700153.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact