КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

Масол Вікторія Володимирівна

УДК.519.21

Асимптотика розподілів деяких характеристик

випадкових матриць над скінченним полем

01.01.05 – теорія ймовірностей та математична статистика

А В Т О Р Е Ф Е Р А Т

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2003

Дисертацією є рукопис

Робота виконана на кафедрі теорії ймовірностей та математичної статистики Київського національного університету імені Тараса Шевченка.

Науковий керівник: член-кореспондент НАН України,

доктор фізико-математичних наук, професор

ЯДРЕНКО Михайло Йосипович,

Київський національний університет

імені Тараса Шевченка,

професор кафедри теорії ймовірностей та математичної статистики

Офіційні опоненти: доктор фізико-математичних наук

САВЧУК Михайло Миколайович,

Національний технічний університет України

“Київський політехнічний інститут”,

завідувач кафедри математичних методів захисту інформації

доктор фізико-математичних наук, старший науковий

співробітник НАКОНЕЧНИЙ Олександр Миколайович,

Міжнародний інститут бізнесу,

професор центру розвитку фінансового менеджменту

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України, м. Київ

Захист відбудеться “15” грудня 2003 р. о 1400 годині на засіданні спеціалізованої вченої ради Д 26.001.37 у Київському національному університеті імені Тараса Шевченка за адресою: 03022, м. Київ22, просп. Академіка Глушкова, 6, корпус 7, механіко-математичний факультет.

З дисертацією можна ознайомитися в науковій бібліотеці Київського національного університету імені Тараса Шевченка (01033, м. Київ, вул.. Володимирська, 58).

Автореферат розісланий “11” листопада 2003 року.

Вчений секретар

спеціалізованої вченої ради Моклячук М.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність дослідження. Прикладні аспекти теорії кодування інформації та захисту її від несанкціонованого доступу, теорії тестування генераторів псевдовипадкових чисел і теорії розпізнавання приводять до задачі про знаходження розподілів характеристик матриці над скінченним полем, яка випадково обирається з певних сукупностей.

Розподіл рангу випадкової матриці над скінченним полем досліджувався за різних умов в роботах Slepian D. (1955), Коваленка І.М. (1965, 1975), Козлова М.В. (1966), Балакіна Г.В. (1968, 1998), Левитської А.О. (1986), Колчіна В.Ф. (1997, 2000), Алєксєйчука А.М. (1998, 1999), Cooper C. (2000, 2001) та інших авторів.

Ранг ліній та перманентний ранг випадкової (0, 1)-матриці розглядався в публікаціях Erdos P. та Renyi A. (1963), Балакіна Г.В. (1967, 1968), Коваленка І.М. (1986); перманент зазначеної матриці вивчали Ahn W. і Choi B. (1986), Сачков В.М. і Тараканов В.Є. (2000), Севастьянов Б.О. (2000).

Розподіл ваги підпростору, породженого випадковою матрицею над скінченним полем, аналізувався в роботах Pierse I.N. (1967), Козлова М.В. (1969, 1971), Ryazanov B.V. (1993), Масола В.І. (1996) та інших.

Особливістю зазначених вище досліджень характеристик випадкових матриць є те, що переважна більшість їх стосується отримання граничних (за умови зростання розмірів матриці до нескінченності) значень імовірностей відповідних подій. Проте, існуючі прикладні задачі потребують розробок, які б дозволяли одержувати розподіли певних характеристик випадкових матриць скінченних розмірів. Зрозуміло, що застосування граничних теорем у цьому випадку може привести до суттєвих похибок.

Тому актуальними і в загальній постановці складними є задачі знаходження розподілів характеристик скінченних матриць, елементи яких незалежні й необов'язково однаково розподілені випадкові величини. Представлення цих розподілів у вигляді рядів за степенями малого параметра, що обирається певним чином, відповідає сучасній концепції побудови оцінок, розвинутої в працях Королюка В.С. (1969, 1979), Турбіна А.Ф. (1979), Анісімова В.В. (1984), Коваленка І.М. (1982, 1989), Наконечного О.М. (1989, 1990, 2001) та інших.

