Algebras of probability distributions on finite sets

A. D. Yashunsky

Informatics and Automation, Complex analysis, mathematical physics, and applications, Tome 301 (2018), pp. 320-335.

Résumé

We consider the problems of transforming random variables over finite sets by discrete functions. We describe the problems of exact and approximate expression of random variables as functions of other random variables from the point of view of universal algebra and provide a review of results in the area. Sufficient conditions are obtained for a system of transforming functions to allow the approximation of an arbitrary probability distribution on a finite set using a given nondegenerate initial distribution.

Bibliographie

[1] Barnes G. R., Cerrito P. B., Levi I., “Random walks on finite semigroups”, J. Appl. Probab., 35:4 (1998), 824–832 | DOI | MR | Zbl

[2] R. G. Bukharaev, “On controlling generators of random numbers”, Probabilistic Methods and Cybernetics. II, Collected works of N.G. Chebotarev Research Institute of Mathematics and Mechanics at the Kazan University, Uch. Zap. Kazan. Gos. Univ., 123, no. 6, Kazan. Univ., Kazan, 1963, 68–87 | MR

[3] R. G. Bukharaev, “Probabilistic automata”, J. Sov. Math., 13:3 (1980), 359–386 | DOI | MR | Zbl | Zbl

[4] Chakrapani L. N., Korkmaz P., Akgul B. E., Palem K. V., “Probabilistic system-on-a-chip architectures”, ACM Trans. Des. Autom. Electron. Syst., 12:3 (2007), 29 | DOI

[5] Gill A., “Synthesis of probability transformers”, J. Franklin Inst., 274:1 (1962), 1–19 | DOI | Zbl

[6] Gill A., “On a weight distribution problem, with application to the design of stochastic generators”, J. Assoc. Comput. Mach., 10:1 (1963), 110–121 | DOI | MR | Zbl

[7] U. Grenander, Probabilities on Algebraic Structures, J. Wiley Sons, New York, 1963 | MR | MR | Zbl

[8] Knuth D. E., Yao A. C., “The complexity of nonuniform random number generation”, Algorithms and complexity: New directions and recent results, Acad. Press, New York, 1976, 357–428 | MR

[9] R. M. Kolpakov, “On generation of some classes of rational numbers by probabilistic $\pi$-nets”, Moscow Univ. Math. Bull., 46:2 (1991), 27–29 | MR | Zbl | Zbl

[10] R. M. Kolpakov, “On the generation of rational numbers by probabilistic contact nets”, Moscow Univ. Math. Bull., 47:5 (1992), 41–46 | MR | Zbl | Zbl

[11] R. M. Kolpakov, “On the bounds for the complexity of generation of rational numbers by stochastic contact $\pi$-networks”, Moscow Univ. Math. Bull., 47:6 (1992), 34–36 | MR | Zbl | Zbl

[12] R. M. Kolpakov, “Generation of rational numbers by probabilistic contact $\pi$-networks”, Discrete Math. Appl., 4:4 (1994), 309–328 | DOI | MR | Zbl

[13] R. M. Kolpakov, “On generation of rational numbers by monotone functions”, Theoretical and Applied Aspects of Mathematical Research, Mosk. Gos. Univ., Moscow, 1994, 13–17 (in Russian)

[14] R. M. Kolpakov, “On upper bounds on the complexity of rational number generation of probabilistic $\pi$-nets”, Moscow Univ. Math. Bull., 50:5 (1995), 55–57 | MR | Zbl

[15] Kolpakov R. M., “On the complexity of generation of rational numbers by Boolean functions”, Fundam. inform., 22:3 (1995), 289–298 | MR | Zbl

[16] R. M. Kolpakov, “Criterion of generativeness of sets of rational probabilities by a class of Boolean functions”, Discrete Appl. Math., 135 (2004), 125–142 | DOI | MR | MR | Zbl

