Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений
Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45210 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45210 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-452102013-06-09T03:09:29Z Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений Ендовицкий, П.А. Краткие сообщения Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення двох однакових комплектів частинок по чарунках. Отримані результати можна застосувати у криптографії для оцінювання трудомісткості побудови колізій хеш-функцій. Proved two theorems about asymptotic behavior group size in birthday paradox. Theorem 1 gives asymptotically best possible estimates for group size in case uniform and independent particle occupancy in cells. Theorem 2 gives asymptotically best possible estimates for group size in case uniform and independent occupancy of two equal sets of particles in cells. These results one may apply in cryptography for estimation working time for construction collisions of hash-functions. 2010 Article Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45210 519.2 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Краткие сообщения Краткие сообщения |
| spellingShingle |
Краткие сообщения Краткие сообщения Ендовицкий, П.А. Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений Кибернетика и системный анализ |
| description |
Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення двох однакових комплектів частинок по чарунках. Отримані результати можна застосувати у криптографії для оцінювання трудомісткості побудови колізій хеш-функцій. |
| format |
Article |
| author |
Ендовицкий, П.А. |
| author_facet |
Ендовицкий, П.А. |
| author_sort |
Ендовицкий, П.А. |
| title |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_short |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_full |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_fullStr |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_full_unstemmed |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_sort |
уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Краткие сообщения |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45210 |
| citation_txt |
Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT endovickijpa utočnenieasimptotičeskojapproksimaciirazmeragruppyvparadoksednejroždenij |
| first_indexed |
2025-07-04T03:50:31Z |
| last_indexed |
2025-07-04T03:50:31Z |
| _version_ |
1836686803471433728 |
| fulltext |
ÓÄÊ 519.2
Ï.À. ÅÍÄÎÂÈÖÊÈÉ
ÓÒÎ×ÍÅÍÈÅ ÀÑÈÌÏÒÎÒÈ×ÅÑÊÎÉ ÀÏÏÐÎÊÑÈÌÀÖÈÈ
ÐÀÇÌÅÐÀ ÃÐÓÏÏÛ Â ÏÀÐÀÄÎÊÑÅ ÄÍÅÉ ÐÎÆÄÅÍÈÉ
Êëþ÷åâûå ñëîâà: ñëó÷àéíîå ðàçìåùåíèå, ïàðàäîêñ äíåé ðîæäåíèé, àñèìïòîòè÷åñêèå íå-
ðàâåíñòâà, ôîðìóëà Ñòèðëèíãà äëÿ ãàììà-ôóíêöèè, ìåòîä êîëëèçèé äëÿ õýø-ôóíêöèé.
Ïàðàäîêñ äíåé ðîæäåíèé ñîñòîèò â ñëåäóþùåì [1, 2]. Ïóñòü ñóùåñòâóåò ãðóïïà èç n ëþ-
äåé (n � 365 ). Áóäåì ñ÷èòàòü, ÷òî äåíü ðîæäåíèÿ êàæäîãî ÷åëîâåêà èç ãðóïïû ïðèõîäèòñÿ
ñ ðàâíîé âåðîÿòíîñòüþ íà îäèí èç 365 äíåé. Òîãäà âåðîÿòíîñòü òîãî, ÷òî â ãðóïïå íàé-
äóòñÿ õîòÿ áû äâà ÷åëîâåêà, äíè ðîæäåíèé êîòîðûõ ñîâïàäàþò, ðàâíà
P n
nn
n n
( )
( ) ( )
� � � �
� � � � �
1
365
365
1
365 364 365 1
365
�
.
Ðàçìåð ãðóïïû, ãäå ñ âåðîÿòíîñòüþ p � 1 íàéäóòñÿ ïî êðàéíåé ìåðå äâà ÷åëîâåêà ñ ñîâ-
ïàäàþùèìè äíÿìè ðîæäåíèÿ, ðàâåí 366, à äëÿ p � 1 îí ãîðàçäî ìåíüøå: P( ) , ...23 0 507� ,
P( ) , ...57 0 990� è ò.ä. (ò.å. â ãðóïïå èç 23 ÷åëîâåê ñ âåðîÿòíîñòüþ, áîëüøåé
1
2
, íàéäóòñÿ äâà
÷åëîâåêà ñ ñîâïàäàþùèìè äíÿìè ðîæäåíèÿ). Ïàðàäîêñ ñîñòîèò â êàæóùåìñÿ ïðîòèâîðå÷èè ñ
ìàëûì ðàçìåðîì ãðóïïû ïðè çàäàííîì p � ( ; )0 1 . Ïîäðîáíåå ñì. â [2].
Îöåíêè âåðîÿòíîñòåé è ðàçìåðà ãðóïïû â çàäà÷å î äíÿõ ðîæäåíèÿ èìåþò âàæíûå ïðè-
ìåíåíèÿ ïðè àóòåíòèôèêàöèè, ïîñòðîåíèè õýø-ôóíêöèé, â êîäèðîâàíèè, â êðèïòîàíàëèçå,
ïðè ðåøåíèè ñèñòåì óðàâíåíèé íàä êîíå÷íûìè àëãåáðàè÷åñêèìè ñòðóêòóðàìè.
1. Ñôîðìóëèðóåì çàäà÷ó î ðàçìåðå ãðóïïû â ïàðàäîêñå äíåé ðîæäåíèé â îáùåì ñëó÷àå
(â òåðìèíàõ ðàçìåùåíèÿ ÷àñòèö ïî ÿ÷åéêàì). Ïóñòü çàäàíû ÷èñëà m N� , p � ( ; )0 1 , m — ÷èñ-
ëî ÿ÷ååê, â ïàðàäîêñå m � 365. Ïóñòü òàêæå P nm( ) — âåðîÿòíîñòü, ÷òî ïðè ðàçìåùåíèè n ÷àñ-
òèö ïî m ÿ÷åéêàì ïî êðàéíåé ìåðå äâå ÷àñòèöû ïîïàäóò â îäíó ÿ÷åéêó (ñ÷èòàåì, ÷òî êàæäàÿ
÷àñòèöà ðàçìåùàåòñÿ íåçàâèñèìî îò äðóãèõ è ðàâíîâåðîÿòíî ïî m ÿ÷åéêàì):
P n
m
m
m m m n
m
Q n n mm
n
n n m( )
( ) ( ) ( )
( ), ,� � � �
� � � � � �
� �1 1
1 1
1 0
�
� 1, (1)
ãäå Q n P nm m( ) ( )� �1 — âåðîÿòíîñòü, ÷òî âñå ÷àñòèöû ïîïàäóò â ðàçíûå ÿ÷åéêè, òîãäà
P n( )
âîçðàñòàåò ïî n ïðè ôèêñèðîâàííîì m, P P( ) ( )0 1 0� � , P m( )� �1 1 (äëÿ óïðîùåíèÿ
çàïèñè âìåñòî P nm( ) áóäåì ïèñàòü P n( )).
Îïðåäåëèì íàòóðàëüíîå ÷èñëî n n m m� � �( ) [ ; ]1 1 , êîòîðîå çàâèñèò îò m è p, èç ñëåäó-
þùåãî óñëîâèÿ:
P n p P n( ) ( )� � �1 , (2)
ò.å. n m( ) — ìèíèìàëüíîå ÷èñëî n ÷àñòèö òàêîå, ÷òî ïðè ðàçìåùåíèè n ÷àñòèö â m
ÿ÷åéêàõ âåðîÿòíîñòü ïîïàäàíèÿ ïî êðàéíåé ìåðå äâóõ ÷àñòèö â îäíó ÿ÷åéêó íå ìåíü-
øå p. Íàïðèìåð, åñëè p �
1
2
, m � 365, òî n( )365 23� , òàê êàê P P( ) ( )22
1
2
23� � .
Ðàññìîòðèì âîïðîñ îá àñèìïòîòè÷åñêîì ïîâåäåíèè n m( ) . Õîðîøî èçâåñòåí ñëåäóþ-
ùèé ðåçóëüòàò (ñì., íàïðèìåð, [2]):
n m am o m( ) ( )� �2 , m � � ,
ãäå a p� � �
ln ( )1 0 .
Öåëü äàííîé ñòàòüè — äîêàçàòü òåîðåìó 1, êîòîðàÿ ñóùåñòâåííî óñèëèâàåò ýòîò ðå-
çóëüòàò.
Òåîðåìà 1. Ïóñòü p � ( ; )0 1 ôèêñèðîâàíî, a p� � �ln ( )1 , òîãäà n m( ) � �2am m� ( ) ,
ãäå ïîñëåäîâàòåëüíîñòü { }� ( ),m m � 1 îãðàíè÷åíà è lim ( )
m
m
��
� � �
1
2 3
a
, lim ( )
m
m
a
��
� ��
3
2 3
.
Äîêàçàòåëüñòâî. Äëÿ òîãî ÷òîáû âîñïîëüçîâàòüñÿ èçâåñòíûìè ðåçóëüòàòàìè î ñâîéñò-
âàõ ãàììà-ôóíêöèè �( )x [3], áóäåì ñ÷èòàòü, ÷òî ÷èñëà n, m èç (1) ìîãóò ìåíÿòüñÿ íåïðåðûâ-
íî. Ïóñòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 185
© Ï.À. Åíäîâèöêèé, 2010
Q x
y
y x y
y x yy x
( )
( )
( )
, ,�
�
� �
� � �
�
�
1
1
0 0 1. (3)
Î÷åâèäíî, ÷òî ïðè íàòóðàëüíûõ x , y â (3) ïîëó÷àåì Q nm( ) èç ôîðìóëû (1).
Îïðåäåëèì õàðàêòåð ìîíîòîííîñòè Q xy ( ) ïðè ôèêñèðîâàííîì y
Q x
y
y x y
t y x
t y
y
t y
y x y
( )
( )
( )
( )
( )
�
�
� �
�
� � �
� � �
�
��
�
�
�
1
1
1
0 1
1
� � �
�
�
1 1
1
t y
y
f t y
�( )
( )
,
ãäå
f t
t
y y
u e du e d
t t
t u t y( )
( )
� � �� �
�
� �
�
� �
� 1 1
0
1
0
� �� .
Ïðè ýòîì f t e dt y' ( ) ln� �
�
� � � �� �1
0
, �
f t( ) , òàê êàê �� �
�
� �
�f t e dt y( ) ln
0
1 2 0� � �� , äèôôå-
ðåíöèðîâàíèå ïîä çíàêîì èíòåãðàëà âîçìîæíî ïî ïðèçíàêó Ëåéáíèöà [3], òàêæå
f y
y
y
y
y
f y
y y
( )
( ) ( )
( )� �
�
� �
�
� � 1
1
1
, ò.å. ïî òåîðåìå Ðîëëÿ � � � �y y y f y0 01 0( , ) : ( )' .
Îòñþäà è èç âîçðàñòàíèÿ f t' ( ) ñëåäóåò, ÷òî f t( ) ïðè t y� ( ; ]0 0 óáûâàåò è ïðè
t y y� �( ; ]0 1 âîçðàñòàåò. Îòñþäà � �z0 0 1( , ) òàêîå, ÷òî Qy ( )� ïðè x z�[ ; ]0 0 âîçðàñòàåò è ïðè
x z y� �[ ; ]0 1 óáûâàåò, ò.å. Qy ( )� óáûâàåò ïðè x y� �[ ; ]1 1 (òàê êàê z0 1� ), íî Qy ( )1 1� ,
Q yy ( )� � �1 0 0 . Çíà÷èò, ââèäó íåïðåðûâíîñòè Qy ( )� äëÿ çàäàííîãî p � ( ; )0 1
� � �! ( ) ( ; )x y y1 1 òàêîå, ÷òî Q x y py ( ( )) � �1 .
Ôóíêöèÿ x y( ) åñòü íåïðåðûâíîå ðàñïðîñòðàíåíèå ïîñëåäîâàòåëüíîñòè {n m m( ), }� 1 èç
(2) äëÿ äåéñòâèòåëüíûõ x y,
0 .
Èññëåäóåì àñèìïòîòè÷åñêîå ïîâåäåíèå x y( ) ïðè y� � � (ýòî â äàëüíåéøåì äàñò âîç-
ìîæíîñòü îïðåäåëèòü àñèìïòîòè÷åñêîå ïîâåäåíèå n m( ) , m � 1). Äëÿ ýòîãî äîêàæåì òðè ëåì-
ìû è ââåäåì îáîçíà÷åíèå x y x y1 1( ) ( )� � äëÿ óïðîùåíèÿ çàïèñè íåêîòîðûõ ôîðìóë.
Ëåììà 1. Ôóíêöèÿ x y( ) � � � ïðè y� � � .
Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî x y( ) âîçðàñòàåò. Äëÿ ýòîãî äîñòàòî÷íî óáåäèòüñÿ, ÷òî
�
b 0 ôóíêöèÿ g y
y
y b yb
( )
( )
( )
�
�
�
�
âîçðàñòàåò ïðè y b
. Ïîêàæåì, ÷òî [ln ( )]g y '
0 , ò.å.
ln ( )g y âîçðàñòàåò
[ln ( )] [ln ( ) ln ( ) ln ]
( )
( )
(
g y y y b b y
y
y
y b
' '� � � � �
�
�
� �
� �
�
�
� )
( )� y b
b
y�
� ,
íî
�
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
( )
( )
a
a a
C
n n an
1 1 1
1
, ãäå C — êîíñòàíòà Ýéëåðà [3].
Îòñþäà
[ln ( )]g y
y y b
b
y n n y n n y b
' � � �
�
� � �
�
�
�
��
�
�
�� � �
� �
�
�
�
1 1 1 1 1 1
�
�
�
�� �
�
�
�
�
��
nn 11
�
� � �
�
��
�
�
b
n c n b c
b
b cn ( )( )0
,
ãäå c y b� �
0 . Íî
b
n c n b c
b
dx
x c x b c
b
c
b
c
b
c
( )( ) ( )( )
ln
� � �
� � �
� �
�
�
�
�
�
�
�
1
10
�
�
�
�� �
�n
b
b c0
,
ïîñêîëüêó ln ( )1
1
�
�
t
t
t
ïðè t
0 . Îòñþäà [ln ( )]g y '
0 , ò.å. g y( ) è x y( ) âîçðàñòàþò.
Åñëè òåïåðü lim ( )
y
x y M R
���
� � , òî äëÿ N M� �[ ] 1 èìååì x y N( ) � �
y 0 , ò.å.
1
1
1
1
� � �
�
�
�
�
� �
p Q x
y
y x y
y
y N y
y y N
y x N
( )
( )
( )
( )
( )
( ) ... (�
�
�
�
)
yN
� 1, y� � � .
Ïîëó÷èëè ïðîòèâîðå÷èå, ò.å. lim ( )
y
x y
���
� � � .
Ëåììà äîêàçàíà.
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Ëåììà 2. Ôóíêöèÿ
x y
y
( )
� 0 ïðè y� � � .
Äîêàçàòåëüñòâî. Åñëè lim
( )
y
x y
y���
0 , òî �
� 0 �
M 0 �
y M x y y: ( )1 � .
 ýòîì ñëó÷àå
