On the rate of convergence to the normal distribution of the number of false solutions of a system of nonlinear random Boolean equations

Authors:
V. I. Masol and S. Ya. Slobodyan

Translated by:
S. Kvasko

Journal:
Theor. Probability and Math. Statist. **76** (2008), 117-129

MSC (2000):
Primary 60C05, 15A52, 15A03

DOI:
https://doi.org/10.1090/S0094-9000-08-00736-9

Published electronically:
July 16, 2008

MathSciNet review:
2368744

Full-text PDF Free Access

Abstract |
References |
Similar Articles |
Additional Information

Abstract: We prove a theorem on the limit normal distribution (as $n \to \infty$) of the number of false solutions of a system of nonlinear equations with independent random coefficients belonging to the field GF(2). We assume that every equation contains at least one coefficient for which the probability that it attains the value 1 is close to $\frac {1}{2}$; the number of equations $N$ and the number of unknowns $n$ are such that $n-N \to \infty$ as $n \to \infty$; the system has a solution containing $\rho (n)$ units and $\rho (n) \to \infty$ as $n \to \infty$.

References
- V. G. Mikhaĭlov,
*Limit theorems for the number of nonzero solutions of a system of random equations over the field ${\rm GF}(2)$*, Teor. Veroyatnost. i Primenen. **43** (1998), no. 3, 598–606 (Russian, with Russian summary); English transl., Theory Probab. Appl. **43** (1999), no. 3, 480–487. MR **1681052**, DOI https://doi.org/10.1137/S0040585X97977082
- 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,
*A theorem on the limit distribution of the number of false solutions of a system of nonlinear random Boolean equations*, Teor. Veroyatnost. i Primenen. **43** (1998), no. 1, 41–56 (Russian, with Russian summary); English transl., Theory Probab. Appl. **43** (1999), no. 1, 75–88. MR **1669972**, DOI https://doi.org/10.1137/S0040585X97976672

References
- V. G. Mikhaĭlov,
*Limit theorems for the number of nonzero solutions of a system of random equations over the field GF(2)*, Teor. Veroyatnost. i Primenen. **43** (1998), no. 3, 598–606; English transl. in Theory Probab. Appl. **43** (1999), no. 3, 480–487. MR **1681052 (2000b:11096)**
- 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,
*A theorem on the limit distribution of the number of false solutions of a system of nonlinear random Boolean equations*, Teor. Veroyatnost. i Primenen. **43** (1998), no. 1, 41–56; English transl. in Theory Probab. Appl. **43** (1999), no. 1, 75–88. MR **1669972 (2000f:60040)**

Similar Articles

Retrieve articles in *Theory of Probability and Mathematical Statistics*
with MSC (2000):
60C05,
15A52,
15A03

Retrieve articles in all journals
with MSC (2000):
60C05,
15A52,
15A03

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. Ya. Slobodyan**

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:
sv_yaros@rambler.ru

Keywords:
Nonlinear random Boolean equations,
the limit normal distribution,
the number of false solutions

Received by editor(s):
March 22, 2006

Published electronically:
July 16, 2008

Article copyright:
© Copyright 2008
American Mathematical Society