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

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

ПОПЕРЕШНЯК Світлана Володимирівна

УДК.519.21

РОЗПОДІЛИ РАНГІВ СЛАБКО- ТА

СИЛЬНОЗАПОВНЕНИХ ВИПАДКОВИХ

МАТРИЦЬ У ПОЛІ)

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

А В Т О Р Е Ф Е Р А Т

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

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

Київ – 2007

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

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

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

МАСОЛ Володимир Іванович,

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

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

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

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

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

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

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

захисту інформації

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

КОВАЛЬЧУК Людмила Василівна,

Інститут спеціального зв’язку і захисту інформації НТУУ “КПІ”,

професор спеціальної кафедри № 1 „Застосування засобів криптографічного та технічного захисту інформації”.

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

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

Автореферат розісланий “ 18 ” грудня 2007 року.

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

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

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

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

Однією з пріоритетних характеристик випадкових матриць над скінченним полем є її ранг. Вивчення розподілу рангу зазначених матриць розпочалося наприкінці 19 століття (Landsberg G. (1895)) і велику увагу привернуло до себе з середини 20 століття, про що свідчать роботи Slepian D. (1955), Erds P., Renyi A.(1963), Коваленка I.М. (1965, 1975), Козлова М.В.(1966), Левитської А.О. (1986) та інших авторів.

Фундаментальні теореми Коваленка І.М. (1975) про область інваріантності розподілу рангу випадкової матриці у полі що складається з двох елементів, вплинули на формування подальших напрямків наукових досліджень. Один з них стосується вивчення розподілу рангу матриці поза областю інваріантності Коваленка І.М. Аналіз публікацій Балакiна Г.В. (1968), Масола В.І.), Blmer J., Karp R., Welrl E. (1997), Cooper C. (2000), Колчiна В.Ф. (2004) та інших авторів засвідчив, що у переважній більшості з них розглядається розподіл рангу слабкозаповненої матриці, утвореної незалежними однаково розподіленими випадковими елементами.

Результати роботи Cooper C. (2000) дають граничний () розподіл рангу сильнозаповненої ()-матриці (також утвореної незалежними однаково розподіленими елементами) при певних обмеженнях на кількість одиничних рядків та стовпців в ній.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках держбюджетної дослідницької теми № 06БФ038-03 "Аналітичні та стохастичні методи дослідження динамічних систем", яка входить до програми "Математичні проблеми природознавства та економіки" (номер державної реєстрації № U002472).

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

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

знаходження оцінок зближення розподілу рангу слабкозаповненої випадкової матриці у полі до граничного () розподілу при заданому відношенні числа рядків до числа стовпців;

аналіз імовірності сумісності неоднорідної системи лінійних випадкових рівнянь у полі з слабкозаповненою випадковою матрицею коефіцієнтів;

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

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

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

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

знайдена оцінка швидкості зближення розподілу рангу слабкозаповненої випадкової матриці у полі до граничного () розподілу при заданому відношенні числа рядків до числа стовпців;

знайдена оцінка імовірності сумісності неоднорідної системи лінійних випадкових рівнянь у полі з слабкозаповненою випадковою матрицею коефіцієнтів;

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

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

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

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

Апробація результатів.

Результати дисертації доповідались та обговорювались на

* Міжнародній конференції "International conference modern problems and new trends in probability theory" (Чернівці, 2005);

* четвертій Міжнародній науково-практичній конференції студентів, аспирантів і молодих вчених "Шевченківська весна. Сучасний стан науки: досягнення, проблеми та перспективи розвитку" (Київ, 2006р.);

* Міжнародній конференції "Сучасна стохастика: теорія і застосування", присвяченої 60-річчю кафедри теорії ймовірностей і математичної статистики та пам’яті М.Й.Ядренка (Київ, 2006);

* Міжнародній конференції "9th International Vilnius Conference on Probability Theory and Mathematical Statistics" (Vilnius, Литва, 2006);

