О двух моделях планирования отсеивающих экспериментов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

:'Г8 ОД

"МОСКОЗСЙШ ^ОСУдаСТВЕШЫП УНИВЕРСИТЕТ ИИЕНИ Ц.В.ЛШОНССОЕА

^ЕШВЖО-"."ЛТЕ!'.'АТ1ЯЕСШ1й ФАКУЛЬТЕТ

/ '

На правах рукоплся

АЛЬ НАСЕР НАСЕР ШАЛЬ "О ДВУХ МОДЕЛЯХ ШАПИКШПЩ ОГСЕИВАИШХ ЭКСПЕРИМЕНТОВ"

/01.01.05. - Теория вероятностей и математическая стагисгяка./

Автореферат

диссертации на сокскатзг учёной степени ' кандидата физико-математических наук.

Москва - 1994

Работа выполнена на каЪедре теоглл вероятностей .-мвханико--математического факультета Московского государственного университета им. М.Б.Ломоносова

Научный руководитель - Доктор фязико-матег.:атических наук, профессор А.Г.ДыгцфВ.

Официальные оппоненты - Доктор физико-математических наук,

профессор Ы.Б.Малктоз; доктор физико-математических наук - А.К.Горбуаов.

Ведущая организация - Научный совет по комплексной проблем "¡кибернетика" РАН.

Защита диссертации состоится /Ш 1984 г.

В "16^" часов на заседании специализированного совета Д.055.05.04 при Московском государственном университете имени •Л.В.Ломоносова по адресу: П28£5, ГСП, Москва, Ленинские гора, МГУ, Механико-математический факультет, аудитория 1Е-24. . .

С диссертацией могло ознакомиться в библиотеке мехашгко--катематического факультета. МГУ / 14 этаж/.

Автореферат разослан " 1т " 1594 г.

/

Учёный секретарь специализированного " ' совета Д.053.05.С4 при Ы7 ' профессор Т.П.Лукашенко

-л-

Атгтуальность теми. После публикаций Реньи El], Каутсз-Синг-летэно ]i а аькже рада других авторов, стало шсрмлроват^ся важное нвцраалвпте 'агтвиамческой теории поиска, сввзаняое'с пря-ачпсанзм теорет'ж^-и^фориационного подхода к планированию эксперимента. Это паправленна поучило название теорий планирования (^^^з^дта^ссгзртарнгов (ПСЭ). С зрения методов исследо-

вания ЛОЭ находится на ст'тм теория вероятностей, интеиатической ciar;:ссаки, теории якфориадий и коибинаторшса. Неготчрыз результаты теории ПОЭ опноаиы в книге Альсведе-БегепзраГ 3 'I- Подробный анализ работ по данной тематике л прилоаенияи.ПОЗ киеетса в обзорной статье йалютозг [ Ц ] .

Тэсрия ПОЭ основана на идее использовать групповые проверки для уменьшения времени поиска небольшого числа эязчпшх факторов, ицеющчхся среди большого числа факторов. Наиболез важной для приложений является булева модель ПОЭ, когда результат проверки равен I, если среди группы проверяемых: факторов имеется хотя бы один значимый и - 0, если все проверяемые факторы незначиш.

Данная диссертация посвящена разработке методов теориии информации и комбинаторной теории кодирования для ксыедовакия некоторых обобщений булевой модели ПОЭ.

1). Eenyi A. On the 'theory of raedoa search. Boll. Ад er. Hath. Sos. , 1965t " v. 71, So 6, pp. 809-828.

2). Xauis 7?.H., Singleton B.C. ííonrandoa "oinary ouperiapssed codea.- IBES Trans. Inform. Theory, 1964, т. 10, Ко 4, pp. 365-577.

Цедь г^ботк. I) Построение границ длины раядощанрозавных статически йлзеов дал обобщенной но деля случайного поиска Рекы:.

2) Построение гранка скорости осЗобщгнккх дизъюнктивных кодов Г Б» о пазиваоишс когкд с даэыонкаивнкм расстоянием и списковым декодирование«. _ ,

Методы исслбБОвакий. При ропешн; поставленни. зад^ч применяются метод':1 теории вероятностей, теории инфориэаци, лкибютггорной теории кодирования л соиштастические метода анализа.

Нагнал навязка. Дня обобщенной модели случайного поиска ?зт; [ []полузж: следу>гдие результаты.

1. Построены (неааимпгоютескяе) верхняя и ниенчя гранты величины - вероятности яарушзняя свойства разделяеизсти случайного плана хшска.

2. Ъьщпелена логарифмическая асимптотика р2 как функции сксрос-т!'. плана.

3. Построены 1-стацз ^ксаситтоглчеокие) грани:?!! величины Р£ -вероятноехк ергдагй по ансамбли оскс'кн случайного плана поиска.

