On the rate of convergence to the normal distribution of the number of false solutions of a system of nonlinear random Boolean equations. (Ukrainian, English) Zbl 1199.60031

Masol, V. I.; Slobodyan, S. Ya.

Teor. Jmovirn. Mat. Stat. 76, 105-116 (2007); translation in Theory Probab. Math. Stat. 76, 117-129 (2008).

The authors deal with the following system of equations \[ \sum_{k=1}^{g_i(n)}\sum_{1\leq j_1<\cdots<j_k\leq n}a_{j_1,\dots,j_k}^{(i)} x_{j_1}\cdots x_{j_k}=b_i,\,i=1,\dots,N, \] over the field \(GF(2)\) containing only two elements, where the coefficients \(a_{j_1,\dots,j_k}^{(i)}, 1\leq j_1<\cdots<j_k\leq n,k=1,\dots,g_i(n)\) are independent random variables taking the value 1 with probability \(P\{a_{j_1,\dots,j_k}^{(i)}=1\}=p_{ik}\), and the value 0 with probability \(1-p_{ik}\), the elements \(b_i,i=1,\dots,N\), are equal to the left hand side of the system, if a fixed \(n\)-dimensional vector \(\vec{x}_0\) is substituted for unknowns, and the functions \(g_i(n),i=1,\dots,N\), are nonrandom and such that \(g_i(n)\in \{2,\dots,N\}\).
Denote by \(\nu(n)\) the number of false solutions of the system, that is, the number of solutions that do not coincide with the vector \(\vec{x}_0\). Conditions are proposed under which the random variable \(\nu(n)\) has the limit normal distribution as \(n\to\infty\). It is assumed that every equation contains at least one coefficient for which the probability that it attains the value 1 is close to \(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 units \(\rho(n)\) and \(\rho(n)\to\infty\) as \(n\to\infty\).

Reviewer: Mikhail P. Moklyachuk (Kyïv)

MSC:

60C05	Combinatorial probability
15B52	Random matrices (algebraic aspects)
60F99	Limit theorems in probability theory

Keywords:

sparse Boolean random matrix; normal distribution; rate of convergence

Citations:

Zbl 0842.60009; Zbl 0926.60022