* XIII Всеросійській школі-колоквіумі із стохастичних методів (Йошкар-Ола, Росія, 2006);

* Міжнародній конференції "Простір Скорохода. 50 років по тому." (Київ, 2007);

* засіданні наукового семінару кафедри прикладної математики Кіровоградського державного педагогічного університету імені Володимира Винниченка (Кіровоград, 2007);

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

* постійно діючому науковому семінарі "Проблеми сучасної криптології" (Київ, 2007).

Публікації. За результатами дисертаційної роботи опубліковано 9 наукових праць [1] - [9]. З них три статті в фахових виданнях з переліку, затвердженого ВАК України, [7] - [9], та шість тез [1] - [6] у матеріалах міжнародних конференцій.

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

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

(1)

де

(2)

Будемо вважати, що матриця має принаймні стовпців так, що для задання розподілів (1) є коректним.

Позначимо ранг матриці і покладемо

Основними результатами другого розділу є теореми 2.1.1, 2.2.1 про оцінки швидкості зближення розподілу випадкової величини до граничного () розподілу, та теореми 2.4.1, 2.4.4 про оцінки ймовірності сумісності неоднорідної системи лінійних випадкових рівнянь у полі

Теорема 2.1.1 Нехай виконуються умови (1), (2),

(3)

Тоді для

де

якщо до того ж виконується

(4)

то

якщо мають місце (4) і

(5)

то

якщо мають місце (4) і

(6)

то

Зауваження 1. Отримання верхніх та нижніх оцінок коефіцієнта при зазначених в теоремі 2.1.1 умовах ґрунтується на використанні його явного виду, встановленого в підрозділі 2.1 дисертації.

На відміну від теореми 2.1.1, в теоремі 2.2.1 припускається, що відношення задовольняє нерівності

(7)

а елементи матриці , , - незалежні випадкові величини з розподілами

(8)

де задовольняє умову (2).

Будемо вважати, що матриця має принаймні рядків так, що для задання розподілів (8) є коректним. Покладемо

Теорема 2.2.1 Нехай виконуються умови (2), (7), (8).

Тоді для

де

якщо до того ж виконується

(9)

то

якщо мають місце (9) і то

якщо мають місце (9) і то

Теореми 2.1.1 та 2.2.1 дозволяють отримати граничні теореми для розподілу рангу слабкозаповненої випадкової матриці у полі при заданому відношенні Наведемо деякі з них.

Теорема 2.3.2 Нехай виконуються умови (1) - (4) і Тоді для фіксованого, має місце співвідношення

Теорема 2.3.4 Нехай виконуються умови теореми (2), (7) - (9) і Тоді для фіксованого, має місце співвідношення

Розглянемо неоднорідну систему лінійних рівнянь у полі

(10)

де елементи -матриці, , - незалежні випадкові величини з розподілами (1), (2). Вектор-стовпець утворений з незалежних випадкових величин які приймають значення 0 та 1,

(11)

де випадкова величина не залежить від випадкових величин ,. Вектор є невідомим -вимірним вектор-стовпцем.

Позначимо ймовірність того, що система (10) є сумісною системою. За допомогою теореми 2.1.1 доведена

Теорема 2.4.1 Нехай виконуються умови (1) - (3) та (11). Тоді

де,

якщо до того ж виконуються умови (4) та

(12)

то

якщо виконується умова (4), то

якщо мають місце (4) і (5), то

якщо мають місце (4), (5) та (12), то

якщо мають місце (4) та (6), то

якщо мають місце (4), (6) та (12), то

Зауваження 2. Отримання верхніх та нижніх оцінок коефіцієнтів, при зазначених в теоремі 2.4.1 умовах ґрунтується на використанні їх явного виду, встановленого в підрозділі 2.4 дисертації.

Теорема 2.4.1 дозволяє встановити наступний результат.

Теорема 2.4.3 Нехай виконуються умови теореми 2.4.1 і при та. Тоді