[17] R. M. Kolpakov, “On transformations of Boolean random variables”, Mathematical Issues of Cybernetics, 9, Fizmatlit, Moscow, 2000, 227–252 (in Russian)

[18] R. M. Kolpakov, “Closed classes of Boolean random variables with rational-valued distributions”, Mathematical Issues of Cybernetics, 10, Fizmatlit, Moscow, 2001, 215–224 (in Russian)

[19] R. M. Kolpakov, “On multivalued transformations of one-element sets of binary distributions with rational probabilities”, Mathematical Issues of Cybernetics, 11, Fizmatlit, Moscow, 2002, 63–76 (in Russian)

[20] R. M. Kolpakov, “On discrete transformations of finite distributions with rational probabilities”, Mathematical Issues of Cybernetics, 12, Fizmatlit, Moscow, 2003, 109–146 (in Russian)

[21] R. M. Kolpakov, “Closed classes of finite distributions of rational probabilities”, Diskretn. Anal. Issled. Oper. Ser. 1, 11:3 (2004), 16–31 | MR

[22] R. M. Kolpakov, “On multivalued transformations of finite sets of binary distributions with rational probabilities”, Discrete Math. Appl., 15:1 (2005), 75–103 | DOI | DOI | MR | Zbl

[23] A. V. Kuznetsov, “Non-repeating contact schemes and non-repeating superpositions of functions of algebra of logic”, Tr. Mat. Inst. im. V. A. Steklova, Akad. Nauk SSSR, 51, 1958, 186–225 | MR | Zbl

[24] Laski J., “The analysis and synthesis of probability transformers”, J. Eng. Math., 7:4 (1973), 289–295 | DOI | MR | Zbl

[25] Lee D., Bruck J., Generating probability distributions using multivalued stochastic relay circuits, Electron. Tech. Rep. Paradise, ETR106, Calif. Inst. Technol., Pasadena, CA, 2011

[26] Lee D., Bruck J., “Generating probability distributions using multivalued stochastic relay circuits”, Proc. 2011 IEEE Int. Symp. on Information Theory (ISIT), IEEE, 2011, 308–312 | DOI

[27] Loh P.-L., Zhou H., Bruck J., “The robustness of stochastic switching networks”, Proc. 2009 IEEE Int. Symp. on Information Theory (ISIT), IEEE, 2009, 2066–2070 | DOI

[28] Lorenc A. A., “On the synthesis of generators of stable probability distributions”, Inform. Control., 24 (1974), 212–230 | DOI | MR | Zbl

[29] L. V. Makarevich, “On realizability of probabilistic operators in logic circuits”, Discrete Analysis, 15, Nauka, Novosibirsk, 1969, 35–56 (in Russian)

[30] Markovski S., Gligoroski D., Bakeva V., “Quasigroup string processing. I”, Makedon. Akad. Nauk. Umet. Oddel. Mat.-Tehn. Nauk. Prilozi., 20:1–2 (1999), 13–28 | MR

[31] Von Neumann J., “Various techniques used in connection with random digits”, Summary written by G. E. Forstyle, Monte Carlo method, Natl. Bur. Stand. Appl. Math. Ser., 12, U. S. Government Printing Office, Washington, 1951, 36–38

[32] N. N. Nurmeev, “On Boolean functions with variables taking random values”, Problems of Theoretical Cybernetics, Abstr. VIII All-Union Conf. Part 2, Gor'kii, 1988, 59–60 (in Russian)

[33] N. N. Nurmeev, “On the complexity of realization of probability transformers by circuits of functional elements”, Methods and Systems of Technical Diagnostics, 18, Saratov Univ., Saratov, 1993, 131–132 (in Russian)

[34] Parker K. P., McCluskey E. J., “Probabilistic treatment of general combinational networks”, IEEE Trans. Comput., 24:6 (1975), 668–670 | DOI | MR | Zbl

