Стр. 3 - Е.Ю. Алехова - Исследование кластеризуемости строк больших разреженных матриц над GF(2)

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012 39
Исходя из этих соображений, оценим сверху и снизу вероятность
наличия среди l строк не менее k строк, все единицы которых содер-
жатся в заданных s столбцах:
.
n s s n s k
m m m m m
l k k l k k
p
n n
m m
l l
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
− − ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
− −
⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
< <
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
(6)
Нижняя и верхняя оценки отличаются одним сомножителем, ко-
торый равен для нижней и для верхней оценок. Оценим отношение
.
n s
m m
l k
r
n k m
l k
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ − ⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎝ ⎠ ⎝ ⎠
⎜ ⎟
− ⎝⎠
=
⎛ ⎞ ⎛ ⎞ − ⎜ ⎟ ⎜
⎟
⎝ ⎠ ⎜ ⎟ − ⎝
⎠
(7)
Для этого представим числитель и знаменатель в следующем виде:
1
1
1 ;
( )! ( )!
l l k
l
i k
i k
n n i
n m m i k m
n l k l k
l k m
− −
−
=
=
⎡ ⎤ ⎛ ⎞ ⎡ ⎤ ⎛ ⎞
− ⎜ ⎟
⎛ ⎞ ⎜ ⎟ ⎢ ⎥ ⎛ ⎞ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ − ⎝ ⎠ ⎜ ⎟ ⎜ ⎟ = = −⎢ ⎥ ⎝ ⎠ − − ⎜ ⎟ ⎛ ⎞
⎢ ⎥ − ⎜ ⎟ ⎝ ⎠ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦
∏
∏ (8)
1
1
1 .
( )! ( )!
l l k
l
i k
i k
n s n s
i
n s m m m m i
m m n n l k l k
l k m m
− −
−
=
=
⎡ ⎤ ⎛ ⎞ ⎛ ⎞ ⎡ ⎤ ⎛ ⎞ ⎛ ⎞
− − ⎜ ⎟ ⎜ ⎟ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎛ ⎞ ⎛ ⎞ ⎢ ⎥ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦ − ⎝ ⎠ ⎝ ⎠ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = = − − ⎢ ⎥ ⎝ ⎠ ⎝ ⎠ − − ⎜ ⎟ ⎛ ⎞ ⎛ ⎞
⎢ ⎥ − ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎢ ⎥ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦
∏
∏ (9)
Выпишем нижние оценки для выражений (8) и (9):
1 ( )( 1)
1 1 ;
2
l
i k
i l k l k
n n
m m
−
=
⎡ ⎤
⎢ ⎥ − − −
⎢ ⎥
− > −
⎢ ⎥ ⎛ ⎞ ⎛ ⎞
⎢ ⎥ ⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
⎣ ⎦
∏ (10)