Дискретные преобразования конечных распределений рациональных вероятностей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

на правах рукописи УДК 519.714.2

Колпаков Роман Максимович

ДИСКРЕТНЫЕ ПРЕОБРАЗОВАНИЯ КОНЕЧНЫХ РАСПРЕДЕЛЕНИЙ РАЦИОНАЛЬНЫХ ВЕРОЯТНОСТЕЙ

(специальность 01.01.09 — дискретная математика и математическая кибернетика)

АВТОРЕФЕРАТ

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

Москва 2004

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

Научный консультант:

доктор физико-математических наук, профессор А.Б. Угольников

Официальные оппоненты:

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

Ведущая организация:

Институт математики Сибирского отделения РАН

Защита диссертации состоится " 1 $ " ^^ро С- -¿-^__ 2005 г.

в 16 час. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им М.В. Ломоносова по адресу: 119992, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

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

Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор

В.Н. Чубариков

Общая характеристика работы

Актуальность темы. Работа посвящена вопросам реализации случайностей, имеющим большое значение для многих разделов дискретной математики и математической кибернетики (см. например, [12]). Объектом исследований являются дискретные преобразований независимых вероятностных распределений. Под дискретным преобразованием вероятностных распределений понимается вероятностное распределение конечной случайной величины, значение которой является функцией от значений случайных величин с исходными вероятностными распределениями. Такие преобразования играют важную роль в задаче реализации случайностей, которая фактически заключается в построении некоторой случайной величины с произвольным требуемым распределением из имеющихся в распоряжении исходных источников случайностей Ci> • • • >С* с фиксированными вероятностными распределениями. Построение величины состоит в задании функции , где flj — множество значений случайной величины Q,i = 0,l,...,k. Отметим, что если случайные величины являются независимыми в совокупности, вероятностное распределение случайной величины

однозначно определяется функцией f и вероятностными распределениями величин Ci>--->C*- Поэтому в этом случае можно говорить о том, что вероятностное распределение величины £о порождается множеством вероятностных распределений величин посредством функции f. Соответственно, вероятностное распределение порождается множеством вероятностных распределений, если это распределение порождается данным множеством посредством какой-либо функции.

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

1Бyxapaeв Р.Г. Основы теории вероятностных автоматов. —М.: Наука, 1985.

2Srinivasan A., Zuckerman D. Computing with Very Weak Random Sources // SIAM J. on Computing. - 1999. - V. 28. - N 4. - P. 1433-1459.

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

Для произвольного непустого множества П различных простых чисел в множестве Бр естественным образом выделяется подмножество 5С[П] всевозможных распределений вероятностей, представимых дробями, все простые делители знаменателей которых принадлежат множеству П. Отметим, что с практической точки зрения среди множеств вероятностных распределений наибольший интерес представляют конечно порожденные множества, т. е. множества, порождаемые своими конечными подмножествами.

Каждому конечному вероятностному распределению может быть сопоставлен вектор вероятностей этого распределения. Отметим, что этот вектор является стохастическим, т. е. все его компоненты неотрицательны и их сумма равна 1. Таким образом, без ограничения общности вероятностные распределения из Бр могут рассматриваться как стохастические векторы, все компоненты которых являются рациональными числами. В случае бинарных вероятностных распределений каждое такое распределение однозначно определяется какой-либо одной из вероятностей этого распределения, т. е. имеется взаимно однозначное соответствие между бинарными распределениями и числами из сегмента [0; 1]. Поэтому для удобства вместо бинарных распределений рассматриваются соответствующие этим распределениям числа. В таком случае множеству всех бинарных распределений из Бр соответствует множество Рр всех рациональных чисел из сегмента [0; 1], а множеству всех бинарных распределений из Ж[П] соответствует множество в[П] всех чисел из Рр, представимых дробями, знаменатели которых являются произведениями степеней чисел из множества П.

Изучение порождения бинарных распределений из Бр было нача-

то Р.Л. Схиртладзе в работе [3], в которой установлено, что множество в[{2}] порождается одним числом и показано таким образом, что это множество является конечно порожденным. Им же в [4] доказан аналогичный результат для множества С[{3}]. Ф.И. Салимовым в [5] доказано, что для любого конечного П, содержащего числа 2 или 3, существуют двухэлементные подмножества множества 6Щ], порождающие это множество. Им же в [6] установлена конечная порожденность множеств С[П] для любого конечного П, и таким образом показано, что множество б[П] является конечно порожденным тогда и только тогда, когда П конечно.

Другой важной проблемой, тесно связанной с проблемой выразимости, является проблема описания всех множеств распределений из замкнутых относительно рассматриваемого порождения распределений. Пример таких замкнутых множеств представляют множества ЖЩ]. Ф.И. Салимовым в работе [6] доказано, что в случае бинарных распределений для любого множества П различных простых чисел и любого числа р из П множество G[П \ {р}] является предполным замкнутым классом в множестве G[П] (замкнутое множество А называется предполным классом в множестве В, если А СБ и не существует замкнутого множества С такого, что АС С С В). Таким образом, была получена структура диаграммы включений для множеств G[П]. Кроме того, в [6] было показано, что существуют замкнутые множества бинарных распределений из отличные от множеств G[П].

Случай произвольных распределений из исследовался Ф.И. Салимовым в работах [7'8,9]. В работе [7] было показано, что все множества

3 Схиртладзе Р.Л. О синтезе р-схемы из контактов со случайными дискретными состояниями // Сообщ. АНГрССР. - 1961. - Т. 26. - N 2. - С. 181-186.

4 Схиртладзе Р.Л. О методе построения булевой случайной величины с заданным распределением вероятностей //Дискретный анализ. Вып. 7.— Новосибирск: ИМ СО АН СССР, 1966. - С. 71-80.

5Салимов Ф.И. К вопросу моделирования булевых случайных величин функциями алгебры логики // Вероятностные методы и кибернетика. Вып. 15. — Казань: Казанский гос. университет, 1979. — С. 68-89.

'Салимов Ф.И. Об одном семействе алгебр распределений // Известия вузов. Сер. Математика. - 1988. - N 7. - С. 64-72.

7Салимов Ф.И. Конечная порожденность некоторых алгебр над случайными величинами // Вопросы кибернетики. Вып. 86. — М., 1982. — С. 122-130.

8Салимов Ф.И. О максимальных подалгебрах алгебр распределений // Известия вузов. Сер. Математика. — 1985. — N 7. — С. 14-20.

9Салимов Ф.И. Конечная порожденность алгебр распределений // Дискретный анализ и исследование операций. Сер. 1. — 1997. — Т. 4. — N 2. — С. 43-50.

5СЩ], где П конечно, порождаются одноэлементными подмножествами, и тем самым установлено, что множество 5С[П] является конечно порожденным тогда и только тогда, когда П конечно. В работе [8] доказано, что для любого множества П различных простых чисел и любого числар из П множество 5С[П\(р}] является предполным классом в множестве 5С[П]. Кроме того, в [8] было найдено дополнительное семейство замкнутых множеств распределений из SQ, являющихся предполными классами в множествах SG^], и показано таким образом, что в каждом множестве SG^] имеется по крайней мере счетное число предполных классов.

Естественным ограничением, которое может быть наложено на порождение вероятностных распределений, является ограничение на число исходных случайных величин. В этом случае мы имеем задачу оценки сложности порождения вероятностных распределений, где под сложностью порождения распределения понимается минимальное число исходных случайных величин, необходимое для порождения данного распределения. Такая сложность, очевидно, существенным образом зависит от исходного множества распределений. В работах Р.Л. Схиртладзе [3 4] и автора [щ 11 12 13 14] (эти результаты автора не включены в диссертацию) был получен ряд оценок сложности порождения бинарных распределений из SQ. Другим сложностным аспектом порождения вероятностных

г 15, 1 6 п

распределений, изучавшимся ранее в литературе [ ], является мини-

10Колпаков Р.М. Об оценках сложности порождения рациональных чисел вероятностными контактными я--сешми // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 1992. - N 6. - С 62-65.

"Колпаков P.M. О порождении рациональных чисел вероятностными контактными тг-сегями // Дискретная математика. — 1994. — N 3. — С. 18-38.

12Колпаков P.M. О верхних оценках сложности порождения рациональных чисел вероятностными ir-сегями // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 19995. - N 5. - С. 99-102.

