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

ВВЕДЕНИЕ.

ГЛАВА I. РАЗДЕЛЯЮЩИЕ СИСТЕМЫ РАЗБИЕНИЙ КОНЕЧНОГО

МНОЖЕСТВА.

§1.1. Основные понятия.

§1.2. Связь ме:эдуКп.Л) - и -планами.

§1.3. Построение Fvs.) -планов на основе кодов

Радемахера.

§1.4. Границы длинКСп.^.)'- и Ы Сп.,4К.) -кодов.

ГЛАВА П. БЛОКОВАЯ ПЕРЕДАЧА ИНФОРМАЦИИ В ОТМИРШЦЕМ КАНАЛЕ МНОЖЕСТВЕННОГО ДОСТУПА С ОБРАТНОЙ СВЯЗЬЮ К ПОСЛЕДОВАТЕЛЬНЫЕ ПЛАНЫ ЗКС1ШРИМЕНТ0В

ДЛЯ ЛИНЕЙНОЙ МОДЕМ.

§2.1. Постановка задачи.

§2.2. Рекуррентный метод получения верхних границ.

§2.3. Диаграммный метод получения верхних границ.

ГЛАВА Ш. ПОСЛЕДОВАТЕЛЬНЫЕ И СЛУЧАЙНЫЕ ПЛАНЫ ЭКСПЕРИМЕНТОВ

ДЛЯ ЛИНЕЙНОЙ МОДЕЛИ С УСЛОВИЕМ НЕСОИЗМЕРИМОСТИ.

§3.1. Основные понятия.

§3.2. Случайные планы экспериментов для линейной модели с условием несоизмеримости факторов над l-i',0-,1]

§3.3. Последовательные планы экспериментов для линейной модели с условием несоизмеримости факторов над TL

А. Вспомогательные результаты.

Б. Построение плана экспериментов.

Б, Оценка числа экспериментов в плане.

Многие сложные явления, зависящие от большого числа факторов, определяются достаточно точно лишь небольшим их числом, называемых "значимыми". Влияние остальных факторов несущественно и сравнимо с погрешностью измерений, проводимых при изучении явления, Эксперименты по поиску значимых факторов называются отсеивающими»

Одним из первых примеров применения отсеивающих экспериментов (ОЭ) были принятые в США. по предложению Р.Дор^мана [ 34 ] двухэтапные групповые проверки на реакцию Вассермана крови солдат, отправляемых на фронт, с целью обнаружения больных некоторым редким заболеванием. Во время массового обследования было замечено, что разумнее анализировать пробу крови целой группы людей. Если такая объединённая проба не содержит определённых антител, имеющихся только у больных, то, значит, ни один из обследуемых не болен. В противном случае среди них есть хотя бы один больной. Индивидуальное обследование проводилось лишь в тех группах, где было замечено наличие больных. Это значительно сократило число анализов, так как количество больных солдат невелико.

Аналогичные процедуры проверки крови доноров успешно апробированы в СССР по предложению М.Б.Малютова в отделении переливания крови Института хирургии им, А.В.Вишневского АМН СССР для выявления доноров, больных гепатитом. Соответствующие анализы используют дорогостоящие импортные реактивы и уменьшение их числа даёт большой экономический эффект.

К модели отсеивающих экспериментов по существу сводится проектирование систем технической диагностики (обнаружения неисправности) некоторых больших электронных комплексов бортовой аппаратуры (например, судов), если эти комплексы обладают избыточностью, т.е. продолжают выполнять свою задачу при выходе из строя небольшого числа элементов [II] . Другая такая модель возникает при кодировании заявок в сети ЭВМ с множественным доступом к каналу связи [ 3 ] .

