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

Original publication:
Teoriya Imovirnostei ta Matematichna Statistika, tom **76** (2007).

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.

**1.**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)****2.**V. F. Kolchin,*Random Graphs*, Fizmatlit, Moscow, 2000, 256 pp. (Russian) MR**1812261 (2002e:60014)****3.**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)****4.**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.**5.**B. A. Sevast'yanov,*A Course in Probability Theory and Mathematical Statistics*, ``Nauka'', Moscow, 1982. (Russian) MR**712294 (85a:60006)**

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

DOI:
https://doi.org/10.1090/S0094-9000-08-00735-7

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