13Kolpakov R.M. On the complexity of generation of rational numbers by Boolean functions // Fundamenta Informaticae. — 1995. — V. 22, — P. 289-298.

14Колпаков P.M. О сложности порождения рациональных чисел одноэлементными множествами в классе всех булевых функций // Материалы VII межгосударственного школы-семинара "Синтез и сложность управляющих систем". — М.: Изд-во МГУ, 1996.

- С. 13-14.

"Захаров В.М., Салимов Ф.И. К теории структурного синтеза детерминированных преобразователей вероятности // Problems of Control and Information Theory. — 1977.

- V. 6 - N 2. - P. 137-148.

мальная сложность реализации функций, применяемых для порождения этих распределений.

Тесно связанной с задачей оценки сложности порождения вероятностных распределений является задача приближенного порождения вероятностных распределений, заключающаяся в том, чтобы из заданного числа исходных случайных величин с заданными распределениями построить случайную величину с распределением, наиболее близким к требуемому вероятностному распределению. Интересные результаты, касающиеся приближенного порождения распределений, получены Р.Л. Схиртладзе и Н.Н. Нурмеевым в работах [4'17]. Важной задачей, близкой по тематике к рассматриваемым вопросам, является также задача о минимальном имплицирующем векторе [ ].

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

г 19, 20 , 21, 22-1

бот [ ] рассматривалось порождение распределений посредством

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

16Нурмеев Н.Н. О сложности реализации преобразователей вероятностей схемами из функциональных элементов // Методы и системы технической диагностики. Вып. 18. — Саратов: Саратовский гос. университет, 1993. — С. 131-132.

17Нурмеев Н.Н. О булевых функциях с аргументами, принимающими случайные значения // Тезисы докладов VIII Всесоюзной конференции "Проблемы теоретической кибернетики", Горький. — 1988. — Часть 2, — С. 59-60.

18Кузнецов СБ., Нурмеев Н.Н., Салимов Ф.И. Задача о минимальном имплицирующем векторе // Математические вопросы кибернетики. Вып. 3. — М.: Наука, 1991. - С. 199-216.

19Neumann J. von. Various technique used in connection with random digits. Monte Carlo Method, Applied Mathematics Series. - 1951. - N 12. - P. 36-38.

20Hoeffding W., Simons G. Unbiased coin tossing with a biased coin // Annals of Math. Statistics. - 1970. - V. 41. - P. 341-352.

21Elias P. The efficient construction of unbiased random sequence //Annals of Math. Statistics. - 1972. - V. 43. - N 3. - P. 865-870.

22Рябко Б.Я., Мачикина Б.П. Эффективное преобразование случайных последовательностей в равновероятные и независимые // Проблемы передачи информации. — 1999. - Т. 36. - Вып. 2. - С. 23-28.

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

Еще раз отметим, что в данной работе все исходные случайные величины, используемые для порождения распределений, преполагаются независимыми в совокупности. Н. Нисаном и Д. Зукерманом в работе [в] было показано, что для приближенного порождения распределений с произвольной точностью могут также использоваться исходные случайные величины, не являющиеся независимыми. Функции, применяемые в таком случае, называются экстракторами. Изучению экстракторов посвящено большое число работ (см., например, [24, 25, 26 , 27]). Следует отметить, что экстракторы требуют сравнительно большого числа исходных случайных величин, и, соответственно, большой оказывается также сложность вычисления значений экстрактора.

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

23Nisan N., Zuckerman D. Randomness is linear in space // J. of Computer and System Sciences. - 1996. - V. 52. - N 1. - P. 43-52.

24Nisan N., Ta-Shma A. Extracting randomness: A survey and new constructions // J. of Computer and System Sciences. — 1999. — V. 58. — N 1. — P. 148-173.

25Raz R., Reingold 0., Vadhan S. Error reduction for extractors // Proceedings of 40th Symposium on Foundations of Computer Science, New York (USA). —1999. — P. 191-201.

2eSrinivasan A., Zuckerman D. Computing with very weak random sources // SIAM J. on Computing. - 1999. - V. 28. - N 4. - P. 1433-1459.

27Trevisan L. Construction of extractors using pseudo-random generators // Proceedings of 31th ACM Symposium on Theory of Computing, Atlanta (USA). — 1999. — P. 141-148.

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

Научная новизна. Основные результаты работы состоят в следующем:

1. Для любого множества распределений из SQ дано явное описание всех распределений, порождаемых этим множеством.

2. Предложен эффективный алгоритм, который для любого заданного распределения и любого заданного конечного множества распределений из SQ за полиномиальное время позволяет определить, порождается ли данное распределение этим множеством.

3. Описаны все замкнутые подмножества множества SQ.

4. Определена структура диаграммы включений для замкнутых подмножеств множества SQ.

5. Описаны все конечно порожденные замкнутые подмножеств множества SQ.

6. Для каждого замкнутого подмножества О множества SQ приведены все предполные классы множества О.

Все представленные в диссертации результаты являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Однако предложенные в работе методы порождения вероятностных распределений могут быть применены как в теории для решения задачи оценки сложности порождения распределений из SQ, так и на практике для создания реальных генераторов случайных чисел.

Апробация работы. Результаты диссертации докладывались и обсуждались на заседаниях следующих научных семинаров: МГУ на механико-математическом факультете: семинар "Математические вопросы кибернетики", под рук. акад. РАН О.Б. Лупанова (неоднократно), семинар "Синтез и сложность управляющих систем"под рук. акад. РАН О.Б. Лупанова (неоднократно), семинар "Функции многозначной логики и смежные вопросы"под рук. проф. А.Б. Угольникова и проф. СБ. Гаш-кова (неоднократно); институт Математики Сибирского отделения РАН: семинар под руководством проф. А.Д. Коршунова и А.Е. Евдокимова; факультет кибернетики университета г. Ливерпуля (Великобритания): семинар под руководством проф. L. Gasieniec.

Результаты диссертации докладывались также на следующих научных конференциях: Международный семинар "Сложность, вероятность и приложения", Франко-русский центр МГУ, Москва (1994); VI Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Нижний Новгород (1994); V Межгосударственная школа-семинар по дискретной математике и ее приложениям, МГУ, Москва (1995) VII Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Минск (1995); XI Международная конференция по проблемам теоретической кибернетики, Ульяновск (1996); II Сибирский конгресс по прикладной и Индустриальной Математике (ИНПРИМ-96), Новосибирск (1996); VIII Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Нижний Новгород (1996); II Международная конференция "Дискретные модели в теории управляющих систем", д/о МГУ "Красновидово"(1997); IX Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Нижний Новгород (1999); XII Международная конференция по проблемам теоретической кибернетики, Нижний Новгород (1999); X Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Минск (1999); XII Межгосударственная школа-семинар "Синтез и сложность управляющих систем", Пенза (2001); XIII Международная конференция по проблемам теоретической кибернетики, Казань (2002); 2-й Международный симпозиум Stochastic Algorithms: Foundations and Applications (SAGA'03), Хат-филд, Великобритания (2003); XV Межгосударственная школа-семинар "Синтез и сложность управляющих систем", ИМ СО РАН, Новосибирск (2004).

Публикации. Основные результаты диссертации опуликованы в 14 работах, список которых приведен в конце автореферата: 7 статьях в центральных математических журналах, одной статье в сборнике, изданном в МГУ, а также в б тезисах докладов на конференциях и публикациях в зарубежных изданиях. Все работы выполнены без соавторства.

Структура и объем диссертации. Диссертация объемом 180 страниц состоит из введения, 3 глав, разбитых на разделы, заключения и списка литературы, содержащего 44 наименования. В диссертации используются сплошная нумерация для утверждений и примеров и нумерация по главам для выключных формул.

Основное содержание диссертации

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

В первой главе приведены вспомогательные понятия, обозначения и утверждения, используемые в работе. В частности, в разделах 1.1 и 1.2 вводятся следующие понятия и обозначения, являющиеся базовыми для данной работы.

Для натурального п через Х[п) обозначается множество всех простых делителей числа п. Для множества натуральных чисел Г через Т* обозначается подмножество всех чисел из Т, больших числа к, и через |Т| обозначается мощность множества Т. Если множество Г конечно, через ||Т|| обозначается произведение всех чисел множества Т. Для пустого множества полагаем ||0|| = 1. Множество чисел из МР1 называется разделимым, если оно содержит меньше двух чисел, либо все его числа попарно просты. Множество натуральных чисел называется взаимно простым с натуральным числом и, если любое число из этого множества взаимно просто с и. Пустое множество считается взаимно простым с любым натуральным числом. Непустое разделимое множество В называется делителем разделимого множества А, если для любого числа Ь из В множество А содержит число, кратное числу Ь. Пустое множество считается делителем любого разделимого множества.

Пусть Л1, ..., Лз — конечные разделимые множества. Наибольшим

общим делителем (Л1, ..., Л) этих множеств называется множество

состоящее из отличных от 1 наибольших общих делителей всевозможных выборок из 5 чисел по одному числу из каждого множества Л1, ..., Л. Если хотя бы одно из множеств Л1, ..., Л5 является пустым, то(Л1; А,) =0.

Понятие наибольшего общего делителя вводится также для бесконечного числа конечных разделимых множеств. Пусть Л1, Л2,... — конечные разделимые множества. Тогда наибольшим общим делителем (Лр Л2,...) этих множеств является множество

состоящее из всех тех чисел из РР1, которые являются наибольшими общими делителями бесконечных выборок чисел из множеств Л1, Л2,... по одному числу из каждого множества. Если хотя бы одно из множеств Л1, Л2,... является пустым, то (Л1, Л2,...) = 0.

В разделе 1.2 приводится также ряд вспомогательных утвержений, касающихся разделимых множеств. Разделы 1.3 и 1.4 содержат вспомогательные теоретико-числовые и комбинаторные понятия и утверждения.

Вторая глава содержит результаты для случая бинарных распределений из Вместо бинарных распределений из для удобства рассматриваются соответствующие этим распределениям числа из множества Рр. Пусть Н — множество чисел из Рр. Число а 6 [0; 1] порождается множеством Н, если существует булева функция /(х1, ..., х) такая, что для некоторых из Н выполняется соотношение

^ _ | р, если <7=1;

Через обозначается замыкание множества Н, т. е. множество всех чисел, порождаемых множеством Н. Множество ЛС [0; 1] порождается множеством Н, если ). Множество Н называется замкнутым, ес-

ли Н = (Я). Рассматривается следующая задача выразимости в Рр: для

любого заданного числа а и любого заданного конечного множества H чисел из PQ определить, порождается ли число а множеством H.

Пусть tl, ^ — взаимно простые натуральные числа, П — произвольное непустое множество различных простых чисел, взаимно простых с tl и t2. Через ОП tl : обозначается следующее подмножество множества ОЩ]:

С[П; : ¿2] = |а = ^

О < а < 1, т е п е Л5,1, 1{п) с п т = О (то(1 ¿х), т = тг (тос1 ¿г)

Пусть Т — конечное разделимое множество натуральных чисел, взаимно простых с множеством П. Через О[П; Т] обозначается следующее подмножество множества О[П]:

С[П;Т] = иС[П;||Г'||:||Т\Т'||],

т>ст

где объединение берется по всем (в том числе и несобственным) под-можествам Т множества Т. В случае Т = 0 полагаем С[П; 0] = С?[П]. В разделе 2.4 показано, что любое множество О[П:Т] является замкнутым.

Мы обозначаем через О совокупность всех множеств О[П:Т]. В разделе 2.4 установлено, что отношение включения между любыми множествами из О определяется следующим образом (см. утверждение 29). Пусть б[П1:Т1], О[П2:Т2] — два множества из О. Тогда

1. в[П1:Т1]СО[П2:Т2] тогда и только тогда, когда П£1 П2 и Т2>2 является делителем множества Т1;

2. О[П1:Т1] = О[П2:Т2] тогда и только тогда, когда П1 = П2 и Т1>2 =

Т! >2 Т 2 .

В разделе 2.5 исследуется случай замыканий одноэлементных множеств чисел из PQ. Без ограничения общности можно рассматривать только замыкания множеств, состоящих из несократимых дробей из интервала (0; 1). Пусть £ — произвольная несократимая дробь из этого интервала. Тогда множество {/, п - /}> является разделимым множеством, взаимно простым с числом п. Поэтому можно рассмотреть множество В разделе 2.5 доказан следующий факт.

Теорема 3. Для любой несократимой дроби £ из интервала (0; 1) выполняется соотношение

Далее в диссертации изучается случай замыканий конечных множеств чисел из Рр. Как и для случая одноэлементных множеств, рассматриваются только множества, состоящие из несократимых дробей из интервала (0; 1). В разделе 2.6 дается следующий критерий порождае-мости множества С[(р}], где р — произвольное простое число, заданным конечным подмножеством.

Теорема4. Пустьр — простоечисло, Я = !• • ■ > | —конечное множество несократимых дробей из 0[{р}], й = ш1(и1 — т1) при я = 1 и 6= (да1(рг1 — т^,.. ,,т/р" — т)) при 5 > 2. Для того чтобы {Н) = 0[{р}], необходимо и достаточно, чтобы й < 2.

В разделе 2.7 теорема 4 обобщается на случай произвольного множества 0[П], где П конечно, следующим образом.

Теорема 6. Пусть П — произвольное конечное множество различных простых чисел, Н = • • •! —конечное множество несократимых дробей из 0[П], й = т1(п1 — т1),..., т/пя — т)) при я > 2 и й = т1(п1 — т1) при я = 1. Для того чтобы (Щ б[П], необходимо и достаточно выполнение следующих двух условий:

а) для любого р € П во множестве {п1,...,пя} найдется число, кратное р; б )с1 <2.

Полученные результаты используются для явного описания замыка-ннй конечных множеств чисел из РС). Чтобы дать это описание, рассмотрим произвольное конечное множество Я = ' •'» г^} несократимых дробей из интервала (0; 1). Положим

и П(Я) = и*-!^^). В разделе 2.10 показано, что множество Т(Н) является разделимым и взаимно простым с любым числом из П(Н). Поэтому можно рассмотреть множество 0[П(Н);Т(Н)>2]. В разделе 2.10 доказано, что это множество является замыканием множества Н.

Теорема 11. Для любого конечного множества Н несократимых дробей из интервала (0; 1) выполняется соотношение

<Я} = С[П(Я);Т(Я)>г].

Полученное описание замыканий конечных множеств чисел из PQ позволяет предложить эффективный алгоритм решения задачи выразимости в PQ. Пусть множество Н состоит из s несократимых дробей из интервала (0;1). Обозначим через Ля величину max(rn,..... ms, n1 - mr.., ns - m). Пусть число а также задано некоторой несократимой дробью — (если а ^ PQ, то, очевидно, а (Я)). Положим т]а = n. В разделе 2.11 предложен алгоритм проверки соотношения а , требующий выполнения не более

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

В разделе 2.12 теорема 11 обобщается на случай замыканий произвольных бесконечных множеств чисел из PQ. Пусть Н = .. -бесконечное множество несократимых дробей из интервала (0;1). Тогда положим

и П(Н) = В таком случае множество Т(Н) также является

разделимым и взаимно простым с любым числом из П(Н). Поэтому снова можно рассмотреть множество G^^^T^^2]. В разделе 2.12 доказана

Теорема 13. Для любого бесконечного множества Ннесократимых дробей из интервала (0; 1) выполняется соотношение

<Я> = С[П(Я);Т(Я)>2].

Отметим, что любой из замкнутых классов чисел из PQ является замыканием некоторого своего подмножества (например, самого этого класса). Поэтому из теорем 11 и 13 следует, что любой замкнутый класс чисел из PQ является элементом множества G. Таким образом, множество G является множеством всех замкнутых подмножеств множества

PQ.

Раздел 2.13 посвящен изучению конечно порожденных замкнутых классов чисел из PQ. Через Gfm мы обозначаем подмножество множества G, состоящее из всех множеств G^;?] таких, что П конечно. Показано, что замкнутое подмножество множества PQ является конечно порожденным тогда и только тогда, когда это подмножество является