Вычислена аакихогака длпик У' -раздзлкпщаго плана [?1 > когда ^—> о .

3). Альсведе Р., Бйгелер И. Задачи поиска, Ц. "Мир", 1382."

4). Иалютоэ Планирование отсеиваявих экспериментов. 3 нн.: Математическая теория планирования эксперимента, "Каукс", 1983, с.З^о-Збэ.

5). Дьячков Л.Г.. Рыков £,3. Обзор теори дазздзнктквннх кодов. .Проо'лекы упрагяания к теории янфоркацни, хЭЗЗ, т. 12,й

с. 22Э-2¥;.

Для обобщенной кобели дйзъшстивних кодов получены следующие результаты.

5. Построзна верхняя граница скорости кода, оЗооцзвдая известную в комбинаторной теории кодирования [ 3 ] границу Ллоткина. С. С г'оиотью кег-ода случайного кодирования построена нижняя граница скорости ::ода и найдена асимптотика критического значения кодового расстояния, при превышении которого скорость кода равна нулч.

ДылюгегГ^я. Полученные результата приценяются для уточнения ранее известных границ длины статических плавов.

Апробация. Результаты диссертации дскладызадась на сеякнарв по теории йнфор!"ТлИ и планированию эксперимента на цех-мате МГУ в- 1992-ЭЗ годах ;: опубликованы в работах, ссызла ¡.а которые даны ■в конце ачюрефераяа.

Диссертация сосюит из введения и дзух глаз.

Содестзние работы.

В первой главе изучается следующая задача. Пусть Ы , Л1 и

6). Eyachkov A,Cr, 4ykov V.T., Basbad A.K. Sup_.fcrimpooed distance codes.-Problems of Control and Iafonnation Theory, 1569, v. 1С, Ho 4, pp.237-250.

7). Дт.ячков А.Г., Ыалвтов М.Б. О слабо раздеяявдих планах.-

В кн.: Методы передачи и обработки инфораада. М. "Наука", 1980, с. 87-1 №.

8). Галлагер Р.Г. Теория информации и надекная связь. М.

"Сов. радио", 1974.

, 1 ^ натуральные числа, [ К ] - инокество из

всех целых чнсез от D до К — 1 , а

фиксированный азЗор из К" целых чисел, удовлетворяющих услови-

ям

Al. ^ М. >/----; Л? /"11/ , 1 ,

(1)

Мв - M - ZI AU •

, /к-i

Рассмотрим икоаягсво , состоящее из всех M './ 1 ^

строк X - f ЭСЙЪ "X (г)> — ;х(М)) длины fA с элементами

У. С 6 [К ] » и®8 для каждой строки число позиций m = 1 M , в которых Х(№) = » Р^0 Мд , Ж е [ К ] • Введем на [ К 1 распределение вероятностей.

Ямя(Ч.<в,'ама>'......^(K-i)),

(2)

<2МФ - MA/M ; су*^ > <у и-1; .

Символом

) Q.Ci)> )}далее везде будем обоз-

начать произвольное фиксированное распределение вероятностей на [К ] , для которого ■

Пусть

flfftj = - - (3)

fco

энтропия Иеннош распределения Q. . Будеа использовать также стандартные сикзсшн Гй "J и j_ Л J для обозначения верхней и нижней целых частей действительного числа й. .

Пустъ X - случайная патрица из А^ строк и ?А столбцов, все строк которой получены путец выборки дапны N с возвра-

щением из мкояесгза *А(\ /И^} ) . Пусть 3£ = ансаибль таких матриц. Для онсаыбля' 3£ обозначим через Р2 -^ Ь С [ ] ) ~ вероятность того, что в цатрщз ^Х" существует хотя бц одна пара совпадают столбцов, а через ^ -= ~ зеР°ЯТН0СТЬ того, что для форсированного

]Г1 = 1, //\ , столбец с ноыерои (71 в матрице X" совпадает с хотя бы одним из остальных Д/| - 1 столбцов.

Отметим, что в ансамбле "X столбцы матрицы )С являются

зявиг.ишга. Этим ансамбль ЭС отличается ог ансамбля кодов с независимым! кодовыми словами (столбцами), каторг применяется

в теории информации [ 8"] лги доказательстве теорема кодирования.

Вероятности Р] и Р2 были зведены в работе! 1 ] | где была поставлена задача построения верхних и низших границ этих вероятностей. Для частного случая 2- такие гранты были получены

