Polynomial Time Checking for Generation of Finite Distributions of Rational Probabilities
- 590 Downloads
We study the generation of finite probabilistic distributions by discrete transformations. By discrete transformation of distributions we mean the distribution of a random variable which is a function of the values of independent random variables with initial distributions. We propose an algorithm which allows to determine in polynomial time whether a given distribution is generated by a given set of finite distributions of rational probabilities. Moreover, we describe all sets of finite distributions of rational probabilities which are closed under the considered generation. Among these sets we find all finitely generated sets. We also determine the structure of the lattice formed of these sets.
KeywordsStochastic automata probabilistic transformations generation of randomness
Unable to display preview. Download preview PDF.
- 1.Bukharaev, R.: Foundations of the Theory of Probabilistic Automata. Nauka, Moscow (1985) (in Russian) Google Scholar
- 3.Kolpakov, R.: On discrete transformations of finite distributions with rational probabilities. Matematicheskie voprosy kibernetiki 12, 109–146 (2003) (in Russian)Google Scholar
- 4.Kolpakov, R.: Closed classes of finite distributions of rational probabilities. Diskretnyj analiz i issledovanie operacij, Ser. 1, Novosibirsk 11(3), 16–31 (2004) (in Russian)Google Scholar
- 5.Nurmeev, N.: On Boolean functions with variables having random values. In: Proceedings of VIII USSR Conference Problems of Theoretical Cybernetics, Gorky, vol. 2, pp. 59–60 (1988) (in Russian)Google Scholar
- 6.Salimov, F.: To the question of modelling Boolean random variables by functions of logic algebra. Verojatnostnye metody i kibernetika 15, 68–89 (1979) (in Russian)Google Scholar
- 7.Salimov, F.: Finite generativeness of some algebras over random values. Voprosy kibernetiki 86, 122–130 (1982) (in Russian)Google Scholar
- 8.Salimov, F.: On maximal subalgebras of algebras of distributions. Izvestija vuzov, Ser. Matematika 7, 14–20 (1985) (in Russian)Google Scholar
- 9.Salimov, F.: On one family of distribution algebras. Izvestija vuzov, Ser. Matematika 7, 64–72 (1988) (in Russian)Google Scholar
- 10.Skhirtladze, R.: On the synthesis of p-circuits of contacts with random discrete states. Soobschenija AN GrSSR 26(2), 181–186 (1961) (in Russian)Google Scholar
- 11.Skhirtladze, R.: On a method of constructing Boolean random variable with a given probability distribution. Diskretnyj analiz, Novosibirsk 7, 71–80 (1966) (in Russian)Google Scholar