Clone-induced approximation algebras of Bernoulli distributions. (English) Zbl 1472.08005
Summary: 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.
MSC:
| 08A40 | Operations and polynomials in algebraic structures, primal algebras |
| 60B99 | Probability theory on algebraic and topological structures |
References:
| [1] | Couceiro, M., Lehtonen, E.: Galois theory for sets of operations closed under permutation, cylindrification, and composition. Algebra Universalis. 67, 273-297 (2012) · Zbl 1257.08002 · doi:10.1007/s00012-012-0184-1 |
| [2] | Dapić, P., Ježek, J., Marković, P., Stanovský, D.: Star-linear equational theories of groupoids. Algebra Universalis. 56, 357-397 (2007) · Zbl 1127.03023 · doi:10.1007/s00012-007-2007-3 |
| [3] | Denecke, K.: The partial clone of linear terms. Sib. Math. J. 57, 589-598 (2016) · Zbl 1351.08002 · doi:10.1134/S0037446616040030 |
| [4] | Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968) · Zbl 0155.23101 |
| [5] | Frankl, P.: On Sperner families satisfying an additional condition. J. Comb. Theory (A) 20, 1-11 (1976) · Zbl 0328.05002 · doi:10.1016/0097-3165(76)90073-X |
| [6] | Gill, A.: Synthesis of probability transformers. J. Franklin Inst. 274, 1-19 (1962) · Zbl 0147.17501 · doi:10.1016/0016-0032(62)90894-3 |
| [7] | Golumbic, MC; Gurvich, VA; Crama, Y. (ed.); Hammer, PL (ed.), Read-once functions, 448-486 (2011), Cambridge · doi:10.1017/CBO9780511852008.011 |
| [8] | Grenander, U.: Probabilities on Algebraic Structures. Wiley, New York (1963) · Zbl 0131.34804 |
| [9] | Kolpakov, R.M.: Criterion of generativeness of sets of rational probabilities by a class of Boolean functions. Discrete Appl. Math. 135, 125-142 (2004) · Zbl 0902.05052 · doi:10.1016/S0166-218X(02)00300-1 |
| [10] | Lau, D.: Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory. Springer, New York (2006) · Zbl 1105.08001 |
| [11] | 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) · Zbl 0121.01508 |
| [12] | 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 |
| [13] | Salimov, F.I.: A family of distribution algebras. Soviet Math. (Iz. VUZ) 32, 106-118 (1988) · Zbl 0683.46032 |
| [14] | 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) · Zbl 1333.68289 |
| [15] | Skhirtladze, R.L.: On a method of constructing a Boolean variable with a given probability distribution. Discret. Analiz 7, 71-80 (1966). (Russian) · Zbl 0168.26103 |
| [16] | 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) |
| [17] | Zhou, H., Loh, P., Bruck, J.: The synthesis and analysis of stochastic switching circuits. arXiv:1209.0715v1 (2012) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