В 1959 г. для планирования и анализа отсеивающих экспериментов был предложен метод, получивший в литературе название метода случайного баланса (МСБ). Он был опубликован в [32] со ссылкой на Ф.Саттерзвайта [40] , успешно црименявшего его в течение нескольких лет в промышленности. Основные идеи этого метода высказывались и ранее [28] . Вообще, метод случайного планирования имеет корни в Фишеровской идее рандомизации. МСБ вызвал резкую дискуссию [33] и был отвергнут большинством статистиков, основным возражением которых было постулируемое превосходство регулярного планирования над случайным. При этом упускалось из вида, что задача построения оптимального регулярного плана отсеивающих экспериментов сложна, в то время как случайное планирование оказывается весьма близким к оптимальному. Критике МСБ способствовала неясность, отсутствие каких-либо оценок применимости и эффективности случайного планирования в [40] . После дискуссии упоминание о МСБ исчезло со страниц зарубежной периодики.

В нашей стране по инициативе В.В.Налимова МСБ был освоен, модифицирован [27, 29, 30] и проверен на модельных и прикладных примерах, где во многих случаях он оказался весьма эффективным.

Первое продвижение по пути обоснования МСБ сделал Л.Д.Ме-шалкин [ 23, 24 ] . В последущем цикле работ [ 15 - 21 ] на модельных задачах была выяснена связь МСБ с теорией передачи информации, объяснившая многие казавшиеся парадоксальными рекомендации МСБ.

В шестидесятые годы А.Реньи опубликовал цикл исследований по применениям идей теории информации в математической статистике, среди которых к нашей теме непосредственное отношение имеют работы по методам поиска (см. [38] , а также обзор [IV] ). Эти исследования были вызваны логическим развитием теории, а не приложениями (хотя считают, что стимулом этих исследований явилось происшествие, в котором А.Реньи не смог найти причину неисправности автомобиля). Под влиянием работ А.Реньи появились по крайней мере два подхода в приложении идей теории информации к планированию эксперимента. Во-первых, это работы И.Вайда [2] , исследовавшего для общей дискретной схемы случайного планирования эксперимента вопрос об асимптотике средней вероятности ошибки. Во-вторых, это работа [41] Дж.Сриваставы. В ней для общей линейной модели без ошибок экспериментов находится условие однозначного восстановления всех значимых факторов, если их число не превосходит S .

В настоящее время работы по планированию отсеивающих экспериментов получили дальнейшее развитие. Появилась целая школа математиков, связанных с семинаром, работающим в МГУ, получен ряд весьма интересных результатов. Из них мы особенно отмечаем работы А.Г.Дьячкова [ 5 - 10 ] , М.Б.Малютова [15 - 21 ] , а также работы других математиков (см. [22, 25, 26] ).

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

В главе I изучаются статические К11- и планы и связанное с ними понятие разделяющей системы разбиений конечного множества. Понятие разделяющей системы было введено А.Реньи [37] в связи с задачами теории информации, рассматривалось Д.Катоной [35] и другими авторами (см. [I, 5, 17, 31, 42] ). —♦ —>

F(A>R-)"" и F(n,4K:) - планы введены в [17] для S = I. Нами установлена связь между FCn.Д)- иР(П,4К) - планами для произвольного 5 , а также получено выражение для длины JNKft/fc)- кот л да через длину некоторого определённого - кода.

Тогда:

Теорема I.I. Пусть П = гк^ >„ . >, ,, к п

5 ' 5+i и L u i> г svi

NU/\l) , ^е ^[Cri-С ^p/U+OJnpaUUZ,

S+l ftfu. L<t, r-iH

Индексы г и [ однозначно определяются из условий:

С L 6 U,., Ь) ) s+i

10,1, s} ? Кг > cvx - JL ) / С i> >, , г-гн s+i

Здесь и всюду в дальнейшем через Гх1 и \х] будем обозначать ближайшее сверку и снизу к. хеЕ. целые числа. Отметим, что для любых Хе 5R. и справедливы тождества: i^i -т ■ too Г*!] = f to^xl , I» i.

Через [ ft] будем обозначать множество натуральных чисел от I до а . 5

Следствие 1.2. Пусть кf, . ic. s 7 а >/ Ц К L . Тогда: ui

NCn., ) = Д) .

Получены нижние и верхние оценки величины и изучено её асимптотическое поведение в некоторых случаях.

Теорема 1.2. Пусть ^ = . = ъ = к. 4 n/Cs+i). Тогда: i^i—1. " a L~ lo^lK) 1 К-Ъ S

