Умови збіжності до нуля ймовірності існування розв'язків системи випадкових рівнянь з n невідомими над полем GF(3) у заданій множині векторів при n, що прагне до нескінченності

Размещено на http://www.allbest.ru/

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

Умови збіжності до нуля ймовірності існування розв'язків системи випадкових рівнянь з невідомими над полем у заданій множині векторів при

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

АВТОРЕФЕРАТ

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

Ромашова Людмила Олександрівна

УДК 519.21

Київ - 2009

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

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

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

Масол Володимир Іванович,

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

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

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

статистики та актуарної математики

механіко-математичного факультету.

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

член-кореспондент НАН України

Великий Анатолій Павлович,

Житомирська філія Європейського університету,

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

інформаційних технологій;

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

Донченко Володимир Степанович,

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

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

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

теорії прийняття рішень.

Захист відбудеться «25» січня 2010р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.37 у Київському національному університеті імені Тараса Шевченка за адресою: 03022, м. Киів-22, пр-т Глушкова, 2, корпус 7, механіко-математичний факультет.

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

Автореферат розіслано «22» грудня 2009 р.

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

спеціалізованої вченої ради

Д 26.001.37 Моклячук М.П.

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

Актуальність теми. Характерними особливостями дослідження систем випадкових рівнянь над конкретною скінченною алгебраїчною структурою є знаходження оцінок ймовірності існування єдиного розв'язку системи рівнянь, асимптотичний аналіз ймовірності існування розв'язків у заданій множині. Про це свідчать публікації Коваленка І. М. (1971), Балакіна Г. В. (1973, 1995), Масола В. І. (1988), Копитцева В. О. (2004), Міхайлова В. Г. (2007).

В останні роки прикладні задачі, які пов'язані з розпізнаванням образів, використанням тризначної логіки (''так'', ''ні'', ''може бути''), із захистом інформації від несанкціонованого доступу, привели до необхідності розгляду систем рівнянь над полем, що складається з трьох елементів. Підтвердженням тому є роботи Courtois N., Klimov А., Patarin J., Shamir А. (2000), Міхайлова В. Г. (2007), Савєльєва Л. Я. (2007). Таким чином, розгляд систем випадкових рівнянь над полем - актуальна проблема. На шляху її дослідження важливо отримати відповідь на питання про асимптотичну поведінку ймовірності існування єдиного розв'язку вихідної системи.

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

Результати дисертаційної роботи лежать у руслі сучасних уявлень про методи математичного моделювання, зокрема, моделювання невизначеності та пов'язаного з ним дослідження спеціальних класів систем рівнянь. Розвиток цих методів викладено в працях Коваленка І. М. (1993), Великого А. П. (2006, 2009), Донченка В. С. (2007), Міхайлова В. Г. (2007), Копитцева В. О. (2002), Колчіна В. Ф. (1997), Левицької А. О. (1996) та інших фахівців.

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

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

* знаходження умов збіжності до нуля ймовірності існування розв'язків однорідної системи лінійних випадкових рівнянь з невідомими над полем в заданій множині векторів за ;

* отримання умов збіжності до нуля ймовірності існування розв'язків однорідної системи нелінійних випадкових рівнянь 2-го порядку над полем, що складається з трьох елементів в заданій множині векторів;

* встановлення умов збіжності до нуля ймовірності існування розв'язків неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем в заданій множині векторів.

Об'єктом дослідження є системи випадкових рівнянь над полем .

Предметом дослідження є необхідні і достатні умови збіжності до нуля ймовірності існування розв'язків системи випадкових рівнянь з невідомими над полем у заданій множині векторів при .

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

Наукова новизна одержаних результатів. Усі отримані результати є новими.

* Доведено теореми, які містять необхідні та достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи лінійних випадкових рівнянь над полем в заданій множині векторів.

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

* Доведено теореми про необхідні та достатні умови збіжності до нуля ймовірності існування розв'язків неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем в заданій множині векторів.

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

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

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

* сьомій Міжнародній Петрозаводській конференції ''Ймовірносні методи в дискретній математиці'' (Петрозаводськ, Росія, 2008);

* шостій Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених ''Шевченківська весна'', присвяченої 90-річчю з дня заснування Українського Студентського Наукового Товариства Київського Університету Святого Володимира (Київ, 2008);

* Міжнародній науковій конференції ''X Білоруська математична конференція'' (Мінськ, Білорусь, 2008);

* дев'ятому Всеросійському симпозиумі по прикладній та промисловій математиці (Волгоград - Волзький, Росія, 2008);

* Міжнародній конференції ''Stochastic analysis and random dynamics'' (Львів, 2009);

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

* засіданні постійно діючого наукового семінару ``Проблеми сучасної криптології'' при кафедрі математичних методів захисту інформації Національного технічного університету України ``Київський політехнічний інститут'' (Київ, 2009).

Публікації. За результатами дисертаційної роботи опубліковано три статті у фахових виданнях ([1]-[3]) з переліку, затвердженого ВАК України, та п'ять тез доповідей на міжнародних конференціях ([4]-[8]).

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

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

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

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

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

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

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