Зауваження 3. З теореми 2.3.2, теореми 2.3.4 та теореми 2.4.3, як наслідок, випливають відповідно теорема 3.3.1, теорема 3.3.2 та теорема 3.3.3 з монографії Колчіна В.Ф. (Колчин В.Ф. Случайные графы. – М. Физматлит, 2004. – 256 c.)

Розділ 2 завершується розглядом неоднорідної системи лінійних рівнянь у полі

де елементи -матриці, , - незалежні випадкові величини з розподілами (2), (8). А саме, за допомогою теореми 2.2.1 доведена

Теорема 2.4.4 Нехай виконуються умови (2), (7), (8) та (11). Тоді

якщо до того ж виконуються умови (9) та

де то при

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

Позначимо подію, яка полягає у тому, що матриця має нульових рядків та нульових стовпців.

Покладемо , фіксоване число довільного знаку.

Теорема 3.1.2 Нехай, , - незалежні випадкові величини з розподілом

де

(13)

Тоді для фіксованих

(14)

(15)

При доведенні теореми 3.1.2 використовувалось наступне співвідношення

(16)

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

, (17)

за умови. Рівність (16) представляє самостійний інтерес і має місце в умовах теореми 3.1.2.

В дисертації наведено наслідки з теореми 3.1.2, одним з яких є наступний.

Наслідок 3.1.2. Нехай, , - незалежні випадкові величини з розподілом

де і задовольняють (13) та

Тоді для фіксованих мають місце (14) та (15).

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

Перед тим, як сформулювати основні результати розділу 4, уведемо наступні позначення.

Нехай - подія, яка полягає у тому, що матриця коефіцієнтів системи (17) має одиничних рядків та одиничних стовпців.

Покладемо - кількість нетривіальних розв'язків системи (17), , - фіксоване число довільного знаку. Припустимо, що, , - незалежні вектори у полі Поряд з (17) розглянемо скорочену систему рівнянь

(18)

число нетривіальних розв'язків якої позначимо Нехай індикатор події: вектор є розв'язком системи (18). Тоді Для числа одиничних компонент (0, 1)-вектора приймемо запис

Теорема 4.1.1. Нехай для деяких послідовностей

де максимум береться по і множині наборів -вимірних (0,1)-векторів, для яких .

Тоді

(19)

(20)

(Тут - символ додавання у полі).

За допомогою теореми 4.1.1 отримано граничний розподіл рангу матриці, утвореної незалежними випадковими величинами у полі за умови відсутності в ній одиничних ліній.

Теорема 4.2.1. Нехай, , - незалежні випадкові величини з розподілом

де

Тоді мають місце (19) та (20).

Зазначимо, що в умовах теореми 4.2.1 має місце наступне співвідношення

, (21)

яке представляє самостійний інтерес і використовувалось при доведенні теореми 4.2.1. Обґрунтування рівності (21) спирається на теорему 4.2.2 про явний вигляд математичного сподівання випадкової величини за умови.

Теорема 4.2.2. Нехай, , - незалежні випадкові величини з розподілом .

Тоді

де розповсюджується на всі набори

,

,

,

, , , , , ,

, ,

,

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

ВИСНОВКИ

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

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

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

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

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

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

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Масол В.И., Поперешняк С.В. О распределении ранга случайной булевой матрицы вне области инвариантности И.Н. Коваленко // International Conference Modern Problems and New Trends in Probability Theory. Abstracts. Chernivtsi, June 19-26, 2005. – Vol. II. – P. .

Масол В.І., Поперешняк С.В. Розподіл рангу випадкової булевої розрідженої матриці і його застосування // Шевченківська весна: Матеріали Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених, присвяченої 15-й річниці незалежності України. Київ, 2-3 березня 2006. – Вип. IV: У 3-х част. – Ч.1. – C. 321-322.

Масол В.І., Поперешняк С.В. Про одне застосування граничного розподілу рангу випадкової розрідженої булевої матриці // International Conference Modern Stochastics: Theory and Applications. Conference Materials. Київ, 19-23 червня 2006. – C. 52-53.

