Poisson estimates of the distribution of the rank of a random matrix over the field GF(2)
The estimates of the rate of convergence of the distribution of the rank of a random matrix over the field GF(2) and the Poisson distribution with the parameter depending on both the matrix sizes and distributions of its elements are found.
Gespeichert in:
| Datum: | 2006 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут математики НАН України
2006
|
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/4446 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) / V.I. Masol, S.V. Popereshnyak // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 106–115. — Бібліогр.: 5 назв.— англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-4446 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-44462009-11-11T12:00:37Z Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) Masol, V.I. Popereshnyak, S.V. The estimates of the rate of convergence of the distribution of the rank of a random matrix over the field GF(2) and the Poisson distribution with the parameter depending on both the matrix sizes and distributions of its elements are found. 2006 Article Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) / V.I. Masol, S.V. Popereshnyak // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 106–115. — Бібліогр.: 5 назв.— англ. 0321-3900 http://dspace.nbuv.gov.ua/handle/123456789/4446 519.21 en Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The estimates of the rate of convergence of the distribution of the rank of a random
matrix over the field GF(2) and the Poisson distribution with the parameter
depending on both the matrix sizes and distributions of its elements are found. |
| format |
Article |
| author |
Masol, V.I. Popereshnyak, S.V. |
| spellingShingle |
Masol, V.I. Popereshnyak, S.V. Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| author_facet |
Masol, V.I. Popereshnyak, S.V. |
| author_sort |
Masol, V.I. |
| title |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| title_short |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| title_full |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| title_fullStr |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| title_full_unstemmed |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) |
| title_sort |
poisson estimates of the distribution of the rank of a random matrix over the field gf(2) |
| publisher |
Інститут математики НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/4446 |
| citation_txt |
Poisson estimates of the distribution of the rank of a random matrix over the field GF(2) / V.I. Masol, S.V. Popereshnyak // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 106–115. — Бібліогр.: 5 назв.— англ. |
| work_keys_str_mv |
AT masolvi poissonestimatesofthedistributionoftherankofarandommatrixoverthefieldgf2 AT popereshnyaksv poissonestimatesofthedistributionoftherankofarandommatrixoverthefieldgf2 |
| first_indexed |
2025-07-02T07:41:22Z |
| last_indexed |
2025-07-02T07:41:22Z |
| _version_ |
1836520133895389184 |
| fulltext |
Theory of Stochastic Processes
Vol. 12 (28), no. 1–2, 2006, pp. 106–115
UDC 519.21
VOLODYMYR I. MASOL AND SVITLANA V. POPERESHNYAK
POISSON ESTIMATES OF THE DISTRIBUTION OF THE
RANK OF A RANDOM MATRIX OVER THE FIELD GF (2)
The estimates of the rate of convergence of the distribution of the rank of a ran-
dom matrix over the field GF (2) and the Poisson distribution with the parameter
depending on both the matrix sizes and distributions of its elements are found.
Introducton
A matrix A over the field GF (2) consisting of two elements is called a sparse Boolean
matrix if the probability of the occurrence of 1 in its positions (i, j) equals 1
n (lnn + xij),
where |xij | ≤ c, c = const, i = 1, T , j = 1, n, T/n/ is the number of rows/columns/ of
the matrix A.
In works [1], [2], using different methods, the limit Poisson distribution of the rank
r(A) of a random sparse Boolean matrix A was established when T = T (n) and n → ∞.
For finite values of the parameters T and n, the distribution of the rank r(A) can be
presented in terms of the factorial moments of the random variable r(A), as stated in [3].
The asymptotics of these moments under certain conditions, in particular, if xij = xi,
i = 1, T , j = 1, n as n → ∞, is given in ([4], Theorem 4).
The question on the rate of convergence of the distribution of the rank of a matrix
A to the Poisson distribution with a properly chosen parameter has not been examined
yet. The suggested paper is devoted to the investigation of the mentioned issue.
The proof of our main result (Theorem 1) is based on the theorem on the rate of con-
vergence in a Poisson scheme given in [5, p.67]. It should also be noted that, in contrast
with works [1], [2], the present paper considers a random matrix A, the distributions of
elements in which can depend on their (elements) positions.
The Main Result
Let the elements of a T × n matrix A = ‖aij‖, i = 1, T , j = 1, n be the independent
random variables that take values in the field GF (2) and have the distribution
(1) P {aij = 1} = 1 − P {aij = 0} =
lnn + xij
n
,
where
(2) |xij | ≤ c, c = const, i = 1, T , j = 1, n.
Let us assume that the matrix A has at least n0 columns so that it is correct to
determine a distribution by formula (1) for n ≥ n0. We denote, by r (A), the rank of the
2000 AMS Mathematics Subject Classification. Primary 60C05.
Key words and phrases. Random matrix over the field GF (2), rank of a matrix, Poisson distribution,
rate of convergence.
106
ESTIMATES OF THE DISTRIBUTION OF THE RANK OF A RANDOM MATRIX 107
matrix A and put λ equal
(3) λ =
1
n
T∑
i=1
exp
⎧⎨
⎩− 1
n
n∑
j=1
xij
⎫⎬
⎭.
Theorem 1. Let conditions (1) and (2) be satisfied, and
(4)
T
n
≤ 1 − log2 lnn
(lnn)q , q = const , 0 < q < 1,
(5) lim
n→∞
T
n
> 0.
Then, for k, k=0, 1, 2 . . . ,∣∣∣∣P {r (A) = T − k} − e−λ · λk
k!
∣∣∣∣ ≤ 2 (1 + δ) c(n, k)
ln4 n
n (ln lnn)2
,
where 1 < limn→∞ c (n, k) ≤ limn→∞ c (n, k) ≤ eec
, δ > 0, δ = const.
Remark. The explicit form of the coefficient c(n, k) is given by equality (30).
Auxiliary Statements
By ξn,T , we denote the number of zero rows of the matrix A.
Lemma 1. When conditions (1) and (2) hold, the distribution of the random variable
ξn,T satisfies the inequality
(6)
∣∣∣∣P {ξn,T = k} − e−λ · λk
k!
∣∣∣∣ ≤ Q(n, k),
where Q(n, k) = ln2 n
n c1(n, k) and 0 < limn→∞ c1 (n, k) ≤ limn→∞ c1 (n, k) ≤ e−1 if
k = 0, 0 < limn→∞ c1 (n, k) ≤ limn→∞ c1 (n, k) ≤ eck
2k! max (k, ec) if k ≥ 1.
Proof. The probability p
(i)
n that the row i of the matrix A consists of zeros exclusively
is, obviously, equal to
p(i)
n =
n∏
j=1
(
1 − lnn + xij
n
)
, i = 1, T .
Let us put a = p
(1)
n + p
(2)
n + . . . + p
(n)
n .
According to the Poisson theorem [5, p. 67], we get the inequality for arbitrary
k = 0, 1, 2, . . .
(7)
∣∣∣∣P {ξn,T = k} − e−a · ak
k!
∣∣∣∣ ≤
T∑
i=1
(
p(i)
n
)2
.
Applying the inequality p
(i)
n ≤ 1
n exp
{
− 1
n
∑n
j=1 xij
}
to the right-hand side of (7), we
obtain
(8)
∣∣∣∣P {ξn,T = k} − e−a · ak
k!
∣∣∣∣ ≤ 1
n2
T∑
i=1
exp
⎧⎨
⎩− 2
n
n∑
j=1
pij
⎫⎬
⎭.
Since
λ (1 − γn) ≤ a ≤ λ,
108 VOLODYMYR I. MASOL AND SVITLANA V. POPERESHNYAK
where γn =
(
ln2 n
2n
) (1−c(ln n)−1)2
1−(ln n−c)n−1 , we get
−λk+1e−λγn
(
1 +
λγn
2
eλγn
)
≤ λke−λ − ake−a ≤ λke−λkγn.
Hence,
(9)
∣∣λke−λ − ake−a
∣∣ ≤ λke−λγn max
{
k, λ
(
1 +
λγn
2
eλγn
)}
.
Combining ratios (8) and (9) leads to∣∣∣∣P {ξn,T = k} − e−λ · λk
k!
∣∣∣∣ ≤ Q(n, k),
where
(10) Q (n, k) =
ln2 n
n
c1(n, k),
c1 (n, k) =
1
n ln2 n
T∑
i=1
exp
⎧⎨
⎩− 2
n
n∑
j=1
pij
⎫⎬
⎭+
+
λke−λ
2 k!
(
1 − c (lnn)−1
)2
1 − (lnn − c)n−1
max
{
k, λ
(
1 +
λγn
2
eλγn
)}
,
0 < limn→∞ c1 (n, k) ≤ limn→∞ c1 (n, k) ≤ e−1 for k=0, 0 < limn→∞ c1 (n, k) ≤
limn→∞ c1 (n, k) ≤ eck
2k! max (k, ec) for k ≥ 1.
Lemma 1 is proved.
By S1 (A), we denote the maximum number of independent critical sets of the matrix
A (see [2, p. 147]), each containing at least one non-zero row.
Lemma 2. If condition (1) is satisfied, the expectation of the random variable S1 (A)
equals
MS1 (A) =
T∑
k=0
∑
1≤i1<···<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
−
−
T∑
k=0
∑
1≤i1<···<ik≤T
k∏
s=1
n∏
j=1
(
1 − lnn + xisj
n
)
.
Proof. Let us take into account that the probability that the number of successes in a
series of k independent trails, with the probability of a success pi, i = 1, k being an even
number, equals
1
2
+
1
2
k∏
i=1
(1 − 2pi).
(It is not difficult to verify it using induction on the parameter k ≥ 1).
Hence, the probability that k rows constitute a critical set can be presented by the
expression
1
2n
n∏
j=1
(
1 +
k∏
i=1
(
1 − 2 (lnn + xij)
n
))
.
ESTIMATES OF THE DISTRIBUTION OF THE RANK OF A RANDOM MATRIX 109
Note that the probability that there is no single 1 in k rows equals
k∏
i=1
n∏
j=1
(
1 − lnn + xij
n
)
.
Now it is not difficult to complete the proof of Lemma 2.
Let us put
f(n) =
[
(ln lnn)−1 (1 + δ1) lnn
]
, δ1 = const, δ1 > 0,
μ (n) =
∑f(n)
k=0
∑
1≤i1<···<ik≤T exp
{
−∑k
s=1
∑n
j=1
lnn+xisj
n
}
.
Lemma 3. If conditions (1), (2), and (4) are satisfied, and
(11) T ≤ n,
then
(12) 1 < lim
n→∞
μ(n) ≤ lim
n→∞ μ(n) ≤ eec
.
Proof. Let us estimate μ (n) from above. The sum μ (n) can be presented as
(13) μ (n) = θ1(n) − θ2(n),
where θ1(n) =
∑T
k=0
∑
1≤i1<···<ik≤T exp
{
−∑k
s=1
∑n
j=1
ln n+xisj
n
}
,
θ2(n) =
∑T
k=f(n)+ 1
∑
1≤i1<···<ik≤T exp
{
−∑k
s=1
∑n
j=1
ln n+xisj
n
}
.
Then θ1(n) can be estimated in such a way:
(14) θ1(n) ≤ eλ.
Since θ2(n) ≥ 0, relations (13) and (14) imply
(15) μ (n) ≤ eλ.
Let us estimate μ (n) from below. Since
θ1(n) ≥ eλ exp
⎧⎨
⎩− 1
2n2
T∑
i=1
exp
⎛
⎝− 2
n
n∑
j=1
xij
⎞
⎠
⎫⎬
⎭ ,
we get
μ (n) ≥ eλ exp
⎧⎨
⎩− 1
2n2
T∑
i=1
exp
⎛
⎝− 2
n
n∑
j=1
xij
⎞
⎠
⎫⎬
⎭− θ2(n).
From the last inequality and (15), it follows that
(16) eλ exp
⎧⎨
⎩− 1
2n2
T∑
i=1
exp
⎛
⎝− 2
n
n∑
j=1
xij
⎞
⎠
⎫⎬
⎭− θ2(n) ≤ μ (n) ≤ eλ.
To analyze θ2(n), it is necessary to take into account conditions (2) and (11), that is
(17) θ2(n) → 0 as n → ∞.
Letting n → ∞ in inequality (16) and taking into account (17) and conditions (2),
(5), and (11), we obtain (12).
Lemma 3 is proved.
Let us set the following Γ(n) = u
(
1 + u(1+δ1)
2 eu(1+δ1)
)
, u = ln4 n
n(ln ln n)2
.
110 VOLODYMYR I. MASOL AND SVITLANA V. POPERESHNYAK
Lemma 4. If conditions (1) and (2) are satisfied, then we have
(18)
f(n)∑
k=0
∑
1≤i1<....<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
≤
≤ μ (n) + μ (n) (1 + δ)Γ (n) .
Proof. The left-hand side of relation (18) can be estimated as
f(n)∑
k=0
∑
1≤i1<···<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
≤
≤
f(n)∑
k=0
∑
1≤i1<···<ik≤T
n∏
j=1
⎛
⎝1 −
k∑
s=1
(lnn + xisj)
n
+
(
k∑
s=1
(lnn + xisj)
n
)2
⎞
⎠.
By (2), the last inequality leads to
(19)
f(n)∑
k=0
∑
1≤i1<···<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
≤
≤ μ(n) · exp
{
f2 (n) (lnn + c)2
n
}
.
Further, we obtain
(20) exp
{
f2 (n) (lnn + c)2
n
}
≤ 1 + u (1 + δ)
(
1 +
u
2
(1 + δ) exp {u (1 + δ)}
)
.
Relations (19) and (20) give, obviously, (18). Lemma 4 is proved.
Lemma 5. If conditions (1), (2), (5), and (11) are satisfied, then
f(n)∑
k=0
∑
1≤i1<···<ik≤T
k∏
s=1
n∏
j=1
(
1 − lnn + xisj
n
)
≥μ (n) − c2 (n)
ln3 n
n · ln lnn
,
where (1+δ1)
2 < limn→∞ c2 (n) ≤ limn→∞ c2 (n) ≤ eec
2 (1 + δ1) .
Proof. With the help of relation (2), we find the following inequalities:
f(n)∑
k=0
∑
1≤i1<···<ik≤T
k∏
s=1
n∏
j=1
(
1 − lnn + xisj
n
)
≥
≥ μ(n) · exp
{
−f(n)
2n
(ln n + c)2 · 1
1 − ln n+c
n
}
.
Therefore, using the notations introduced earlier, we come to
f(n)∑
k=0
∑
1≤i1<···<ik≤T
k∏
s=1
n∏
j=1
(
1 − lnn + xisj
n
)
≥μ(n) − c2(n) · ln3 n
n · ln lnn
,
where
c2(n) =
μ(n)
2
(1 + δ1)
(
1 +
c
lnn
)2 1
1 − ln n+c
n
.
Taking into account (12), we get (1+δ1)
2 < limn→∞ c2(n) ≤ limn→∞ c2(n) ≤ 1
2eec
(1 + δ1)
as n → ∞.
ESTIMATES OF THE DISTRIBUTION OF THE RANK OF A RANDOM MATRIX 111
Lemma 5 is proved.
Lemma 6. If conditions (1), (2), (5), and (11) are satisfied, then
∑
k: n
2 (1− 1
ln n)<k≤ n
2 (1+ 1
ln n )
k−integer
(
n
k
)
1
2n
T∑
l=f(n)
(
T
l
)((
1 − 2 (lnn − c)
n
)k
)l
≤
≤
(
c3(n)
f(n)
)f(n)
· 1√
f(n)
· c4(n),
where 0 < limn→∞ c3(n) ≤ limn→∞ c3(n) ≤ e2+c, limn→∞ c4(n) = (2π)−
1/2.
Proof. For (n/2)
(
1 − 1/lnn
)
< k ≤ (n/2)
(
1 + 1/lnn
)
, we find
(
1 − 2 (lnn − c)
n
)k
≤ e−2k(ln n−c)n−1 ≤ 1
n
ec+1− c
ln n .
Using the obtained estimation, we establish that
∑
k: n
2 (1− 1
ln n)<k≤ n
2 (1+ 1
ln n )
k−integer
(
n
k
)
1
2n
T∑
l=f(n)
(
T
l
)((
1 − 2 (lnn − c)
n
)k
)l
≤
∑
k: n
2 (1− 1
ln n )<k≤ n
2 (1 + 1
ln n )
k−integer
(
n
k
)
1
2n
T∑
l=f(n)
(
T
l
)(
1
n
ec+1− c
ln n
)l
≤
T∑
l=f(n)
(
T
n
)l (ec+1− c
ln n
)l
l!
.
Applying the Stirling formula, we get
T∑
l=f(n)
(
T
n
)l (ec+1− c
ln n
)l
l!
≤
(
c3(n)
f(n)
)f(n)
· 1√
f(n)
· c4(n),
where c3(n) = T
n · e2+c− c
ln n , c4(n) = 1√
2π
·
(
1 − c3(n)
f(n)
)−1
; taking into account (5)
and (11), we find the following expressions: 0 < limn→∞ c3(n) ≤ limn→∞ c3(n) ≤
e2+c, limn→∞ c4(n) = (2π)−1/2
Lemma 6 is proved.
Lemma 7. If conditions (1), (2), (4), and (5) are satisfied, then
T∑
k=f(n) + 1
∑
1≤i1<···<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
≤ c5(n) · (lnn)
− n·c6(n)
(ln n)q
+
+
(
c3(n)
f(n)
)f(n)
· 1√
f(n)
· c4(n) + c7(n) · exp
{
− n
2 ln2 n
c8(n)
}
,
where limn→∞ c5(n) = (2π)−1/2, limn→∞ c6(n) = 1 − q, limn→∞ c8(n) = 1,
√
2
π <
limn→∞ c7(n) ≤ limn→∞ c7(n) ≤ ec+1+ec−1√
2π
.
Proof. Denote S =
∑T
k=f(n)
∑
+1 1≤i1<···<ik≤T
1
2n
∏n
j=1
(
1 +
∏k
s=1
(
1 − 2(ln n+xisj)
n
))
.
With the help of condition (2), we find that, for n ≥ n0,
0 ≤ S ≤ σ,
112 VOLODYMYR I. MASOL AND SVITLANA V. POPERESHNYAK
where σ =
∑T
k=f(n)
(
T
k
)
1
2n
(
1 +
(
1 − 2(ln n−c)
n
)k
)n
.
Using elementary transformations, we can obtain the following presentation for the
sum σ:
σ =
n∑
k=0
Ak (f (n)),
where Ak (f(n)) =
(
n
k
)
1
2n
∑T
l=f(n)
(
T
l
)(
1 − 2(ln n−c)
n
)kl
.
Using this presentation, we obtain the inequality
σ ≤ S1 + S2 + S3 + S4,
where S1 =
∑
0≤k≤k1
Ak(0), S2 =
∑
k1<k≤k2
Ak(0), S3 =
∑
k2<k≤k3
Ak(f(n)), S4 =
=
∑
k3<k≤n Ak(0),
k1 =
[
n
(lnn)q
]
, k2 =
[
n
2
(
1 − 1
lnn
)]
, k3 =
[
n
2
(
1 +
1
lnn
)]
.
Let us proceed to the estimations of the sum S1. We have
S1 ≤ (1 + k1) · 2T−n · nk1
k1!
.
With the help of the Stirling formula and (4), we come to the relation
(21) S1 ≤ c5(n) · (lnn)
− n·c6(n)
(ln n)q
,
where c6(n) = 1− q − 1
ln ln n
(
1 − ln
(
1 − (ln n)q
n
)
+ 1
2n (lnn)1+q − q(ln n)q ln ln n
2n
)
, c5(n) =
1√
2π
· (1 + k−1
1
)
and limn→∞ c5(n) = (2π)−1/2, limn→∞ c6(n) = 1 − q.
Let us proceed to the estimation of the sum S2. Taking into consideration that Ak(0)
is a non-decreasing function with the parameter k to be in the scope k1 < k ≤ k2, we get
S2 ≤ n
2
Ak2 (0) =
n
2
(
n
k2
)
1
2n
θ3(n),
where θ3(n) =
(
1 +
(
1 − 2(ln n−c)
n
)k2
)T
.
It is obvious that θ3(n) satisfies the inequality
(22) θ3(n) ≤
(
1 + exp
{
−2k2 (lnn − c)
n
})T
≤
(
1 +
1
n
ec+1− c
ln n + 2 ln n−c
n
)T
≤ c9(n),
where c9(n) = exp
{
T
n ec+1− c
ln n +2 ln n−c
n
}
.
Then
(23) S2 ≤ 1√
2π
(
1 − 1
ln2 n
) · exp
{
− n
2 ln2 n
(
1 − 1
2 ln n
− 1
2 ln2 n
− ln3 n
n
)}
· c9(n).
Using condition (5) and relation (11) [it follows directly from (4)], we have
1 < lim
n→∞
c9(n) ≤ lim
n→∞ c9(n) ≤ e1+c.
To estimate the sum S4, we use the following expression:
S4 ≤ n
2
Ak3(0) =
n
2
(
n
k3
)
1
2n
(
1 +
(
1 − 2 (lnn − c)
n
)k3
)T
.
ESTIMATES OF THE DISTRIBUTION OF THE RANK OF A RANDOM MATRIX 113
Hence,
(24) S4 ≤ 1√
2π
(
1 − 1
ln2 n
) · exp
{
− n
2 ln2 n
(
1 − 1
2 lnn
− 1
2 ln2 n
− ln3 n
n
)}
· c10(n),
where c10(n) = exp
{
T
n ec−1+ c
ln n
}
. From condition (5) and relation (11), it follows that
1 < lim
n→∞
c10(n) ≤ lim
n→∞ c10(n) ≤ ec−1.
Inequalities (23) and (24) result in
(25)
S2 + S4 ≤ 1√
2π
(
1 − 1
ln2 n
) · exp
{
− n
2 ln2 n
(
1 − 1
2 lnn
− 1
2 ln2 n
− ln3 n
n
)}
×
× (c9(n) + c10(n)) ≤ c7(n) · exp
{
− n
2 ln2 n
c8(n)
}
,
where c8(n) =
(
1 − 1
2 ln n − 1
2 ln2 n
− ln3 n
n
)
, c7 (n) = 1
2π(1− 1
ln2 n
)
· (c9(n) + c10(n), )√
2
π < limn→∞ c7(n) ≤ limn→∞ c7(n) ≤ ec+1+ec−1√
2π
, and limn→∞ c8(n) = 1.
Combining estimates (21), (25), and the estimate for the sum S3 found in Lemma 6,
we obtain Lemma 7.
We now denote the maximum number of independent critical sets of the matrix A by
S (A).
Lemma 8. If conditions (1) and (2) are satisfied, then, for k, k = 0, 1, 2, . . . ,∣∣∣∣P {S (A) = k} − e−λ · λk
k!
∣∣∣∣ ≤ 2MS1 (A) + Q (n, k) ,
where MS1 (A)is found in Lemma 2, while Q (n, k) in Lemma 1.
Proof. Taking into account Lemma 1, we get the following relation:∣∣∣∣P {S (A) = k} − e−λ · λk
k!
∣∣∣∣ ≤ |P {S (A) = k} − P {ξn,T (A) = k}| + Q (n, k) =
= |P {S1 (A) + ξn,T (A) = k} − P {ξn,T (A) = k}| + Q (n, k) .
Applying the relations
P {S1(A) + ξn, T = k} =
k∑
l=0
P {S1 (A) = l, ξn, T = k − l},
|P {S1 (A) = 0, ξn, T = k} − P { ξn, T = k} | ≤ P {S1 (A) ≥ 1}
together with Chebyshev inequality, we find∣∣∣∣P {S (A) = k} − e−λ · λk
k!
∣∣∣∣ ≤ 2P {S1 (A) ≥ 1} + Q (n, k) ≤ 2MS1(A) + Q (n, k) .
Lemma 8 is proved.
The proof of Theorem 1
To estimate MS1(A), we introduce the notation
Δ 1 (k) =
∑
1≤i1<···<ik≤T
1
2n
n∏
j=1
(
1 +
k∏
s=1
(
1 − 2 (lnn + xisj)
n
))
,
114 VOLODYMYR I. MASOL AND SVITLANA V. POPERESHNYAK
Δ 2 (k) =
∑
1≤i1<···<ik≤T
k∏
s=1
n∏
j=1
(
1 − lnn + xisj
n
)
for k ≥ 0. With the help of Lemma 2, MS1(A) can be presented as
MS1(A) =
f(n)∑
k=0
Δ1 (k) +
T∑
k=f(n)+1
Δ1 (k) −
⎛
⎝f(n)∑
k=0
Δ2 (k) +
T∑
k=f(n)+1
Δ2 (k)
⎞
⎠ .
This leads to
MS1(A) ≤
f(n)∑
k=0
Δ1 (k) +
T∑
k=f(n)+1
Δ1 (k) −
f(n)∑
k=0
Δ2 (k) .
From Lemmas 4 and 5, it follows that
(26)
f(n)∑
k=0
Δ1 (k) −
f(n)∑
k=0
Δ2 (k) ≤
≤ μ (n) + μ (n) (1 + δ)Γ (n) −
(
μ (n) − c2 (n)
ln3 n
n · ln lnn
)
=
= μ (n) (1 + δ)Γ (n) + c2 (n)
ln3 n
n · ln ln n
.
Combining (26) with the estimate for the sum
∑T
k=f(n)+1 Δ1 (k) obtained in Lemma
7, we establish the inequality
(27) MS1(A) ≤ μ (n) (1 + δ) Γ (n) + F (n),
where
(28)
F (n) = c2 (n)
ln3 n
n · ln lnn
+ c5(n) · (lnn)
− n·c6(n)
(ln n)q
+
+
(
c3(n)
f(n)
)f(n) 1√
f(n)
c4(n) + c7(n) exp
{
− n
2 ln2 n
c8(n)
}
.
According to (27) and Lemma 8,∣∣∣∣P {S (A) = k} − e−λ · λk
k!
∣∣∣∣ ≤ 2 (μ (n) (1 + δ) Γ (n) + F (n)) + Q(n, k).
Using the explicit expression for Γ(n), we can write∣∣∣∣P {S (A) = k} − e−λ · λk
k!
∣∣∣∣ ≤ 2 (1 + δ) c11(n)u + 2F (n) + Q (n, k) ,
where
(29) c11(n) = μ(n) + μ(n)
u
2
(1 + δ) exp {u (1 + δ)} ,
The last inequality and the relation r(A) + s(A) = T (see [2, p. 148]) imply∣∣∣∣P {r (A) = T − k} − e−λ · λk
k!
∣∣∣∣ ≤ 2 (1 + δ) c(n, k)
ln4 n
n (ln lnn)2
,
where
(30) c(n, k) = c11(n) +
F (n)
(1 + δ)u
+
Q(n, k)
2u(1 + δ)
,
ESTIMATES OF THE DISTRIBUTION OF THE RANK OF A RANDOM MATRIX 115
c11(n), F (n), and Q(n, k) are determined in equalities (29), (28), and (10).
Limited distribution of the rank of a sparse random Boolean matrix
Theorem 2. I. Let the conditions of Theorem 1 hold and
(31) λ → λ0 if n → ∞.
Then 0 < λ0 < ∞, and, for a fixed k, k = 0, 1, 2, . . . ,
(32) P {r(A) = T − k} → e−λ0
λk
0
k!
, n → ∞.
II. If conditions (1), (2), (4), and (31) are satisfied, and λ0 > 0, then λ0 < ∞, and
relation (32) holds true.
Theorem 1 makes it not difficult to prove Theorem 2.
Corollary. If condition (1) holds for xij = x, i = 1, T , j = 1, n, where x is a fixed
number, and T
n → α as n → ∞, where 0 < α < 1, then relation (32) holds for λ0 = αe−x.
To prove the corollary, it is enough to note that the conditions of the corollary imply
immediately the conditions of the first (or the second) part of Theorem 2.
Remark 2. The result of the above-mentioned corollary was obtained, in particular, in
([1], Theorem 1) and in ([2], Theorem 3.3.1).
Conclusions
In the paper, the rate of convergence of the distribution of the rank of a sparse Boolean
matrix to the Poisson distribution (Theorem 1) has been found. Theorem 1 implies
Theorem 2 that generalizes the known result on the limit distribution of the rank of
the mentioned matrix in case where the distributions of its elements depend on their
positions, and the ratio of the number of rows to the number of columns does not exceed
1 − γ(n), where γ(n) tends slowly to zero and takes only positive values.
Bibliography
1. G.V. Balakin, Distribution of the rank of random matrices over a finite field XIII (1968), no. 4,
Probability theory and its application, 631-641. (in Russian)
2. V.F. Kolchin, Random Graphs, Fizmatlit, Moscow, 2004, pp. 256. (in Russian)
3. V.I. Masol, Moments of the number of solutions of a system of random Boolean equations,
Random Oper. and Stoch. Equations. 1 (1993), no. 2, 171-179.
4. V.I. Masol, Theorems of invariance for systems of random Boolean equations (1993), Sixth
Intern. Vilnius Conf. of Probability Theory and Math. Statist.: Abstr. of Communic., Vilnius,
19-20.
5. B.A. Sevastyanov, Course of the Theory of Probability and Mathematical Statistics, Nauka,
Moscow, 1982, pp. 256. (in Russian)
E-mail : vimasol@ukr.net
E-mail : Popereshnyak sv@mail.ru
|