*[9 ] •

Цель перзой главы- обобщать метод случайного поиска Реши к построить при К У; 2 верхние и ниание границы вероятностей р,- , ( - \ >1 • Для описания границ удобно ввести параметр I? > о , .называемый скоростью [ 2 ] и положить

-I- - 1 I I.

Перейдем к перечислению результатов первой главы. В теоремах 1.1 - 1.3 исследуются границы вероятности £

9). Рашад А.К. Некоторые задачи теории планирования отсеивающих экспериментов. Кандидатская диссертация,. Ш7У, цеханико-ыатеыатический факультет, 1978.

Теотзеиа 1.1. Для любого й и либо го набора [ /VI ^ |

Р < ~- [-Л/Ег(Й,ем) } ,

где распоеделание определено (2), а показатель экспоненты

— /VI

Е2 CR.fi-) = нг(£) - гЯ, • (<о

'Ь1 _ .2

- 21 а^-А) . (5)

.41=0

Теорема 1.2., Для лвбою Я > С и любого набора [ ] при М = вероятность

- СХ Р [ - 2 N 1г () ] - ех? N £3

где распределение определено (2), функция (.£) задана в (4)-(5), а К-1 , '

Рассмотрим зеишмоткку данных границ, когда

К , Я /V—/И ;

1.М'£с-Й}] ^ = j . (6)

Теорема 1.3. В условиях (6) при О < ¡2 < Н2 I & )/2

Р2 = Г2 ОЧМ*] ) = у-

-7В работало] длй ансамбля ЭС к декретного канала без памяти бшш построены верхняя и киекяя асимитотпчзсхие границы (и шч;;сяена логарифмическая гаяттоглка) средней по X вероятнос-:и ошибки. Для накего частного случая канала без шуиа зта средняя 10 X вероятность ошибки совпадает с вероятностью Р4 и результат [1 о] означает, что в условиях (б) существует

» -МО'АЫ ) _ ■

-Г/ /71 -—---Ь^^М)^.) ,

у-^ с/э И

где

» К""1 1+/ ,/) = . (з)

11=. с

Наша цель - построить достаточно близкие друг другу нззе.кпто-тпческие верхнюю и имению границы Р, . Эти границы даны в те-ореыах 1.4 и 1.5, доказываемых с помощью методов, разработанных в Цй~\ . В формулировках теоре« используются обозначения (2), (5), (7) и (8).

Теорема 1.4. Для любого Я. у о и любого набора | М^ |

Ю). Дьячков Л.Г., Яолтырез Г.И. Асимптотика средней вероятности ошибки для одного ансаио'ля кодов с зависимыми кодовым слова»®. Проблемы управления и теории информации, 1Э82, т. II, й 5, с. 365-372.

Теорема 1.5. Для любого Я > О и любого набора | М^ |

(I--

где показатели экспонент

1^,0.) - Н2(<3) - гЬ

с (Я,Г »714* (-/Я О^Я] -~2 ~ ИГ <.г 1

Езвестно[д] , что функция ") (о. , определенная (5), есть монотонно возрастающая-выпуклая вверх функция параметра о , а значение - 0 . Показатель экспоненты Е,( , оп-

ределенный (?), есть кокэсонно кевозрасхающзл выпуклая вниз функция параметра к. > О . Причеи, при С Н , где Н ( - энтропия (3), Е4 С Й^О.) > О .а при £ Назначения Е^ С . Введем число

„ глот,!)! у 1Ш-И / = тю

Как следствие теорем 1.4 и 1.5 доказывается Теореца 1.6. При 0 £ < К^С-^в 1 слизнях (б)

где НгС(2-) определена (5).

Теорема 1.4 ознанает, что при О -С Ц <С Н ( С ) в условиях (6)

существует уС.1УП р Д/, [ ) - 0 '

//—? СО 1

С поцооьо некоторого обобщения неравенства Оано [ 8 ] доказывается

Теорема 1.8. В условиях (6) при Я > И ( Чг ) д

т.е. при > Н ( вероятность Р^ в условиях (б) не стремится к нулю.

Пусть X = И , ¿С ГГр/ , т. = 17м 1агрица из А/

строк и М столбцов с элементами Х(. С /тг) £ [ К ] • Обозначим через

Х- ........ Х-с/И)) (хс

строки (столбцы) матрицы уС • Пусть набор чиселудовлетворяет условиям (I). Введем следующее

Определение. Будем говорить, что матрица является

I! МдЦ - планом, если в кандой строке х£ > ¿ = , число позиций т. - I, Д\ , где X. Ш) = , не превосходит

