Портал освітньо-інформаційних послуг «Студентська консультація»

  
Телефон +3 8(066) 185-39-18
Телефон +3 8(093) 202-63-01
 (093) 202-63-01
 studscon@gmail.com
 facebook.com/studcons

<script>

  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){

  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),

  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)

  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

 

  ga('create', 'UA-53007750-1', 'auto');

  ga('send', 'pageview');

 

</script>

Асимптотичні методи в задачах імовірнісної комбінаторики

Предмет: 
Тип роботи: 
Автореферат
К-сть сторінок: 
45
Мова: 
Українська
Оцінка: 

величини   (теорема 3. 7. 3).

Розділ 4. Дослідження дискретних схем комбінаторно-ймовірнісними методами. Четвертий розділ присвячено вивченню властивостей дискретних моделей, що застосовуються для аналізу поведінки певних характеристик керуючих пристроїв, зокрема, систем криптографічного захисту інформації.
У §4. 1 описується така схема розміщення.   пронумерованих ячейок розташовані послідовно по колу, тобто таким чином, що за  -ю ячейкою йде ячейка з номером  , а їй передує ячейка з номером  . В ячейках розташовуються   комплектів частинок по   частинок в кожному так, що в окремому комплекті частинки з рівною ймовірністю займають будь-які   ячейок, що йдуть поспіль, а розташування частинок різних комплектів незалежні. Будемо казати, що два комплекти перетинаються, якщо існує хоча б одна ячейка, яка містить частинки з обох комплектів. Позначимо   випадкову величину, рівну числу комплектів, що перетинаються рівно з   іншими комплектами;   – число комплектів, що мають перетин не більше ніж з   іншими комплектами.
Наведена схема розміщення використовується при аналізі датчиків псевдовипадкових послідовностей (що, як відомо, мають певний період) та методів вибору серій «відрізків» знаків послідовності для застосування в системах захисту інформації, наприклад для криптографічних ключів. Тут важливо знати, зокрема, ймовірність перетину таких відрізків, який створює небезпеку системі захисту. Перетин відрізків псевдовипадкових чисел може також викликати помилки при обчисленнях на ЕОМ. Деякі інші схеми розміщення частинок на колі досліджувалися в роботах В. Н. Сачкова, Г. І. Івченка, В. Г. Михайлова.
У §4. 1 розвивається комбінаторно-ймовірнісний метод асимптотичного дослідження при   факторіальних моментів   випадкових величин   для будь-якого фіксованого   і «не дуже швидко» зростаючих  . У §4. 2, 4. 3 використовуються експоненціальні твірні функції факторіальних моментів для дослідження граничного розподілу випадкових величин   і   при  ,     та будь-якому фіксованому  . Для отримання скінченних формул для твірних функцій використовувалися спеціальні перетворення початкових рядів, через які були виражені твірні функції згідно з результатами §4. 1. Граничний розподіл, наприклад, випадкової величини  ,   може збігатися з розподілом деякої лінійної комбінації незалежних пуассонівських випадкових величин з різними параметрами, з гауссівським розподілом. Наводяться також асимптотичні результати для неперервного аналогу цієї задачі.
Параграф 4. 4 присвячено дослідженню характеристик варіаційного ряду ймовірностей серій відмінних наслідків у поліноміальній схемі іспитів. Розглянемо поліноміальну схему іспитів з   наслідками та ймовірностями появи кожного наслідку  ,  ,  . Для визначеності будемо вважати, що  . Нехай після   іспитів з'явилося   різних наслідків:   при  . Ймовірність   появи такого вектора   за умови, що всі   відмінні, визначається за формулою .
На множині всіх векторів   вимірності   таких, що  ,  ,   при  , останнє співвідношення задає ймовірнісний розподіл,  . Можна сказати, що при реалізації поліноміальної схеми ми розглядаємо тільки випадки появи   попарно різних наслідків. Така схема використовується, наприклад, при генеруванні безповторних випадкових вибірок, випадкових розміщень комплектів частинок по ячейках, побудові випадкових функцій, давачів випадкових чисел тощо. Для відповідних застосувань важливо знати, як залежить розподіл ймовірностей на  -вимірних векторах   від ймовірностей наслідків поліноміальної схеми  ,  . Введемо наступну характеристику розподілу ймовірностей  : для довільного фіксованого  ,  , визначимо величину   як найменше можливе число векторів  , таке, що сума їх ймовірностей буде не меншою  . Функція   залежить від  ,  ,   та ймовірностей  ,  . Властивості та характеристики   використовується при аналізі якості та ефективності генераторів випадкових функцій, пристроїв захисту інформації, деяких схем комутації тощо.
У рівноймовірному випадку при  ,   маємо   і для   будуть справедливі різні асимптотичні формули, наприклад, така: при. Існують нерівноймовірні випадки, для яких асимптотичні значення   визначаються значеннями  .
У випадках, що не зводяться до рівноймовірних, навіть один виділений по ймовірності наслідок поліноміальної схеми істотно впливає на розподіл ймовірностей на  -векторах та поведінку величини  .
Розглянемо схему з наступними значеннями ймовірностей  :  ,  .
У пункті 4. 4. 3 §4. 4 проведено повний комбінаторний аналіз цієї схеми та описано алгоритм точного визначення   для будь-яких скінченних  ,   і  , що потребує обчислення не більше ніж   доданків, кожний з яких містить факторіальні степені з показником, не більшим  . Асимптотичний аналіз описаної схеми з одним виділеним більш ймовірним наслідком дав змогу знайти прості оцінки для випадкової величини   у наступних трьох випадках.
Нехай в попередній поліноміальній схемі з одним виділеним наслідком  , а  ,   та   залишаються фіксованими. Тоді буде справедливим наступне правило для отримання асимптотичних оцінок  : якщо  , то  , якщо  , то  , де  .
Нехай у поліноміальній схемі з ймовірностями  ,   при   значення   та   фіксовані, а   так, що  . Тоді вся ймовірнісна міра асимптотично зосереджена на перших   векторах   (вважаючи їх впорядкованими по спаданню їх ймовірностей). Завжди існує деяке  , таке, що  . Асимптотична оцінка   та значення   задаються тими ж співвідношеннями, як і в першому випадку.
 
Отримані наступні асимптотичні оцінки для  : якщо  , то  ; якщо  , то   .
Чим більше  , тим більша частина
Фото Капча