Limit theorems for the number of nonzero solutions of a system of random equations over the field $\mathrm{GF}(2)$

V. G. Mikhailov

Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 70-81

Résumé

We study the properties of the number $\nu$ of non-zero solutions of system of random equations over $\mathrm{GF}(2)$ with the left-hand sides which are products of expressions of the form $a_{t1}x_1+\ldots+a_{tn}x_n+a_t$ with independent equiprobable coefficients. The right-hand sides of the system are zeros. We derive inequalities for the factorial moments of the random variable $\nu$ and necessary and sufficient conditions of the validity of the Poisson limit theorem for $\nu$. The research was supported by the Russian Foundation for Basic Research, grants 99–01–00012 and 96–15–96092.

Bibliographie

[1] Mikhailov V. G., “Predelnye teoremy dlya chisla nenulevykh reshenii odnoi sistemy sluchainykh uravnenii nad polem GF(2)”, Teoriya veroyatnostei i ee primeneniya, 43:3 (1998), 598–606

[2] Kovalenko I. N., Levitskaya A. A., Savchuk M. N., Izbrannye zadachi veroyatnostnoi kombinatoriki, Naukova Dumka, Kiev, 1986 | MR | Zbl

[3] Kolchin V. F., Sistemy sluchainykh uravnenii, MIEM, Moskva, 1988

[4] Balakin G. V., “Vvedenie v teoriyu sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 1, 1997, 1–18 | MR | Zbl

[5] Balakin G. V., “Sistemy sluchainykh sistem uravneii nad konechnym polem”, Trudy po diskretnoi matematike, 2, 1998, 21–37 | MR | Zbl

[6] Sevastyanov B. A., Chistyakov V. P., “O chisle vkhodnykh posledovatelnostei, sootvetstvuyuschikh vykhodnoi posledovatelnosti konechnogo avtomata”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:1 (1994), 96–107

[7] Sachkov V. N., “Asimptoticheskoe povedenie chisla $t$-minimalnykh pokrytii”, Diskretnaya matematika, 5:1 (1993), 36–44 | MR | Zbl

[8] Kopyttsev V. A., “O raspredelenii chisla reshenii sluchainykh zavedomo sovmestnykh sistem uravnenii”, Teoriya veroyatnostei i ee primeneniya, 40:2 (1995), 430–437 | MR

[9] Mikhailov V. G., “Predelnye teoremy dlya sluchainogo pokrytiya konechnogo mnozhestva i dlya chisla reshenii sistemy sluchainykh uravnenii”, Teoriya veroyatnostei i ee primeneniya, 41:2 (1996), 272–283 | MR | Zbl

[10] Kopyttsev V. A., “O nekotorykh sluchainykh zavedomo sovmestnykh sistemakh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:1 (1994), 56–84 | Zbl

[11] Polin S. V., “O sluchainykh bluzhdaniyakh na grafe s otmechennym rebrom”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:1 (1994), 85–92 | MR | Zbl

[12] Mikhailov V. G., “Asimptoticheskaya normalnost logarifma chisla probrazov vykhodnoi posledovatelnosti konechnogo avtomata”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:1 (1994), 126–135 | Zbl

[13] Masol V. I., “Teorema o predelnom raspredelenii chisla lozhnykh reshenii sistemy nelineinykh sluchainykh bulevykh uravnenii”, Teoriya veroyatnostei i ee primeneniya, 43:1 (1998), 41–56 | MR | Zbl