Abstract
We consider the problem of approximating distributions of Bernoulli random variables by applying Boolean functions to independent random variables with distributions from a given set. For a set B of Boolean functions, the set of approximable distributions forms an algebra, named the approximation algebra of Bernoulli distributions induced by B. We provide a complete description of approximation algebras induced by most clones of Boolean functions. For remaining clones, we prove a criterion for approximation algebras and a property of algebras that are finitely generated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Couceiro, M., Lehtonen, E.: Galois theory for sets of operations closed under permutation, cylindrification, and composition. Algebra Universalis. 67, 273–297 (2012)
Dapić, P., Ježek, J., Marković, P., Stanovský, D.: Star-linear equational theories of groupoids. Algebra Universalis. 56, 357–397 (2007)
Denecke, K.: The partial clone of linear terms. Sib. Math. J. 57, 589–598 (2016)
Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968)
Frankl, P.: On Sperner families satisfying an additional condition. J. Comb. Theory (A) 20, 1–11 (1976)
Gill, A.: Synthesis of probability transformers. J. Franklin Inst. 274, 1–19 (1962)
Golumbic, M.C., Gurvich, V.A.: Read-once functions. In: Crama, Y., Hammer, P.L. (eds.) Boolean Functions: Theory, Algorithms and Applications, pp. 448–486. Cambridge University Press, Cambridge (2011)
Grenander, U.: Probabilities on Algebraic Structures. Wiley, New York (1963)
Kolpakov, R.M.: Criterion of generativeness of sets of rational probabilities by a class of Boolean functions. Discrete Appl. Math. 135, 125–142 (2004)
Lau, D.: Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory. Springer, New York (2006)
Muchnik, A.A., Gindikin, S.G.: The completeness of a system made up of nonreliable elements realizing a function of algebraic logic. Sov. Phys., Dokl 7, 477–479 (1962)
von Neumann, J.: Various techniques used in connection with random digits. Appl. Math. Ser 12, 36–38 (1951). Notes by G.E. Forstyle, Nat. Bur. Stand
Salimov, F.I.: A family of distribution algebras. Soviet Math. (Iz. VUZ) 32, 106–118 (1988)
Shaltiel, R.: An Introduction to Randomness Extractors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming. ICALP 2011. LNCS 6756, pp. 21–41. Springer, Berlin (2011)
Skhirtladze, R.L.: On a method of constructing a Boolean variable with a given probability distribution. Discret. Analiz 7, 71–80 (1966). (Russian)
Yashunsky, A.D.: On probability transformations by read-once Boolean formulas. In: Proc. of the XVI Int. workshop Synthesis and complexity of control systems (Saint-Petersburg, June 26–30, 2006), pp. 150–155. Lomonosov MSU, Moscow (2006). (Russian)
Zhou, H., Loh, P., Bruck, J.: The synthesis and analysis of stochastic switching circuits. arXiv:1209.0715v1 (2012)
Acknowledgements
The author expresses his gratitude to O. M. Kasim-Zade for his attention to the present work.
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by Á. Szendrei.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research was supported by the RScF Grant, Project 14-21-00025 P.
Rights and permissions
About this article
Cite this article
Yashunsky, A.D. Clone-induced approximation algebras of Bernoulli distributions. Algebra Univers. 80, 5 (2019). https://doi.org/10.1007/s00012-019-0578-4
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-019-0578-4