Q x
y
y x y
y
y y
Q yy x y y( )
( )
( )
( )
( )
( )�
�
� �
�
�
�
�1
1 �
�
�
, � �� �1 .
Ïîêàæåì, ÷òî Q yy ( )� � 0 ïðè y� � � . Ïî ôîðìóëå Ñòèðëèíãà äëÿ �-ôóíêöèè [3] èìååì:
� � � � � � � �ln ( ) ln
( )
( )
ln ( ) ln ( ) lnQ y
y
y y
y y y yy y
�
�
� �
�
�
�
� �
� � �
�
�
�
�
�
� � � �
�
�
�
�
�
� � � � �y y y y y y y y o
1
2
1
2
1ln ln ln ( )� � � �
� � � � � � � �y o( ln ) ln ( )1
1
2
1� � � � , y� � � ,
òàê êàê 1 0� �
� � �ln ïðè � � ( ; )0 1 . Îòñþäà 1 0� � � �p Q x Q yy y( ) ( )� , y� �� .
Ïîëó÷èëè ïðîòèâîðå÷èå, ò.å. lim
( )
y
x y
y���
� 0 .
Ëåììà äîêàçàíà.
Ëåììà 3. Ôóíêöèÿ x y a y
a
o( ) ( )� � � �2
1
2 3
1 ïðè y� � � .
Äîêàçàòåëüñòâî. Ïóñòü a p� � �
ln( )1 0 , òîãäà ïî ôîðìóëå Ñòèðëèíãà äëÿ �-ôóíêöèè
èìååì
a Q x y y x x yy� � � � � � � �ln ( ) ln ( ) ln ( ) ln� � 1 1
� � �
�
� �
�
� �
�
�( )ln ln
( )
y x
y
y x
x
y
y x y y x
1
1
1
1
1 2
1
1
2 12 12
� �
� �
�
� �
�
�
�
�
�
� � � � �x
u
u
u u
u
x
u
1
1
1
21
1
1
1
2
1
12 1
ln ( )
ln ( ) ln ( )
� �
2 11x u( )�
,
ãäå u u y
x y
y
� � �( )
( )1 0 , y� � � , � �1 2 0 1, ( ; )� .
Îòñþäà
x y
a
u y
a
o( )
( )
( )� � �
�
�
�
�
�
� �
2
2
1
2 3
1 y� � � ,
è, ñëåäîâàòåëüíî,
x y a y
a
o( ) ( )� � � �2
1
2 3
1 , y� � � .
Ëåììà äîêàçàíà.
Òåïåðü çàêîí÷èì äîêàçàòåëüñòâî òåîðåìû 1. Èç ëåììû 3 èìååì, ÷òî
x m( ) � � � , m � � � ,
x m x m( ) ( )� � �1 0 , m � � � ,
îòñþäà ñëåäóåò, ÷òî äðîáíûå ÷àñòè { }x m( ) , m N� , âñþäó ïëîòíû â [ ; ]0 1 .
Èç óñëîâèÿ (2) òàêæå ñëåäóåò, ÷òî n m x m n m( ) ( ) ( )� � �1 . Îòñþäà è èç ëåììû 3 ïîëó-
÷èì, ÷òî äëÿ � ( ) ( )m n m am� � 2 áóäåò âûïîëíÿòüñÿ { ( ), } ;� m m
a a
� � � �
�
��
�
�
1
1
2 3
3
2 3
(÷åðòà
íàä ìíîæåñòâîì îçíà÷àåò çàìûêàíèå).
 ÷àñòíîñòè, lim ( )