элементом множества GГln. Таким образом, установлено, что множество GГш является множеством всех конечно порожденных замкнутых подмножеств множества Рр. Более того, доказано, что любое множество (?[П, Т\ из <5Гш порождается некоторым своим подмножеством, содержащим не более |Г| + 2 чисел.

В разделе 2.14 приводится ряд результатов, касающихся структуры замкнутых множеств чисел из Рр. В частности, доказывается, что любое замкнутое множество чисел из Рр имеет базис28. Кроме того, для каждого замкнутого множества чисел из Рр дается описание всех его предполных классов. Для случая множества G[П] мы полагаем

5о[П] = | иР€п(С[П \ {р}]}. если |П| > 1;

Через П обозначаем множество всех простых чисел.

Следствие 29. Пусть S — множество всех предполных классов в множестве С[П]. Тогда

1. если П содержит число 2, то

5 = 50[П]и у {С[П; {*}]};

2. если П не содержит числа 2, то

5 = 50[П]и{С[П;{4}]}и у {С[П;{«}]}.

Для случая множества G[П;Т], где Т = {/1..., t}, q > 1, мы полагаем

5 ГП-Т1 = / иР€Пда\ М;21>, если |П| > 1; . \ 0, если |П| = 1;

гех(ЦГЦ)

где через /г) обозначается единственное число из Т, кратное г, и

дат] = и^ {Штит \ {МЛ]}.

28Порождающее подмножество некоторого множества называется базисом, если любое собственное подмножество этого подмножества не является порождающим для данного множества.

и

Следствие 30. Пусть ^ — множество всех предполных классов в множестве (г\11; Т\, где Т непусто. Тогда

1. если либо П, либо Х(||Т||) содержит число 2, то

3 = 5о[П; г] и и {С^ТиШи^р^иШТ!;

2. если ни П, ни Х(ЦТ||) не содержит числа 2, то

Таким образом, получено, что в каждом из замкнутых подмножеств множества Рр имеется счетное число предполных классов.

В третьей главе рассматривается порождение произвольных распределений из 8р. Для удобства вероятностные распределения рассматриваются в виде стохастических векторов. Пусть — стохастические векторы размерности кр..., кк соответственно. Через будем обозначать_/-ю компоненту стохастического вектора V. Обозначим через П{Т>и ...,Т>к) множество {0, 1,..., — 1} х ... х {0, 1,..., кк — 1}. Для любого подмножества Е этого множества положим29

Для функции / : Г,..., 2?*) —> {0,1,..., к - 1} будем обозначать через ЛТД/), где I = 0, 1, ..., к - 1 , множество всех наборов из ..., Р*), на которых функция / принимает значение ;. Пусть Н — множество различных стохастических векторов. Стохастический вектор V размерности к порождается множеством Н, если для некоторых Т>1,...,Т)к из Н найдется функция / : —>• {0, 1, ..., к - 1} такая, что

Ш = Т^.Ы^и---М ] = 1, ..., к.

Через (Я) обозначается замыкание множества Н, т. е. множество всех стохастических векторов, порождаемых множеством Н. Множество Н

29 В случае полагаем = 0.

называется замкнутым, если (Я) = H. Будем говорить, что множество А стохастических векторов порождается множеством H, если А С (Я). Рассматривается следующая задача выразимости в SQ: для любого заданного стохастического вектора V и любого заданного конечного множества М стохастических векторов из SQ определить, порождается ли вектор V множеством М.

Пусть П — произвольное непустое множество различных простых чисел, Т — конечное разделимое множество натуральных чисел, взаимно простых со множеством П. Обозначим через 5С[П;7] следующее подмножество множества 5С[П]30:

di = тп,- € Z+, i = l,...,h, пе N, 1(п)СП,

Y,U di = 1, BTt.....Th.u Т Э Ti Э Т2 2 ■ • • 2 Tft-1,

£}=1 Щ s 0 (mod ||T,||)f г = 1,..., h -1, £}в1т, = п (mod ЦТ\Tj||), г = 1,...,ft - 1

В случае Т = полагаем 5С[П; 0j = 5ЩП]. В разделе 3.3 показано, что любое множество 5С[П; T] является замкнутым.

Через SG обозначается совокупность всех множеств 5С[П; T]. В разделе 3.3 установлено, что отношение включения между любыми множествами из SG определяется следующим образом (см. утверждение 39). Пусть ОДП'; T], ОДП"; T'] — два множества из SG. Тогда

1. 5С[П'; 7"]С5С[П"; T'] тогда и только тогда, когда П' С П" и Т" является делителем множества Т";

2. 5С[П'; T] = 5С[П"; T'] тогда и только тогда, когда П' = П" и Т = Т"

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

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

"Рассматриваемые в этом определении подмножества Т...., Ты множества Тмогут быть несобственными.

что для решения этой задачи без ограничения общности можно рассматривать только замыкания множеств, состоящих из позитивных векторов, т. е. векторов, все компоненты которых отличны от чисел 0 и 1.

Сначала исследуется простейший случай замыкания множества, состоящего из одного двумерного позитивного вектора V 6 SQ. Без ограничения общности можно полагать, что V = (l — , где I, п € N, (l,n) = 1. Положим Т(Р) = {I, п - lfl и IKD) = 1{п). Можно показать, что множество Т(2?) является разделимым и взаимно простым с любым числом из П(Р). Поэтому может быть рассмотрено множество SG[T(V);T(V)]. В разделе 3.5 доказано, что ({D}) = 5(?[П(1>);Т(Х>)].

Результаты, полученные в разделе 3.5, обобщаются в разделе 3.6 на случай замыканий произвольных одноэлементных множеств веторов из SQ. Для этого рассматривается произвольный позитивный вектор "D = (d{, ...; dt) из SQ, где t > 3. Без ограничения общности можно предполагать, что компоненты вектора представлены дробями, приведенными к наименьшему общему знаменателю n, т. е. d = -j-, где i = 1, ..., t и (ml,...,mt) = 1. Дляj = 1, ..., t обозначим через l. наибольший общий делитель всех чисел ml,...,ml кроме числа mf Положим T(V) = {lv ..., /t}>1 иП(Р) = 1(п). Тогда, как и для случая двумерного вектора, множество T(D) является разделимым и взаимно простым с любым числом из n(Z7). Поэтому снова может быть рассмотрено множество SG[T(V); T(V)]. В разделе 3.6 доказано, что в этом случае также выполняется равенство ({Р}) = SG[n(D );Г(Р)]. Таким образом, имеет место

Теорема 18. Для любого позитивного вектора "D из SQ справедливо соотношение {{Щ S(i\HiV):'/CD)\.

Далее в диссертации рассматриваются замыкания конечных множеств векторов из SQ. В разделе 3.7 изучается случай замыканий конечных множеств двумерных векторов. Пусть М — {Vi,..., D,,} — произвольное конечное множество двумерных позитивных векторов из SQ. Как и для случая одноэлементного множества, мы полагаем T>i = — , где ж., n.Ç п.) = 1, ; == 1,..., 5. Положим

и П(М) = UUAm) Отметим, что множество Т(М) является разделимым и взаимно простым с любым числом из П(М). Рассмот-

рим множество SG[П(M);T(M)]. В разделе 3.7 доказано, что (М) = SG[П(M);T(M)].

В разделе 3.8 рассматриваются замыкания конечных множеств векторов из произвольной размерности. Пусть М = { Т>\,..., Т)>} — произвольное конечное множество позитивных стохастических векторов из размерности к1 соответственно. Как и для случая одноэле-

ментного множества, мы полагаем, что каждый вектор представлен в виде

