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), 103116
MSC (2000):
Primary 68U20; Secondary 60G10
Published electronically:
July 14, 2008
MathSciNet review:
2368743
Fulltext 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
(39 #4892)
 2.
V.
F. Kolchin, Sluchainye grafy, \cyr Teoriya
Veroyatnosteĭ\ i Matematicheskaya Statistika. [Probability Theory
and Mathematical Statistics], FizikoMatematicheskaya Literatura, Moscow,
2000 (Russian, with Russian summary). 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), http://dx.doi.org/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. 1920.
 5.
B.
A. Sevast′yanov, Kurs teorii veroyatnostei i matematicheskoi
statistiki, “Nauka”, Moscow, 1982 (Russian). MR 712294
(85a:60006)
 1.
 G. V. Balakin, The distribution of the rank of random matrices over a finite field, Teor. Verojatnost. i Primenen. XIII (1968), no. 4, 631641; English transl. in Theor. Probab. Appl. 13 (1968), no. 4, 594605. 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, 171179. 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. 1920.
 5.
 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
DOI:
http://dx.doi.org/10.1090/S0094900008007357
PII:
S 00949000(08)007357
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