(1)

де , , та - символ додавання у полі , яка задовольняє умову , а саме:

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

Позначимо - сукупність усіх -вимірних векторів, компоненти яких належать полю .

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

Нехай .

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

(2)

Зокрема, , де , , , де , .

Основним результатом другого розділу є теорема 2.1 про необхідні і достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи лінійних випадкових рівнянь з невідомими над полем у множині за .

Нехай випадкова величина дорівнює кількості розв'язків системи (1), які належать множині .

Теорема 2.1. Нехай виконуються умови та , , де , .

Тоді умова

 (3)

де , , є достатньою, а умова за , є необхідною для того, щоб мало місце співвідношення , .

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

Лема 2.1. Якщо виконується умова , то математичне сподівання випадкової величини дорівнює

де

Позначимо .

Лема 2.2. Якщо виконується умова , то другий факторіальний момент

випадкової величини дорівнює

де

cумування відбувається за всіма такими, що , , та ; параметри , визначаються відповідно рівностями , , , .

В теоремах 2.2 та 2.3 другого розділу знайдено необхідні і достатні умови збіжності до одиниці ймовірності існування єдиного розв'язку системи (1).

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

Основними результатами третього розділу є: теорема 3.1, в якій отримано необхідну та достатню умови збіжності до нуля ймовірності існування розв'язків зазначеної системи над полем у множині за ; теореми 3.2 та 3.3, в яких знайдено необхідні та достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи нелінійних випадкових рівнянь 2-го порядку над полем в заданих множинах та за умови, що .

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

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

(4)

де , , яка задовольняє умову , а саме:

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

Позначимо , де - число ненульових компонент вектора .

Нехай кількість розв'язків , , системи (4).

Теорема 3.1. Нехай виконуються умови та

(5)

де , . Тоді умова , де , , за , є достатньою, а умова

(6)

де за , є необхідною для того, щоб , .

Позначимо підмножину множини і, крім того, довільні вектори належать тоді і тільки тоді, коли виконується співвідношення (2).

Нехай випадкова величина дорівнює кількості розв'язків системи (4), які належать множині .

Теорема 3.2. Нехай виконуються умови та , де , .

Тоді умова (3) є необхідною та достатньою, для того, щоб мало місце співвідношення , .

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

Нехай випадкова величина дорівнює кількості розв'язків системи (4), які належать множині .

Теорема 3.3. Нехай виконуються умови та (5).

Тоді умова (3) є необхідною та достатньою, для того, щоб мало місце співвідношення , .

За однакових припущень на розподіли ненульових коефіцієнтів в теоремах 3.1 та 3.3 знайдено необхідні та достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи нелінійних випадкових рівнянь 2-го порядку над полем у заданих множинах векторів.

Теореми 3.2 та 3.3 відрізняються від теореми 3.1 введенням спеціальних множин та , яким можуть належати розв'язки вказаної системи. Введення зазначених множин дозволило поєднати необхідну та достатню умови в теоремах 3.2 та 3.3. На відміну від теореми 3.3, в теоремі 3.2 змінено інтервал, якому належать розподіли коефіцієнтів.

При обґрунтуванні теорем третього розділу були використані наступні твердження.

Лема 3.1. Якщо виконується умова , то

Де

 (7)

Лема 3.2. Якщо виконується умова , то

теорія система рівняння поле

де визначається рівністю (7).

Лема 3.3. Якщо виконуються умови , то

(8)

де

(9)

cумування відбувається за всіма такими, що ; в рівності (8) елементи множини задовольняють співвідношенням , , ; параметри , визначаються відповідно рівностями

 (10)

Лема 3.4. Якщо виконується умова , то

де визначається співвідношенням (9); сумування відбувається за всіма , , такими, що , , та ; сумування відбувається за всіма , , такими, що , , та ; параметри , , визначаються рівностями (10).

Четвертий розділ містить умови збіжності до нуля ймовірності існування розв'язків неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем в заданій множині векторів.

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

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

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

(11)

де , , яка задовольняє умову , а саме:

1) коефіцієнти , , - незалежні випадкові величини, які приймають значення з ймовірністю , , і значення з ймовірністю ;

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

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

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

(12)

де - ціле невід'ємне число.

Нехай випадкова величина дорівнює кількості розв'язків системи (11), які належать множині .

Теорема 4.1. Нехай виконуються умови , (12) та

, ,

де ;

,

де ;

,

де , , , , за ;

(13)

де , за .

Тоді умова (6) є необхідною і достатньою для того, щоб ймовірність події задовольняла співвідношенню .

В дисертаційній роботі наведені приклади виконання умов теореми 4.1.

Позначимо кількість розв'язків , , системи (11), які відмінні від , тобто розв'язків, що належать множині .

Теорема 4.2. Нехай виконуються умови , , , та

(14)

де .

Тоді умова (6) є необхідною і достатньою для того, щоб виконувалося співвідношення

(15)

Теорема 4.3. Нехай виконуються умови ,

,

де за та

