Polynomial Time Checking for Generation of Finite Distributions of Rational Probabilities

  • Roman Kolpakov
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


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.


Stochastic automata probabilistic transformations generation of randomness 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bukharaev, R.: Foundations of the Theory of Probabilistic Automata. Nauka, Moscow (1985) (in Russian) Google Scholar
  2. 2.
    Kolpakov, R.: Classes of Binary Rational Distributions Closed under Discrete Transformations. In: Albrecht, A.A., Steinhöfel, K. (eds.) SAGA 2003. LNCS, vol. 2827, pp. 157–166. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  3. 3.
    Kolpakov, R.: On discrete transformations of finite distributions with rational probabilities. Matematicheskie voprosy kibernetiki 12, 109–146 (2003) (in Russian)Google Scholar
  4. 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. 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. 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. 7.
    Salimov, F.: Finite generativeness of some algebras over random values. Voprosy kibernetiki 86, 122–130 (1982) (in Russian)Google Scholar
  8. 8.
    Salimov, F.: On maximal subalgebras of algebras of distributions. Izvestija vuzov, Ser. Matematika 7, 14–20 (1985) (in Russian)Google Scholar
  9. 9.
    Salimov, F.: On one family of distribution algebras. Izvestija vuzov, Ser. Matematika 7, 64–72 (1988) (in Russian)Google Scholar
  10. 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. 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
  12. 12.
    Srinivasan, A., Zuckerman, D.: Computing with very weak random sources. SIAM J. on Computing 28(4), 1433–1459 (1999)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Roman Kolpakov
    • 1
  1. 1.Moscow State UniversityMoscowRussia

Personalised recommendations