Отсюда при ь = I ползаем усиление результата Д.Катоны из [35]

Следствие 1.4. При rx^Sifv. справедливо неравенство: Ьх

N С п.,к.) = ^ в^СЛ/Ю а

- 1

Этот результат получен также независимо И.Вегенером см. [I, 421).

Следствие 1.5. Пусть к. > = к. s = к. = осп) приа-^+оо

Тогда: е* г и п

• С L+ ОС1>)

Следствие 1.6. Пусть ъ = осп) цри а -v <*> . Тогда: о8г* а ft

Теорема 1.3. Имеют место неравенства:

Cl+ ОС1)) s+ Z>L

4 j

2, cn.-о

Следствие 1.7. При rt »[( m.ax kl)-Cs + £ К-О] / I + 1

UUs справедливо равенство:

L=1 & L

L=L ITLOL^K^

14 Us

NC^,^) = l Ov-l)

S + E»4 1=1

Следствие 1.8. Имеют место неравенства:

Теорема 1.4» Пусть такое, что I К: .т к u-i п / I Kl . кТ \ I V1

1=1

Тогда N (.к-, ^ Но •

Следствие 1.9. Пусть 1 = Гlpt'M ^Р1 ^ = ^ ? • • • > s ^ s ?

S' где Е = 1 • K,t = о См) при t > s' . Тогда: 1

HU,^) = • и*°Ш> •

Отметим, что для s= s' = I результат этого следствия впервые получен в работе [35] , и для s = s' - вероятностными методами в работе [51 .

Следствие I.IQ. Пусть ^ t = ] при C = 1,.,S#4S7 э ' где се>о 7 о < <5 < 1 nt=o(jn) при £>$ . Тогда:.

1- е

- п. -- • ci+ocD) .

U-ev £ сР e=i

Б главе II изучается линейная модель поиска [ 36 ] двух дефектных элементов. Построена последовательная стратегия, улучшающая границы для числа экспериментов последовательных планов из работ [22, 361 . Обозначим через N(A,m.) минимальную длину последовательного плана, определяющего дефектные элементы в двух группах из п. и m элементов, каждая из которых содержит ровно по одному дефектному. Нами получен следующий результат. При а 4 га справедливо неравенство:

N(n,m.) 4 1 + Vi"tocj8nl+ £ocj J^] . (2.15)

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

Предположим, что имеются два источника, которые синхронно

СоС) , , , в дискретные моменты времени подают сигналы X е [О, I} ( = I, 2). Эти сигналы поступают в суммирующий канал с обратной связью и результат у € { О, I, 2 } передаётся без искажений адресату (рис.0.1).

С помощью неравенства (2.15) установлена новая нижняя граница Р Q. L области пропускной способности канала при блоковой передаче информации. На рисунке 0.2 приведена для сравнения простейшая верхняя граница этой области (граница кооперативного кодирования) Р S Т L .

Б главе III продолжается изучение МСБ для линейной модели, начатое в работах [20, 23, 24] .

Для случая несоизмеримости факторов над множеством (о, ± 1} нами указан метод анализа результатов случайных экспериментов, позволяющий с вероятностью не меньшей 1 - ( 0 < J> < I ) определить все факторы при условии, что проведено не менее обратная связь обратная связь а, о

Р = ( 0; I ), S

L = ( I; 0 ), Т Q = ( 0,75; 0,75 ). 0,58496; I ), ( I; 0,58496 ),

Рис.0.2.

ZK -f cn.-* + i) - 1о§г J> экспериментов. Ошибка в определении факторов исключается. Здесь через П- обозначено общее количество факторов, а через к. -количество значимых факторов, которое может быть заранее неизвестно и определится в ходе экспериментов.

На основе метода анализа случайных экспериментов построен алгоритм, определяющий номера и значения всех значимых факторов. Оценено математическое ожидание М ^ случайного момента Т остановки работы алгоритма в предположении, что известна верхняя граница & числа значимых факторов и : п.-к.) , к: 4 ь < а , +

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