Пусть -О. -11 ^ 11...... М I • Зафиксируем произвольный )| /И^ Ц -

-план 11 в соответствии с его столбцами Х{ ) . т-СХ^

разобьем на два непересекающихся подмножества

= -^(Х) -¡т • Чп^т , ход'; Р хип)) ;

Л2 = П^Х)3£^ - ^Скг)! *

Пусть | . Будем говорить, чтоЦ/У^Ц -плач X являет-

ся (иду, X ) ~РазДелЯЕШИМ планом Г у ] , если число элементов з ->2.2 не превосходит /у\ . Обозначим через

шшиаалгно возможное число строк [ $ ^ - раздзлядкего плана с № столбцами. В диссертации исследована асимптотика ятоЧ величины, когда

^ - Соп^ , » О , /'Л--

------(9)

[м-М] л -I .-КМ

Теозека 1.9. Б уолсзигп: (9) справедливо асимптпФ>;чес:гоз равен-стзо

где Н - энтропия (3).

Эта теорема квляетсь некоторым обоищаниеа результата, полученного в [ 1 ] 3 , для сличая ^ ~ О , который соотзетстзуег задаче Реньи £ I ] л комбинаторной постановке.

Во второй главе диссертации рассматривается проблема построения границ скорости обобщенных дизъюнктивных кодое 6 ] , незы-ваэюлх кодами с дизъюнктивным расстоянием и списковпм декодированием. Пусть i¿¡S<. > 1 ^ I - £ 1 Р < А/ целые числа, [ Д/ ] - множество целых чисел от I до /V , , ^ г{ , - подмножества [ N ] • Используя стандартные обозначения для теоретико-множественных операций и объема множества, введем следующее

II). Лузгин В.Н. Разделяющие системы разбиений конечного мнокест-ва. - В кн.: Комбинаторный анализ.- и. "Издательство МГУ", 1980, с, 39-45.

о ^

Определение. Семейство яож'-чскеств & { , > ' " ^ инсжества£/У] называется (cj jL / D ) -- секзГштзоц объема Г , если для любого набора из S + /. отличных друг от друга понсроз

>72, .»71,-. ...... I PL. » tit. .......» r/L , *

I L Hi <

выполнено условие

j U Я, x \J я,

Пусть Г CS ^ /У- 1«ахмиэльыо ьозкозный объчы^ Л. D}- семейства. Введем параметр J , о ¿L <J \ • Для фиксированных S , L vi d опрзделиы скорости

Р (J) - ^m -*-----

? //—j.« /V

iL)

Цель данной главк - получить верхние к нигние транкчк (<j ) .

В частном случае S - L = 1 рассматриваемая задача соответствует некоторой кодификации классической задачи кокбинаторной теории кодирования [ g ] по построению границ скорости кода, исправляющего V -1 oqi:uok. Другие частные случаи этой ксггбинаторн ной задачи исследовались ранее в теории дизьпнкгявнкх ;:одоз. йзу-чазмай в [5 3 случай D - ^ соответствует дизъюнктивным кодам со списковым декодировании.'.! с обьешэм списка' L ^ i -В случэс L~ 1 S ^ 2 грзншш скорости кода с дмзъвнкгаышы расстоянием построены бГ^ j .

Пусть [ & 3 ' = wa.-x.lo¿(О,. Определяй

Л- r-J- V/L

b*L [ <+l_ /

Обобщекие известной границы ПлогкинаГ 2 ] и верхней граница скорости, полученной в[61 дли - 1 , даст

Теорема 2.1. Для. любого с1 , о с. с!< 1 , скорость

ь

Ь помощью метода случайного кодирования для ансамбля кодов с независимым;: элемзктаии кодовых слов]_ь1до^а?^ы>тся

Теореиа 2.2. При 0<с/С£ скорость

/

12^ -и- ь ^ си)

Данный результат является обобщением некоторой шгакей оценки скорости, построенной в£6] для 1 . Поскольку рассттнис Кульбака К где равенство лишь при с*. = р , то из (1С)

и (II) вытекает зааное следствие, которое представляет собой основной результат второй главы. ^

Следствие 2.1. При 4 ^ скорость Ы) ~ О , а при

о < с/< с//4 скорость •

Автор благодарен своему научному руководителю Дьячкову Аркадию Георгиевичу за постановки задач, постоянное внимание и помощь в работе.'

Публикации по теке диссертации. I. Насер Аль Насер, Дьячков А.Г. Об одной комбинаторной задаче в теории дизъюнктивных кодов. Вест. Моск. ун-та, сер. I, Мех-кат.,.1993, Ё 4, с. 30-34.