Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем
Запропоновано метод прискореного моделювання для обчислення кількості k-вимірних підпросторів ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Для ω=1 та ω=2 будуються незміщені оцінки, а для ω=3 — верхні та нижні оцінки. Доведено обмеженість відносної середньоквадрати...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45197 |
| 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: | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем / В.И. Масол, И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 3. — С. 69-83. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860114058598940672 |
|---|---|
| author | Масол, В.И. Кузнецов, И.Н. |
| author_facet | Масол, В.И. Кузнецов, И.Н. |
| citation_txt | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем / В.И. Масол, И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 3. — С. 69-83. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано метод прискореного моделювання для обчислення кількості k-вимірних підпросторів ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Для ω=1 та ω=2 будуються незміщені оцінки, а для ω=3 — верхні та нижні оцінки. Доведено обмеженість відносної середньоквадратичної похибки оцінок при q → ∞. Високу точність методу ілюструють чисельні приклади.
A fast simulation method for the evaluation of the number of k-measurable subspaces of the weight ω of n-measurable vector+ space over the Galois field containing q components is proposed. The unbiased estimates are constructed for the cases ω=1 and ω=2, and lower and upper estimates are proposed for the case ω=3. It is proved that relative error remains bounded as q → ∞. High accuracy of the method proposed is demonstrated on numerical examples.
|
| first_indexed | 2025-12-07T17:35:17Z |
| format | Article |
| fulltext |
ÓÄÊ 519.12
Â.È. ÌÀÑÎË, È.Í. ÊÓÇÍÅÖÎÂ
ÏÐÈÌÅÍÅÍÈÅ ÓÑÊÎÐÅÍÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß Ê ÎÖÅÍÊÅ
ÊÎËÈ×ÅÑÒÂÀ ÍÅÊÎÒÎÐÛÕ k-ÌÅÐÍÛÕ ÏÎÄÏÐÎÑÒÐÀÍÑÒÂ
ÍÀÄ ÊÎÍÅ×ÍÛÌ ÏÎËÅÌ
Êëþ÷åâûå ñëîâà: âåêòîðíîå ïðîñòðàíñòâî, ïîëå Ãàëóà, âåñ ïðîñòðàíñòâà, ìå-
òîä âçâåøåííîãî ìîäåëèðîâàíèÿ, íåñìåùåííàÿ îöåíêà, îòíîñèòåëüíàÿ ñðåäíå-
êâàäðàòè÷åñêàÿ ïîãðåøíîñòü.
Ðàññìîòðèì n-ìåðíîå âåêòîðíîå ïðîñòðàíñòâî Vn íàä êîíå÷íûì ïîëåì GF(q), ñîäåð-
æàùèì q ýëåìåíòîâ, ãäå q — ñòåïåíü ïðîñòîãî ÷èñëà. Èçâåñòíî [1, ñ. 219], ÷òî îá-
ùåå ÷èñëî ðàçëè÷íûõ k-ìåðíûõ ïîäïðîñòðàíñòâ Vk n, ïðîñòðàíñòâà Vn ðàâíî
n
k
q
q
k n
n i
k i
i
k
�
��
�
��
�
�
�
1
1
1
0
1
, .
Âåñîì âåêòîðà ��Vn íàçûâàåòñÿ ÷èñëî îòëè÷íûõ îò íóëÿ êîìïîíåíò âåêòîðà �.
Âåñîì k-ìåðíîãî ïîäïðîñòðàíñòâà Vk n, ïðîñòðàíñòâà Vn íàçûâàåòñÿ ÷èñëî, ðàâíîå
ìèíèìàëüíîìó âåñó âåêòîðà ��Vk n, , îòëè÷íîãî îò íóëåâîãî. ×èñëî k-ìåðíûõ ïîä-
ïðîñòðàíñòâVk n, ïðîñòðàíñòâàVn , êàæäîå èç êîòîðûõ èìååò âåñ ��
{ }1 1, ,� n k ,
îáîçíà÷èì n
k
��
��
�
��
. Î÷åâèäíî, ÷òî
n
k
n
k
n k
�
��
�
��
� �
��
�
���
�
�
�
1
1
, 1
k n.
Ýôôåêòèâíîñòü êîäèðîâàíèÿ èíôîðìàöèè ñ ïîìîùüþ ëèíåéíûõ ( , )n k -êîäîâ
(èìåííî òàê íàçûâàþò åù¸ ïîäïðîñòðàíñòâî Vk n, ) ïðèíÿòî õàðàêòåðèçîâàòü ÷èñëîì
k
n
(ñì., íàïðèìåð, [2, ñ. 12]). Ïîâûøåíèå ýôôåêòèâíîñòè ïðèâîäèò ê ñíèæåíèþ
âåñà �, ÷òî íå âåçäå æåëàòåëüíî äëÿ ïðîöåññà êîäèðîâàíèÿ èíôîðìàöèè, òàê êàê
óìåíüøàåò åãî êîððåêòèðóþùèå âîçìîæíîñòè, ñâîäÿ èõ ê íóëþ ïðè � �1. Òåì íå
ìåíåå ïîäïðîñòðàíñòâà Vk n, íåáîëüøîãî âåñà �, â ÷àñòíîñòè � �1, íàõîäÿò ïðèìå-
íåíèå ïðè êîäèðîâàíèè (ïîñêîëüêó ïîçâîëÿþò óâåëè÷èâàòü ýôôåêòèâíîñòü) ñ ïî-
ñëåäóþùåé ïåðåäà÷åé âûñîêîíàäåæíûìè êàíàëàìè ñâÿçè, î ÷åì áûëî ñêàçàíî â [3].
 ñâîþ î÷åðåäü, îöåíêà ÷èñëà ïîäïðîñòðàíñòâ Vk n, çàäàííîãî âåñà � ïðåäñòàâëÿåò