[35] Qian W., Riedel M. D., Barzagan K., Lilja D., “The synthesis of combinational logic to generate probabilities”, Proc. Int. Conf. on Computer-Aided Design 2009 (ICCAD'09), ACM, New York, 2009, 367–374

[36] Qian W., Riedel M. D., Bazargan K., Lilja D. J., “Synthesizing combinational logic to generate probabilities: Theories and algorithms”, Advanced techniques in logic synthesis, optimizations and applications, Springer, New York, 2011, 337–357 | DOI

[37] Qian W., Riedel M. D., Zhou H., Bruck J., “Transforming probabilities with combinational logic”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 30:9 (2011), 1279–1292 | DOI

[38] F. I. Salimov, “The question of simulation of Boolean random variables by means of logic algebra functions”, Probabilistic Methods and Cybernetics, 15, Kazan. Univ., Kazan, 1979, 68–89 (in Russian)

[39] F. I. Salimov, “On a system of generators for algebras over random variables”, Sov. Math., 25:5 (1981), 92–97 | MR | Zbl | Zbl

[40] F. I. Salimov, “Finite generatedness of some algebras over random variables”, Voprosy Kibernetiki, 86, Moscow, 1982, 122–130 | Zbl

[41] F. I. Salimov, “On Sheffer elements in distribution algebras”, III All-Union Symp. on Probabilistic Automata and Their Applications, Abstracts, Kazan, 1983, 104

[42] F. I. Salimov, “On maximal subalgebras of algebras of distributions”, Sov. Math., 29:7 (1985), 18–26 | MR | Zbl

[43] F. I. Salimov, “A family of distribution algebras”, Sov. Math., 32:7 (1988), 106–118 | MR | Zbl | Zbl

[44] F. I. Salimov, “Finitely generated distribution algebras”, Discrete Appl. Math., 135 (2004), 259–265 | DOI | MR | MR | Zbl

[45] Saloff-Coste L., “Random walks on finite groups”, Probability on discrete structures, Encycl. Math. Sci., 110, Springer, Berlin, 2004, 263–346 | DOI | MR | Zbl

[46] R. L. Skhirtladze, “On synthesis of $p$-schemes using switches with random discrete states”, Soobshch. Akad. Nauk Gruz. SSR, 26:2 (1961), 181–186

[47] R. L. Skhirtladze, Modeling of random variables by logic algebra functions, Cand. Sci. (Phys.-Math.) Dissertation, Tbilisi, 1966

[48] R. L. Skhirtladze, “On a method of constructing a Boolean variable with a given probability distribution”, Discrete Analysis, 7, Nauka, Novosibirsk, 1966, 71–80 (in Russian)

[49] Shaltiel R., “An introduction to randomness extractors”, Automata, languages and programming, Proc. 38th Int. Colloq. ICALP 2011. Part II, Lect. Notes Comput. Sci., 6756, eds. L. Aceto, M. Henzinger, J. Sgall, Springer, Berlin, 2011, 21–41 | DOI | MR | Zbl

[50] Sheng C. L., “Threshold logic elements used as a probability transformer”, J. Assoc. Comput. Mach., 12:2 (1965), 262–276 | DOI | Zbl

[51] J. Štefka, “Transformers of probability”, Kybernetika, 7:3 (1971), 218–226 | Zbl

[52] N. N. Vorob'ev, “Addition of independent random variables on finite abelian groups”, Mat. Sb., 34:1 (1954), 89–126 | MR | Zbl

[53] Warfield J. N., “Synthesis of switching circuits to yield prescribed probability relations”, 6th Ann. Symp. on Switching Circuit Theory and Logical Design (SWCT 1965), IEEE, 1965, 303–309 | DOI

[54] Wilhelm D., Bruck J., “Stochastic switching circuit synthesis”, Proc. 2008 IEEE Int. Symp. on Information Theory (ISIT), IEEE, 2008, 1388–1392 | DOI

[55] Wilhelm D., Bruck J., Stochastic switching circuit synthesis, Electron. Tech. Rep. Paradise, ETR089, Calif. Inst. Technol., Pasadena, CA, 2008 | Zbl

[56] S. V. Yablonskii, Introduction to Discrete Mathematics, Vysshaya Shkola, Moscow, 2001 (in Russian) | MR

[57] V. V. Yakovlev, R. F. Fedorov, Stochastic Computing Machines, Mashinostroenie, Leningrad, 1974 (in Russian)

[58] A. D. Yashunsky, “On probability transformations by read-once Boolean formulas”, Synthesis and Complexity of Control Systems, Proc. XVI Int. Sch.-Sem. (St. Petersburg, June 26–30, 2006), Mekh.-Mat. Fak. Mosk. Gos. Univ., Moscow, 2006, 150–155

[59] A. D. Yashunskii, “On transformations of probability distributions by read-once quasigroup formulae”, Discrete Math. Appl., 23:2 (2013), 211–223 | DOI | DOI | MR | Zbl

[60] A. D. Yashunsky, On probability distribution sets preserved by finite field operations, Preprint No. 51, Keldysh Inst. Appl. Math., Moscow, 2014

[61] A. D. Yashunsky, “On operations on independent random variables over a finite linearly ordered set”, Discrete Models in the Theory of Control Systems, Proc. IX Int. Conf. (Moscow and Moscow region, May 20–22, 2015), MAKS Press, Moscow, 2015, 272–274

[62] A. D. Yashunsky, “On transformations of random variables over a linearly ordered three-element set”, Algebra, Number Theory and Discrete Geometry: Contemporary Issues and Applications, Proc. XIII Int. Conf. devoted to the 85th birthday of S. S. Ryshkov (Tula, May 25–30, 2015), Tul. Gos. Pedagog. Univ. im. L. N. Tolstogo, Tula, 2015, 206–208

[63] A. D. Yashunskii, “On read-once transformations of random variables over finite fields”, Discrete Math. Appl., 25:5 (2015), 311–321 | DOI | MR

[64] A. D. Yashunsky, On convex polytopes of distributions preserved by finite field operations, Preprint No. 11, Keldysh Inst. Appl. Math., Moscow, 2016

[65] A. D. Yashunsky, Bernoulli distribution transformations by Boolean functions from closed classes, Preprint No. 38, Keldysh Inst. Appl. Math., Moscow, 2016

[66] A. D. Yashunsky, Approximation of probability distributions by $k$-valued logic functions, Preprint No. 58, Keldysh Inst. Appl. Math., Moscow, 2016

[67] A. D. Yashunsky, Finite systems of operations for discrete probability distributions approximation, Preprint No. 10, Keldysh Inst. Appl. Math., Moscow, 2017

[68] A. D. Yashunsky, “On transformations of discrete random variables by polynomials”, Problems of Theoretical Cybernetics, Proc. XVIII Int. Conf. (Penza, June 19–23, 2017), MAKS Press, Moscow, 2017, 268–271

[69] A. D. Yashunskii, “Convex polyhedra of distributions preserved by operations over a finite field”, Moscow Univ. Math. Bull., 72:4 (2017), 165–168 | DOI | MR | Zbl

[70] V. M. Zakharov, F. I. Salimov, “A contribution to the theory of structural synthesis of determinate ‘probability converter’ ”, Probl. Control Inf. Theory, 6:2 (1977), 137–148 | Zbl

[71] V. M. Zakharov, F. I. Salimov, “On the problem of synthesis of probability transformers”, Probabilistic Methods and Cybernetics, 14, Kazan. Univ., Kazan, 1978, 47–50 (in Russian)

[72] Zhou H., Bruck J., “On the expressibility of stochastic switching circuits”, Proc. 2009 IEEE Int. Symp. on Information Theory (ISIT), IEEE, 2009, 2061–2065 | DOI

[73] Zhou H., Loh P.-L., Bruck J., The synthesis and analysis of stochastic switching circuits, E-print, 2012, arXiv: 1209.0715v1[cs.IT]