Implementing a random variable generator based on a d-ary tree
https://doi.org/10.26907/2541-7746.2025.3.507-518
Abstract
A method was proposed for calculating the probability distribution of a discrete random variable (DRV) using a d-ary tree. The tree has n leaves, which is equivalent to the number of elements in the DRV probability distribution, and the remaining vertices represent the DRV generators with the probability distribution including d elements (d-DRV). Variation in the DRV probability distribution by zeroing one of its elements reduces to the recalculation of the d-DRV probability distributions, the number of which increases logarithmically with respect to the value of n.
About the Authors
V. M. Zakharov
Kazan National Research Technical University named after A.N. Tupolev – KAI
Russian Federation
Russian Federation
Vyacheslav M. Zakharov, Dr. Sci. (Engineering), Full Professor, Department of Computer Systems
Kazan
S. V. Shalagin
Kazan National Research Technical University named after A.N. Tupolev – KAI
Russian Federation
Russian Federation
Sergei V. Shalagin, Dr. Sci. (Engineering), Professor, Department of Computer Systems
Kazan
References
1. Zakrevskii A.D. Implementation of random events with a given probability.Tr. SFTI, 1965, vol. 47, pp. 56–59. (In Russian) 2. Bukharaev R.G. Automaton conversion of probability sequences. Veroyatn. Metody Kibern., 1966, vol. 1, pp. 24–33. (In Russian)
2. Chentsov V.M. A method of synthesizing an autonomous stochastic automaton. Cybernetics, 1968, vol. 4, no. 3, pp. 27–30. https://doi.org/10.1007/BF01073919.
3. Bukharaev R.G. Veroyatnostnye avtomaty [Probabilistic Automata]. Kazan, Izd. Kazan. Univ., 1970. 188 p. (In Russian)
4. Pospelov D.A. Veroyatnostnye avtomaty [Probabilistic Automata]. Moscow, Energiya, 1970. 88 p. (In Russian)
5. Pollyak Yu.G. Veroyatnostnoe modelirovanie na elektronnykh vychislitelnykh mashinakh [Probabilistic Modeling on Electronic Computers]. Moscow, Sov. Radio, 1971. 400 p. (In Russian)
6. Gladkii V.S. Veroyatnostnye vychislitelnye modeli [Probabilistic Computational Models]. Moscow, Nauka, 1973. 300 p. (In Russian)
7. Walker A.I. An efficient method for generating discrete random variables with general distributions. ACM Trans. Math. Software, 1977, vol. 3, no. 3, pp. 253–256. https://doi.org/10.1145/355744.355749.
8. Fedorov R.F., Yakovlev V.V., Dobris G.V. Stokhasticheskie preobrazovateli informatsii [Stochastic Information Converters]. Leningrad, Mashinostroenie, 1978. 304 p. (In Russian)
9. Chetverikov V.N., Bakanovich E.A., Menkov A.V. Vychislitel’naya tekhnika dlya statisticheskogo modelirovaniya [Computer Technology for Statistical Modeling]. Moscow, Sov. Radio, 1978. 312 p. (In Russian)
10. Bukharaev R.G. Osnovy teorii veroyatnostnykh avtomatov [Fundamentals of the Theory of Probabilistic Automata]. Moscow, Nauka, 1985. 287 p. (In Russian)
11. Pokhodzej B.B. Complexity of tabular methods for modeling finite discrete distributions. Sov. Math., 1985, vol. 29, no. 7, pp. 64–72.
12. Levin B.R., Schwartz W. Veroyatnostnye modeli i metody v sistemakh svyazi i upravleniya [Probabilistic Models and Methods in Communication and Control Systems]. Moscow, Radio Svyaz’, 1985. 312 p. (In Russian)
13. Veroyatnostnye avtomaty i ikh prilozheniya (Dokl. simpoz., 6–8 iyunya 1983 g.) [Probabilistic Automata and Their Applications (Proc. Symp., June 6–8, 1983)]. Zakharov V.M. (Ed.). Kazan, Izd. Kazan. Univ., 1986. 212 p. (In Russian)
14. Chetverikov V.N., Bakanovich E.A. Stokhasticheskie vychislitel’nye ustroistva sistem modelirovaniya [Stochastic Computing Devices of Simulation Systems]. Moscow, Mashinostroenie, 1989. 272 p. (In Russian)
15. Dorodnitsyn A.A. et al. Slovar’ po kibernetike [Dictionary of Cybernetics]. Mikhalevich V.S. (Ed.). Kyiv, Gl. Red. Ukr. Sov. Entsikl., 1989. 751 p. (In Russian)
16. Zakharov V.M., Shalagin S.V. On the development of statistical modeling hardware. Tr. SORUCOM–2014. III Mezhdunarodn. nauch.-prakt. konf. “Razvitie vychislitel’noi tekhniki i ee programmnogo obespecheniya v Rossi i v stranakh byvshego SSSR: istoriya i perspektivy”. Kazan’, 13–17 okt. 2014 g. [SORUCOM–2014. Proc. 3rd Int. Sci.-Pract. Conf. “The History of Computers and Informatics in the Soviet Union and Russian Federation: History and Prospects”. Kazan, October 13–17, 2014]. Kazan, 2014, pp. 103–108. URL: https://computer-museum.ru/articles/materialy-mezhdunarodnoy-konferentsii-sorucom-2014/490/. (In Russian)
17. Shalagin S.V. Realizatsiya tsifrovykh ustroistv v arkhitekture PLIS/FPGA pri ispol’zovanii raspredelennykh vychislenii v polyakh Galua: monografiya [Implementing Digital Devices in FPGA Architecture When Using Distributed Computing in Galois Fields: A Monograph]. Kazan, Izd. KNITU – KAI, 2016. 228 p. URL: https://e.lanbook.com/book/149577. (In Russian)
18. Zakharov V.M, Shalagin S.V., Eminov B.F. Avtomatnye markovskie modeli nad konechnym polem: monografiya [Automata Markov Models over a Finite Field: A Monograph]. Kazan, Spets. Fond Upr. Tselevym Kapitalom Razvit. KNITU – KAI, 2022. 328 p. URL: https://e.lanbook.com/book/366542. (In Russian)
19. Zakharov V.M., Shalagin S.V., Gumirov A.I. Discrete random variable generator with the given distribution law in FPGA-architecture.Vestn. DGU. Ser. 1: Estestv. Nauki, 2023, vol. 38, no. 3, pp. 28–33. https://doi.org/10.21779/2542-0321-2023-38-3-28-33. (In Russian)
20. Feller W. Vvedenie v teoriyu veroyatnostei i ee prilozheniya [An Introduction to Probability Theory and Its Applications]. Vol. 1. Moscow, Mir, 1967. 499 p. (In Russian) 22. Vorontsova I.P. Algorithms for changing stochastic automata transition probabilities. Probl. Inf. Transm., 1965, vol. 1, no. 3, pp. 97–101. (In Russian)
21. Zacharov V.M., Kuznetsov S.E. Complexity of the problem of approximation of stochastic matrix by rational elements. In: Budach L., Bukharajev R.G., Lupanov O.B. (Eds.) Fundamentals of Computation Theory: International Conference FCT’87 Kazan, USSR, June 22–26, 1987. Proceedings. Ser.: Lecture Notes in Computer Science. Vol. 278. Berlin, Heidelberg, Springer, 1987, pp. 483–487. https://doi.org/10.1007/3-540-18740-5_106.
22. Shalagin S.V. Solving the traveling salesman problem by statistical testing using complex Markov chains. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2024, vol. 166, no. 4, pp. 639–650. https://doi.org/10.26907/2541-7746.2024.4.639-650. (In Russian)
23. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximate algorithms. Autom. Remote Control, 1989, vol. 50, no. 11, pp. 1459–1479.
24. Quang T.L., Aibin M. Traveling Salesman Problem: Exact solutions vs. heuristic vs. approximation algorithms. Baeldung. 2024. URL: https://www.baeldung.com/cs/tsp-exact-solutions-vs-heuristic-vs-approximation-algorithms.
25. Al’pin Yu.A., Zakharov V.M. A theoretical automata method for describing and modeling random processes. Veroyatn. Metody Kibern., 1983, vol. 19, pp. 10–16. URL: http://eudml.org/doc/69222. (In Russian)
26. Aho A., Hopcroft J., Ullman J. Postroenie i analiz vychislitel’nykh algoritmov [The Design and Analysis of Computer Algorithms]. Slisenko A.O. (Trans.), Matiyasevich Yu.V. (Ed.). Moscow, Mir, 1979. 536 p. (In Russian)
Review
For citations:
Zakharov V.M., Shalagin S.V. Implementing a random variable generator based on a d-ary tree. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2025;167(3):507-518. (In Russ.) https://doi.org/10.26907/2541-7746.2025.3.507-518
Views:
7
Email this article 