Актуальними є також дослідження проблеми оцінювання швидкості збіжності до граничних значень розподілів згаданих вище характеристик випадкових матриць над скінченним полем. Про підвищення інтересу до отримання асимптотичних формул, які можуть бути застосовані в задачах перетворення інформації, побудови випадкових функцій, генераторів псевдовипадкових чисел тощо, свідчать публікації останніх років Савчука М.М. (1999, 2001), Михайлова В.Г. (2001) та інших.

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана в рамках держбюджетної дослідницької теми № 01БФ03806 “Розвиток теорії випадкових полів та динамічних систем на алгебраїчних структурах”, яка входить до програми “Побудова та застосування математичних методів дослідження детермінованих та стохастичних еволюційних систем” (номер державної реєстрації № 0101U002472).

Мета та задачі дослідження. Метою роботи є подальший розвиток теорії випадкових матриць над скінченним полем для створення умов ефективного і широкого використання результатів даної теорії в прикладних задачах (зокрема, тестування генераторів псевдовипадкових чисел, кодування інформації та захисту її від несанкціонованого доступу тощо).

Основні задачі дослідження:

? одержання точного й асимптотичного представлень за степенями малого параметра ймовірності того, що випадкова матриця над полем, яке складається з двох елементів, має максимальний ранг;

? доведення теореми про асимптотику розподілу виміру випадкового підпростору над скінченним полем;

? аналіз асимптотичної поведінки ймовірності того, що випадково обраний підпростір над скінченним полем має мінімальну вагу;

? знаходження асимптотики ймовірності того, що підпростір, випадково та рівно-ймовірно обраний із сукупності всіх k(n)-вимірних підпросторів n-вимірного векторного простору над полем, яке утворене з q(n) елементів, має задану вагу, при n .

Методика дослідження. Для розв'язання сформульованих задач в дисертаційній роботі використовуються результати і методи теорії ймовірностей, теорії розбиттів, математичного аналізу.

Наукова новизна одержаних результатів. Основними результатами, які визначають наукову новизну і виносяться на захист, є такі:

