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