m
m
a
��
� ��
1
2 3
, lim ( )
m
m
a
��
� ��
3
2 3
.
Òåîðåìà äîêàçàíà.
Òåîðåìà 1 äàåò àñèìïòîòè÷åñêè òî÷íîå âûðàæåíèå äëÿ n m( ) , òàê êàê
lim ( ) lim ( )� �m m� � 1, ò.å. îòðåçîê �
�
� � �
�
�
�� ��
2 2am m am m
m m
lim ( ); lim ( )� � ñîäåðæèò íå áîëåå
÷åì îäíó öåëóþ òî÷êó n m
0
( ) , êîòîðóþ ìîæíî ðàññìàòðèâàòü êàê ïðèáëèæåíèå äëÿ n m( ) ïðè
áîëüøèõ m .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 187
Ïðèìåð. Åñëè m � 264, p �
1
2
, òî n m0 5056937541( ) � , ïðè ýòîì
P n( ) , ...0 0 500000000006094� ,
P n( ) , ...0 1 0 499999999869026� � .
2. Ðàññìîòðèì ñëåäóþùèé âàðèàíò ïàðàäîêñà äíåé ðîæäåíèé [1]: â m ÿ÷åéêàõ íåçàâèñè-
ìî ðàçìåùàåòñÿ äâå ãðóïïû ïî n ÷àñòèö, ïðè÷åì â êàæäîé ãðóïïå ÷àñòèöû ïîïàäàþò â ðàçëè÷-
íûå ÿ÷åéêè è âñå Cm
n âîçìîæíûõ ðàçìåùåíèé îäíîé ãðóïïû ðàâíîâåðîÿòíû. Ïóñòü R nm( ) —
âåðîÿòíîñòü òîãî, ÷òî ïðè ðàçìåùåíèè äâóõ ãðóïï ïî n ÷àñòèö ïî m ÿ÷åéêàì õîòÿ áû äâå ÷àñ-
òèöû èç ðàçíûõ ãðóïï ïîïàäóò â îäíó ÿ÷åéêó:
R n
C
C
m n
m m n
S nm
m n
n
m
n m( )
( )!
!( )!
( )� � � �
�
�
��1 1
2
1
2
, n k k
m
� �
�
��
�
�
0
2
, , ,
ãäå S n R nm m( ) ( )� �1 — âåðîÿòíîñòü, ÷òî âñå ÷àñòèöû ïîïàäóò â ðàçíûå ÿ÷åéêè. Ïðè
n
m
�
��
�
� 2
èìååì R nm( ) � 1.
Ïóñòü çàäàíî ÷èñëî p � ( ; )0 1 , îïðåäåëèì íàòóðàëüíîå ÷èñëî n n m k� � �( ) [ ; ]1 1 , êîòî-
ðîå çàâèñèò îò m è p , èç óñëîâèÿ R n p R n( ) ( )� � �1 , ò.å. n m( ) — ìèíèìàëüíîå ÷èñëî n ÷àñòèö
òàêîå, ÷òî ïðè ðàçìåùåíèè äâóõ ãðóïï ïî n ÷àñòèö â m ÿ÷åéêàõ âåðîÿòíîñòü ïîïàäàíèÿ äâóõ
÷àñòèö â îäíó ÿ÷åéêó íå ìåíüøå p .
Çàäà÷à ñîñòîèò â îïðåäåëåíèè àñèìïòîòè÷åñêîãî ïîâåäåíèÿ äëÿ n m( ) . Ñïðàâåäëèâà
ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Ïóñòü p � ( ; )0 1 ôèêñèðîâàíî, a p� � �ln( )1 , òîãäà n m am m( ) ( )� � � , ãäå
ïîñëåäîâàòåëüíîñòü { }� ( ),m m � 1 îãðàíè÷åíà è lim ( )
m
m
a
��
� ��
2
, lim ( )
m
m
a
��
� � ��
2
1.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî òåîðåìû 2 àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 1.
Ââåäåì ôóíêöèþ
S x
y x
y y x
y x
y y
y ( )
( )
( ) ( )
( )
( ) (
�
� �
� � �
�
�
�
�
� �
�
� �
1
1 2 1 2
2
1
2
1 1 x)
, y y1 1 1� �
, 0
2
� �x
y
.
Îïðåäåëèì ôóíêöèþ x y( ) : ( ; ) ( ; )0 0� � � � � èç ñîîòíîøåíèÿ S x y py ( ( )) � �1 . Òîãäà
n m x m n m( ) ( ) ( )� � �1 , m N� , x y a y
a
o( ) ( )� � �
2
1 ïðè y� � � .
Îòñþäà ñëåäóåò óòâåðæäåíèå òåîðåìû 2.
Ýòè ðåçóëüòàòû ìîæíî ïðèìåíèòü, íàïðèìåð, äëÿ îöåíèâàíèÿ âåðîÿòíîñòè êîëëèçèé
õýø-ôóíêöèé è òðóäîåìêîñòè ïîñòðîåíèÿ êîëëèçèé [4], â êðèïòîàíàëèçå, â òåîðèè ñëó÷àé-
íûõ ðàçìåùåíèé è ñëó÷àéíûõ îòîáðàæåíèé, ïðè îöåíêå ñîâïàäåíèÿ ðåäêèõ ñîáûòèé [5, 6].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ø è ð ÿ å â À . Í . Âåðîÿòíîñòü. — Ì.: Íàóêà, 1980. — 576 ñ.
2. Ñ å ê å é Ã . Ïàðàäîêñû â òåîðèè âåðîÿòíîñòåé è ìàò. ñòàòèñòèêå. — Ì.: Ìèð, 1990. — 240 ñ.
3. Ô è õ ò å í ã î ë ü ö à . Ì . Êóðñ äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ. Ò.2. — Ì.: Íàóêà,
1966. — 800 ñ.
4. À ë ô å ð î â À . Ï . , Ç ó á î â À . Þ . , Ê ó ç ü ì è í À . Ñ . , × å ð å ì ó ø ê è í À . Â . Îñíîâû êðèïòî-
ãðàôèè. — Ì.: Ãåëèîñ ÀÐÂ, 2001. — 480 ñ.
5. Ñ o o p e r C . , G i l c h r i s t R . , K o v a l e n k o I . N . , N o v a c o v i c D . Deriving the number of good
permutstions with applications to cryptography // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1999. — ¹ 5. —
Ñ. 10–16.
6. Ã è ë ê ð è ñ ò Ð . , Ê î â à ë å í ê î È . Í . Îá îöåíêå âåðîÿòíîñòè îòñóòñòâèÿ êîëëèçèé íåêîòîðûõ ñëó-
÷àéíûõ îòîáðàæåíèé // Òàì æå. — 2000. — ¹ 1. — Ñ. 132–138.
Ïîñòóïèëà 17.11.2009
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
|