где (т<1>,...,т/>) = 1. Положим Т(М) = ГЯГ>1), .... Т(V,)) в случае 5 > 2 и Т(М) = Т(Т>\) в случае 5 = 1. Положим также П(М) = и-=1 £("<)• В разделе 3.8 показано, что множество Т(М) является разделимым и взаимно простым с любым числом из П(М), и рассмотрено множество SG[П(M);T(M)], для которого справедлива

Теорема 19. Для любого конечного множества М позитивных стохастических векторов из выполняется соотношение (М) = SG[П(M)■;T(M)]•

В разделе 3.9 на основе теоремы 19 предлагается эффективный алгоритм решения задачи выразимости в Пусть множество М состоит из позитивных векторов Т>\, ..., Д размерности Н,, ..., На соответственно. Предполагается, что все компоненты этих векторов изначально заданы несократимыми дробями. Пусть компоненты вектора Ц заданы несократимыми дробями, знаменателями которых являются числа п( ,...,п®,

I = 1, ...,5. Положим Щм = шах^л/'7 , — шахД и Ем = Отметим, что если Бф 8(3, то, очевидно, Щ. (М). Поэтому можно предполагать, что Д Пусть вектор К имеет размерность Н, и все компоненты этого вектора заданы несократимыми дробями, знаменателями которых являются числа п{0> ,...,пН(0 . Положим т/ц = шахп(0). В разделе 3.9 предъявлен алгоритм проверки соотношения V € {М), требующий выполнения не более ариф-

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

В разделе 3.10 теорема 19 обобщается на случай замыканий произвольных бесконечных множеств стохастических векторов из Пусть М = {Т^!,^,...} — бесконечное множество позитивных векторов из

Тогда мы также можем рассмотреть множество 80[П(М);Т(М)], где

Т(М) = (тро,т(р2),...) и п(м) =

Теорема 21. Для каждого бесконечного множества М позитивных векторов из выполняется равенство {М) — 80[Н(М);Т(М)].

Поскольку любой из замкнутых классов векторов из является замыканием некоторого своего подмножества (например, самого этого класса), из теорем 19 и 21 следует, что любой замкнутый класс векторов из является элементом множества Таким образом, множество является множеством всех замкнутых подмножеств множества В разделе 3.11 изучаются конечно порожденные замкнутые классы векторов из Через обозначается подмножество множества состоящее из всех множеств 8в[П;Т] таких, что П конечно. Доказано, что замкнутое подмножество множества является конечно порожденным тогда и только тогда, когда это подмножество является элементом множества ЗОА^. Таким образом, показано, что множество 80Пп является множеством всех конечно порожденных замкнутых подмножеств множества Кроме того, для каждого множества 50[ГГ,Т| из Звй^ непосредственно предъявляется одноэлементное подмножество, порождающее это множество.

В разделе 3.12 приводится ряд результатов, связанных со структурой замкнутых множеств векторов из В частности, показано, что любое замкнутое множество векторов из имеет базис. Кроме того, для каждого замкнутого множества векторов из дается описание всех его предполных классов. Для множеств 80[и] все предполные классы описываются следующим образом.

Следствие 42. Совокупностью всех предполных классов в множестве БО[и] является множество

50[П]и у {5С[П; {*}]},

^ 5о[п] = | иреП{50[П \ {р}]}, если |П| > 1;

В случае множества 5£7[П; Т], где Т непусто, для каждого числа г из мы обозначаем через единственное число из Т, кратное г. В таком случае имеем

Следствие 43. Совокупностью всех предполных классов во множестве 80[П,Т], где Т = {11,... ,1}, q > 1, является множество

50(П;Т]и У {5С[П;Тиф]}и

№П\(ПиГ(||Т||))

U (J {Я?[Л;Ти{#

г€1(||Г||)

где

1 <i<j<4

5„[П;Т] = { иР€п{5С[П \ {р};Т]}, если |П| > 1;

Из следствий 42 и 43 вытекает, что в каждом из замкнутых подмножеств множества имеется счетное число предполных классов.

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

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

Автор глубоко признателен своему научному консультанту профессору А.Б. Угольникову, академику РАН профессору О.Б. Лупанову, профессору О.М. Касим-Заде и доценту Ю.В. Таранникову за ряд ценных советов и замечаний, обсуждение и поддержку данной работы.

Статьи автора по теме диссертации

1. Колпаков P.M. Критерий порождения множеств рациональных вероятностей в классе булевых функций // Дискретный анализ и исследование операций. Сер. 1. — 1999. — Т. 6. — N 2. — С. 41-61.

2. Колпаков P.M. О преобразованиях булевых случайных величин // Математические вопросы кибернетики. Вып. 9. — М.: Наука, 2000. - С. 227-252.

3. Колпаков P.M. Замкнутые классы булевых случайных величин с рациональнозначными распределениями // Математические вопросы кибернетики. Вып. 10. — М.: Наука, 2001. — С. 215-224.

4. Колпаков P.M. Замыкания одноэлементных множеств бинарных распределений с рациональными вероятностями для многозначных преобразований // Математические вопросы кибернетики. Вып. 11. - М.: Наука, 2002. - С. 63-76.

5. Колпаков P.M. О многозначных преобразованиях конечных множеств бинарных распределений с рациональными вероятностями // Дискретная математика. — 2005. — N 1.

6. Колпаков P.M. О дискретных преобразованиях конечных распределений с рациональными вероятностями // Математические вопросы кибернетики. Вып. 12. — М.: Наука, 2003. — С; 109-146.

7. Колпаков P.M. Замкнутые классы конечных распределений рациональных вероятностей // Дискретный анализ и исследование операций. Сер. 1. - 2004. - Т. 11. - N 3. - С. 16-31.

8. Колпаков P.M. О порождении рациональных чисел монотонными функциями // Теоретические и прикладные аспекты мат. исследований (сборник научных трудов). — М.: Изд-во МГУ, 1994. — С. 13-17.

Тезисы докладов и зарубежные публикации автора по теме диссертации

9. Колпаков P.M. Критерий порождаемости некоторых множеств рациональных чисел булевыми функциями // Тезисы докладов XI Международной конференции "Проблемы теоретической кибернетики". - М.: Изд-во РГГУ, 1996. - С. 96-97.

10. Колпаков P.M. О преобразованиях вероятностных распределений

. булевыми операторами // Материалы X межгосударственной школы-семинара "Синтез и сложность управляющих систем". — М.: Изд-во МГУ, 2000. - С. 8-11.

11. Колпаков P.M. О дискретных преобразованиях конечных рацио-нальнозначных вероятностных распределений // Тезисы докладов XIII Международной конференции "Проблемы теоретической кибернетики", Казань. - М.: Изд-во МГУ, 2002. - Часть I. - С. 92.

12. Колпаков P.M. Полиномиальный алгоритм проверки порождаемо-сти конечных распределений рациональных вероятностей // Материалы XV межгосударственной школы-семинара "Синтез и сложность управляющих систем". — Новосибирск: ИМ СО РАН, 2004. - С. 45-50.

13. Kolpakov R.M., Criterion of generativeness of sets of rational probabilities by a class of Boolean functions // Discrete Applied Mathematics. - 2003. - V. 135 - P. 125-142.

14. Kolpakov R.M. Classes of Binary Rational Distributions Closed under Discrete Transformations // Stochastic Algorithms: Foundations and Applications (SAGA'03). — Springer Verlag, 2003. (Lecture Notes in Computer Science, V. 2827). - P. 157-166.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать 2.Л. ¡¿. 04 Формат 60x90 1/16. Усл. печ. л.

Тираж 100 экз. Заказ И

Лицензия на издательскую деятельность ИД В 04059,

от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

1 Вспомогательные определения и результаты

1.1 Используемые обозначения.

1.2 Разделимые множества.

1.3 Вспомогательные теоретико-числовые утверждения

1.4 Вспомогательные элементы комбинаторики.

2 Порождение бинарных распределений рациональных Belt роятностей

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

2.2 Вспомогательные определения и утверждения.

2.3 Доказательство теоремы 2.

2.4 Замкнутые классы в PQ.

2.5 Замыкания одноэлементных множеств чисел.

2.6 Критерий порождаемости множеств G[{p}].

2» 7 Критерий порождаемости множеств С?[{П}] для произвольного П.

2.8 Основная лемма.

2.9 Вспомогательные результаты для замыканий числовых множеств.

2.10 Замыкания конечных множеств чисел

2.11 Проверка порождаемости чисел конечными множествами

2.12 Замыкания бесконечных множеств чисел

2.13 Конечно порожденные замкнутые классы в PQ.

2.14 Структура замкнутых классов в PQ.

3 Порождение конечных распределений рациональных вероятностей

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

3.2 Вспомогательные определения и утверждения.

3.3 Замкнутые классы в SQ.

3.4 Вспомогательные результаты для стохастических векторов

3.5 Замыкания одноэлементных множеств двумерных векторов

3.6 Замыкания одноэлементных множеств векторов произвольной размерности.

3.7 Замыкания конечных множеств двумерных векторов

3.8 Замыкания конечных множеств векторов произвольной размерности

3.9 Проверка порождаемости стохастических векторов конечными множествами

3.10 Замыкания бесконечных множеств векторов произвольной размерности

3.11 Конечно порожденные замкнутые классы в SQ.

3.12 Структура замкнутых классов в SQ

Работа посвящена исследованиям дискретных преобразований независимых вероятностных распределений. Под дискретным преобразованием вероятностных распределений понимается вероятностное распределение конечной случайной величины, значение которой является функцией от значений случайных величин с исходными вероятностными, распределениями. Такие преобразования играют важную роль в вопросах реализации случайностей, имеющих большое значение для многих разделов дискретной математики и математической кибернетики (см. [1, 29]), поскольку задача реализации случайностей фактически заключается в построении некоторой случайной величины Со с произвольным требуемым распределением из имеющихся в распоряжении исходных источников случайностей Съ--->Сл: с фиксированными вероятностными распределениями, отличными от требуемого распределения. Значение случайной величины Со, очевидно, должно быть функцией от значений случайных величин £i,.,0fc- Поэтому построение величины Со состоит в задании функции / : Qi х . х Qk —> где — множество значений случайной величины С*, г = 0,1,.,/:. Отметим, что если случайные величины Ci>---j0fe являются независимыми в совокупности, вероятностное распределение случайной величины Со однозначно определяется функцией / и вероятностными распределениями величин Съ • ••, Сь Поэтому в этом случае мы можем говорить о том, что вероятностное распределение величины Со порождается множеством вероятностных распределений величин Съ • • •, 0ь посредством функции /. Соответственно, мы говорим, что вероятностное распределение порождается множеством вероятностных распределений, если это распределение порождается данным множеством посредством какой-либо подходящей функции.

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

Для произвольного непустого множества П различных простых чисел во множестве SQ естественным образом выделяется подмножество *5"С[П] всевозможных распределений вероятностей, представимых дробями, все простые делители знаменателей которых принадлежат множеству П. Отметим, что с практической точки зрения среди множеств вероятностных распределений наибольший интерес представляют конечно порожденные множества, т. е. множества, порождаемые своими конечными подмножествами.

Сначала мы исследуем наиболее изученный случай бинарных вероятностных распределений. Поскольку бинарное вероятностное распределение однозначно определяется какой-либо одной из вероятностей этого распределения, мы имеем взаимно однозначное соответствие между бинарными распределениями и числами из сегмента [0;1]. Поэтому для удобства вместо бинарных распределений мы рассматриваем соответствующие этим распределениям числа. В таком случае множеству всех бинарных распределений из SQ соответствует множество PQ всех рациональных чисел из сегмента [0; 1], а множеству всех бинарных распределений из Й^П] соответствует множество С?[П] всех чисел из PQ, представимых дробями, знаменатели которых являются произведениями степеней чисел из множества П. Изучение порождения рациональных чисел из PQ было начато Р. Схиртладзе в работе [19], в которой установлено, что множество G[{2}] порождается одним числом и показано таким образом, что это множество является конечно порожденным. Им же в [20] доказан аналогичный результат для множества С7[{3}]. Ф. Салимовым в [14] получено, что для любого конечного П, содержащего числа 2 или 3, существуют двухэлементные подмножества множества С?[П], порождающие это множество. Им же в [17] установлена конечная порожденность множеств (?[П] для любого конечного П, и таким образом показано, что множество б^П] является конечно порожденным тогда и только тогда, когда П конечно. В настоящей работе для любого множества чисел из PQ дано явное описание всех чисел, порождаемых этим множеством, и тем самым получено полное решение проблемы выразимости для бинарных распределений из SQ. Предложен также эффективный алгоритм, который за полиномиальное время позволяет определить для любого заданного числа и любого заданного конечного множества чисел из PQ, порождается ли данное число данным множеством.

Другой важной проблемой, тесно связанной с проблемой выразимости, является проблема описания всех множеств распределений из SQ, замкнутых относительно рассматриваемого порождения распределений. Простейший пример таких замкнутых множеств представляют упомянутые выше множества 5"G[n]. Ф. Салимовым в [17] доказано, что в случае бинарных распределений для любого множества П различных простых чисел и любого числа р из П множество С?[П \ {р}] является предпол-ным1 замкнутым классом в множестве С?[П]. Таким образом, была установлена структура диаграммы включений для множеств С?[П]. Кроме того, в [17] было показано, что существуют замкнутые множества бинарных распределений из SQ, отличные от множеств Ст[П]. Используя полученное в настоящей работе решение проблемы выразимости для бинарных распределений из SQ, мы находим все замкнутые множества таких распределений. Мы также определяем структуру диаграммы включений для этих множеств. Кроме того, мы устанавливаем, какие из этих замкнутых множеств являются конечно порожденными, и для каждого конечно порожденного замкнутого множества непосредственно предъявляем конечное подмножество, порождающее это множество. В качестве следствий из полученных результатов мы приводим ряд результатов, касающихся структуры замкнутых множеств бинарных распределений из SQ.

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

1 Замкнутое множество А называется предполным классом в множестве В, если А С В и не существует замкнутого множества С такого, что А С С С В.

Заметим, что каждому конечному вероятностному распределению может быть сопоставлен вектор вероятностей этого распределения. Отметим, что этот вектор является стохастическим, т. е. все его компоненты неотрицательны и их сумма равна 1. Таким образом, без ограничения общности вероятностные распределения из SQ могут рассматриваться как стохастические векторы, все компоненты которых являются рациональными числами. Случай произвольных распределений из SQ исследовался ранее Ф. Салимовым в работах [15, 16, 18]. В [15] им было показано, что все множества 5(7 [П], где П конечно, порождаются одноэлементными подмножествами, и тем самым установлено, что множество 5С?[П] является конечно порожденным тогда и только тогда, когда П конечно. Им же в [16] доказано, что для любого множества П различных простых чисел и любого числатг из П множество 5С?[П\{р}] является предполным классом в множестве б^П]. Таким образом, диаграмма включений для множеств .S'G'fn] полностью совпадает с диаграммой включений для множеств С?[П]. Кроме того, в [16] было найдено дополнительное семейство замкнутых множеств распределений из SQ, являющихся предполными классами в множествах iSGfri], и показано таким образом, что в каждом множестве бТ^П] имеется по крайней мере счетное число предполных классов. Из результатов настоящей диссертации вытекает, что никаких других предполных классов, кроме найденных в [16], в множествах SG^Il] не существует, т. е. что в [16] были в действительности найдены все предполные классы в множествах «^[П]. В диссертации результаты, полученные для бинарных распределений из SQ, обобщаются на случай произвольных распределений из SQ: для любого множества распределений из SQ дается явное описание всех распределений, порождаемых этим множеством, и предлагается эффективный алгоритм, который для любого заданного распределения и любого заданного конечного множества распределений из SQ за полиномиальное время позволяет определить, порождается ли данное распределение данным множеством. Исходя из полученного решения проблемы выразимости произвольных распределений из SQ, описываются все замкнутые множества таких распределений и определяется структура диаграммы включений для этих множеств. Также устанавливается, какие из этих множеств являются конечно порожденными, и для каждого конечно порожденного множества непосредственно указывается одноэлементное подмножество, порождающее это множество. Кроме того, аналогично случаю бинарных распределений приводится ряд результатов, касающихся структуры замкнутых множеств произвольных распределений из SQ.

Следует отметить, что в ряде работ рассматривалось порождение вероятностных распределений с наложенными на него дополнительными ограничениями. Одним из таких ограничений является ограничение на класс функций, используемых для порождения распределений. Например, в [19, 20] рассматривалось порождение бинарных распределений в классе булевых функций, реализуемых бесповторными формулами над базисом {&, V}. Автором в работе [4]2 было показано, что в данном классе функций конечно порожденным является любое множество <7[П], где П конечно и содержит по крайней мере два числа. Остается открытым вопрос о конечной порожденности в классе булевых функций, реализуемых бесповторными формулами над базисом {&,V}, множеств Сг[{т?}], где р — простое число, большее 3. Ряд результатов, связанных с порождением бинарных распределений в более широком классе булевых функций, реализуемых бесповторными контактными схемами, получен автором в [5]. Из этих результатов вытекает, что в плане своих выразительных возможностей данный класс функций является значительно более слабым, чем класс всех булевых функций. Поэтому представляется интересным выявление классов булевых функций, сопоставимых по выразительности с классом всех булевых функций. В разделе 2.3 главы 2 показывается, что таким классом может оказаться класс всех монотонных булевых функций: для некоторых конечных систем бинарных распределений замыкания этих систем относительно порождения в классе всех монотонных булевых функций совпадают с их замыканиями относительно порождения в классе всех булевых функций.

Другим естественным ограничением, которое может быть наложено на порождение вероятностных распределений, является ограничение на число исходных ■ случайных величин. В данной работе мы полагаем, что для порождения распределений можно использовать неограниченное число независимых копий случайных величин с вероятностными распределениями из исходного множества распределений. Если ограничить возможное число таких копий, то мы имеем задачу оценки сложности порождения вероятностных распределений, где под сложностью порождения распределения понимается минимальное число исходных случайных величин, необходимое для порождения данного распределения. Такая сложность, очевидно, существенным образом зависит от исходного множества распределений. В работах [19, 20, 6, 7, 8, 24, 9] был нолучен ряд оценок сложности порождения бинарных распределений из SQ как в классе булевых

2Эта и другие работы автора, касающиеся вопросов, связанных с дополнительными ограничениями на порождение распределений, не включены в данную диссертацию. функций, реализуемых бесповторными формулами над базисом {&, V}, так и в классе всех булевых функций. Однако в общем случае эта задача остается нерешенной даже для класса всех булевых функций. Отметим, что предложенные в данной работе методы порождения вероятностных распределений являются экономными в плане использования исходных случайных величин и поэтому могут оказаться полезными для решения данной проблемы. Другим сложностным аспектом порождения вероятностных распределений, изучавшимся ранее в литературе [3, 12], является минимальная сложность реализации функций, применяемых для порождения этих распределений.

Тесно связанной с задачей оценки сложности порождения вероятностных распределений является задача приближенного порождения вероятностных распределений, заключающаяся в том, чтобы из заданного числа исходных случайных величин с заданными распределениями построить случайную величину с распределением, наиболее близким к требуемому вероятностному распределению. Интересные результаты, касающиеся приближенного порождения распределений, получены Р. Схиртладзе и Н. Нурмеевым в работах [20, 11]. Важной задачей, близкой по тематике к рассматриваемым вопросам, является также задача о минимальном имплицирующем векторе [10].

Отметим, что в данной работе мы рассматриваем порождение распределений посредством функций, все значения которых являются значениями реализуемых ими случайных величин. Такое порождение можно назвать синхронным. Начиная с середины прошлого века, в ряде работ [25, 23, 21, 13] рассматривалось порождение распределений посредством функций, которые кроме значений реализуемых случайных величин принимают также "неопределенное"значение. "Неопреде-ленное"значение функции означает, что мы не можем получить значение реализуемой случайной величины на данном наборе значений исходных случайных величин и поэтому надо использовать новую порцию исходных случайных величин для повторной попытки реализации требуемой случайной величины. Поскольку в таком случае требуемая случайная величина может быть получена с некоторой задержкой, пропорциональной числу повторных попыток ее реализации, в отличие от рассматриваемого синхронного порождения такое порождение можно назвать асинхронным. Асинхронное порождение распределений является практичным в случае, если реализуется большая серия случайных величин и допускается неограниченно большая задержка в реализации между двумя последовательными случайными величинами из этой серии. В противном случае такой подход к порождению распределений является неприемлемым. Одним из возможных путей устранения этого недостатка асинхронного порождения представляется комбинирование асинхронного порождения с синхронным порождением, заключающееся в том, чтобы в случае достаточно большой задержки при реализации случайной величины применять синхронное порождение, т. е. функцию, не принимающую "неопределен-ное"значение.

Еще раз отметим, что в данной работе все исходные случайные величины, используемые для порождения распределений, преполагаются независимыми в совокупности. Н. Нисаном и Д. Зукерманом в [27] было показано, что для приближенного порождения распределений с произвольной точностью могут также использоваться исходные случайные величины, не являющиеся независимыми. Функции, применяемые в таком случае, называются экстракторами. В последние годы за рубежом проводились активные исследования экстракторов (см., например, [26, 28, 29, 30]). Существенным недостатком экстракторов является их сравнительно высокая сложность: экстракторы требуют большого числа исходных случайных величин, и, соответственно, большой оказывается также сложность вычисления значений экстрактора.

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

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

Глава 2 содержит результаты для случая бинарных распределений из SQ. Сначала даются явное описание замыканий одноэлементных множеств чисел из PQ (теорема 3) и критерий порождаемости множества <?[П], где П конечно, любым заданным конечным подмножеством (теоремы 4 и 6). Затем эти результаты обобщаются на случай замыканий произвольных множеств чисел из PQ (теоремы 9, 11, и 13) и предлагается эффективный алгоритм, который для любого заданного числа и любого заданного конечного множества чисел из PQ за полиномиальное время позволяет определить, порождается ли данное число данным множеством (теорема 12). На основе полученного описания замыканий произвольных множеств чисел из PQ определяются все замкнутые подмножества множества PQ (теорема 14) и устанавливается структура диаграммы включений для этих подмножеств (утверждение 29). Также определяются все конечно порожденные замкнутые множества чисел из PQ (теорема 15) и для каждого такого множества непосредственно предъявляется конечное порождающее подмножество (теорема 16). Кроме того, приводится ряд результатов, касающихся структуры замкнутых множеств чисел из PQ. В частности, доказывается, что все замкнутые множества чисел из PQ имеют базис (следствие 28), и для каждого такого множества дается описание всех его предполных классов (следствия 29 и 30).

В главе 3 рассматривается порождение произвольных распределений из SQ. Сначала дается явное описание замыканий одноэлементных множеств стохастических векторов из SQ (теорема 18). Далее это описание обобщается на случай замыканий произвольных множеств стохастических векторов из SQ (теоремы 19 и 21). Исходя из полученного описания, предлагается эффективный алгоритм, который для любого заданного стохастического вектора и любого заданного конечного множества векторов из SQ за полиномиальное время позволяет определить, порождается ли данный вектор данным множеством (теорема 20). Затем определяются все замкнутые подмножества множества SQ (теорема 22) и устанавливается структура диаграммы включений для этих подмножеств (утверждение 39). Также определяются все конечно порожденные замкнутые множества векторов из SQ (теорема 24) и для каждого такого множества непосредственно предъявляется одноэлементное подмножество, порождающее это множество (теорема 23). Наконец, аналогично случаю бинарных распределений доказывается, что все замкнутые множества векторов из SQ имеют базис (следствие 41), и для каждого такого множества дается описание всех его предполных классов (следствия 42 и 43).

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

Автор глубоко признателен своему научному консультанту профессору А.В. Угольникову, академику РАН профессору О.Б. Лупанову, профессору О.М. Касим-Заде и доценту Ю.В. Таранникову за ряд ценных советов и замечаний, обсуждение и поддержку данной работы.

Заключение

В данной работе исследованы вопросы выразимости конечных вероятностных распределений с рациональными вероятностями посредством дискретных преобразований независимых вероятностных: распределений без учета сложностных аспектов этой выразимости (под сложностью порождения вероятностного распределения может пониматься как минимальное число исходных независимых случайных величин, необходимое для этого порождения, так и минимальная сложность реализации функции, используемой для этого порождения). Ряд вопросов, касающихся сложности порождения бинарных вероятностных распределений, рассмотрен в [3, 12, 24, 9]. Тем не менее проблемы, связанные со сложностью порождения вероятностных распределений, остаются недостаточно исследованными, и решение этих проблем является, на наш взгляд, важным этапом дальнейших исследований в данной области. Мы полагаем, что предложенные в работе методы могут быть использованы для получения асимптотически оптимальных оценок минимального числа исходных независимых случайых величин, необходимого для порождения конечных вероятностных распределений рациональных вероятностей.

Другим важным направлением дальнейших исследований, позволяющим в некоторой мере обобщить полученные результаты на случай произвольных конечных вероятностных распределений, является изучение приближенного порождения вероятностных распределений (см. [11, 20]). Представляется также интересным рассмотрение распределений вероятностей из числовых множеств, более широких, чем множество рациональных чисел (например, распределений вероятностей, являющихся алгебраическими числами (см. [12])).

Автор глубоко признателен О.В. Лупанову, А.Б. Угольникову, О.М. Касим-Заде и Ю.В. Таранникову за ряд ценных советов и замечаний, касающихся данной работы, и за поддержку проведенных исследований.

1. Бухараев Р.Г. Основы теории вероятностных автоматов. — М.: Наука, 1985.

2. Виноградов И.М. Основы теорий чисел. — М.: Наука, 1981.

3. Захаров В.М., Салимов Ф.И. К теории структурного синтеза детерминированных преобразователей вероятности // Problems of Control and Information Theory. — 1977. — V. 6 — N 2. — P. 137-148.

4. Колпаков P.M. О порождении некоторых классов рациональных чисел вероятностными 7г-сетями // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 1991. — N 2. — С. 27-30.

5. Колпаков P.M. О порождении рациональных чисел вероятностными контактными сетями // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 1992. — N 5. С. 46-52.

6. Колпаков P.M. Об оценках сложности порождения рациональных чисел вероятностными контактными 7Г-сетями // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 1992. — N 6. — С. 62-65.

7. Колпаков P.M. О порождении рациональных чисел вероятностными контактными тг-сетями // Дискретная математика. — 1994. — N 3. С. 18-38.

8. Колпаков P.M. О верхних оценках сложности порождения рациональных чисел вероятностными 7г-сетями // Вестник Моск. ун-та. Сер. 1 Математика. Механика. 1995. — N 5. — С. 99-102.

9. Колпаков P.M. О сложности порождения рациональных чисел одноэлементными множествами в классе всех булевых функций // Материалы VII межгосударственной школы-семинара "Синтез и сложность управляющих систем". — М.: Изд-во МГУ, 1996. — С. 13-14.

10. Кузнецов С.Е., Нурмеев Н.Н., Салимов Ф.И. Задача о минимальном имплицирующем векторе // Математические вопросы кибернетики. Вып. 3. М.: Наука, 1991. - С. 199-216.

11. Нурмеев Н.Н. О булевых функциях с аргументами, принимающими случайные значения // Тезисы докладов VIII Всесоюзной конференции "Проблемы теоретической кибернетики", Горький. — 1988.- Часть 2, С. 59-60.

12. Нурмеев Н.Н. О сложности реализации преобразователей вероятностей схемами из функциональных элементов // Методы и системы технической диагностики. Вып. 18. — Саратов: Саратовский гос. университет, 1993. — С. 131-132.

13. Рябко Б.Я., Мачикина Е.П. Эффективное преобразование случайных последовательностей в равновероятные и независимые // Проблемы передачи информации. — 1999. — Т. 36. — Вып. 2. — С. 23-28.

14. Салимов Ф.И. К вопросу моделирования булевых случайных величин функциями алгебры логики j j Вероятностные методы и кибернетика. Вып. 15. — Казань: Казанский гос. университет, 1979. — С. 68-89.

15. Салимов Ф.И. Конечная порожденность некоторых алгебр над случайными величинами // Вопросы кибернетики. Вып. 86. — М., 1982.- С. 122-130.

16. Салимов Ф.И. О максимальных подалгебрах алгебр распределений // Известия вузов. Сер. Математика. — 1985. — N 7. — С. 14-20.

17. Салимов Ф.И. Об одном семействе алгебр распределений // Известия вузов. Сер. Математика. — 1988. — N 7. — С. 64-72.

18. Салимов Ф.И. Конечная порожденность алгебр распределений j j Дискретный анализ и исследование операций. Сер. 1. — 1997. — Т. 4.- N 2. С. 43-50.

19. Схиртладзе P.JI. О синтезе р-схемы из контактов со случайными дискретными состояниями // Сообщ. АН ГрССР. — 1961. — Т. 26. — N 2.- С. 181-186.

20. Схиртладзе P.JI. О методе построения булевой случайной величины с заданным распределением вероятностей // Дискретный анализ. Вып. 7.- Новосибирск: ИМ СО АН СССР, 1966. С. 71-80.

21. Elias P. The efficient construction of unbiased random sequence // Annals of Math. Statistics. 1972. - V. 43. - N 3. - P. 865-870.

22. Hailperin Th. Boole's logic and probability: a critical exposition from the standpoint of contemporary algebra, logic and probability theory. — Amsterdam: North-Holland Publishing Co., 1976. (Studies in logic and the foundations of mathematics, V. 85).

23. Hoeffding W., Simons G. Unbiased coin tossing with a biased coin // Annals of Math. Statistics. — 1970. — V. 41. — P. 341-352.

24. Kolpakov R'.M. On the complexity of generation of rational numbers by Boolean functions // Fundamenta Informaticae. — 1995. — V. 22, — P. 289-298.

25. Neumann J. von. Various technique used in connection with random digits. Monte Carlo Method, Applied Mathematics Series. — 1951. — N 12.1. P. 36-38.

26. Nisan N., Ta-Shma A. Extracting randomness: A survey and new constructions // J. of Computer and System Sciences. — 1999. — V. 58.1. N 1. — P. 148-173.

27. Nisan N., Zuckerman D. Randomness is linear in space j j J. of Computer and System Sciences. — 1996. — V. 52. — N 1. — P. 43-52.

28. Raz R., Reingold O., Vadhan S. Error reduction for extractors // Proceedings of 40th Symposium on Foundations of Computer Science, New York (USA). 1999. - P. 191-201.

29. Srinivasan A., Zuckerman D. Computing with very weak random sources // SIAM J. on Computing. — 1999. — V. 28. — N 4. — P. 14331459.

30. Trevisan L. Construction of extractors using pseudo-random generators // Proceedings of 31th ACM Symposium on Theory of Computing, Atlanta (USA). — 1999. P. 141-148.

31. Список публикаций по теме диссертации

32. Колпаков P.M. О порождении рациональных чисел монотонными функциями // Теоретические и прикладные аспекты мат. исследований (сборник научных трудов). — М.: Изд-во МГУ, 1994. — С. 13-17.

33. Колпаков P.M. Критерий порождаемости некоторых множеств рациональных чисел булевыми функциями // Тезисы докладов XI Международной конференции "Проблемы теоретической кибернетики". — М.: Изд-во РГГУ, 1996. С. 96-97.

34. Колпаков P.M. Критерий порождения множеств рациональных вероятностей в классе булевых функций // Дискретный анализ и исследование операций. Сер. 1. — 1999. — Т. 6. — N 2. — С. 41-61.

35. Колпаков P.M. О преобразованиях булевых случайных величин j j Математические вопросы кибернетики. Вып. 9. — М.: Наука, 2000. — С. 227-252.

36. Колпаков P.M. О преобразованиях вероятностных распределений булевыми операторами // Материалы X межгосударственной школы-семинара "Синтез и сложность управляющих систем". — М.: Изд-во МГУ, 2000. С. 8-11.

37. Колпаков P.M. Замкнутые классы булевых случайных величин с ра-циональнозначными распределениями // Математические вопросы кибернетики. Вып. 10. — М.: Наука, 2001. — С. 215-224.

38. Колпаков P.M. Замыкания одноэлементных множеств бинарных распределений с рациональными вероятностями для многозначных преобразований // Математические вопросы кибернетики. Вып. 11. — М.: Наука, 2002. — С. 63-76.

39. Колпаков P.M. О дискретных преобразованиях конечных рациональ-нозначных вероятностных распределений // Тезисы докладов XIII Международной конференции "Проблемы теоретической кибернетики", Казань. — М.: Изд-во МГУ, 2002. — Часть I. — С. 92.

40. Колпаков P.M. О многозначных преобразованиях конечных множеств бинарных распределений с рациональными вероятностями // Дискретная математика. — 2005. — N 1.

41. Колпаков P.M. О дискретных преобразованиях конечных распределений с рациональными вероятностями // Математические вопросы кибернетики. Вып. 12. — М.: Наука, 2003. — С. 109-146.

42. Колпаков P.M. Замкнутые классы конечных распределений рациональных вероятностей // Дискретный анализ и исследование операций. Сер. 1. 2004. - Т. 11. - N 3. - С. 16-31.

43. Колпаков P.M. Полиномиальный алгоритм проверки порождаемости конечных распределений рациональных вероятностей // Материалы XV межгосударственной школы-семинара "Синтез и сложность управляющих систем". — Новосибирск: ИМ СО РАН, 2004.

44. Kolpakov R.M., Criterion of generativeness of sets of rational probabilities by a class of Boolean functions // Discrete Applied Mathematics. — 2003. V! 135 - P. 125-142.

45. Kolpakov R.M. Classes of Binary Rational Distributions Closed under Discrete Transformations // Stochastic Algorithms: Foundations and Applications (SAGA'03). — Springer Verlag, 2003. (Lecture Notes in Computer Science, V. 2827). — P. 157-166.