èíòåðåñ êàê äëÿ çàäà÷ êîäèðîâàíèÿ, òàê è äëÿ ðåøåíèÿ ïðîáëåìû çàùèòû
èíôîðìàöèè îò íåñàíêöèîíèðîâàííîãî äîñòóïà.
Äëÿ âû÷èñëåíèÿ n
k
��
��
�
��
ïðè � �1è � � 2 â [4, 5] ïðåäëîæåíû ðåêóððåíòíûå ôîð-
ìóëû. Â íàñòîÿùåé ñòàòüå äëÿ îöåíêè n
k
��
��
�
��
ðàçðàáîòàí ïðèíöèïèàëüíî íîâûé
ïîäõîä, îñíîâàííûé íà óñêîðåííîì ìîäåëèðîâàíèè ìàëûõ âåðîÿòíîñòåé. Â îñíîâå
ïðåäëàãàåìîãî ìåòîäà ëåæèò èäåÿ È.Í. Êîâàëåíêî [6–8] î ðàçëîæåíèè èñêîìîé õà-
ðàêòåðèñòèêè ïî ñòåïåíÿì íåêîòîðîãî ïàðàìåòðà. Â òåîðèè íàäåæíîñòè òàêîé ïîä-
õîä ìíîãîêðàòíî èñïîëüçîâàëñÿ äëÿ ïîâûøåíèÿ òî÷íîñòè âû÷èñëåíèé. Ïðè ýòîì
íåèçâåñòíàÿ õàðàêòåðèñòèêà ðàñêëàäûâàåòñÿ â ðÿä ïî ñòåïåíÿì ìàëîãî ïàðàìåòðà,
ïðè÷åì êîýôôèöèåíòû ýòîãî ðÿäà îöåíèâàþòñÿ ìåòîäîì Ìîíòå-Êàðëî. Âûñîêàÿ
ýôôåêòèâíîñòü âû÷èñëåíèé äîñòèãàåòñÿ çà ñ÷åò áûñòðîé ñõîäèìîñòè ðÿäà.  îòëè-
÷èå îò çàäà÷ òåîðèè íàäåæíîñòè â íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ ðàçëîæèòü n
k
��
��
�
��
ïî ñòåïåíÿì áîëüøîãî ïàðàìåòðà q (òèïè÷íûå çíà÷åíèÿ q q� �2 28 16, èëè q � 232 ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 69
© Â.È. Ìàñîë, È.Í. Êóçíåöîâ, 2010
 ñòàòüå ïðåäëîæåí ìåòîä óñêîðåííîãî ìîäåëèðîâàíèÿ, ïîçâîëÿþùèé ñòðîèòü íå-
ñìåùåííûå îöåíêè äëÿ n
k
��
��
�
��
ïðè � �1è � � 2, à òàêæå âåðõíèå è íèæíèå îöåíêè ïðè
� � 3. Äîêàçàíà îãðàíè÷åííîñòü îòíîñèòåëüíîé ñðåäíåêâàäðàòè÷åñêîé ïîãðåøíîñòè
îöåíîê ïðè q ��. Âûñîêàÿ òî÷íîñòü ìåòîäà èëëþñòðèðóåòñÿ ÷èñëåííûìè ïðèìåðàìè.
ÎÁÙÀß ÑÕÅÌÀ ÓÑÊÎÐÅÍÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß
Ïåðåôîðìóëèðóåì ïîñòàâëåííóþ âûøå çàäà÷ó ýêâèâàëåíòíûì îáðàçîì. Ïðè ýòîì
êëþ÷åâóþ ðîëü èãðàåò àëãîðèòì [9] ïîñòðîåíèÿ ìíîæåñòâà áàçèñíûõ âåêòîðîâ
k-ìåðíîãî ïîäïðîñòðàíñòâà Vk n, ïðîñòðàíñòâà Vn ( )1
k n . Ýòîò àëãîðèòì ñâî-
äèòñÿ ê ïîñòðîåíèþ ìàòðèöû A :
r r r
A
a a
a a a
k
r
r r
1 2
11 1 1
21 2 1 2 1
1
1 1
1 0 0 0 0 0 0 0 0
0
� � �
�
� � � �
� � � �
� � � � � � � � � � � � � � �
� �
a
a a a a
r
k kr kr k
2 1
1 1 1
2
1 1
1 0 0 0 0 0
0
r kr kra a
k2 21 1 10 1 0 0
�
�
�
�
�
�
�
�
�
�
�
�� �
.
Ïóñòü r r rk� ( , , )1 � — k-ìåðíûé âåêòîð, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ
óïîðÿäî÷åííûå íàòóðàëüíûå ÷èñëà, U r r r r nk�
� � �
{ }: 1 1 2 � .
Àëãîðèòì [9]
1. Âûáèðàåì ïðîèçâîëüíûé âåêòîð r U� .
2.  ìàòðèöå A ñ k ñòðîêàìè è n ñòîëáöàìè îáðàçóåì åäèíè÷íóþ ìàòðèöó ðàç-
ìåðíîñòè k k� , ñòîëáöû êîòîðîé èìåþò íîìåðà, çàäàâàåìûå âåêòîðîì r.
3. Â i-é ñòðîêå ìàòðèöû A ( )1
i k çàïèñûâàåì íóëü âî âñå ïîçèöèè j ri� .
4. Îñòàâøèåñÿ ìåñòà â ìàòðèöå A çàïîëíÿåì ýëåìåíòàìè ïîëÿ íåçàâèñèìûì
îáðàçîì.
Ñòðîêè ïîñòðîåííîé ìàòðèöû ÿâëÿþòñÿ áàçèñíûìè âåêòîðàìè íåêîòîðîãî ïîä-
ïðîñòðàíñòâàV Vk n n, � . Ïîýòîìó çàäà÷à íàõîæäåíèÿ êîëè÷åñòâà k-ìåðíûõ ïîäïðîñ-
òðàíñòâ âåñà � ñâîäèòñÿ ê îïðåäåëåíèþ êîëè÷åñòâà ìàòðèö A ñ áàçèñíûìè âåêòîðà-
ìè, ëèíåéíàÿ êîìáèíàöèÿ êîòîðûõ äàåò âîçìîæíîñòü ïîñòðîèòü âåêòîð, ñîäåðæà-
ùèé ðîâíî � íåíóëåâûõ êîìïîíåíò, è â òî æå âðåìÿ íå ñóùåñòâóåò ëèíåéíîé
êîìáèíàöèè áàçèñíûõ âåêòîðîâ ñ ìåíüøèì ÷èñëîì íåíóëåâûõ êîìïîíåíò.
Îáîçíà÷èì:
n
k
r�;�
��
�
��
— êîëè÷åñòâî k-ìåðíûõ ïîäïðîñòðàíñòâ âåñà � ïðè ôèêñèðîâàííîì
âåêòîðå r U� ;
U L r U r r r r k Lk� �( ) : , ( ) ( ) ( )� � �
�{ }1 2 32 3 � ,
( ) ( ) ( ) ( )k L k n k
1 1 1� ;
| ( ) |U L� — êîëè÷åñòâî ýëåìåíòîâ âî ìíîæåñòâå U L� ( ) .
Ó÷èòûâàÿ, ÷òî n
k
r�;�
��
�
��
� 0 ïðè r U L
L k
k n k
�
�
( ) ( )
( ) ( )
( )
1 1
1
�
�� , èìååì: äëÿ ëþáîãî
��
{ }1 1, ,� n k
n
k
n
k
r
r U L k
k n k
r
� �
�
�
��
�
��
� �
��
�
��
�
� �
� �;
( ) ( )
( ) ( )
1 1
1
�
� �
��
�
��
�
U L
n
k
r
�
�
( )
;
�
�
�
� �| ( )|
( ) ( )
( ) ( )
( )
U L q
q
L
L k
k n k
r U L
L�
�
�
�
�
1
1 1
1
1
�
��
�
��
�
1
1n
k
r
U L
�
�
;
| ( )|
�
��
�Z
U L q
Z
c r
L
r U LL k
k n
�
�
�
�
�
� �
| ( )|
( )
( )( ) ( )
( ) ( 1
1 1
1
� �
k
U L
Z c
)
| ( )|
( ) | ,
1
�
� � � � �M M{ } (1)
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
ãäå
Z U L q
L k
k n k
L
�
�
�
��
�
�
( ) ( )
( ) ( )
| ( )|
1 1
1
1, c r
q
n
k
r
L� �
�( ) ;� �
��
�
��
1
1
, (2)
ìàòåìàòè÷åñêîå îæèäàíèå M� áåðåòñÿ ïî ðàñïðåäåëåíèþ ñëó÷àéíîé âåëè÷èíû �,
ïðèíèìàþùåé çíà÷åíèå L k� {( ) ( ),1 1� ( ) ( ) , , ( ) ( )k k n k
1 1 1 1� � } ñ âåðî-
ÿòíîñòüþ
1 1
Z
U L qL
�
�
�| ( )|
; ïðè ôèêñèðîâàííîì � ñëó÷àéíûé âåêòîð � èìååò
ðàâíîìåðíîå ðàñïðåäåëåíèå íà ìíîæåñòâå U� �( ) .
Äëÿ òîãî ÷òîáû âîñïîëüçîâàòüñÿ ñîîòíîøåíèÿìè (1), (2), íåîáõîäèìî óìåòü
âû÷èñëÿòü | ( )|U L� è c r� ( ) ïðè ëþáûõ ôèêñèðîâàííûõ L , r è �. Îñíîâíóþ ïðîáëå-
ìó ïðåäñòàâëÿåò âû÷èñëåíèå c r� ( ) .  ñëåäóþùèõ ðàçäåëàõ ïðèâåäåíû ÿâíûå àíà-
ëèòè÷åñêèå ôîðìóëû äëÿ c r1 ( ) è c r2 ( ) , à òàêæå íèæíÿÿ è âåðõíÿÿ îöåíêè äëÿ
c r3 ( ) . Îñòàíîâèìñÿ ïîäðîáíee íà íàõîæäåíèè | ( )|U L� .
Êîëè÷åñòâî ýëåìåíòîâ âî ìíîæåñòâå U L� ( ) ïðè ôèêñèðîâàííûõ n k, è L
îáîçíà÷èì �� ( , , )n k L ( | ( )| ( , , )U L n k L� ��� ). Ñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåí-
òíàÿ ôîðìóëà: ïðè 2 1 1 1
i k i m n i l, , ( ) ( )� � ( ) ( ),i m i 1
� ��
�
�( , , ) (
min , ( ) ( )
m i l j
j i
l
i
m l i i
�
�
�
��
�
��
�
1
1 2{ }
1 1, , ( ))i l j i , (3)
ãäå
l
i
j j
l
i
�
��
�
��
� �
�
�
!
"
#1 1
min : . Ñîîòíîøåíèå (3) äîïîëíÿåòñÿ ãðàíè÷íûìè óñëîâèÿìè:
$ � �� ( , , )m m10 1�
äëÿ ëþáîãî m � �;
$ � �� % & & % ' % ''( ) ) �* * * äëÿ ëþáûõ m i m�
� �1 2 1, +
Ôîðìóëà (3) âûòåêàåò èç ñëåäóþùèõ ñîîáðàæåíèé. Îïðåäåëèì çíà÷åíèÿ, êàêèå
ìîæåò ïðèíèìàòü ri , åñëè èçâåñòíî, ÷òî r1 � � è
( ) ( ) ( )r r r i li2 32 3
�� . (4)
Ïîñêîëüêó r ss � � 1 äëÿ ëþáîãî s i� 2 1, ,� , òî èç (4) ñëåäóåò, ÷òî
( ) ( )�
1 2i r i li , ò.å. r l i ii
( ) ( )� 1 2 . Â òî æå âðåìÿ r mi
, ïîýòîìó
r m l i ii
min , ( ) ( ){ }� 1 2 . Èç (4) ñëåäóåò, ÷òî
r l r r r
i i
l r ri i i i i�
�
( )
( ) ( )
[( ) ( )1 2 2
1 2
2
1 2�
�
�
�
( )]
( ) ( )
( ) ( )r i
i i
l i r i ii i2
1 2
2
2 1 ,
ïîýòîìó r i
l
i
i �
�
��
�
��1
. Åñëè r ji � , òî �
� � �
r r r ji1 2 1 1� ; ïðè ýòîì çíà÷å-
íèå l óìåíüøàåòñÿ íà j i (èìåííî ñòîëüêî ïîçèöèé áûëî ðàñïîëîæåíî â i-é
ñòðî÷êå äëÿ çàïîëíåíèÿ ýëåìåíòàìè ïîëÿ — ñì. àëãîðèòì).
Ïðåäïîëîæèì, ÷òî íàéäåíû ÿâíûå àíàëèòè÷åñêèå ôîðìóëû äëÿ âû÷èñëåíèÿ êîýôôè-
öèåíòà c r� ( ) ïðè ëþáîì � è ëþáûõ çíà÷åíèÿõ ïàðàìåòðîâ L r, . Ôîðìóëû (1), (2) ïîçâîëÿ-
þò ïðåäëîæèòü ïðîñòîé àëãîðèòì ïîñòðîåíèÿ íåñìåùåííûõ îöåíîê äëÿ n
k
��
��
�
��
.
1. Ñ ïîìîùüþ îïèñàííîãî âûøå ðåêóððåíòíîãî àëãîðèòìà (ñì. (3)) âû÷èñëÿåì
| ( )| ( , , )U L n k L� ��� äëÿ âñåõ L k k n k� ( ) ( ), , ( ) ( )1 1 1� � .
2. Ñîãëàñíî (2) âû÷èñëÿåì Z� .
3. Ñòðîèì ðåàëèçàöèþ ñëó÷àéíîé âåëè÷èíû �, êîòîðàÿ ðàâíà L k� {( ) ( ),1 1� �
... , ( ) ( )k n k 1 } ñ âåðîÿòíîñòüþ
| ( )|U L q
Z
L
�
�
�
1
.
4. Ñòðîèì ðåàëèçàöèþ ñëó÷àéíîãî âåêòîðà �, èìåþùåãî ðàâíîìåðíîå ðàñïðå-
äåëåíèå íà ìíîæåñòâå U� �( ) (ïðè ýòîì ñóùåñòâåííûì îáðàçîì èñïîëüçóåòñÿ ñîîò-
íîøåíèå (3), ïîçâîëÿþùåå ðåêóððåíòíî ìîäåëèðîâàòü êîìïîíåíòû âåêòîðà �).
5. Âû÷èñëÿåì c r� ( ) .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 71
6.  êà÷åñòâå îöåíêè äëÿ n
k
��
��
�
��
, ïîñòðîåííîé â îäíîé ðåàëèçàöèè àëãîðèòìà,
âûáèðàåì � ( ) ( )� � �� � �� Z c .
Çàìå÷àíèå. Ïðè ôèêñèðîâàííîì � âû÷èñëåíèå Z� (ïåðâûå äâà øàãà àëãîðèò-
ìà) ïðîâîäèòñÿ âñåãî îäèí ðàç.
Òåîðåìà 1. Îöåíêà � ( )� �� ÿâëÿåòñÿ íåñìåùåííîé, ò.å. M� ( )� � �� � �
��
�
��
n
k
.
Óòâåðæäåíèå òåîðåìû ñëåäóåò íåïîñðåäñòâåííî èç ñîîòíîøåíèé (1) è (2).
 ñëåäóþùèõ äâóõ ðàçäåëàõ ïðèâåäåíû ôîðìóëû, ïîçâîëÿþùèå âû÷èñëÿòü
c r� ( ) â ÿâíîì âèäå ïðè � �� �1 2, , à òàêæå ñòðîèòü âåðõíèå è íèæíèå îöåíêè äëÿ
c r� ( ) ïðè � � 3 .
ÍÀÕÎÆÄÅÍÈÅ c r� ( ) ÏÐÈ � � 1 È � � 2
Ïóñòü r r rk� ( , , )1 � — âåêòîð, îïðåäåëÿþùèé íîìåðà ñòîëáöîâ, îáðàçóþùèõ
åäèíè÷íóþ ìàòðèöó â ìàòðèöå A (ñì. àëãîðèòì ïîñòðîåíèÿ ìíîæåñòâà áàçèñíûõ
âåêòîðîâ k-ìåðíîãî ïîäïðîñòðàíñòâà Vk n, ). Êîëè÷åñòâî ïîçèöèé â i-é ñòðî÷êå
( , , )i k�1 � , äîñòóïíûõ äëÿ çàïîëíåíèÿ ýëåìåíòàìè ïîëÿ, ðàâíî r ii . Î÷åâèäíî,
÷òî r i r ji j
ïðè i j� .  äàëüíåéøåì èñêëþ÷èì èç ðàññìîòðåíèÿ ñòîëáöû
ìàòðèöû A ñ íîìåðàìè, çàäàâàåìûìè âåêòîðîì r, à òàêæå ñòîëáöû ñ íîìåðàìè
j rk� .  ðåçóëüòàòå ïîëó÷èì ïðÿìîóãîëüíóþ ìàòðèöó ðàçìåðíîñòè k r kk� ( ) .
Åñëè N r( ) — îáùåå êîëè÷åñòâî âàðèàíòîâ ðàçìåùåíèÿ ýëåìåíòîâ ïîëÿ, òî
N r q q
r i
i
k r i
i
i
i
k
( ) .
( )
� �
�
�
� �
1
1 (5)
Ââåäåì íåêîòîðûå îáîçíà÷åíèÿ, îáëåã÷àþùèå äàëüíåéøåå èçëîæåíèå:
$ , — ìíîæåñòâî ýëåìåíòîâ ïîëÿ Ãàëóà (q ýëåìåíòîâ);
$ { }�
j
i
ij r i i k( ) , , , , , ,� �1 1� � — íåçàâèñèìûå â ñîâîêóïíîñòè îäèíàêîâî
ðàñïðåäåëåííûå ñëó÷àéíûå âåëè÷èíû, ïðèíèìàþùèå çíà÷åíèÿ èç , ñ îäíîé è òîé
æå âåðîÿòíîñòüþ
1
q
;
$ � � � �( ) ( ) ( ) ( )( , , , , , , ),i i i
r i
i
r r i k
i
k i
�
1 2
0 0� �
��� ��
i k�1, , ,� — âåêòîðû ðàçìåðíîñòè
- .. /
$ ( )x — êîëè÷åñòâî íåíóëåâûõ êîìïîíåíò âåêòîðà x ðàçìåðíîñòè r kk ;
$ z q r i q q r q ii
r i
i i
r i
i
i i� � �
1 1 1 1 1 1( ) ( ), ( ) ( ), ,� � , k.
Âîñïîëüçóåìñÿ ñîîòíîøåíèåì
n
k
r N r Y r� �; ( ) ( )�
��
�
��
� P { }, (7)
ãäå Y r� ( ) — ñîáûòèå, ñîñòîÿùåå â òîì, ÷òî ñòðî÷êè ìàòðèöû A ñ âûáðàííûìè
ñëó÷àéíûì îáðàçîì ýëåìåíòàìè { }aij (ïðè ôèêñèðîâàííîì r) ÿâëÿþòñÿ áàçèñíû-
ìè âåêòîðàìè k-ìåðíîãî ïîäïðîñòðàíñòâà âåñà �. Èç ôîðìóë (2), (5) è (7) ñëåäó-
åò, ÷òî
c r
q
n
k
r
N r
q
Y r q
L L
r
� � � �
��( ) ;
( )
( )� �
��
�
��
� �
1
1 1
1P P{ } { }Y r� ( ) . (8)
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2. Ïðè � �1 èìååò ìåñòî ðàâåíñòâî
c r
q q
r r i r j
j
i
i
k
i j
1 1
1
1
2
1
1
1
1
1
( ) �
�
�
�
�
�
�
�
�
�
�
�� . (9)
Ïóñòü � � 2 . Åñëè r1 2� , òî
c r
q q
r i
i
k
i
2
2
1
1
1
1
( ) �
�
�
��
�
�
��
�
�
�
�
�
�
�
�
�
� . (10)
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
(6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 73
Ïóñòü r1 3� . Åñëè �m
0 (ñì. (6)) äëÿ íåêîòîðîãî m k�{ }2, ,� , òî
c r q
q
r
r i
i
k
i
2
2
1
1 1
1
( ) �
�
�
�
�
�
�
�
�
�
� . (11)
Åñëè æå �m � 0 äëÿ âñåõ m k�{ }2, ,� , òî
c r
r q
q
r q
q
i
r i ri
2
1
2
1 1 1 1 1
1
1
1
( )
( ) ( ) ( ) ( )
�
�
�
0
0
�
�
�
�
�
�
�
�
�
�
��
( ) ( )r q
q
j
r j
j
i
i
k
j
1 1
1
1
2
�
�
�
�
�
�
�
�
!
"
0
#0
�
�1
1
1
1 2
1
1
q q
r i r r j
j
i
i j
. (12)
Äîêàçàòåëüñòâî. Äëÿ òîãî ÷òîáû k-ìåðíîå ïîäïðîñòðàíñòâî èìåëî âåñ � �1,
íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû õîòÿ áû â îäíîé ñòðî÷êå íà âñåõ äîïóñòèìûõ ïî-
çèöèÿõ áûëè ðàñïîëîæåíû íóëè. Èíà÷å ãîâîðÿ,
P P{ } { }Y r
q
i
i
k
r ii
� �( ) ( )( )� �
�
�
0
0
!
"
0
#0
�
�
�
�
�
0 1 1
1
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
� ��
i
k
r i r j
j
i
i
k
q qi j
1 1
1
1
1
1
1
.
 ïîñëåäíåì ðàâåíñòâå èñïîëüçîâàëîñü ñîîòíîøåíèå
1 1 1
1 1
1
1
�
� �
�
� ��( ) ( )g g gi
i
k
i j
j
i
i
k
, (13)
ãäå 0 1 1
g i ki , . Ó÷èòûâàÿ ñîîòíîøåíèå (8) ïðè � �1, ïîëó÷àåì ðàâåíñòâî (9).
Âûâåäåì aíàëîãè÷íûå ôîðìóëû äëÿ c r2 ( ) ïðè ôèêñèðîâàííûõ L è r. Äëÿ òîãî
÷òîáû k-ìåðíîå ïîäïðîñòðàíñòâî èìåëî âåñ � � 2 , íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû
ïðîèçîøëî îäíî èç äâóõ íåñîâìåñòíûõ ñîáûòèé:
$ B i� �{ �( )( ) 1 äëÿ íåêîòîðîãî i k�{ }1, ,� è �( ) ,( )j j i� 11 };
$ C i� �{ �( )( ) 2 äëÿ âñåõ i k�{ }1, ,� , è ñóùåñòâóþò j l k, , , ,�{ }1 � j l� , òàêèå,
÷òî � � �( ) ( )j l+ � 0 äëÿ íåêîòîðîãî � �� 1, , 0}.
Òîãäà Y r B C� ( ) � 2 . Ïðè ýòîì
P P{ } { } { }B i
i
k
i
i
k
� � 3 �
�
�
0
0
!
"
0
#0
�
� �
� �( ) ( )( ) ( )1 1
1 1
� P { } �( )( )i
i
k
�
�
�
0
0
!
"
0
#0
�
1
1
�
�
�
0
0
!
"
0
#0
�
�
�
�
�
�
�
�
��
�
�P { } �( )( )i
i
k
r i
i
k
q i
2 1
1
1 1
�
�
�
�
�
�
�
�
�
� 1
1 1
1
( ) ( )r i q
q
i
r i
i
k
i
. (14)
Îáîçíà÷èì:
C j l j l( , ) ( ) ( )� �{ +� � � 0 äëÿ íåêîòîðîãî � �� 1
�
, , ,0 1} j l k;
C C i k C C C C Ci
j l
j l i
k k k
j l� � � � � �
�
( , ) ( , ), , , , ,
1
1 2
1
2 � �
j l k�
� .
Åñëè r1 2� , òî P{ }C � 0 è
c r B
q q
r i
i
k
i
2
2
1
1
1
1
( ) � �
�
�
��
�
�
��
�
�
�
�
�
�
�
�
�
�P { } .
Ïðåäïîëîæèì, ÷òî r1 3� . Òîãäà
P P{ } { }C Ci
i
k
j l
j l k
� � 3
�
�
0
0
!
"
0
#0
�
�
�
�( )( ) ( , )2
1 1
�
� �
�
�
0
0
!
"
0
#0
�
� �
P P{ } { } � �( ) ( )( ) ( )|i
i
k
k
i
i
k
C2 1 2
1 1
�
�
0
0
!
"
0
#0
�
�
�
�
�
�
�
�
�
� 3 �
�
�
0
0
!
"
0
#0
�
�
�
z
q
C Ci
r i
i
k
m m
i
i
k
i
1
1
1
1 2P | ( )( ){ } �
m
k
�
�
�
�
�
�
�
�
�
�2
, (15)
ãäå C1 — äîñòîâåðíîå ñîáûòèå. Ïîñêîëüêó C C C m km m
j m
j
m
� 3 �
�
1
1
1
2( , ) , , , � ,
òî ñ ó÷åòîì îáîçíà÷åíèé (6) ïîëó÷èì ñîîòíîøåíèå
P PC C Cm m
i
i
k
j m
j
m
| ( )( ) ( , )
� �
3 �
�
�
0
0
!
"
0
#0
�1
1 1
1
2{ } { � | ( )( )Cm
m
3 � �1 2{ }} �
� 3 �
�
�
0
0
!
"
0
#0
�
�
1 2 1
1
1
1P C C
mj m
j
m
m
m( , ) ( )| ( )
(
� { } �
1 1) ( )q
z zm
m
m
�
�
(16)
(îáùåå ÷èñëî âàðèàíòîâ ðàçìåùåíèÿ ýëåìåíòîâ â m-é ñòðî÷êå, áëàãîïðèÿòñòâóþ-
ùèõ óñëîâèþ { } �( )( )m � 2 , ðàâíî z qm
r mm�
1 ( ) ( )r m qm 1 ; èç íèõ ëèøü
( ) ( )m q 1 1 âàðèàíòîâ áëàãîïðèÿòñòâóþò ñîáûòèþ C j m
j
m
( , )
�
1
1
� ). Ïîýòîìó èç (15) è
(16) ñëåäóåò ðàâåíñòâî
P{ }C
z
q z
i
r i
i
k
m
mm
k
i
�
�
�
�
�
�
�
� �
� �
1 2
1
�
. (17)
Åñëè �m
r m
mq r qm�
1 1 1 0( ) ( ) äëÿ íåêîòîðîãî m k�{ }2, ,� , òî
P{ }C
z
q
i
r i
i
k
i
�
�
�
1
.  ýòîì ñëó÷àå
c L r q B C q
q
r r
r i
i
k
i
2
2 2
1
1 1 1
1
( , ) [ { } { }]� �
�
�
�
�
�
�
�
�
�
P + P � .
Ïðåäïîëîæèì òåïåðü, ÷òî �m � 0 äëÿ âñåõ m k�{ }2, ,� . Òîãäà èç (14) è (17)
ñëåäóåò, ÷òî
c L r q B C q
q
r r
r i
i
k
i
2
2 2
1
1 1 1
1
( , ) [ ]�
�
�
�
�
�
�
�
�
�
�
P P{ } { } � �
�
�
0
0
!
"
0
#0
�
� i
r i
i
k
q i
1
(ïðè ýòîì ó÷èòûâàåòñÿ, ÷òî z1 1� � ). Îáîçíà÷èâ
�
i
i
r i
q
i k
i
� �
1 1, , ,� , èç (13)
èìååì
c L r q
q q
r
r i r j
j
i
i
k
i j
2
2
1
1
1
1 1
1
1
1
( , ) �
�
�
�
�
�
�
�
�
�
�
�� 1 1
1
1
1
�
�
0
0
!
"
0
#0
�
�
�
��
i j
j
i
i
k
( )
�
�
�
0
0
( ) ( ) ( ) ( ) (r q
q
r q
q
r
i
r i r
j
i
1
2
1 1 1 1 1
1
1
1
1 1
1
1
2
) ( )q
q
r j
j
i
i
k
j
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
!
"
0
#0
�
�1
1
1
1 2
1
1
q q
r i r r j
j
i
i j
.
Òåîðåìà 2 äîêàçàíà.
ÂÅÐÕÍßß È ÍÈÆÍßß ÎÖÅÍÊÈ ÄËß c r3( )
Äëÿ òîãî ÷òîáû k-ìåðíîå ïîäïðîñòðàíñòâî èìåëî âåñ � � 3 , íåîáõîäèìî è äîñ-
òàòî÷íî, ÷òîáû ïðîèçîøëî ñîáûòèå
Y r D E F G H� ( ) ( )� 3 3 2 2 ,
ãäå:
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
D i ki� � �{ } �( ) , , ,( ) 2 1 � ,
E E Ei j i j i j
i j k
� � 1
�
( , ) ( , ) ( ) ( ), { +� � � 0
1
äëÿ âñåõ � �� 1, , 0},
F F F i ki i i
i k
� � � �
( ) ( ) ( ), ( ) , , ,{ } � 2 1
1
�� ;
G G Gi j
i j k
i j i j� � �
�
( , ) ( , ) ( ) ( ),
1
1� { +� � � äëÿ íåêîòîðîãî � �� 1, , 0},
H H i j l
i j l k
�
� �
( , , ) ,
1
�
H i j l i j l( , , ) ( ) ( ) ( )� �{ + +� � � � � 0 äëÿ íåêîòîðûõ � � � �, , ,� 1 1, 0 0}.
Ñèìâîëè÷åñêàÿ çàïèñü � � �( ) ( )i j+ � 1 îçíà÷àåò, ÷òî ëèíåéíàÿ êîìáèíàöèÿ
óêàçàííûõ âåêòîðîâ ðàâíà âåêòîðó ðàçìåðíîñòè r kk , ó êîòîðîãî ëèøü îäíà èç
êîìïîíåíò îòëè÷íà îò íóëÿ. Èìååò ìåñòî ðàâåíñòâî
Q r Y r D E F D E F G D E F G H� �( ) ( )� �
P P P P{ } { } { } { }. (18)
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 3. Åñëè �m
r m
mq r qm�
1 1 1 0( ) ( ) äëÿ íåêîòîðîãî
m k�{ }2, ,� , òî c r3 0( ) � .
Ïóñòü �m m k� �0 2, , ,� . Åñëè r1 3� , òî
c r
q
r q
q
i
r i
i
i
3
2
2
1
1
1
1 1 1
( )
( ) ( )
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
�
k
� . (19)
Åñëè æå r1 3� , òî ñïðàâåäëèâû îöåíêè:
1
1
2
3
�
�
��
�
�
�� �
�
q
h r g r r c r r[ ( ) ( )] ( ) ( ) ( )( ) ( )� �low up 1
1
2
�
�
��
�
�
��q
h r( ), (20)
ãäå:
h r
w
w
C
w
q qm
r m
j
r j
j
m
m
k
j
r j
j m
k
m j j
( ) �
��
�
�� �1 2
21 1
�
�
�
� �
w
q
w
w
r m m C
j
r j
j
k
m
m m
m
k
j
2
1
1
2
2
1[( ) ( ) ] , (21)
g r
w
w
m m
q
C
m
qm
m
m
( ) ( ) ( ) min ,�
�
�
��
�
�
��
�
1
1
21 2
1
1
1
1
12
k
�
�
�
�
�
�
�
1
�
��w q
r i
w w
i C
f r
w
i
i jj k
j i
i
k
j
ij
1
2
32
1
21 1( ) ( )
( )
, i ji j k w2
�
�
�
�
�
�
�
�
�
�
�
�
, (22)
w q r q C qj
r j
j r j
j
j
�
1 1 1 12 2( ) ( ) ( ) , (23)
f r j i r i r j i i r j r i Cij i j j i i
( ) ( ) ( ) ( ) ( ) ( ) ( )�
1 1
1
2
C C i C i j i
i j i1
2
1
2
1
21 1 1( ) ( ) ( ) . (24)
Äîêàçàòåëüñòâî. Åñëè �m
r m
mq r qm�
1 1 1 0( ) ( ) äëÿ íåêîòîðîãî
m k�{ }2, ,� , òî ñóùåñòâóþò i j k, , , ,�{ }1 � i j� , òàêèå, ÷òî � � �( ) ( )i j+ � 0 äëÿ íå-
êîòîðîãî � �� 1, , 0 (ñì. äîêàçàòåëüñòâî òåîðåìû 2), ò.å. P { }E � 0 è Q r� ( ) � 0 .
Ñëåäîâàòåëüíî, c r3 0( ) � .
Ïðåäïîëîæèì, ÷òî �m m k� �0 2, , ,� . Îöåíèì â îòäåëüíîñòè êàæäîå èç ñëà-
ãàåìûõ, ñòîÿùèõ â ïðàâîé ÷àñòè ñîîòíîøåíèÿ (18). Îáîçíà÷èì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 75
� �i
i
r i r i
j j
ij j
q
C q j r i i
i i
( ) ( ) ( ) , ,( )� � �
�
P { }
1
1 0 1, ,� k, (25)
� � �i
i
i
l
j
ij j l j r i i k( ) ( ) ( ), , , ,( )� � �
�
�
�P{ } 1 0 1
0
� . (26)
Âû÷èñëåíèå âåðîÿòíîñòè P { }D E F . Îáîçíà÷èì:
U i m i mm
i m i� � � � � �
{ � � �( ) , , , , ( ) , ( ) , ,( ) ( ) ( )2 1 1 2 2 1� � , ,k}
m k�1, ,� ;
E E l kl
i j
i j l
� �
�
( , ) , , , ,
1
2 3 � .
Î÷åâèäíî, ÷òî
E E E Ek2 34 4 4 �� . (27)
Ïîñêîëüêó D F Um
m
k
�
�1
� è U Um l3 �5 ïðè m l1 , òî
P P P P{ } { } { } { }D E F E U U E Um
m
k
m m
m
k
� �
� �
� �
1 1
| ,
(28)
ãäå
P{ }Um m j
j
m
j
j m
k
�
�
�
� �� � �( ) ( ) ( )2 2 1
1
1
1
. (29)
Ó÷èòûâàÿ (27), èìååì
P P P{ } { } { }E U E U E E Um k m j j m
j
k
| ||� �
�
� 1
2
, (30)
ãäå E
1
ðàññìàòðèâàåì êàê äîñòîâåðíîå ñîáûòèå. Ñîáûòèå Um îçíà÷àåò, ÷òî
�( )( )m � 2 è �( )( )l � 2 ïðè l m� , ïîýòîìó
P { }E E Um m m| �1 1. (31)
Ïóñòü j m� . Òîãäà
P { }E E U
j q
q r j q C
j j m r j
j r j
j
j
|
( ) ( )
( ) ( )
�
1 1
1 1
1 1 2 21 2( ) ( )q
w
q
j
r j
j
j
�
�
, (32)
ãäå w j è � j ( )2 îïðåäåëÿþòñÿ ñîãëàñíî (23) è (26). Åñëè æå j m� , òî
P { }E E U
j q
q r j q q
j j m r j
j
j
rj j
|
( ) ( )
( ) ( )
�
�1 1
1 1
1 1
�
j
j� ( )1
. (33)
Åñëè r1 3� , òî P{ }U m km � �0 2, , , ,� à òàêæå D F �5, ïîýòîìó
c r Y r U E U3 1 1( ) ( ) |� �P P P{ } { } { }� .
Âîñïîëüçîâàâøèñü ñîîòíîøåíèÿìè (29), (30) è (33) ïðè m �1, ïîëó÷èì (19).
Ïðåäïîëîæèì, ÷òî r1 4� . Èç ôîðìóë (5), (28)–(33) íàõîäèì âåðîÿòíîñòü
P { }D E F
w
q
m j
j
m
j
j m
k
j
r j
jj
j
�
�
�
�
� �� � �
�
( ) ( ) ( )
( )
2 2 1
21
1
1 1
1
1 1 1
m
m
k
j
r j
jj m
k
q j
�
�
�� � �
�
� ( )
�
�
� �
�� �
( )
( )
q
N r
C w
r m j
j
m
m
k
j
j m
k
m
1 2
2
1
1
1 1
� (34)
(åñëè w j � 0 äëÿ íåêîòîðûõ j, òî â ôîðìóëå (34) èõ ñëåäóåò çàìåíèòü íóëÿìè).
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Âåðõíèå è íèæíèå îöåíêè âåðîÿòíîñòè P { }D E F G . Î÷åâèäíî, ÷òî
P P{ } { }D E F G D E F G Gi j
i j k
i j i j
i j
( , ) ( , ) ( , )
1 1
1 1 2 2
1 1
�
�
�
�
�
�
k
i j k
j j
,
,1 2 2
1 2
�
�
�
P { }D E F G G
i j i j
i j k
i j k
j j i
( , ) ( , )
,
,
,
1 1 2 2
1 1
2 2
1 2
1
1
1 2
1
�
�
� �
i
i j
i j k
D E F G D E F GP P{ } { }( , ) . (35)
Ïîñòðîèì âåðõíèå è íèæíèå îöåíêè äëÿ P { }D E F G i j( , ) . Îáîçíà÷èì
S l m m km
l� � � �{ } �( ) , , , , , ,( ) 3 1 1� � . Ïîñêîëüêó D F S k� , òî
P P P P{ } { } { } { }D E F G E S G S E S E Si j
k
i j
m m m m
m
( , ) ( , ) |� �
�
1 1 1
2
j
� �
1
�
�
P P{ } { }E S G E S E S E S Gj j
i j
j j m m m m
i j
m j
( , ) ( , )| |1 1 1 1
1
k
� . (36)
Î÷åâèäíî, ÷òî
P P P{ } { }E S E S E E Sm m m m
m
i
m
i j
m| ( )( ) ( , ) |
�
� � 1 1
1
1
13 � � m
�
�
0
0
!
"
0
#0
�1
�
� �
�m r m
m
r m
m q
q
w
q
m j
m m
( )
( ) ( )
, , ,2
1 1
1 1� (37)
(êàê è ðàíåå, wm çàìåíÿåì íóëåì, åñëè wm � 0 ). Àíàëîãè÷íî
P { }E S E S G
w
q
m j km m m m
i j m
r mm
| , , , .( , )
� �
1 1 1 � (38)
Ðàññìîòðèì ïîäðîáíee âåðîÿòíîñòü P { }E S G E Sj j
i j
j j
( , ) | 1 1 . Èìååì
P { }E S G E Sj j
i j
j j
( , ) | �1 1
= S G E S E S G E Sj
i j
j j j j
i j
j jP P{ } { }( , ) ( , )| | . 1 1 1 1
(39)
Ïðåäïîëîæèì, ÷òî ñèìâîëû � � �( ) ( ) ( )( , , , , , )i i
r i
i
i
� 1
0 0� � i-é ñòðî÷êè ôèêñè-
ðîâàíû. Ïîäñ÷èòàåì êîëè÷åñòâî âàðèàíòîâ ðàñïîëîæåíèÿ ñèìâîëîâ â j-é ñòðî÷êå,
áëàãîïðèÿòñòâóþùèõ ñîáûòèþ { } �( )( ) ( , )j i jG� 33 . Âîçìîæíû òðè ñëó÷àÿ.
Ñëó÷àé 1. � �( ) ( )( ) ( )j i s� � � 3. ×èñëî êîìáèíàöèé, áëàãîïðèÿòñòâóþùèõ
ñîáûòèþ G i j( , ) , ðàâíî s q q( ) ( ) 1 2 . Äåéñòâèòåëüíî, â j-é ñòðî÷êå íåíóëåâûå ñèì-
âîëû ìîæíî ðàçìåùàòü ëèøü íà òåõ æå ïîçèöèÿõ, ÷òî è â i-é ñòðî÷êå. Âûáåðåì
îäíó èç ýòèõ ïîçèöèé (s ñïîñîáîâ). Òîãäà � ( ) ( ) ( )i i ia b�
, ãäå âåêòîð a i( ) ïîëó÷à-
åòñÿ èç � ( )i îáíóëåíèåì âñåõ ïîçèöèé, çà èñêëþ÷åíèåì âûäåëåííîé; àíàëîãè÷íî
b i( ) ïîëó÷àåòñÿ èç � ( )i îáíóëåíèåì ëèøü âûäåëåííîé ïîçèöèè. Ñîáûòèå G i j( , ) ïðî-
èçîéäåò òîãäà è òîëüêî òîãäà, êîãäà âåêòîð � ( )j èìååò âèä � � �( ) ( ) ( ) ,j i ia b�
� � � �, , ,� 1, � �1 10 0, (( ) ( )q q 1 2 êîìáèíàöèé).
Ñëó÷àé 2. � �( ) ( )( ) ( )j i s � � �1 3. Ðàññóæäåíèÿ, àíàëîãè÷íûå ïðèâåäåííûì
âûøå, ïîçâîëÿþò ñäåëàòü âûâîä, ÷òî ÷èñëî êîìáèíàöèé, áëàãîïðèÿòñòâóþùèõ ñî-
áûòèþ G i j( , ) , ðàâíî ( ) ( )r j s qj 1 2 .
Ñëó÷àé 3. � �( ) ( )( ) ( )j i s
� � �1 4. ×èñëî ñîîòâåòñòâóþùèõ êîìáèíàöèé
ðàâíî s q( ) 1 . Çàìåòèì, ÷òî äàííûé ñëó÷àé âîçíèêàåò ëèøü ïðè s � 4.
Òàêèì îáðàçîì, îáùåå ÷èñëî êîìáèíàöèé íå ïðåâîñõîäèò ( ) ( )r j qj 1 2 . Ñëå-
äîâàòåëüíî,
P { }S G E S
r j q
q
j
i j
j j
j
r jj
( , ) |
( ) ( )
1 1
21
. (40)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 77
Åñëè æå îòáðîñèòü êîìáèíàöèè, ñîîòâåòñòâóþùèå ñëó÷àþ 3 ïðè s � 3, òî ïîëó-
÷èì îöåíêó ñíèçó
P { }S G E S
r j q q
q
j
i j
j j
j
r jj
( , ) |
( ) ( ) ( )
�
1 1
21 3 1
. (41)
 òî æå âðåìÿ
P P{ | } { | }
(( , ) ( , )E S G E S E E Sj j
i j
j j
l
j
l j
j j
�
��1 1
1
1
1 1
j q
q
r jj
1 1) ( )
. (42)
Îáúåäèíÿÿ ôîðìóëû (36)–(42), ïîëó÷àåì îöåíêó
( )
( )
( ,q
N r
w
w
r j
j
q
D E F Gm
m
k
j
j
i j
�
�
��
�
�
��
�
�
1 1 2
1
2
1
P { ) ( )
( )
}
�
�
q
N r
w
r j
w
m
m
k
j
j
1 2
1
. (43)
Ïðîñóììèðîâàâ ïî i è j i j k( )1
�
, áóäåì èìåòü
( )
( )
q
N r
w
j
w
r j
j
q
Dm
m
k
j
j
j
k
�
�
��
�
�
��
� �
� �
1 1 2
1
2
1 2
P { E F G i j
i j k
( , ) }
1
�
�
� �
� �
( )
( )
( )
q
N r
w
j
w
r jm
m
k
j
j
j
k1 12
1 2
. (44)
Äëÿ ïîäñ÷åòà ÷èñëà êîìáèíàöèé, áëàãîïðèÿòñòâóþùèõ ñîáûòèÿì G
i j( , )1 1 è
G
i j( , )2 2 , âîñïîëüçóåìñÿ îïèñàííûì âûøå ïîäõîäîì.  ðåçóëüòàòå ïîëó÷èì âåðõíèå
îöåíêè:
P { }D E F G G
i j i j
i j k
i j k
j j
( , ) ( , )
,
,
(1 1 2 2
1 1
2 2
1 2
1
1
�
�
�
�
q
r j
w
r j
w
w
q
j
j
j
j
m
r m
m
k
i j k
i
m
�
�
�
�1 4 1 2
11
1
1
1
2
21 1
2
)
,
�
�
�
j k
j j
2
1 2
,
�
�
�
� �
( )
( )
( ) ( )
q
N r
w i j
r i
w
r j
w
m
m
k
i
i
j
ji j k
1
1 1
4
1 2
; (45)
P { }D E F G G
i j i j
i j k
i j k
j j i
( , ) ( , )
,
,
,
1 1 2 2
1 1
2 2
1 2 1
1
1
�
�
� �
�
�
� �
�
i
i
i
j
j
m
r m
m
k
i j
q
r i
w
r j
w
w
q m
2
2
2
2
21 1
1 4 2 2
11
( )
k
i j k
j j i i
,
,
,
1 2 2
1 2 1 2
�
� �
�
�
�
�
� �
( )
( )
( )
q
N r
w i
r i
w
r j
w
m
m
k
i
i
j
ji j k
1
1
4
1 2
. (46)
Âåðõíèå è íèæíèå îöåíêè âåðîÿòíîñòè P { }D E F G H . Î÷åâèäíî, ÷òî
P P{ } { }D E F G H D E F H i j l
i j l k
� �
� ( , , )
1
, (47)
P P P P{ } { } { } { }D E F G H D E F H D E F G H D E F H i j l
i j l k
� �
� �
� ( , , )
1
� �
� �
P { }D E F H H
i j l i j l
i j l k
i j
( , , ) ( , , )
,
1 1 1 2 2 2
1 1 1
2 2
1
1 l k
l l
i j l i j l
i j l
D E F H H
2
1 2
1 1 1 2 2 2
1 1 11
�
� �
�
,
( , , ) ( , , )P { }
� �
� �
�
k
i j l k
l l j j
,
,
,
1 2 2 2
1 2 1 2
� �
� �
P { }DEF H H
i j l i j l
i j l k
i j
( , , ) ( , , )
,
1 1 1 2 2 2
1 1 1
2 2
1
1 l k
l l j j i i
i j i j l
DEF G H
2
1 2 1 2 1 2
1 1 2 2 2
� � �
�
,
, , ,
( , ) ( , , )P { }
1
1
1 1
2 2 2
�
� �
�
i j k
i j l k
,
. (48)
Ðàññìîòðèì âåðîÿòíîñòü P { }D E F H i j l( , , ) . Èñïîëüçóÿ ââåäåííûå âûøå îá-
îçíà÷åíèÿ, èìååì
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
P P P P{ } { } { } {D E F H E S H S E S E Si j l
k
i j l
m m m m
( , , ) ( , , ) |� � 1 1 1}
m
l
�
� �
2
1
� P P{ } { }E S H E S E S E S Hl l
i j l
l l m m m m
i j l
m
( , , ) ( , , )| |1 1 1 1
�
�
l
k
1
. (49)
Êàê è ðàíåå, âåðîÿòíîñòè P { }E S E S m lm m m m| , , �1 1 è P {E Sm m |
E S H m lm m
i j l
�1 1
( , , ) , ,} âû÷èñëÿþòñÿ ñîãëàñíî (37) è (38) (ñ çàìåíîé G i j( , ) íà
H i j l( , , ) ). Â òî æå âðåìÿ âåðîÿòíîñòü P { }E S H E Sl l
i j l
l l
( , , ) | 1 1 óäîâëåòâîðÿåò ñî-
îòíîøåíèþ
P P{ } { }E S H E S S H E Sl l
i j l
l l l
i j l
l l
( , , ) ( , , )| | � 1 1 1 1
P { }E S H E Sl l
i j l
l l
( , , ) | 1 1 . (50)
Ïðè ôèêñèðîâàííûõ � ( )i è � ( )j ñîáûòèå H i j l( , , ) áóäåò âûïîëíåíî òîãäà è òîëü-
êî òîãäà, êîãäà � � � � �( ) ( ) ( )l i j�
äëÿ íåêîòîðûõ � � �, , ,� 1, 0 � 1 0 . ×èñëî òà-
êèõ âàðèàíòîâ ðàâíî ( )q 1 2 . Ó÷èòûâàÿ, ÷òî ïðè ýòîì âîâñå íåîáÿçàòåëüíî ïðîèçîé-
äåò ñîáûòèå { } �( )( )l � 3 , ïîëó÷èì îöåíêó ñâåðõó
P { }S H E S
q
q
l
i j l
l l r ll
( , , ) |
( )
1 1
21
. (51)
 òî æå âðåìÿ ÷èñëî âàðèàíòîâ, êîãäà ìîæåò îêàçàòüñÿ, ÷òî �( )( )l
2 , íå ïðå-
âîñõîäèò 2 1( )q (êîýôôèöèåíò � îäíîçíà÷íî âûáèðàåòñÿ ïî � �, ( )i è � ( )j ; èñêëþ-
÷åíèå ñîñòàâëÿåò ñëó÷àé �( )( )i � 3 è �( )( )j � 3, êîãäà � ìîæåò ïðèíèìàòü äâà çíà-
÷åíèÿ). Ïîýòîìó èìååì îöåíêó ñíèçó
P { }S H E S
q q
q
l
i j l
l l r ll
( , , ) |
( ) ( )
�
1 1
21 2 1
. (52)
Äàëåå èìååì î÷åâèäíóþ îöåíêó
P P{ } { }E S H E S E E Sl l
i j l
l l
m l
l l
m
l
( , , ) ( , )| |
�
�1 1 1 1
1
1
�
( ) ( )l q
q
r ll
1 1
. (53)
Èç ôîðìóë (37), (38) è (49)–(53) îêîí÷àòåëüíî ïîëó÷àåì îöåíêó
( )
max , ( ,q
w
l
q
w
q
D E F H
l
m
r m
m
k
i j
m
�
�
!
"
#
�
�
1
0 1
1
1
2
1
P { , ) ( )l
l
m
r m
m
kq
w
w
q m
}
�
�
1 2
1
.
Ïðîñóììèðîâàâ ïî i, j è l i j l k( )1
� �
, èìååì
( )
( )
max ,
q
N r
w
C
w
l
q
m
m
k
l
ll
k
�
�
!
"
#
�
�
� �
1
0 1
1
1
2
1
1
2
3
P { }D E F H i j l
i j l k
( , , )
1
� �
�
� �
� �
( )
( )
q
N r
w
C
w
m
m
k
l
k
l
l
1 2
1 3
1
2
. (54)
Èñïîëüçóÿ îïèñàííûé âûøå ïîäõîä è ñîîòíîøåíèå (51), ïîëó÷àåì îöåíêè:
P { }D E F H H
i j l i j l
i j l k
i j l
( , , ) ( , , )
,
1 1 1 2 2 2
1 1 1
2 2
1
1
� �
� � 2
1 2
1 21 1 1
1 1
4
1 1
1
�
�
� �
� �
k
l l
m
m
k
l li j l k
q
N r
w
w w
,
,
( )
( )
i j l k
l l
2 2 2
1 2
� �
�
� �
,
�
�
�
� �
( )
( )
q
N r
w C C
w w
m
m
k
i j
i ji j k
1 1
4
1
1
2
1
2
3
; (55)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 79
P { }D E F H H
i j l i j l
i j l k
i j l
( , , ) ( , , )
,
1 1 1 2 2 2
1 1 1
2 2
1
1
� �
� � 2
1 2 1 2
2 11 1
1 1
4
1 1
� �
�
� �
� �
k
l l j j
m
m
k
j li j l
q
N r
w
w w
,
,
( )
( )
1
2 2 2
1 2 1 2
1
� �
� �
� �
k
i j l k
l l j j
,
,
,
�
�
�
� �
( )
( )
( )
q
N r
w i C
w w
m
m
k
i
i ji j k
1
1
1
4
1
1
2
3
; (56)
P { }D E F H H
i j l i j l
i j l k
i j l
( , , ) ( , , )
,
1 1 1 2 2 2
1 1 1
2 2
1
1
� �
� � 2
1 2 1 2 1 2
2 1
1 1
4
1 1
� � �
�
� �
k
l l j j i i
m
m
k
i li
q
N r
w
w w
,
, ,
( )
( )
1 1 1
2 2 2
1 2 1 2 1 2
1
� �
� �
� � �
� �
j l k
i j l k
l l j j i i
,
,
, ,
�
�
�
� �
( )
( )
( ) ( )
q
N r
w i j i
w w
m
m
k
i ji j k
1
1 1
1
4
1 2
. (57)
Àíàëîãè÷íî, èñïîëüçóÿ ñîîòíîøåíèÿ (40) è (51), ïîëó÷àåì îöåíêó
P P{ }DEF G H
i j i j l
i j k
i j l k
( , ) ( , , )
,
1 1 2 2 2
1 1
2 2 2
1
1
�
� �
�
{ }S G Hk
i j i j l
i j k
i j l k
j l
( , ) ( , , )
,
,
1 1 2 2 2
1 1
2 2 2
1
1
1
�
� �
1 2
�
�
� �
P { }S G Hk
i j i j l
i j k
i j l k
j
( , ) ( , , )
,
,
1 1 2 2 2
1 1
2 2 2
1
1
1
�
�
�
�
l i j
k
i j i j l
i j k
i
S G H
2 1 2
1 1 2 2 2
1 1
2
1
1
,
( , ) ( , , )
,
P { }
j l k
j l i j
2 2
1 2 1 2
�
� �
�
,
,
�
�
� �
�
( )
( ) ,
q
N r
w
r j
w w
m
m
k
j
j li j k
i j l
1 4
1
1
1
1
1
1 21 1
2 2 2
1
�
� �
�
�
k
j l
j
j ji j k
i j l k
j l
r j
w w
,
,
,
1 2
1
1 21 1
2 2 2
1 2
1
1
1
,
,
,
,i j
i
i li j k
i j l k
j l i
r i
w w
1 2
1
1 21 1
2 2 2
1 2
1
1
1
�
� �
�
�
1 2�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
j
�
� �
1
�
� ��
( )
( )
( )
,
q
N r
w
r i
w w
i Cm
m
k
j
j i
k
i
i ji
k
j
1
1
4
1 32
1
2
�
�
�
�
�
�
�
�
�
�
�
�
��
r j
w w
i i
r i
w w
C
j
i j
i
i j
i
i j ki j k
( )1
1
2
32
. (58)
Îáúåäèíÿÿ îöåíêè (34), (44)–(46) è (54)–(58), ïîëó÷àåì ðåçóëüòèðóþùóþ
îöåíêó (20).
Òåîðåìà äîêàçàíà.
ÎÃÐÀÍÈ×ÅÍÍÎÑÒÜ ÎÒÍÎÑÈÒÅËÜÍÎÉ ÑÐÅÄÍÅÊÂÀÄÐÀÒÈ×ÅÑÊÎÉ
ÏÎÃÐÅØÍÎÑÒÈ ÎÖÅÍÎÊ
Îäíèì èç âàæíåéøèõ ñâîéñòâ, îïðåäåëÿþùèõ âûñîêóþ òî÷íîñòü (óñòîé÷èâîñòü)
ìåòîäà Ìîíòå-Êàðëî, ïðèíÿòî ñ÷èòàòü îãðàíè÷åííîñòü îòíîñèòåëüíîé ñðåäíåê-
âàäðàòè÷åñêîé ïîãðåøíîñòè (ÎÑÊÏ) îöåíîê ïðè èçìåíåíèè òåõ èëè èíûõ ïàðà-
ìåòðîâ ñèñòåìû. ÎÑÊÏ îïðåäåëÿåòñÿ êàê îòíîøåíèå êîðíÿ îò äèñïåðñèè îöåíêè
ê åå ìàòåìàòè÷åñêîìó îæèäàíèþ. Êîëè÷åñòâî ðåàëèçàöèé, òðåáóåìûõ äëÿ äîñòè-
æåíèÿ çàäàííûõ îòíîñèòåëüíîé ïîãðåøíîñòè è äîñòîâåðíîñòè îöåíêè, ïðîïîðöè-
îíàëüíî êâàäðàòó ÎÑÊÏ. Ñëåäóþùàÿ òåîðåìà óñòàíàâëèâàåò îãðàíè÷åííîñòü
ÎÑÊÏ îöåíîê � ( ), , ,� � �� �1 2 � ( ) ( )( ) ( )� � � �
3 3
low low� Z è � ( ) ( )( ) ( )� � � �
3 3
up up� Z
ïðè q �� , ò.å. ñ ðîñòîì ÷èñëà ýëåìåíòîâ ïîëÿ Ãàëóà.
80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 81
Òåîðåìà 4. ÎÑÊÏ K
D
M
K
D
M
�
�
�
� �
� �
�
� �
�
� � �
� ( )
� ( )
, , ,
� ( )
�
( )
( )
(
1 2
3
3
3
low
low
low) ( )
,
�
K
D
M
3
3
3
( )
( )
( )
� ( )
� ( )
up
up
up
�
� �
� �
ðàâíîìåðíî îãðàíè÷åíû ïî q.
Äîêàçàòåëüñòâî. Ïîñêîëüêó r i ri � 1 1äëÿ ëþáîãî i, òî èç ñîîòíîøåíèÿ (9) ñëåäóåò, ÷òî
1 1
c r k( ) ðàâíîìåðíî ïî L è r. Ñëåäîâàòåëüíî, M c1 1( )� � è M M[ ( )] ( )c k c1
2
1� �
, ò.å.
K k1 1
(ïðè ýòîì ó÷èòûâàåòñÿ, ÷òî Z1 ÿâëÿåòñÿ êîíñòàíòîé).
Ðàññìîòðèì ñëó÷àé � � 2 . Äëÿ äîêàçàòåëüñòâà ðàâíîìåðíîé îãðàíè÷åííîñòè
ÎÑÊÏ ïî q äîñòàòî÷íî äîêàçàòü îãðàíè÷åííîñòü ÎÑÊÏ ïðè q ��. Ïîñòðîèì âåð-
õíèå è íèæíèå îöåíêè äëÿ êîýôôèöèåíòà c r2 ( ) . Åñëè r1 2� , òî èç (10) ñëåäóåò, ÷òî
q
q
c r
k
�
�
��
�
�
��
1
12 ( ) . (59)
Ïóñòü òåïåðü r1 3� . Ýòî îçíà÷àåò, ÷òî r mm �
2 äëÿ ëþáîãî m k�{ }2, ,� . Ïîý-
òîìó ïðè áîëüøèõ çíà÷åíèÿõ q ñëó÷àé �m
0 èñêëþ÷àåòñÿ (ôîðìóëà (11) äëÿ
c r2 ( )). Âîñïîëüçîâàâøèñü òåì, ÷òî r i ri � 1 1, èç ôîðìóëû (12) èìååì îöåíêè
c r r k n
i
k
i2
1
1( ) ( )
�
� . (60)
 òî æå âðåìÿ
c r r
r
q
r
q
i
r i r
i
k
i
2 1 1
2
11
1
1 2
1
( ) ~
��
�
� �� . (61)
Èç (59)–(61) ñëåäóåò, ÷òî K 2 àñèìïòîòè÷åñêè ïðè q �� íå ïðåâîñõîäèò
k n 1, ÷òî ñâèäåòåëüñòâóåò î ðàâíîìåðíîé îãðàíè÷åííîñòè K 2 .
Ðàññìîòðèì ñëó÷àé � � 3. Åñëè r1 3� , òî èç (19) ñëåäóåò, ÷òî
c r r r
q
3 1( ) ( ) ( ) ~( ) ( )� �
��
� �low up (62)
ðàâíîìåðíî ïî { }r ii , � 2 . Ïðåäïîëîæèì, ÷òî r1 4� . Èç ôîðìóëû (21) ñ ó÷åòîì
(23) è (24) èìååì
h r C
q
C r m m
q r r m r
m
k
r m m
m m
( ) ~ [ ( ) ( )
��
�
�
1 1
1
2
1
2
21
1
C
m 1
2 ] . (63)
 òî æå âðåìÿ èç (22) ñëåäóåò, ÷òî
g r
q q
m m C m
q r m r m
m
k
m
( ) ~ [( ) ( ) ( )]
��
�
�1 1
1 2 1
1 1 1
2
2
�
1
� �
( ) ( )
,
r i i
q
C
q
i
r i r
i
k
j
r j
j k
j i
i j
1
1 1
2
1
2
2
3
1
1 1
2
1
2
1q
f r
q
r i r
i
k
ij
r j
j i
k
i j
�
�
� �
( )
. (64)
Ïîñêîëüêó r1 4� , òî r jj �
3. Èç ñðàâíåíèÿ ôîðìóë (63) è (64) ñëåäóåò, ÷òî
g r
h r q
( )
( )
�
��
0 (65)
ðàâíîìåðíî îòíîñèòåëüíî r. Ôîðìóëû (62)–(65) ïîçâîëÿþò ñäåëàòü âûâîä î ðàâ-
íîìåðíîé îãðàíè÷åííîñòè ÎÑÊÏ K
3
( )low è K
3
( )up .
Òåîðåìà äîêàçàíà.
×ÈÑËÅÍÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Íà ÷èñëåííûõ ïðèìåðàõ ïðîèëëþñòðèðóåì âûñîêóþ òî÷íîñòü îöåíîê, ïîëó÷àå-
ìûõ ïðåäëîæåííûì ìåòîäîì. Âñå ïðèâåäåííûå íèæå îöåíêè ïîñòðîåíû ñ îòíî-
ñèòåëüíîé ïîãðåøíîñòüþ 1% è äîñòîâåðíîñòüþ 0,99. Ââåäåì ñëåäóþùèå îáîçíà-
÷åíèÿ:
$ � ( , ), ,
�� n k �1 2 , — íåñìåùåííàÿ îöåíêà äëÿ n
k
��
��
�
��
, ïîñòðîåííàÿ ñ óêàçàí-
íûìè âûøå îòíîñèòåëüíîé ïîãðåøíîñòüþ è äîñòîâåðíîñòüþ;
$ � ( , )( )
3
low n k è � ( , )( )
3
low n k — âåðõíèå è íèæíèå îöåíêè äëÿ n
k
3�
��
�
��
;
$ � ( , )N n k� — êîëè÷åñòâî ðåàëèçàöèé, èñïîëüçîâàííûõ äëÿ ïîñòðîåíèÿ ñîîòâå-
òñòâóþùèõ îöåíîê.
 òàáë. 1 ïðè q � 28 è n k� 2 ïðîâåäåíî ñðàâíåíèå îöåíîê � ( , ), ,
�� n k �1 2 ,
ñ ñîîòâåòñòâóþùèìè òî÷íûìè çíà÷åíèÿìè n
k
��
��
�
��
, � �1 2, , à òàêæå óêàçàíû âåðõíèå
è íèæíèå îöåíêè � ( , )( )
3
low n k , � ( , )( )
3
up n k äëÿ ÷èñëà n
k
3�
��
�
��
ïîäïðîñòðàíñòâ âåñà
� � 3 , òî÷íîå çíà÷åíèå êîòîðîãî íåèçâåñòíî. Êðîìå òîãî, èññëåäóåòñÿ èçìåíåíèå
êîëè÷åñòâà çàòðà÷åííûõ ðåàëèçàöèé ïðè óâåëè÷åíèè k.
Ñðàâíåíèå òî÷íûõ çíà÷åíèé ñ îöåíêàìè, ïîëó÷åííûìè ìîäåëèðîâàíèåì �� �1 2, ),
ñâèäåòåëüñòâóåò î âûñîêîé òî÷íîñòè ïðåäëîæåííîãî ìåòîäà.  ÷àñòíîñòè, ëåãêî óáå-
äèòüñÿ, ÷òî âî âñåõ ðàññìîòðåííûõ ñëó÷àÿõ òî÷íûå çíà÷åíèÿ ïîïàäàþò â ñîîòâåòñòâóþ-
ùèå îäíîïðîöåíòíûå äîâåðèòåëüíûå èíòåðâàëû. Ñëåäóåò òàêæå îòìåòèòü, ÷òî â øèðî-
êîì äèàïàçîíå èçìåíåíèÿ n äîñòèãàåòñÿ âåñüìà âûñîêàÿ òî÷íîñòü íèæíèõ è âåðõíèõ îöå-
íîê � ( , )( )
3
low n k è � ( , )( )
3
up n k .  êà÷åñòâå äîâåðèòåëüíîãî èíòåðâàëà äëÿ n
k
3�
��
�
��
ìîæíî
âûáðàòü ( , � ( , ), , � ( , ))( ) ( )0 99 101
3 3
low upn k n k . Ñ óâåëè÷åíèåì k íàáëþäàåòñÿ ðîñò ÷èñëà
� ( , )N n k� òðåáóåìûõ ðåàëèçàöèé, êîòîðûé áëèçîê ê ëèíåéíîìó.
82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
k �
n
k ��
��
�
��
� ( , )n k � ( , )
( )
3
low
n k � ( , )
( )
3
up
n k � ( , )N n k�
5
1 1,467 61049 1,468 61049 — — 52 763
2 1,684 61052 1,693 61052 — — 137 580
3 — — 1,140 61055 1,144 61055 156 635
10
1 1,107 610218 1,113 610218 — — 133 640
2 2,683 610221 2,685 610221 — — 323 360
3 — — 4,088 610224 4,110 610224 410 320
20
1 5,432 610916 5,450 610916 — — 297 924
2 2,701 610920 2,695 610920 — — 695 847
3 — — 8,649 610923 8,725 610923 916 882
30
1 8,884 6102096 8,915 6102096 — — 462 765
2 6,683 6102100 6,681 6102100 — — 1 066 495
3 — — 3,257 6102104 3,298 6102104 1 421 617
40
1 5,743 6103758 5,735 6103758 — — 627 701
2 5,785 6103762 5,792 6103762 — — 1 436 501
3 — — 3,776 6103766 3,837 6103766 1 927 766
50
1 1,547 6105902 1,539 6105902 — — 792 678
2 1,953 6105906 1,964 6105906 — — 1 802 621
3 — — 1,596 6105910 1,628 6105910 2 433 320
Ò à á ë è ö à 1
 òàáë. 2 èññëåäóåòñÿ òî÷íîñòü îöåíîê ñ ðîñòîì q mm� �2 1 22 , , , � . Ðàññìàò-
ðèâàåòñÿ ñëó÷àé n k� �60 30, .
Ïðèâåäåííûå â òàáë. 2 äàííûå íå òîëüêî ïîäòâåðæäàþò âûñîêóþ òî÷íîñòü íåñìå-
ùåííûõ îöåíîê (� �1 2, ), ïîñòðîåííûõ ïðè ðàçëè÷íûõ çíà÷åíèÿõ q, íî è íàãëÿäíî äå-
ìîíñòðèðóþò âîçðàñòàíèå òî÷íîñòè íèæíèõ è âåðõíèõ îöåíîê äëÿ n
k
3�
��
�
��
ñ ðîñòîì q.
Òàê, åñëè ïðè q � 4 ó îöåíîê � ( , )( )
3
low n k è � ( , )( )
3
up n k ñîâïàäàåò ïåðâàÿ çíà÷à-
ùàÿ öèôðà (÷òî óæå ÿâëÿåòñÿ âûñîêîé òî÷íîñòüþ ðàñ÷åòà), òî ïðè q � 4 096 ñîâïàäà-
þò òðè çíà÷àùèå öèôðû. Çàìåòèì, ÷òî ïðè êàæäîì � ñ ðîñòîì q êîëè÷åñòâî ðåàëè-
çàöèé îñòàåòñÿ ïðèìåðíî îäíèì è òåì æå, ÷òî âïîëíå ñîãëàñóåòñÿ ñ óòâåðæäåíèåì
òåîðåìû 4 îá îãðàíè÷åííîñòè ÎÑÊÏ ñ ðîñòîì q.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ý í ä ð þ ñ Ã . Òåîðèÿ ðàçáèåíèé. — Ì.: Íàóêà, 1982. — 256 ñ.
2. Ì à ê - Â à ë ü ð à ñ Ô . Ä æ . , Ñ ë î ý í Í . Ä æ . Òåîðèÿ êîäîâ, èñïðàâëÿþùèõ îøèáêè. — Ì.: Ñâÿçü,
1979. — 744 ñ.
3. M a s o l V . V . Investigation of linear codes possessing some extra properties // Cryptography and Coding.
— 2001. — P. 301–306.
4. Ì à ñ î ë  . È . Íåêîòîðûå ïðèìåíåíèÿ àëãîðèòìîâ ïîñòðîåíèÿ ïîäïðîñòðàíñòâ íàä êîíå÷íûì ïîëåì
// Óêð. ìàò. æóðí. — 1989. — 41, ¹ 8. — Ñ. 1146–1148.
5. Ì à ñ î ë  . È . Àñèìïòîòèêà ÷èñëà íåêîòîðûõ k-ìåðíûõ ïîäïðîñòðàíñòâ íàä êîíå÷íûì ïîëåì //
Ìàòåì. çàìåòêè. — 1996. — 59, âûï. 5. — Ñ. 729–736.
6. Ê î â à ë å í ê î È . Í . Èññëåäîâàíèÿ ïî àíàëèçó íàäåæíîñòè ñëîæíûõ ñèñòåì. — Êèåâ: Íàóê. äóìêà,
1975. — 210 ñ.
7. Ê î â à ë å í ê î È . Í . Àíàëèç ðåäêèõ ñîáûòèé ïðè îöåíêå ýôôåêòèâíîñòè è íàäåæíîñòè ñèñòåì. —
Ì.: Ñîâ. ðàäèî, 1980. — 209 ñ.
8. K o v a l e n k o I . N . , K u z n e t s o v N . Y u . , P e g g P h . A . Mathematical theory of reliability of time
dependent systems with practical applications. — Chichester: Wiley, 1997. — 303 p.
9. C a l a b i E . , W i l f H . On the sequential and random selection of subspaces over a finite field //
J. Combin. Theory. — Ser. A. — 1977. — 22, N 1. — P. 107–109.
Ïîñòóïèëà 01.02.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 83
q �
n
k ��
��
�
��
� ( , )
� n k � ( , )
( )
3
low
n k � ( , )
( )
3
up
n k � ( , )N n k�
4
1 5,400 610525 5,412 610525 — — 342 401
2 4,779 610527 4,782 610527 — — 789 777
3 — — 2,181 610529 2,777 610529 1 049 452
16
1 2,468 6101049 2,465 6101049 — — 433 549
2 1,092 6101052 1,091 6101052 — — 1 001 480
3 — — 2,736 6101054 3,166 6101054 1 335 009
64
1 1,451 6101573 1,442 6101573 — — 456 816
2 2,697 6101576 2,689 6101576 — — 1 055 104
3 — — 3,103 6101579 3,267 6101579 1 411 798
256
1 8,884 6102096 8,915 6102096 — — 462 765
2 6,683 6102100 6,681 6102100 — — 1 066 495
3 — — 3,257 6102104 3,298 6102104 1 421 617
1 024
1 5,490 6102620 5,477 6102620 — — 464 212
2 1,657 6102625 1,662 6102625 — — 1 067 278
3 — — 3,272 6102629 3,283 6102629 1 425 224
4 096
1 3,399 6103144 3,392 6103144 — — 464 576
2 4,107 6103149 4,120 6103149 — — 1 067 970
3 — — 3,255 6103154 3,258 6103154 1 426 069
Ò à á ë è ö à 2
|
| id | nasplib_isofts_kiev_ua-123456789-45197 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:35:17Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Масол, В.И. Кузнецов, И.Н. 2013-06-08T17:54:37Z 2013-06-08T17:54:37Z 2010 Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем / В.И. Масол, И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 3. — С. 69-83. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45197 519.12 Запропоновано метод прискореного моделювання для обчислення кількості k-вимірних підпросторів ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Для ω=1 та ω=2 будуються незміщені оцінки, а для ω=3 — верхні та нижні оцінки. Доведено обмеженість відносної середньоквадратичної похибки оцінок при q → ∞. Високу точність методу ілюструють чисельні приклади. A fast simulation method for the evaluation of the number of k-measurable subspaces of the weight ω of n-measurable vector+ space over the Galois field containing q components is proposed. The unbiased estimates are constructed for the cases ω=1 and ω=2, and lower and upper estimates are proposed for the case ω=3. It is proved that relative error remains bounded as q → ∞. High accuracy of the method proposed is demonstrated on numerical examples. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем Застосування прискореного моделювання для оцінки кількості деяких k-вимірних підпросторів над скінченним полем Application of the fast simulation method to the evaluation of the number of some k-measurable subspaces over a finite space Article published earlier |
| spellingShingle | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем Масол, В.И. Кузнецов, И.Н. Кибернетика |
| title | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| title_alt | Застосування прискореного моделювання для оцінки кількості деяких k-вимірних підпросторів над скінченним полем Application of the fast simulation method to the evaluation of the number of some k-measurable subspaces over a finite space |
| title_full | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| title_fullStr | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| title_full_unstemmed | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| title_short | Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| title_sort | применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45197 |
| work_keys_str_mv | AT masolvi primenenieuskorennogomodelirovaniâkocenkekoličestvanekotoryhkmernyhpodprostranstvnadkonečnympolem AT kuznecovin primenenieuskorennogomodelirovaniâkocenkekoličestvanekotoryhkmernyhpodprostranstvnadkonečnympolem AT masolvi zastosuvannâpriskorenogomodelûvannâdlâocínkikílʹkostídeâkihkvimírnihpídprostorívnadskínčennimpolem AT kuznecovin zastosuvannâpriskorenogomodelûvannâdlâocínkikílʹkostídeâkihkvimírnihpídprostorívnadskínčennimpolem AT masolvi applicationofthefastsimulationmethodtotheevaluationofthenumberofsomekmeasurablesubspacesoverafinitespace AT kuznecovin applicationofthefastsimulationmethodtotheevaluationofthenumberofsomekmeasurablesubspacesoverafinitespace |