Для случая несоизмеримости факторов над 7L построен последовательный план, определяющий все факторы не более чем за с • mito. (. и) + + ^ + 4 5 tn.а. • >П?- С1+оШ) экспериментов. Здесь а - общее количество факторов, - количество значимых факторов, к. —* + °о , П к: >> 2, ; с = - to^1 эе. - I < 1,7, где эе = 0,773. - корень уравнения К.СХ)=Х ; Ьлэс.) = - х tocj^x - с 1-х) focj^Cl-X) - энтропия Шеннона.

Основные результаты диссертации опубликованы в работах [ 12, 13, 14 .

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук профессору К.А.Рыбникову за руководство работой. Он также благодарен сотрудникам кафедры теории вероятностей механико-математического факультета МГУ М.В.Меныпикову и А.Г.Дьячкову за постановки некоторых задач и ценные советы при их обсуждении. Автор признателен участникам семинаров по комбинаторному анализу, теории информации и планированию эксперимента, коллективу кафедры теории вероятностей мех-мата МГУ за внимание и подцержку во время работы над диссертацией.

Автор выражает глубокую благодарность механико-математическому факультету М1У, его профессорам, преподавателям и сотрудникам, за переданные ему знания и годы, проведённые на факультете.

1. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982.

2. Вайда И. 0 случайном планировании экспериментов. Проблемы передачи информации, т. 1У, $ 4, 1968.

3. Гельфанд С.И., Прелов В.В. Связь со многими пользователями. -В сб. "Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика", 15, М.: ВИНИТИ, 1978.

4. Дискретная математика и математические вопросы кибернетики. Под редакцией С.В.Яблонского и О.БДупанова, т.1, М., 1974.

5. Дьячков А.Г. Лекции по теории информации. М.: МГУ, 1980.

6. Дьячков А.Г. С А . Gr. ) . Otv а ЗеагсА M.oolel of $atse Colas 7 Ргос. CotLoc^uxa. Ma- tlx. DocLe tat Is JctlXOS Bot^oU С Kesztkcty ) 7 Kun^ai^ , 19?^ .

7. Дьячков А.Г. Об одной модели поиска фальшивых монет. В сб. "Доклады У1 конференции по теории кодирования и передачи информации", ч. I, Москва - Томск, Научный совет по комплексной проблеме "Кибернетика", 1975.

8. Дьячков А.Г. 0 детектирующих матрицах. В сб. "Четвёртый международный симпозиум по теории информации". Тезисы докладов, ч. I, Москва - Ленинград, АН СССР, 1976.

9. Дьячков А.Г., Малютов М.Б, 0 слабо разделяющих планах.В сб. "Методы передачи и обработки информации", М.: Наука, 1980.

10. Дьячков А.Г., Рыков В.Б. Об одной модели кодирования для суммирующего канала с множественным доступом. Проблемы передачи информации, т. ХУЛ, в. 2, 1981.

11. Зубашич В.Ф., Лысянский А.В., Малютов М.Б. Блочно рандомизированный метод построения распределительных систем технической диагностики. - Изв. АН СССР, Техн. киб., В 6, 1976.

12. Лузгин В.Н. Разделяющие системы разбиений конечного множества. Комбинаторный анализ, выпуск 5, Изд-во ГЯУ, М., 1980.

13. Лузгин В.Н. Метод случайного баланса для линейной модели. -Комбинаторный анализ, выпуск 5, Изд-во МГУ, М., 1980.

14. Лузгин В.Н. О разделяющих системах разбиений конечных множеств. В сб. "Некоторые вопросы математики и механики", Изд-во М1У, М., 1981.

15. Малютов М.Б. Оценки необходимого числа экспериментов методом случайного баланса. В сб. "Тезисы докладов 17 Всесоюзной конференции по планированию и автоматизации эксперимента в научных исследованиях", ч. I, М., Изд-во МЭЙ, 1973.

16. Малютов М.Б. О рандомизированном планировании отсеивающих экспериментов. В сб. "Планирование и автоматизация эксперимента в научных исследованиях", М.: Сов. радио, 1974.

17. Малютов М.Б. Математические модели и результаты в теории отсеивающих экспериментов. Вопросы кибернетики, в. 35, М.: Сов. радио, 1977.

