An estimate for the rate of convergence of the distribution of the number of false solutions of a system of nonlinear random equations in the field \(GF(2)\). (Ukrainian, English) Zbl 1199.60030

Masol, V. I.; Slobodyan, M. V.

Teor. Jmovirn. Mat. Stat. 77, 109-121 (2007); translation in Theory Probab. Math. Stat. 77, 121-134 (2008).

The authors deal with the 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\). The rate of convergence of the distribution of the random variable \(\nu(n)\) to the limit Poisson distribution as \(n\to\infty\) is estimated.
For more results and references see [V. G. Mikhailov, Theory Probab. Appl. 43, No. 3, 480–487 (1998; Zbl 0951.60011); translation from Teor. Veroyatn. Primen. 43, No. 3, 598–606 (1998)].

Reviewer: Mikhail P. Moklyachuk (Kyïv)

MSC:

60C05	Combinatorial probability
15B52	Random matrices (algebraic aspects)
15A03	Vector spaces, linear dependence, rank, lineability

Keywords:

system of nonlinear random equations; Poisson distribution; false solution; distribution convergence

Citations:

Zbl 0951.60011