On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations
The theorem on a normal limit (n → ∞) distribution of the number of false solutions of a system of nonlinear Boolean equations with independent random coefficients is proved. In particular, we assume that each equation has coefficients that take value 1 with probability that varies in some neighborh...
Saved in:
| Date: | 2007 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/4485 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations / V. Masol, S. Slobodyan // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 144-151. — Бібліогр.: 5 назв.— англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859726531468722176 |
|---|---|
| author | Masol, V. Slobodyan, S. |
| author_facet | Masol, V. Slobodyan, S. |
| citation_txt | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations / V. Masol, S. Slobodyan // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 144-151. — Бібліогр.: 5 назв.— англ. |
| collection | DSpace DC |
| description | The theorem on a normal limit (n → ∞) distribution of the number of false solutions of a system of nonlinear Boolean equations with independent random coefficients is proved. In particular, we assume that each equation has coefficients that take value 1 with probability that varies in some neighborhood of the point 1/2; the system has a solution with the number of ones equals ρ(n), ρ(n) → ∞ as n → ∞. The proof is constructed on the check of auxiliary statement conditions which in turn generalizes one well-known result.
|
| first_indexed | 2025-12-01T11:16:55Z |
| format | Article |
| fulltext |
Theory of Stochastic Processes
Vol.13 (29), no.1-2, 2007, pp.144-151
VOLODYMYR MASOL AND SVITLANA SLOBODYAN
ON THE ASYMPTOTIC NORMALITY OF THE
NUMBER OF FALSE SOLUTIONS OF A SYSTEM
OF NONLINEAR RANDOM BOOLEAN
EQUATIONS
The theorem on a normal limit (n → ∞) distribution of the number
of false solutions of a system of nonlinear Boolean equations with
independent random coefficients is proved. In particular, we assume
that each equation has coefficients that take value 1 with probability
that varies in some neighborhood of the point 1
2 ; the system has a
solution with the number of ones equals ρ(n), ρ(n) → ∞ as n →
∞. The proof is constructed on the check of auxiliary statement
conditions which in turn generalizes one well-known result.
1. Introduction
Let us consider a system of equations over the field GF(2) consisting of
two elements
gi(n)∑
k=1
∑
1≤j1<...<jk≤n
a
(i)
j1...jk
xj1 . . . xjk
= bi, i = 1, . . . , N, (1)
that satisfies condition (A).
Condition (A):
1) Coefficients a
(i)
j1...jk
, 1 ≤ j1 < ... < jk ≤ n, k = 1, ..., gi(n), i =
1, ..., N , are independent random variables that take value 1 with probability
P
{
a
(i)
j1...jk
= 1
}
= pik and value 0 with probability P
{
a
(i)
j1...jk
= 0
}
= 1−pik.
2) Elements bi, i = 1, ..., N , are the result of the substitution of a fixed
n-dimensional vector x̄0, which has ρ (n) /n − ρ (n)/, components equal to
one /zero/ into the left-hand side of the system (1).
3) Function gi(n), i = 1, ..., N, is nonrandom, gi(n) ∈ {2, ..., n} , i =
1, ..., N.
2000 Mathematics Subject Classifications. Primary 60C05, 15A52, 15A03.
Key words and phrases. The nonlinear random Boolean equations, normal limit
distribution, number of false solutions
144
THE NORMAL LIMIT DISTRIBUTION 145
Denote by νn the number of false solutions of the system (1), i.e. the
number of solutions of the system (1) different from the vector x̄0.
We are interested in the conditions under which the random variable νn
has a normal limit (n → ∞) distribution.
2. Formulation of the theorem
Theorem. Let condition (A) hold, and moreover
[λ] = 2m, (2)
where m = n − N, [·] is the sign of the integral part,
λ =
1
2(1 + α + ω)
log2
ρ(n)
ϕ(n) lnn
, ϕ(n) > 0, (3)
λ → ∞, (4)
λ (α ln α − α − 1) → ∞, (5)
ω
√
λ → ∞ (6)
as n → ∞;
let for any arbitrary i, i = 1, ..., N, there exist a nonempty set Ti such that
for all sufficiently large values of n
Ti ⊆ {2, 3, ..., gi(n)} , Ti �= ∅,
δit(n) ≤ pit ≤ 1 − δit(n), t ∈ Ti; (7)
lim
n→∞ (α + ω)λ B (ρ(n) − 1, 1) < ∞, (8)
B (X, Y ) =
N∑
i=1
exp
{
−2
∑
t∈Ti
δit(n)Ct−Y
X
}
;
(2 + (1 + α + ω) ln 2)λ − ln λ
2
+ ln B (εϕ(n), 0) → −∞ (n → ∞), (9)
where ε = const, 0 < ε < 1;
lim
n→∞ (− ln N + ln B (εϕ(n), 1)) < 0 (n → ∞). (10)
Then distribution function of the random variable νn−λ√
λ
tends to the stan-
dard normal distribution function .
146 VOLODYMYR MASOL AND SVITLANA SLOBODYAN
3. Auxiliary statements
Lemma 1. Let ξ and η be random variables that take non-negative integer
values. If
max
1≤r≤T
∣∣∣M(ξ)r(M(η)r)
−1 − 1
∣∣∣ = εT < 1; (11)
M(η)r ≤ Cλ r
1 , 1 ≤ r ≤ T, (12)
where M(ζ)r denotes r–factorial moment of a random variable ζ, r ≥ 1,
then for an arbitrary t, 0 ≤ t ≤ T − αλ1 and α > 1,
|P {ξ ≥ t} − P {η ≥ t}| ≤
≤ C√
2π max(1,λ1−1)
(
εT e2λ1 + 1+εT√
2π max(1,αλ1)
exp {(t + λ1 − T )u(α)}
)
,
(13)
where u(α) = (α−1)−1(α ln α−α−1) for 2 > ln α > 0, and u(α) = ln α−1
for ln α ≥ 2.
Proof. By virtue of Bonferrony inequalities, for any arbitrary random vari-
able ζ that takes non-negative integer values, and for any arbitrary integers
t > 0 and d ≥ 0
t+2d+β∑
r=t
(−1)r+tCt−1
r−1
1
r!
M(ζ)r ≤ P{ζ ≥ t} ≤
t+2d∑
r=t
(−1)r+tCt−1
r−1
1
r!
M(ζ)r, (14)
where min (M(ζ)t+2d+β , M(ζ)t+2d) < ∞, β ∈ {−1, 1}. (Proof of relation
(14) for β = −1, M(ζ)t+2d−1 < ∞ look, for example, in ([1], p.136, 223))
Let numbers t and T have identical parity. Then, using (14) for β = −1,
we receive
P{ξ ≥ t} − P{η ≥ t} ≤ Γ(T ) + M(ξ)T Ct−1
T−1
1
T !
, (15)
P{ξ ≥ t} − P{η ≥ t} ≥ Γ(T ) − M(η)T Ct−1
T−1
1
T !
, (16)
where Γ(T ) =
T−1∑
r=t
(−1)r+tCt−1
r−1
1
r!
M(η)r
(
M(ξ)r
M(η)r
− 1
)
.
If the difference P{ξ ≥ t}−P{η ≥ t} is non-negative /non-positive/that
we obtain
|P{ξ ≥ t} − P{η ≥ t}| ≤ |Γ(T )| + 1
T !
Ct−1
T−1 max (M(ξ)T , M(η)T ) (17)
by virtue of conditions (15), (16).
It is easy to check up that
max (M(ξ)T , M(η)T ) ≤ M(η)T
(
1 +
∣∣∣∣∣M(ξ)r
M(η)r
− 1
∣∣∣∣∣
)
. (18)
THE NORMAL LIMIT DISTRIBUTION 147
Using (17), (18) and conditions (11), (12), we obtain
|P{ξ ≥ t} − P{η ≥ t}| ≤
≤ C
(
εT
T−1∑
r=t
Ct−1
r−1
1
r!
λr
1 + (1 + εT )λT
1
1
T !
Ct−1
T−1
)
.
(19)
Hence
|P{ξ ≥ t} − P{η ≥ t}| ≤ C
(
λt
1
t!
eλ1εT + (1 + εT )
λT−t
1
(T − t)!
λt
1
t!
)
. (20)
Below the following relations will be established for the integer u, u ≥ 1,
λu
1
u!
≤ (2π max(1, λ1 − 1))−1/2 eλ1 ; (21)
for the integer N, N ≥ max(1, αλ1),
λN
1
N !
≤ (2π max(1, αλ1))
−1/2 exp{(λ1 − N)u(α) − λ1}, (22)
where u(α) = (α − 1)−1(α ln α − α − 1) for 2 > lnα > 0, u(α) = ln α − 1
for ln α ≥ 2.
Relations (20)–(22) prove (13), when t and T have identical parity .
Let now parameters t and T have different parity. Let us show, that
we can obtain (17) in this case. Using (14) for some d ≥ 0, β = 1 and
t + 2d = T − 1, we receive
P{ξ ≥ t} − P{η ≥ t} ≤ Γ(T ) + M(η)T
1
T !
Ct−1
T−1, (23)
P{ξ ≥ t} − P{η ≥ t} ≥ Γ(T ) − M(ξ)T
1
T !
Ct−1
T−1. (24)
By virtue of (23), (24), we obtain (17) similarly when we used inequalities
(15) and (16).
To complete the proof of Lemma 1 it is, therefore, enough to establish
(21) and (22).
Let us check (21). Indeed, it follows from Stirling formula that u! ≥
(u/e)u
√
2πu. Hence
λu
1
u!
≤
(
λ1e
u
)u
1√
2πu
. (25)
Let ϕ(u) =
(
λ1e
u
)u
and let us show that
max
u≥λ1−1
ϕ(u) = ϕ(λ1). (26)
Indeed, the first derivative ϕ′(u) = ϕ(u)(lnλ1 − ln u) and ϕ′(u) = 0 at
u = λ1. Since the second derivative ϕ′′(u) = ϕ(u)((lnλ1 − ln u)2 − u−1)
148 VOLODYMYR MASOL AND SVITLANA SLOBODYAN
is negative at u = λ1, ϕ′′(λ1) < 0, relation (26) holds. Using (26), we
establish (21) for u ≥ max(1, λ1 − 1).
Let further 1 ≤ u ≤ λ1 − 1; and let ψ(u) =
(
λ1e
u
)u
1√
u
, then
max
1≤u≤λ1−1
ψ(u) = ψ(λ1 − 1). (27)
Indeed,
ψ′(u) = ψ(u)(lnλ1 − f(u)), (28)
where f(u) = lnu + (2u)−1.
Let us show that function f(u) takes its maximal value on an interval
1 ≤ u ≤ λ1 − 1 at u = λ1 − 1,
max
1≤u≤λ1−1
f(u) = f(λ1 − 1). (29)
Indeed, f ′(u) = u−1 − 1
2
u−2, and f ′(u) = 0 at u = 1
2
. At the same time
f ′′(u)|u= 1
2
= (−u−2 + u−3)|u= 1
2
= 4. Therefore, function f(u) increases for
u > 1
2
and (29) holds on the interval 1 ≤ u ≤ λ1 − 1. As a result we get
ψ′(u) > 0 for 1 ≤ u ≤ λ1 − 1. (30)
Indeed, taking into account (29),
ln λ1 − f(u) ≥
≥ ln
(
1 + 1
λ1−1
)
− 1
2(λ1−1)
≥ 1
2(λ1−1)
(
1 − 1
λ1−1
)
> 0
(31)
for λ1 > 2. (Here the inequality ln(1 + x) > x − 1
2
x2 has been used for
x > 0.)
Relations (28) and (31) prove (30). Estimate (30) allows, apparently, to
conclude that equality (27) holds. With the help of (25) and (27) we find
λu
1
u!
≤
(
λ1e
λ1 − 1
)λ1−1
1√
2π(λ1 − 1)
≤ eλ1√
2π(λ1 − 1)
(32)
for 1 ≤ u ≤ λ1 − 1.
Estimate (32) proves (21) for 1 ≤ u ≤ λ1 − 1. Relation (21) is proved.
Let us check (22). With the help of Stirling formula and inequality
λ1
N
≤ 1
α
, we can obtain
λN
1
N !
≤ 1√
2πN
eλ1(1−ln α)×
× exp
{(
1 − ln α + 2−ln α
α−1
)
(N − λ1)
}
exp {−λ1(2 − ln α)} .
(33)
By virtue of conditions N ≥ αλ1, 2 − ln α > 0, and α > 1, the right-hand
side of the inequality (33) can be estimate as follows
1√
2πN
eλ1(1−ln α) exp
{(
1 − ln α + 2−ln α
α−1
)
(N − λ1)
}
×
× exp {−λ1(2 − ln α)} ≤ 1√
2πN
e−λ1 exp
{
(λ1 − N)α lnα−α−1
α−1
}
.
(34)
THE NORMAL LIMIT DISTRIBUTION 149
From relations (33) and (34) the estimate (22) follows for α < e2.
Let now α ≥ e2. Then
λN
1
N !
≤ 1√
2πN
e−λ1 exp {−(N − λ1)(lnα − 1)} .
Relation (22) is proved for all α > 1. Lemma 1 is proved.
Lemma 2. Let X and Y be random variables that take non-negative integer
values, and MX = λ∗. If for all r ≤ (α + γ)λ∗
M(Y )r ≤ C(λ∗)r (35)
with some constant C, and
λ∗ (α ln α − α − 1) → ∞, (36)
γ ≥ 0, (37)
max
1≤r≤(α+γ)λ ∗
∣∣∣M(X)r(M(Y )r)
−1 − 1
∣∣∣ e2λ ∗
√
λ∗ → 0 (38)
as λ∗ → ∞,
then
max
0≤t≤γλ ∗ |P {X ≥ t} − P {Y ≥ t}| → 0 (λ∗ → ∞). (39)
Proof. Assumptions (35) and (38) imply the conditions of Lemma 1, by
virtue of which (13) holds for 0 ≤ t ≤ γλ ∗, α > 1. Using (36) and (37)
it is easy to show that exp{(t + λ ∗ − (α + γ)λ ∗) u(α)} → 0 as λ∗ → ∞
uniformly for 0 ≤ t ≤ γλ ∗. Taking into account (38), it follows from the
last statement that the right-hand side of the inequality (13) tends to zero
as λ∗ → ∞ uniformly, for 0 ≤ t ≤ γλ ∗. The left-hand side of the inequality
(13) tends, therefore, to zero too for λ ∗ and t mentioned above, which
proves, obviously, (39). Lemma 2 is proved.
Remark. The lemma 2 (for α = 5 and γ = 2) follows from the lemma 3 in
[2].
4. Proof of the theorem
Let us show that under the conditions of the theorem we can use Lemma 2.
Let the random variable Y in the mentioned lemma have a Poisson dis-
tribution with parameter 2m, while the distribution of the random vari-
able X coincides with the distribution of the random variable νn. Then
150 VOLODYMYR MASOL AND SVITLANA SLOBODYAN
M(Y )r = 2mr, r ≥ 1, while expectation Mνn can, by virtue of its explicit
form obtained in [3], be presented in the following way
Mνn = 2m
(
1 − 1
2n
)
M̃, (40)
where exp {−B(ρ(n) − 1, 1)} ≤ M̃ ≤ exp {B(ρ(n) − 1, 1)}.
Now condition (35) becomes
2mr ≤ C(Mνn)r. (41)
It follows from (40) that inequality (41) holds true for r ≤ (1 + α + ω)Mνn
and
C ≥
(
1 − 1
2n
)−(1+α+ω)Mνn
exp{(1 + α + ω)B(ρ(n) − 1, 1)Mνn}. (42)
By virtue of conditions (3), (8), and equality (40), the right-hand side of
(42) is limited as n → ∞. Therefore, it is possible to choose a limited
constant C < ∞ such that condition (35) holds true.
Further we note that under conditions (3)–(10) relation (38) is estab-
lished in [4] for α = 5 and ω = 1. For arbitrary α and ω satisfying conditions
of the theorem, verification of the relation (38) can be executed similarly.
By virtue of Lemma 2, we obtain
max
0≤t≤(1+ω)λ ∗
|P {νn ≥ t} − P {Y ≥ t}| → 0 as n → ∞, (43)
where λ∗ = Mνn according to the notations introduced above. By virtue of
(40) and conditions (3) and (8), the last equality allows to present λ∗ as
λ∗ = [λ] (1 + r(n)) , (44)
where
r(n) = O (B(ρ(n) − 1, 1)) + O
(
1
2n
)
(45)
and r(n) → 0 as n → ∞.
We can write relation (43) in the following way
max
−√
λ∗≤l≤ω
√
λ ∗
∣∣∣∣∣P
{
νn − λ∗
√
λ∗ ≥ l
}
− P
{
Y − λ∗
√
λ∗ ≥ l
}∣∣∣∣∣ → 0, n → ∞, (46)
where l = t−λ∗√
λ∗ .
Let us show that distributions of the random variables νn−λ∗√
λ∗ and νn−λ√
λ
coincide as n → ∞. Indeed,
νn − λ∗
√
λ∗ =
νn − λ√
λ
+ ηn, (47)
THE NORMAL LIMIT DISTRIBUTION 151
where ηn = νn−λ√
λ
(
O
(
ε(n)
λ
)
+ O(r(n))
)
− λr(n)−ε(n)(1+r(n))√
λ∗ , [λ] = λ − ε(n),
0 ≤ ε(n) < 1.
The random variable ηn tends in probability to zero as n → ∞. Indeed, for
an arbitrary ε > 0
P {|ηn| > ε} ≤ 1
ε
M |ηn| ≤ 1
ε
(∣∣∣∣∣O
(
1√
λ
)∣∣∣∣∣ +
∣∣∣O (√
λr(n)
)∣∣∣
)
(48)
and, by virtue of (3), (8), and (45), the right-hand side of (48) tends to zero
as n increases, i.e.
P {|ηn| > ε} → 0, n → ∞. (49)
Relations (47), (49), and theorem ([5], p.157) prove that distributions of
the random variables νn−λ∗√
λ∗ and νn−λ√
λ
coincide as n → ∞. Similarly we can
verify that distributions of Y −λ∗√
λ∗ and Y −[λ]√
[λ]
are the same as n → ∞.
Thus, relation (46) can be writen as
max
−√
λ∗≤l≤ω
√
λ ∗
∣∣∣∣∣∣P
{
νn − λ√
λ
≥ l
}
− P
⎧⎨
⎩Y − [λ]√
[λ]
≥ l
⎫⎬
⎭
∣∣∣∣∣∣ → 0, n → ∞. (50)
Finally we notice that the random variable Y −[λ]√
[λ]
has the standard normal
distribution as λ → ∞. The theorem is proved.
Bibliography
1. Zubkov A.M., Sevastianov B.A., Chistyakov V.P., The collection of prob-
lems in probability theory, Moscow, Nauka,(1989). (in Russian)
2. Zubkov A.M., Inequalities for transitions with prohibitions , The mathe-
matical collection, (1979), v.109 (151), no.4 (11), 491–532. (in Russian)
3. Masol V.I., Moments of the number of solutions of system of random
Boolean equations, Random Oper. and Stoch. Equations, (1993), vol.
1, no. 2, 171–179.
4. Masol V.I., Slobodyan S.Y., On the convergence to the normal limit dis-
tribution of the number of false solutions of a system of nonlinear random
Boolean equations, PT&MS, (2007), (Submitted). (in Ukrainian)
5. Chistyakov V.P., Course of probability theory, Moscow, Nauka, (2003). (in
Russian)
Department of Probability Theory and Mathematical Statistics,
Kyiv National Taras Shevchenko University, Kyiv, Ukraine.
E-mail address: vimasol@ukr.net
Department of Probability Theory and Mathematical Statistics,
Kyiv National Taras Shevchenko University, Kyiv, Ukraine.
E-mail address: sv yaros@rambler.ru
|
| id | nasplib_isofts_kiev_ua-123456789-4485 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0321-3900 |
| language | English |
| last_indexed | 2025-12-01T11:16:55Z |
| publishDate | 2007 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | Masol, V. Slobodyan, S. 2009-11-19T10:18:19Z 2009-11-19T10:18:19Z 2007 On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations / V. Masol, S. Slobodyan // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 144-151. — Бібліогр.: 5 назв.— англ. 0321-3900 https://nasplib.isofts.kiev.ua/handle/123456789/4485 The theorem on a normal limit (n → ∞) distribution of the number of false solutions of a system of nonlinear Boolean equations with independent random coefficients is proved. In particular, we assume that each equation has coefficients that take value 1 with probability that varies in some neighborhood of the point 1/2; the system has a solution with the number of ones equals ρ(n), ρ(n) → ∞ as n → ∞. The proof is constructed on the check of auxiliary statement conditions which in turn generalizes one well-known result. en Інститут математики НАН України On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations Article published earlier |
| spellingShingle | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations Masol, V. Slobodyan, S. |
| title | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations |
| title_full | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations |
| title_fullStr | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations |
| title_full_unstemmed | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations |
| title_short | On the asymptotic normality of the number of false solutions of a system of nonlinear random Boolean equations |
| title_sort | on the asymptotic normality of the number of false solutions of a system of nonlinear random boolean equations |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/4485 |
| work_keys_str_mv | AT masolv ontheasymptoticnormalityofthenumberoffalsesolutionsofasystemofnonlinearrandombooleanequations AT slobodyans ontheasymptoticnormalityofthenumberoffalsesolutionsofasystemofnonlinearrandombooleanequations |