Limit theorems for the number of solutions of a system of random equations

V. A. Kopyttsev

Teoriâ veroâtnostej i ee primeneniâ, Tome 45 (2000) no. 1, pp. 52-72

Résumé

We investigate the number and the set structure of the solutions of a consistent system of random equations of the form $$ \varphi_t(x_{s_1(t)},\ldots,x_{s_{d(t)}(t)})=a_t,\quad t=1,\ldots, T, $$ with respect to the variables $x_1,\ldots, x_n\in\{0,\ldots,q-1\}$, $q\ge 2$, where the indices $s_1(t),\ldots,s_{d(t)}(t)$ are selected randomly and independently for different $t$ according to the equiprobable selection procedure without replacement. Conditions are found under which the distribution of the number of solutions of the system converges to the distribution of a random variable of the form $A\cdot 2^{\eta_1}\cdots q^{\eta_{q}-1}$, where $A$ is the order of the group of permutations $g: \{0,\ldots,q-1\}{\longleftrightarrow}\{0,\ldots,q-1\}$ satisfying the conditions $\varphi_t(y_1,\ldots y_{d(t)})\equiv\varphi_t(g(y_1),\ldots, g(y_{d(t)}))$, $t=1,\ldots,T$, and $\eta_1,\ldots,\eta_{q-1}$ are independent Poisson random variables with parameters $\lambda_1,\ldots,\lambda_{q-1}$, respectively. Explicit expressions for the parameters $\lambda_1,\ldots\lambda_{q-1}$ are given. These results essentially generalize analogous theorems proved for the case $q=2$ in [V. A. Kopytsev, Theory Probab. Appl., 40 (1995), pp. 376–383] and [V. G. Mikhailov, Theory Probab. Appl., 41 (1996), pp. 265–274].

Détail

Keywords: systems of random equations, vicinity of a true solution, the total number of solutions, permutation groups
Mots-clés : true solution, Poisson distribution.