1. Знайдена оцінка коефіцієнтів розкладу за степенями малого параметра ймовірності того, що матриця, елементи якої є незалежними випадковими величинами (необов'язково однаково розподіленими), що приймають значення 0 або 1, має максимальний ранг.

2. Знайдені явний вигляд та умови збіжності до нуля оцінки залишкового члена розкладу, визначеного в п. 1.

3. Запропоновані співвідношення для знаходження явного вигляду коефіцієнтів розкладу, визначеного в п. 1.

4. Встановлена асимптотика розподілу виміру підпростору, випадково й рівноймовірно обраного з сукупності всіх підпросторів n-вимірного векторного простору над скінченним полем, при n .

5. Знайдена асимптотична поведінка ймовірності того, що підпростір, випадково й рівноймовірно обраний із сукупності всіх підпросторів n-вимірного векторного простору над скінченним полем, має мінімальну вагу, при n .

6. Знайдена асимптотична поведінка ймовірності того, що підпростір, випадково й рівноймовірно обраний із сукупності всіх k(n)-вимірних підпросторів n-вимірного векторного простору над полем, яке складається з q(n) елементів, має задану вагу, при n .

Практичне значення одержаних результатів. Дисертація має теоретичне спрямування, і одержані результати є внеском в розвиток теорії випадкових матриць над скінченним полем. На практиці вони можуть бути використані для тестування генераторів псевдовипадкових чисел, розв'язування прикладних задач теорії лінійних кодів та захисту інформації, а також в інших галузях, де використовуються випадкові матриці над скінченним полем.

Особистий внесок здобувача. Визначення напряму дослідження і загальна постановка задач належать науковому керівнику члену-кореспонденту НАН України Ядренку М.Й. Проблема про розклад в ряд за степенями малого параметра розподілу випадкового визначника у полі, що складається з двох елементів, запропонована академіком НАН України Коваленком І.М. Всі результати дисертації, у тому числі варіант розв'язку зазначеної проблеми, отримані здобувачем самостійно.

Апробація результатів. Результати дисертаційного дослідження доповідалися й обговорювалися на:

? Третій Міжнародній школі “Applied Statistics, Financial and Actuarial Mathematics” (Феодосія, 2000);

? Сьомій Всеросійській школі-колоквіумі із стохастичних методів (Сочі, 2000);

? Міжнародній школі “Mathematical and Statistical Applications in Economics” (Vдsterеs, ?веція, 2001);

? Міжнародній науково-методичній конференції “Гнєденківські читання”, присвяченій 90-й річниці з дня народження Б.В.Гнєденка (Київ, 2002);

? Міжнародній конференції “Kolmogorov and Contemporary Mathematics” (Москва, 2003);

? літній школі “Advanced Computational Methods for Statistical Inference” (Marseille, Франція, 2001);

? засіданні наукового семінару з теорії ймовірностей та математичної статистики при кафедрі теорії ймовірностей та математичної статистики механіко-математичного факультету Київського національного університету імені Тараса Шевченка (Київ, 2003);

? науковому семінарі кафедри математики та фізики Мелардаленського університету (Malardalen University, Vдsterеs, ?веція, 2003).

Публікації. За результатами дисертаційного дослідження опубліковано 8 наукових робіт. З них 5 у фахових виданнях, затверджених ВАК України; 3 у тезах доповідей на конференціях.

Структура дисертації. Дисертація складається із вступу, чотирьох розділів, розбитих на підрозділи, висновків та списку використаних джерел. Дисертація викладена на 140 сторінках основного тексту. У роботі використано 74 літературних джерела.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

У вступі обґрунтовано актуальність роботи, визначено мету та задачі дослідження; висвітлено методи, наукову новизну, теоретичне та практичне значення дослідження, особистий внесок здобувача, апробацію отриманих результатів.

Перший розділ містить огляд літератури за тематикою дослідження, аналіз сучасного стану проблем, які розглядаються в дисертаційній роботі.

У другому розділі досліджено ймовірність того, що булева матриця, елементи якої є незалежними та необов'язково однаково розподіленими випадковими величинами, має максимальний ранг. Для зазначеної ймовірності знайдений розклад в ряд за степенями малого параметра, від якого залежать розподіли елементів матриці. Одержаний розклад дозволив, зокрема, сформулювати умови, за яких ця ж ймовірність може бути обчислена з наперед заданою точністю, і отримати оцінку швидкості збіжності до нуля залишкового члену розкладу, коли кількість рядків матриці прямує до нескінченності.

Перейдемо до строгого формулювання задачі.

Нехай (T n)-матриця над полем GF(2), яке складається з двох елементів (тут T кількість рядків, n кількість стовпців матриці A), ,. Покладемо m = T n, і надалі будемо вважати, що

Елементи матриці є незалежними випадковими величинами, які мають розподіл

де – достатьо мале фіксоване число

Позначимо через індикатор, = {1, якщо матриця A складається з n лінійно незалежних в полі GF(2) стовпців; 0, у протилежному випадку}. Далі будемо розглядати ймовірність. З урахуванням (2) її можна подати у вигляді

де коефіцієнти, s 0, набувають дійсних значень і не залежать від параметра ?.

Основними результатами другого розділу є теореми про нетривіальне оцінювання та знаходження явного вигляду коефіцієнтів, , а також про точне та асимптотичне (T ) представлення ймовірності того, що матриця A має максимальний ранг.

Теорема 2.1. Якщо виконуються умови (1), (2) і

Позначимо через R (s) множину, яка складається з s попарно різних елементів

де символ позначає додавання за всіма попарно різними наборами R (s), tR(s) дійсне число.

В теоремі 2.2. встановлена формула для знаходження чисел tR(s) при довільних R(s), що з урахуванням останнього співвідношення дає можливість обчислювати коефіцієнти, , в явному вигляді.

Теорема 2.2. Нехай набір складається з k, 1 k n, елементів сукупності J, ,. Якщо виконуються умови (1) і (2), то

де 0 множина всіх матриць в полі GF(2), кожна з яких має ранг k 1 і задовольняє умові парності

, j {1, 2, …, k–1},

, символ позначає операцію додавання в полі GF(2), , j J.

Наведемо декілька прикладів обчислення коефіцієнтів за допомогою теореми 2.2.

Приклад 2.1.

.

Приклад 2.3.

.

Зауважимо, що при s = 1 та s = nT нерівність (4) перетворюється на рівність, якщо для всіх i I та j J x ij = K n,T. При s = 0 можна показати, що

.

Теореми 2.1 та 2.2 дозволяють отримати розклад в ряд за степенями параметра розподілу випадкової величини, і дати оцінку залишкового члена ряду.

Теорема 2.4. Якщо виконуються умови (1), (2) і (3), то

,

де коефіцієнти, 1 s k, обчислюються за допомогою (5) і теореми 2.2,

, k 0.

Наступна теорема дає оцінку залишку та умови, за яких він прямує до нуля.

Теорема 2.6. Якщо виконуються умови (1)(3) і при цьому

(i) для деякого 0 справедливо

, T ,

то

, T ;

(ii), T , то

, T , (6)

, T ,

.

Результати другого розділу дисертації можуть знайти практичне застосування, наприклад, для задач кодування інформації, тестування генераторів псевдовипадкових чисел тощо. Зокрема, в задачах тестування виникає потреба знаходити ймовірність того, що випадкова (T n)-матриці, кількість рядків якої T значно більша, ніж кількість стовпців n, T >> n, n = const, K n, T = const, має максимальний ранг. Саме за таких умов теорема 2.6 дозволяє зафіксувати параметр так, щоб рівність (6) давала значення ймовірності із наперед заданою точністю для всіх T, починаючи з деякого T0 , T T0.

В третьому та четвертому розділах дисертації досліджено розподіли характеристик випадкових матриць над довільним скінченним полем GF(q), що складається з q елементів (q степінь простого числа).

Розглянемо множину всіх (k n)-матриць рангу k над полем GF(q) (k число рядків, n число стовпців (k n)-матриці), 1 k n, n 1, і розіб'ємо її на класи еквівалентності таким чином, що до одного класу належать ті і лише ті (k n)-матриці, рядки кожної з яких можуть бути отримані як лінійна комбінація рядків будь-якої іншої матриці з цього класу. За побудовою, кожному класу еквівалентності взаємно однозначно відповідає деякий k-вимірний підпростір n-вимірного векторного простору над полем GF(q). Тобто будь-яка матриця з кожного класу є базисною для відповідного k-вимірного підпростору.

Враховуючи зазначену взаємно однозначну відповідність між класами еквівалентних (k n)-матриць рангу k та k-вимірними підпросторами, у подальшому будемо використовувати термінологію теорії векторних просторів.

Розглянемо сукупність усіх підпросторів n-вимірного векторного простору над полем GF(q) і позначимо її через M. На сукупності M задамо рівномірний розподіл, поклавши для кожного підпростору з M ймовірність 1/|M|.

Основними результатами третього розділу є асимптотичне (n ) представлення розподілу виміру підпростору, який випадково та рівноймовірно обирається із сукупності M, та асимптотика ймовірності того, що зазначений підпростір має мінімальну вагу.

Асимптотика розподілу виміру підпростору випливає з теореми про асимптотичний розподіл випадкової величини, яка визначається наступним чином.

Нехай n, n = 1, 2, …, випадкова величина, яка приймає цілі невід'ємні значення з ймовірністю

, j = 0, 1, …, n, (7)

де вираз є многочленом Гаусса, , q > 1;

, t > 0.

Наступна теорема дає асимптотику (n ) розподілу випадкової величини n.

Теорема 3.1. Нехай q > 1 та

(і) для цілих чисел r(n) виконується умова

Зауваження 3.1. Якщо q степінь простого числа, то співпадає з числом j-вимірних підпросторів n-вимірного векторного простору над полем GF(q), 0 j .n.

Звідси з урахуванням (7) випливає, що коли q степінь простого числа і t = 1 розподіл випадкової величини n співпадає з розподілом виміру підпростору, випадково обраного з сукупності M, і теорема 3.1 дає асимптотичне представлення зазначеного розподілу.

Зауваження 3.2. Якщо t = q = 2, то сума 1 + Hn (t) співпадає з числом мультиафінних булевих функцій, кожна з яких залежить від n аргументів; вираз 2j для 1 j n співпадає з числом мультиафінних булевих функцій, для кожної з яких існує представлення у вигляді кон'юнкції j афінних функцій від n аргументів, причому однорідні частини цих функцій лінійно незалежні.

Отже, якщо t = q = 2, то теорема 3.1 дає асимптотичне представлення розподілу числа множників при кон'юнктивному представленні мультиафінної n-вимірної булевої функції, випадково й рівноймовірно обраної із сукупності всіх n-вимірних мультиафінних булевих функції при n .

Позначимо через Vn (q) n-вимірний векторний простір над полем GF(q).

Означення 3.1. Вагою вектора v Vn (q), n 1, називається число ненульових компонент вектора v.

Означення 3.2. Вагою простору Vn (q) називається число, яке дорівнює мінімальній вазі ненульового вектора v Vn (q), v 0.

Позначимо через число всіх k-вимірних підпросторів n-вимірного векторного простору Vn (q), кожний з яких має вагу , {1, 2, ..., n}, k = 1, 2, ..., n, n 1.

Розглянемо випадкову величину n = {1, якщо підпростір, випадково обраний з множини M, має мінімальну вагу; 0, у протилежному випадку}. За умови рівномірного розподілу, введеного на множині M, розподіл випадкової величини n можна подати у вигляді

.

Наступна теорема дає оцінку швидкості збіжності розподілу випадкової величини n до нуля.

Теорема 3.2. При n

,

де, ,

,

фіксоване число, > 0.

Теорему 3.2 можна проінтерпретувати, зокрема, наступним чином: з ймовірністю, яка прямує до 1 зі швидкістю порядку 1 О(nq-n/2), n , підпростір, випадково обраний з множини M, має вагу більшу або рівну 2.

В четвертому розділі продовжено дослідження ймовірності того, що випадковий підпростір має мінімальну вагу, за інших умов вибору підпростору, а також знайдено асимптотику ймовірності того, що цей випадковий підпростір має вагу 2.

Нехай Mk сукупність усіх k-вимірних підпросторів n-вимірного простору Vn (q). На множині Mk задамо рівномірний розподіл, поклавши для кожного підпростору з Mk ймовірність. Із сукупності Mk випадково обирається деякий підпростір. Задача полягає в тому, щоб дослідити розподіл ваги обраного таким чином випадкового підпростору.

Нехай k,n вага випадково обраного з множини Mk підпростору. За умови рівномірного розподілу на Mk ймовірність можна записати у вигляді

, = 1, ..., n.

Основним результатами четвертого розділу дисертації є теореми про нетривіальні оцінки швидкості збіжності ймовірності, i = 1, 2, до граничних значень.

Покладемо m = n k, m 0.

Теорема 4.7. Нехай m 1.

(i) Якщо при n

kq m x, 0 x 1,

то

, n ;

(ii) якщо при n

kq m x, 0 x < , (8)

i

q , n ,

то

, n ;

(ііі) якщо виконується (8) і q = const, то

, n .

Наслідок 4.2. Якщо kq m 0, n , то, n , причому

,

де

.

Зокрема, з наслідку 4.2 випливає, що коли n k >> ln k, то з ймовірністю, яка прямує до 1 зі швидкістю порядку 1 О (nq-m), n , всі k-вимірні підпростори n-вимірного векторного простору над полем GF(q) мають вагу не меншу, ніж 2.

Теорема 4.8. Якщо kq m x при n , де 0 < x < , m 1, то

З теореми 4.8 випливає, що коли n відрізняється від k на величину порядку ln k, n k ~ ln k, то асимптотика (n ) ймовірності появи k-вимірного підпростору мінімальної ваги має експоненційний вигляд:. Якщо n і k відрізняються неістотньо, наприклад, на величину, що не перевищує o(ln k) (тобто n k << ln k), то теорема 4.11 дає, що з ймовірністю, яка прямує до 1 зі швидкістю порядку 1 , n , кожний k-вимірний підпростір n-вимірного векторного простору має вагу 1.

Використовуючи теорему 4.8, можна отримати граничний розподіл і швидкість збіжності до нього ваги підпростору, випадково обраного із сукупності Mk, а саме:

Теорема 4.9. Якщо виконуються умови теореми 4.8 і q при n , то мають місце співвідношення (9)(12) і

Теорема 4.10. Якщо при n kq m x, (q 1) 1 < x < , де q фіксоване число, то при n мають місце співвідношення (9), (13), і при цьому

Результати третього і четвертого розділів можуть знайти практичне застосування, передусім, при розв'язанні задач кодування і захисту інформації від несанкціонованого доступу.

У висновках сформульовані основні результати дисертаційного дослідження.

В И С Н О В К И

В дисертаційній роботі досліджуються розподіли деяких характеристик випадкових матриць над скінченним полем. В першому розділі міститься огляд літератури за тематикою дослідження. У другому розділі знайдено розклад в ряд за степенями малого параметра ймовірності того, що булева матриця має максимальний ранг (елементи матриці є незалежними випадковими величинами, розподіл яких залежить від малого параметра). За допомогою отриманого розкладу знайдене асимптотичне представлення зазначеної ймовірності, коли кількість рядків матриці прямує до нескінченності.

Теорема при асимптотичне (n ) представлення розподілу виміру підпростору, що випадково та рівноймовірно обирається із сукупності всіх підпросторів n-вимірного векторного простору над довільним скінченним полем, та теорема про асимптотичне (n ) представлення ймовірності того, що зазначений підпростір має мінімальну вагу, доведені в третьому розділі.

В четвертому розділі дисертації досліджено асимптотику (n ) ймовірності того, що підпростір, випадково та рівноймовірно обраний із сукупності всіх k(n)-вимірних підпростірів n-вимірного векторного простору над полем, яке утворене з q(n) елементів, має задану вагу (розглянуто випадки, коли підпростір має вагу 1 або 2). Асимптотику зазначеної ймовірності отримано для всіх можливих співвідношень між параметрами n та k(n).

Всі одержані в роботі результати є новими, і вони вносять вклад в розвиток теорії випадкових матриць над скінченним полем. Практичне застосування результати дисертації можуть знайти при розв'язанні задач кодування та захисту інформації від несанкціонованого доступу, тестування генераторів псевдовипадкових чисел та в інших галузях, де використовуються випадкові матриці над скінченним полем.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Масол В.В. Разложение по степеням малого параметра распределения случайного детерминанта в поле GF(2) // Обозрение прикладной и промышленной математики. М.: ТВП. 2000. Т. 7. Вып. 2. С. 511512.

2. Masol V.V. Explicit Representation of Some Coefficients in the Expansion of the Random Matrix Rank Distribution in the Field GF(2) // Theory of Stochastic Processes. 2000. Vol. 6(22), issue 34. Р. 122126.

3. Масол В.В. Розклад за малим параметром імовірності того, що випадковий визначник у полі GF(2) дорівнює одиниці // Теорія ймовірностей та математична статистика. 2001. Вип. 64. С. 102105.

4. Масол В.В. Асимптотика розподілу деяких характеристик випадкових просторів над скінченним полем // Теорія ймовірностей та математична статистика. 2002. Вип. 67. С. 97103.

5. Masol V.V. The Asymptotic of Distributions Constructed by Means of Gaussian Polynomials // Abstracts of the International Gnedenko Conference. Kyiv. June 37, 2002. P. 212.

6. Масол В.В. Разложение по степеням малого параметра распределения максимального ранга случайной булевой матрицы // Кибернетика и системный анализ. 2002. № 6. С. 176180.

7. Masol V.V. The Properties of Probabilistic Characteristics of Matrices over the Finite Field // Abstracts of the International Conference “Kolmogorov and Contemporary Mathematics”. Moscow. June 1621, 2003. P. 497498.

8. Масол В.В. Деякі застосування точних виразів ймовірності того, що випадковий k-вимірний підпростір має мінімальну вагу // Вісник Київського університету. Механіка. Математика. 2003. № 10. C. 113117.

А Н О Т А Ц І Я

Масол В.В. Асимптотика розподілів деяких характеристик випадкових матриць над скінченним полем. Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.05 – теорія ймовірностей і математична статистика. Київський національний університет імені Тараса Шевченка, Київ, 2003.

У дисертації досліджуються розподіли характеристик випадкових матриць над скінченним полем. Знайдені точне та асимптотичне представлення ймовірності того, що випадкова матриця над полем, яке складається з двох елементів, має максимальний ранг. Доведено теорему про асимптотику розподілу виміру підпростору випадково та рівноймовірно обраного із сукупності всіх підпросторів n-вимірного векторного простору над довільним скінченним полем, та теорему про асимптотичне представлення ймовірності того, що зазначений підпростір має мінімальну вагу. Досліджено асимптотику ймовірності того, що підпростір, випадково та рівноймовірно обраний із сукупності всіх k(n)-вимірних підпростірів n-вимірного векторного простору над полем, яке утворене з q(n) елементів, має задану вагу, при n .

Ключові слова: випадкова матриця, асимптотика розподілу, скінченне поле, випадковий простір, розклад розподілу за малим параметром, різнорозподілені елементи матриці.

А Н Н О Т А Ц И Я

Масол В.В. Асимптотика распределений некоторых характеристик случайных матриц над конечным полем. Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.05 – теория вероятностей и математическая статистика. Киевский национальный университет имени Тараса Шевченко, Киев, 2003.

Интерес к задачам о нахождении распределений характеристик случайной матрицы над конечным полем, которая выбирается из определенных совокупностей, вызван прикладными аспектами теории кодирования информации и защиты ее от несанкционированного доступа, теории тестирования генераторов псевдослучайных чисел и теории распознавания. К указанным характеристикам можно отнести, например, ранг матрицы, перманентный ранг, ранг линий, вес и размерность пространства, порожденного строками случайной матрицы.

Распределения указанных характеристик изучались многими авторами. Но традиционно основное внимание уделялось получению предельных значений соответствующих вероятностей. В частности, было установлено предельное значение вероятности того, что матрица над конечным полем имеет максимальный ранг при условии, что размерность матрицы стремиться к бесконечности, а элементы ее независимые и необязательно одинаково распределенные случайные величины. Найдено также предельное (n ) значение вероятности того, что подпространство, случайно и равновероятно извлекаемое из совокупности всех k(n)-мерных подпространств n-мерного векторного пространства над конечным полем, имеет заданный вес.

Вместе с тем, актуальными являются задачи нахождения распределений характеристик случайной матрицы конечных размеров. Также требует решения вопрос об оценивании скорости сходимости распределений выше названых характеристик к предельным значениям. Указанные проблемы определили направление и задачи диссертационного исследования.

При решении поставленных задач использовались результаты и методы теории вероятностей, теории разбиений, математического анализа.

До настоящего времени получение асимптотических представлений распределений характеристик случайной матрицы в виде ряда по степеням малого параметра оставалось без должного внимания. Хотя именно такие представления являются реальным инструментом для решения практических задач и, как следствие этого, находятся в русле современной концепции построения оценок, развивающейся более трех десятилетий в рамках теории вероятностей и теории надежности. Это определяет актуальность тематики исследования.

В диссертации указанная концепция адаптируется следующим образом. Рассматривается случайная матрица над полем GF(2) и предполагается, что распределение каждого элемента матрицы зависит от малого параметра и номеров строки и столбца, на пересечении которых находится этот элемент. В работе найдено разложение в ряд по степеням малого параметра вероятности того, что указанная матрица имеет максимальный ранг. Предложены формулы для нахождения явного вида коэффициентов при степенях малого параметра, приведены примеры использования этих формул, установлены оценки коэффициентов разложения. Сформулированы условия, при которых остаточный член ряда стремится к нулю, при T , где T число строк (T n)-матрицы, T n, и получена оценка скорости сходимости.

Рассмотрено n-мерное векторное пространство, порожденное строками случайной матрицы над произвольным конечным полем GF(q), q число элементов поля, q степень простого числа. Найдена асимптотика распределения размерности подпространства, случайно и равновероятно извлекаемого из совокупности всех подпространств n-мерного векторного пространства над полем GF(q), и асимптотическое представление вероятности того, что указанное подпространство имеет минимальный вес, при n . Асимптотика распределения размерности получена как следствие из общей теоремы об асимптотике распределения случайной величины, определяемого многочленами Гаусса. Еще одним следствием указанной общей теоремы является асимптотика распределения числа сомножителей при представлении мультиафинной булевой функции f от n аргументов в виде конъюнкции афинных булевых функций с независимыми однородными частями, при условии, что f случайно и равновероятно извлекается из совокупности всех мультиафинных булевых функций от n аргументов, n .

Исследована асимптотика вероятности того, что подпространство, случайно и равновероятно извлекаемое из совокупности всех k(n)-мерных подпространств n-мерного векторного пространства над полем, которое состоит из q(n) элементов, имеет минимальный вес, при n . При этом рассмотрены все возможные соотношения между параметрами k(n) и n. Для некоторых из этих соотношений получено асимптотическое (n ) представление распределения веса указанного подпространства.

Ключевые слова: случайная матрица, асимптотика распределения, конечное поле, случайное пространство, разложение распределения по малому параметру, разнораспределенные элементы матрицы.

A N N O T A T I O N

Masol V.V. The Asymptotic of the Distributions of Some Characteristics of Random Matrices over a Finite Field. – Manuscript.

The thesis for obtaining the Candidate of Physical and Mathematical Sciences degree on the specialty 01.01.05 – Probability Theory and Mathematical Statistics. Kyiv National Taras Shevchenko University.

The distributions of some characteristics of random matrices over a finite field are studied in the thesis. The exact and asymptotic representations of the probability that a random matrix over the two-element field has maximum rank are found. There are proved theorem on the asymptotic (n ) of the distribution of the given dimension of the subspace, whose choice is random and equiprobable, chosen among the set of all subspaces of the n-dimensional vector space over a finite field, and theorem on the asymptotic representation of the probability that the subspace mentioned above has minimal weight. The asymptotic of the probability that a subspace, whose choice is random and equiprobable, chosen among the set of all k(n)-dimensional subspaces of the n-dimensional vector space over the field consisting of q(n) elements has minimal weight is investigated as n .

Key words: random matrix, distribution asymptotic, finite field, random space, distribution expansion in a small parameter, non-identically distributed matrix entries.