18. Малютов М.Б. Разделяющее свойство случайных матриц. Математические заметки, т. 23, $ I, 1978.

19. Малютов М.Б. Планирование отсеивающих экспериментов. -Теория вероятностей и её применения, т. ХХУ, № 3, 1980.

20. Малютов М.Б., Пинскер М.С. Замечание о простейшей модели метода случайного баланса. В сб. "Вероятностные методы исследования", М., Изд-во МГУ, 1974.

21. Малютов М.Б., Фрейдлина В.Л. Применение теории информации к одной задаче выделения значимых факторов. Теория вероятностей и её применения, т. ХУТП, В 2, 1973.

22. Меньшиков М.В., Хромов М.Н. Некоторые задачи последовательного планирования в теории отсеивающих экспериментов. -Комбинаторный анализ, выпуск 5, Изд- во М1У, М., 1980.

23. Мешалкин Л. Д. К обоснованию метода случайного баланса. -Заводская лаборатория, т. 36, $ 3, 1970.

24. Мешалкин Л.Д. Два замечания о поисковых экспериментах типа "случайного баланса". Вопросы кибернетики, выпуск 35, М.: Сов. радио, 1977.

25. Мятлев В.Д. Теоремы и алгоритмы об одной схеме последовательного поиска дефектных элементов. Вопросы кибернетики, выпуск 35, М.: Сов. радио, 1977.

26. Мятлев В.Д. Групповые проверки, минимизирующие среднюю длину. Вопросы кибернетики, выпуск 71, М.: Сов. радио, 1980.

27. Налимов В.В., Чернова Н.А. Статистические методы планирования экстремальных экспериментов. М.: Наука, 1965.

28. Протодьяконов М.М. Составление горных норм и пользование шли. М.: Госгориздат, 1932.

29. Слободчикова Р.И., Лапина З.С. Выделение значимых факторов методом случайного баланса с помощью многоуровневых планов. Заводская лаборатория, т. ЖЕХ, № I, 1973.

30. Слободчикова Р.И., Фрейдлина В.Л., Лапина З.С., Налимов В.В. Повышение эффективности метода случайного баланса. Заводская лаборатория, т. XXXII, № I, 1966.31. balanced Z.S. 0а a seaidi рго(э(хт. о| G. О.Н. K.atoaa. Stadia ScL . Matк. Киш^осг.

31. Llvxolsixom B. Setexn-arun.cj sulsets un.xaml| leolexperiments. Зигъеу of Statistical design. ah.d LlneaxHodth , CLtrbstexolotrrv , Nottfx RoCtcmcl. PиЦ. to. , 19 7 5.

32. Remjl A . On a рго^ет, of Infoxmcctlon. TLeoxij . "Mottk . in.st. Huix^olx. CLcccd. Scl 6 , 19 61.

33. Rci-l^L a . Oh. tie "Нхеог.^ of Txmdora Seated . ЬиЯ .СХтег. ticdk. Sot. , v. 71, 1 9 65.

34. Ri^seT ИЛ. MaxlmxtE oUttxmxnants in comkacttoxi^ Ih/besticjoitIons . CocacLolloLa Journal o| Matixenaati.cs , 8 , 19 5 6.

35. SattextfxwaLte F.E. R<xn.otom, feasance expexlmen.ta.tu>n.TecWometxlcs , V. 1 , 195 9.

36. Sxtbasta/boc J. N. We f^ex tWu| 4 «extent £lneaim.ocleEs . Cordxi. button. to CLpp Ileal Statistics , fcasel Luxol Stuttcja^t, (blittiOLUsei VetEacj , 197b.

37. Wegener I On Sepotxouictx^ systems *fcose eEeiueats axeSets of oct wuost K, elements . -Discxete Ha.t?ietuailcs ,Май, 19 79.

38. Vosenxxa^t Т.П., &еЦ{еп В., Sequential decoding , Wi.te.ij , New - London , 1861.

39. Лузгин B.H., Белокопытов А.Я. Об одной задаче последовательного планирования в теории отсеивающих экспериментов. У1 Международный симпозиум по теории информации. Тезисы докладов, часть I, Москва-Ташкент, 1984, стр.121-122.