Работа посвящена исследованиям дискретных преобразований независимых вероятностных распределений. Под дискретным преобразованием вероятностных распределений понимается вероятностное распределение конечной случайной величины, значение которой является функцией от значений случайных величин с исходными вероятностными, распределениями. Такие преобразования играют важную роль в вопросах реализации случайностей, имеющих большое значение для многих разделов дискретной математики и математической кибернетики (см. [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) и критерий порождаемости множества .
В главе 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])).
Автор глубоко признателен О. В. Лупанову, А. Б. Угольникову, О.М. Касим-Заде и Ю. В. Таранникову за ряд ценных советов и замечаний, касающихся данной работы, и за поддержку проведенных исследований.