V. Masol, S. Popereshnyak. Some properties of the distribution of the rank of a spase random matrix over a field GF(2) // 9th Vilnius Conference on Probab. Theory. Abstracts. Vilnius, June 25-30, 2006. – P. 228-229.

Масол В.И., Поперешняк С.В. Асимптотика распределения некоторых характеристик случайной булевой матрицы // Обозрение прикладной и промышленной математики. – Москва: ТВП. – 2006. –Т. , Вып.6. – С. 1032 -1033.

Masol V.I., Popereshnyak S.V. The asymptotic of the distribution of the rank of a random matrix over the field GF(2) // Skorokhod Space. 50 Years On. International conference. Abstracts. Kyiv, June 17-23, 2007. – Book 2, Sect. 7-8. – P. 126.

В.І. Масол, С.В. Поперешняк. Про сумісність одного класу лінійних випадкових булевих рівнянь // Вісник Київського університету. Серія фіз.-мат. – 2006. – №3. – C. 29-36.

Masol V.I., Popereshnyak S.V. Poisson estimates of distribution of the rank of a random matrix over the field GF(2) // Theory of Stochastic Processes. – 2006. – Vol. 12(28), №1-2. – P. 106-115.

Масол В.И., Поперешняк С.В. Граничний розподіл числа нетривіальних розв'язків системи лінійних випадкових булевих рівнянь з розрідженою матрицею коефіцієнтів // Прикладна статистика. Актуарна та фінансова математика: Наук. журнал/ Донецький нац. ун-т. – 2006.– № 1-2. – C. – 126.

АНОТАЦІЯ

Поперешняк С.В. Розподіли рангів слабко- та сильнозаповнених випадкових матриць у полі). - Рукопис.

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

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

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

АННОТАЦИЯ

Поперешняк С.В. Распределения рангов слабо- и сильнозаполненных случайных матриц в поле). - Рукопись.

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

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

В научной литературе слабозаполненные случайные матрицы над полем называют также матрицами с малым числом единиц, разреженными матрицами. Особенностью слабозаполненной /сильнозаполненной/ случайной матрицы над полем является то, что распределения ее элементов не удовлетворяют условиям теоремы инвариантности Коваленка И.Н. (1975). Распределение ранга слабозаполненной случайной матрицы рассматривалось многими авторами. При этом основное внимание уделялось получению предельных () распределений в предположении независимости и одинаковой распределенности элементов матрицы, а также специальной взаимосвязи между числом строк и числом столбцов. Предельное () распределение ранга сильнозаполненной -матрицы, элементы которой независимые случайные величины с одним и тем же распределением, следует из теоремы Cooper C. (2000), посвященной изучению ранга -матрицы с ограничениями на количество ее нулевых и единичных линий.

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

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

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

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

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

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

ANNOTATION

Popereshnyak S.V. Distributions of ranks of sparse and saturated Random Matrices in the Field GF(2). - 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.

In the thesis distributions of ranks of sparse and saturated random matrices above a two-elements field are investigated. Estimations of the rate of the convergence of distribution of a rank sparse the random matrix formed not necessarily by identically distributed elements, to Poisson distribution are found under different assumptions about the relations of the number of its columns. The limiting () theorems of distribution of a rank of a sparse random matrix are proved. The estimations of probability of compatibility of inhomogeneous system of the linear equations with the sparse matrix of coefficients and random free members. Known results, which concern asymptotic () probability of compatibility of the systems of the equations above are generalized. The theorem about limiting () distribution of a rank of the sparse random matrix is proved under conditions of existence of the fixed number of zero rows and columns and under the fixed value of a difference in it. Based on the established general theorem about limiting () distribution of a rank of a random matrix under conditions of absence of unity rows and columns and under fixed value of a difference in it, the theorem about limiting () distribution of a rank saturated the matrix formed by independent random variables is proved, under conditions of absence of unity lines and.

Key words: sparse random matrix, saturated random matrix, asymptotic of distributions of a rank, field, estimations of the rate of the convergence.