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

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.**13**(1968), 631–641 (Russian, with English summary). MR**0243571****2.**V. F. Kolchin,*Sluchainye grafy*, \cyr Teoriya Veroyatnosteĭ i Matematicheskaya Statistika. [Probability Theory and Mathematical Statistics], Fiziko-Matematicheskaya Literatura, Moscow, 2000 (Russian, with Russian summary). MR**1812261****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**, 10.1515/rose.1993.1.2.171**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,*Kurs teorii veroyatnostei i matematicheskoi statistiki*, “Nauka”, Moscow, 1982 (Russian). MR**712294**

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