(16)

де . Тоді умова (6) є необхідною і достатньою для того, щоб виконувалося співвідношення (15).

Відмінність теорем 4.2 та 4.3 полягає в різних припущеннях на кількість ненульових компонент істинного розв'язку системи (11), і як наслідок цього, появу різних інтервалів для розподілів ненульових коефіцієнтів (див. умову (14) теореми 4.2 та умову (16) теореми 4.3) неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем .

Зауважимо також, що необхідна та достатня умова збіжності до нуля ймовірності існування розв'язків випадкової системи (11) над полем в теоремі 4.1 отримано за умови, що , (це випливає із співвідношення (13)). В теоремах 4.2 та 4.3, на відміну від теореми 4.1, припускається, що для довільного .

Позначимо , , , .

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

Лема 4.1. Якщо виконується умова , то ,

(17)

де

,

сумування , та здійснюється за всіма , та , таким, що , , ; в рівності (17) числа задовольняють співвідношенням ; .

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

ВИСНОВКИ

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

У даній роботі отримано наступні результати:

* знайдено необхідні і достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи лінійних випадкових рівнянь над полем у множині за (розділ 2);

* встановлено необхідні і достатні умови збіжності до нуля ймовірності існування розв'язків однорідної системи нелінійних випадкових рівнянь 2-го порядку над полем в заданих множинах за (розділ 3);

* доведено необхідну і достатню умову збіжності до нуля ймовірності існування розв'язків неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем у множині за (розділ 4);

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

[1] Ромашова Л. О. Теореми існування єдиного розв'язку системи нелінійних випадкових рівнянь у полі / В. І. Масол, Л. О. Ромашова // Прикладна статистика. Актуарна та фінансова математика: Наук. журн. - 2007. - № 2. - C. 118-135.

[2] Ромашова Л. О. Теорема існування єдиного розв'язку однорідної системи випадкових рівнянь у полі / В. І. Масол, Л. О. Ромашова // Науковий вісник Ужгородського університету. Сер. матем. і інформ. - 2008. - Вип. 17. - С. 145-160.

[3] Ромашова Л. О. Необхідні і достатні умови існування єдиного розв'язку однорідної системи лінійних випадкових рівнянь над полем / В. І. Масол, Л. О. Ромашова // Український математичний вісник. - 2009. - Т.6, № 1. - С. 97-112.

[4] Ромашова Л. О. Необхідна і достатня умова існування єдиного розв'язку системи нелінійних випадкових рівнянь у полі / В. І. Масол, Л. О. Ромашова // Шевченківська весна: Матеріали Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених, присвяченої 90-річчю з дня заснування Українського Студентського Наукового Товариства Київського Університету Святого Володимира. - 2008. - Вип. VІ, ч.3. - С. 34-36.

[5] Ромашова Л. А. Некоторые свойства систем нелинейных случайных уравнений над полем / В. И. Масол, Л. А. Ромашова // Обозрение прикладной и промышленной математики (Седьмая Международная Петрозаводская конференция ''Вероятносные методы в дискретной математике''. Тезисы докладов. Часть I). - М.: ТВП. - 2008. - Т. 15, вып. 3. - С. 563-564.

[6] Ромашова Л. А. О единственности решения в заданном множестве векторов однородной системы нелинейных случайных уравнений над полем / В. И. Масол, Л. А. Ромашова // Международная научная конференция X «Белорусская математическая конференция»: Тезисы докладов. - 2008. - Ч. 5. - С. 13.

[7] Ромашова Л. А. Критерий существования единственного решения неоднородной системы нелинейных случайных уравнений над полем полем / В. И. Масол, Л. А. Ромашова // Обозрение прикладной и промышленной математики (Пятнадцатая Всероссийская школа-коллоквиум по стохастическим методам). - М.: ТВП. - 2009. - Т. 16, вып. 1. - С. 124-125.

[8] Romashova L. Conditions comparison of existence of an unique decision of the system of the random equations over the finite fields / Volodymyr Маsol, Liudmyla Romashova // International Conference ''Stochastic analysis and random dynamics'': Abstracts: [June 14-20, 2009 Lviv, Ukraine]. - 2009. - P. 157-158.

АНОТАЦІЯ

Ромашова Л. О. Умови збіжності до нуля ймовірності існування розв'язків системи випадкових рівнянь з невідомими над полем у заданій множині векторів при . - Рукопис.

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

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

Отримано необхідні і достатні умови збіжності до одиниці ймовірності існування єдиного розв'язку для однорідної системи лінійних випадкових рівнянь та для неоднорідної системи нелінійних випадкових рівнянь 2-го порядку над полем .

Знайдено необхідні і достатні умови збіжності до нуля ймовірності існування розв'язків систем випадкових рівнянь у заданих множинах. Вказані умови знайдені для однорідної системи лінійних випадкових рівнянь, для однорідної системи нелінійних випадкових рівнянь 2-го порядку та для неоднорідної системи нелінійних випадкових рівнянь 2-го порядку.

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

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

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

Размещено на Allbest.ru

...