A theorem on the distribution of the rank of a sparse Boolean random matrix and some applications
Authors:
V. I. Masol and S. V. Popereshnyak
Translated by:
N. Semenov
Journal:
Theor. Probability and Math. Statist. 76 (2008), 103-116
MSC (2000):
Primary 68U20; Secondary 60G10
DOI:
https://doi.org/10.1090/S0094-9000-08-00735-7
Published electronically:
July 14, 2008
MathSciNet review:
2368743
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider some estimates of the rate of convergence of the distribution of a sparse Boolean random matrix to the Poisson distribution. The results obtained in the paper are applied to estimate the probability that a nonhomogeneous system of Boolean random linear equations is consistent.
References
- G. V. Balakin, The distribution of the rank of random matrices over a finite field., Teor. Verojatnost. i Primenen. 13 (1968), 631–641 (Russian, with English summary). MR 0243571
- V. F. Kolchin, Sluchaĭ nye grafy, Teoriya Veroyatnosteĭ i Matematicheskaya Statistika. [Probability Theory and Mathematical Statistics], Fiziko-Matematicheskaya Literatura, Moscow, 2000 (Russian, with Russian summary). MR 1812261
- V. I. Masol, Moments of the number of solutions of a system of random Boolean equations, Random Oper. Stochastic Equations 1 (1993), no. 2, 171–179. MR 1254185, DOI https://doi.org/10.1515/rose.1993.1.2.171
- V. I. Masol, Invariance theorems for systems of random Boolean equations, Sixth Intern. Vilnius Conf. of Probability Theory and Math. Statist., Abstracts of Communications, 1993, pp. 19–20.
- B. A. Sevast′yanov, Kurs teorii veroyatnosteĭ i matematicheskoĭ statistiki, “Nauka”, Moscow, 1982 (Russian). MR 712294
References
- G. V. Balakin, The distribution of the rank of random matrices over a finite field, Teor. Verojatnost. i Primenen. XIII (1968), no. 4, 631–641; English transl. in Theor. Probab. Appl. 13 (1968), no. 4, 594–605. MR 0243571 (39:4892)
- V. F. Kolchin, Random Graphs, Fizmatlit, Moscow, 2000, 256 pp. (Russian) MR 1812261 (2002e:60014)
- V. I. Masol, Moments of the number of solutions of a system of random Boolean equations, Random Oper. Stochastic Equations 1 (1993), no. 2, 171–179. MR 1254185 (94h:60089)
- V. I. Masol, Invariance theorems for systems of random Boolean equations, Sixth Intern. Vilnius Conf. of Probability Theory and Math. Statist., Abstracts of Communications, 1993, pp. 19–20.
- B. A. Sevast’yanov, A Course in Probability Theory and Mathematical Statistics, “Nauka”, Moscow, 1982. (Russian) MR 712294 (85a:60006)
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2000):
68U20,
60G10
Retrieve articles in all journals
with MSC (2000):
68U20,
60G10
Additional Information
V. I. Masol
Affiliation:
Department of Probability Theory and Mathematical Statistics, Faculty for Mechanics and Mathematics, National Taras Shevchenko University, Academician Glushkov Avenue 6, Kyiv 03127, Ukraine
Email:
vimasol@ukr.net
S. V. Popereshnyak
Affiliation:
Department of Probability Theory and Mathematical Statistics, Faculty for Mechanics and Mathematics, National Taras Shevchenko University, Academician Glushkov Avenue 6, Kyiv 03127, Ukraine
Email:
Popereshnyak_sv@mail.ru
Keywords:
Boolean random matrix,
rank of a matrix,
the probability that a system is consistent,
the rate of convergence of distributions
Received by editor(s):
December 27, 2005
Published electronically:
July 14, 2008
Article copyright:
© Copyright 2008
American Mathematical Society
