Исследования по теории итеративных систем, порождаемых конечными случайными величинами. Арифметический и комбинаторно-логический подход тема диссертации и автореферата по ВАК РФ 01.01.06, доктор наук Яшунский Алексей Дмитриевич

• Яшунский Алексей Дмитриевич
• доктор наук
• 2021

Оглавление диссертации доктор наук Яшунский Алексей Дмитриевич

2.2 Аппроксимационная полнота в Р2

2.3 Сильная аппроксимационная полнота Р^

2.4 Достаточные условия аппроксимационной полноты

2.5 Аппроксимационная полнота многочленов в кольцах вычетов

Глава 3. Предельные распределения итеративных систем

3.1 Булевы системы с конечным множеством распределений

3.2 Булевы системы с единственным предельным распределением

3.3 Число предельных распределений у булевых систем

3.4 Квазигрупповые системы и их обобщения

3.5 Системы с единственным предельным распределением

Глава 4. Логические, арифметические и смежные системы

4.1 Булевы системы

4.2 Конечные цепи

4.3 Выпуклые классы распределений на полях вычетов

4.4 Кольца вычетов и их обобщения

4.5 Поля вычетов и их обобщения

Заключение

Литература

Введение

Актуальность темы и степень ее разработанности

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

Понятие «преобразователя вероятности» как некоторого детерминированного устройства, получающего на входе значения случайных величин и осуществляющего вычисления с ними, тем самым генерируя новые случайные величины с иными распределениями, регулярно возникает в практических и теоретических исследованиях. Чаще всего речь идет о преобразованиях булевых случайных величин1, принимающих значения 0 и 1, в двоичных устройствах (см., например, [59,65]).

Рассматриваемые преобразователи случайных величин можно условно разделить на два класса. К первому относятся преобразователи, работающие с потенциально бесконечной последовательностью входных величин: это могут быть как преобразования последовательностей конечными автоматами (см. [32,56,69,70,80]), так и общие алгоритмы преобразования случайных последовательностей (например, [73,85]). При этом с практической точки зрения наиболее востребованной выглядит задача получения из произвольной случайной или псевдо-случайной последовательности равномерно распределенных случайных величин. Обзор результатов в этой области, называемой «извлечение случайности» («randomness extraction»), можно найти, например, в [94].

1 Также называемых «бернуллиевскими», подробнее см. Главу

Второй класс рассматриваемых преобразователей не предполагает обработки потенциально бесконечной последовательности случайных величин, а оперирует в каждом преобразовании с некоторым конечным набором случайных величин. Фактически каждый такой преобразователь вычисляет некоторую функцию от заданного набора случайных аргументов. Один из вариантов формализации таких преобразований — итеративная система, порождаемая некоторым набором операций и последовательностью случайных величин, в которой новые случайные величины получаются путем применения к исходных случайным величинам различных комбинаций имеющихся операций (далее — итеративная система случайных величин). Частным случаем итеративных систем случайных величин являются, например, преобразователи булевых случайных величин, рассматривавшиеся в [86,95,96].

Исследования подобных преобразующих систем для случайных величин, принимающих значения в произвольных конечных множествах, в частности, мотивированы задачами синтеза вероятностных автоматов [6], а также криптографическими приложениями [1, 82, 93] и вероятностными вычислениями. К последним относится как построение вычислительных устройств на вероятностных принципах (см. [65,100]), востребованное в автономных системах с ограниченными ресурсами, так и моделирование некоторых естественных систем, — см., например, работу [99] о «биологических» вычислительных системах.

Несмотря на очевидную вероятностную составляющую задачи, она оказалась практически вне поля зрения исследователей, занимающихся непосредственно теорией вероятностей. Так, например, в монографии У. Гренандера «Вероятности на алгебраических структурах» [10] рассматриваются практически только случайные величины с континуальным множествами значений: упоминания о конечных случайных величинах единичны и лишь иллюстрируют свойства, установленные для континуальных алгебраических структур.

Анализ и построение преобразователей конечных случайных величин порождают целый ряд задач, среди которых, в частности, присутствуют практически значимые вопросы об устойчивости преобразователей к колебаниям вероятностей аргументов (см. [13,14,48, 79,102]), построение управляемого генератора вероятностей (см. [5,14,97,98]) или же более теоретические вопросы о связи преобразований вероятностей со спектром булевых функций [74]. Однако центральным вопросом оказывается, собственно, описание случайных величин, реализуемых в различных итеративных системах.

Для описания имеющихся результатов введем ряд обозначений. Будем считать, что случайные величины принимают значения из множества Ек = {0,1,... ,к — 1}. Распределение случайной величины X со значениями в Ек, обозначаемое далее через Р(Х), будем понимать как век-

тор р = (р0,... ,Рк—1), г-я компонента которого — вероятность обращения X в г. Компоненты удовлетворяют условиям ^ = 1 и ^ 0, % = 0,...,к — 1. Такие вектора называются стохастическими, они образуют в К* симплекс, который будем обозначать Носителем вектора р е называется множество д(р) = {г е Ек | рг > 0} с Ек. Для некоторых распределений используем специальные обозначения, а именно, вершины стохастического симплекса будем обозначать е(0) = (1,0,..., 0), е(1) = (0,1,0..., 0),..., е(к—1) = (0,..., 0,1), а равномерное на множестве Ек распределение будем обозначать и = (1,..., 1).

Обозначим множество п-местных функций на Ек через Рк(п) и поло-

00

жим Рк = и Рк(п). Для заданного множества функций В с Рк и набора

п=0

независимых в совокупности случайных величин Х0, принимающих значения из Ек, распределения которых лежат в заданном множестве начальных распределений С порождаемая итеративная система случайных вели-

00

чин X определяется как объединение X = и Хп множеств:

П=1

V _ \ V \ I выразима бесповторным термом над В, \

= \!(Х1,...,ХП) ХхеХ0 ),

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

Чаще всего предполагается, что порождающее итеративную систему множество случайных величин Х0 бесконечно, однако в некоторых работах (Н. Н. Нурмеев [37], а также М.Д. Ридель и др. [89]) фактически рассматриваются итеративные системы, порождаемые конечными множествами случайных величин. Наиболее распространены постановки задач, в которых множество Х0 имеет вид {Хьё}гем,ёес где С — некоторое заданное множество начальных распределений. В дальнейшем мы будем рассматривать итеративные системы случайных величин, порождаемые именно такими наборами Х0, и обозначать их X(С, В).

Для заданной системы X = X(С, В) можно рассматривать задачу выразимости случайных величин, заключающуюся в описании множества {Р(Х) | X е X} распределений случайных величин, входящих в систему

X. Введя на множестве распределений метрику (мы будем использо-

к—1

вать метрику р(%, Ь) = ^ — можно также рассматривать в системе

¡=0

X задачу аппроксимируемости по распределению случайных величин. Она заключается в описании всех таких случайных величин У со значениями в Ек, что для любого е > 0 найдется случайная величина X е X, удовлетворяющая р(Р(Х), Р(У)) < е.

Множества распределений выразимых и аппроксимируемых в итеративной системе X(С, В) случайных величин можно описать как класс рас-

пределений, замкнутый относительно преобразований, связанных с операциями, входящими в систему В. Каждой функции /(х1,..., хп) е Рк(п) поставим в соответствие индуцированную вектор-функцию /, отображающую (8(^)п ^ 8(^, следующим образом. Пусть Х1,... ,Хп — независимые в совокупности случайные величины со значениями в Ек и распределениями р(1),..., р(п) е соответственно. Определим значение }(р(1),..., р(п)) как распределение ц е случайной величины /(Х1,..., Хп). Компоненты до,..., дк—1 распределения ц удовлетворяет равенствам:

® = Е №

(а1,...,ап):

Класс распределений Н с называется замкнутым относительно преобразований из множества В = {/ | / е В}, если для любых распределений Ь(1),..., Ь(п) е Н и любой функции /(х1,..., хп) е В выполнено /(Ь(1),...,Ь(п)) е Н. Наименьший по включению класс распределений, замкнутый относительно В, и содержащий заданное множество С будем обозначать Ув(С). Этот класс распределений оказывается (см. теорему 1.28 и ее следствия) в точности совпадающим с множеством распределений случайных величин, входящих в итеративную систему X(С, В). При этом множество распределений аппроксимируемых над системой X(С, В) случайных величин будет совпадать с топологическим замыканием множества Ув (С) (т. е. добавлением в него всех его предельных точек): обозначим его Wв(С). Таким образом, задачи выразимости и аппроксимируемости случайных величин в итеративных системах X(С, В) сводятся к исследованию структуры классов распределений, замкнутых относительно операторов Ув и Wв.

Классы распределений, замкнутые относительно операторов Ув и Wв для различных систем В, связанны между собой. Обозначая [В]0 множество всех функций, выразимых бесповторными термами над системой В можно записать равенства Ув(С) = У[щ0(С) и Шв(С) = W[щ0(С), т. е. преобразующие системы функций В можно рассматривать с точностью до их бесповторного замыкания [В]0. Среди бесповторно замкнутых классов функций [В]0 будут содержаться и замкнутые классы (клоны) [В], содержащие все функции, выразимые произвольными (не обязательно бесповторными) термами над В.

Если для систем В' и В'' выполнено соотношение [В']0 с [В'']0, то будем говорить, что В' — слабее, а В" — сильнее. Все классы распределений, замкнутые относительно индуцированных функций более сильной системы, будут также замкнуты относительно индуцированных функций более слабой системы. В частности, класс распределений Н, удовлетворяющий соотношениям УРк (Н) = Н (соответственно Wpk (Н) = Н) будет замкнут относительно оператора Ув (соответственно Wв) для любого В с Рк.

Задача выразимости рассматривалась в основном для случайных величин с рациональными распределениями, т.е. исследовались замкнутые подклассы распределений в множестве п 0>к, обозначаемом далее SQ(fc). Как несложно проверить, это множество замкнуто относительно всех функций из Рк. Отметим, что имеющиеся результаты о выразимости и замкнутых классах рациональных распределений оказываются в итоге связаны с факторизацией компонент вероятностных распределений, и по своей сути являются арифметическими.

При исследовании выразимости случайных величин с рациональными распределениями одним из центральных вопросов (в том числе и из прикладных соображений) была конечная порожденность классов случайных величин с распределениями из множества Н в итеративных системах X(С, В), понимаемая как существование такого конечного множества С с SQ(fc),что Ув(С) = Н.

Наиболее исследованной является задача выразимости булевых случайных величин (т. е. случай к = 2 для величин, принимающих значения в множестве Ек). Отметим, что их распределения (называемые бернул-лиевскими) полностью определяются одной из своих компонент, поэтому существует взаимно однозначное соответствие между распределениями (р0,р1) е 8(2) и отрезком [0; 1]. Традиционно оно устанавливается как (р0,р1) ^ р1, т. е. каждое бернуллиевское распределение однозначно определяется вероятностью обращения случайной величины в единицу. В качестве преобразователей булевых случайных величин выступают булевы функции. В свете упомянутого выше соответствия между 8(2) и отрезком [0; 1] можно рассматривать индуцированные ими функции как действующие на отрезке [0; 1] и, говоря о преобразованиях бернуллиевских распределений, понимать их как преобразования чисел из отрезка [0; 1]. Классы бернуллиевских распределений С естественно понимать как подмножества отрезка [0; 1], т. е. множества чисел.

Рассматривавшиеся ранее системы булевых функций В, порождающие итеративные системы булевых случайных величин X(С, В), перечислены1 ниже и упорядочены по включению.

[{&, -}]0 с [{(^1&Ж2) V (-(Ж1)&Ж3),С0,С1}]0

и п

[{&, V}]o с ВКС с [{&, V}] с Р2

Под Вкс понимается класс функций проводимости бесповторных контактных схем (см. [31]).

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

1Для булевых функций используются следующие обозначения: & — конъюнкция, V — дизъюнкция, - — отрицание, с0, с\ — константы, равные 0 и 1 соответственно.

сел. Пусть Я с N — некоторое (возможно бесконечное) множество взаимно простых чисел. Положим:

Г[Я] = /т rь...,га е Я а1,...,аа е ^ 1 |0 п

[ ] \п п = г^1 • • •г"а, 0 <т<п I { , }.

В случае конечного множества Я = {г,г3} будем опускать фигурные скобки, записывая Г[г..,г3]. Если все числа в множестве Я — простые, то легко проверяется равенство Ур2 (Г[Я]) = Г[Я], и, как следствие, замкнутость множества Г[ Я] относительно оператора Ув для произвольной системы булевых функций В.

В общем случае, т. е. если числа в Я не обязательно простые, а лишь взаимно просты, множества Г[ Я] могут не быть замкнутыми. В частности Ф. И. Салимовым в [45] для системы В = {(х\&х2) V (—(х\)&х3), с0,с 1} и, как следствие, для всех более сильных систем, в том числе и для Р2 показано, что включение Г[ Я] с Ув (Г[Я]) может быть строгим. Там же описаны фрагменты решетки замкнутых классов распределений, состоящие из множеств Г[ Я], где Я — множество простых чисел, и установлено, что каждый такой класс конечно порожденный тогда и только тогда, когда множество Я — конечно.

Помимо множеств Г[ Я] в решетку классов рациональных бернуллиев-ских распределений, замкнутых относительно УР2, входят некоторые их подмножества, определяемые ниже. Пусть Я — некоторое множество простых чисел, а Т — множество чисел, взаимно простых с каждым числом Я. Положим:

Г[Я; Т] = { т е Г[Я]

Тъ

НОД(т,п) = 1,

Т с т, п = п I, ъ = п I,

геТ' геТ\Т'

т = 0(modrl),т = n(mod т2)

и{0,1},

где пустое произведение считается равным 1. Тогда, в частности, выполнено равенство Г[ Я; 0] = Г[Я], т. е. множества Г[Я; Т] обобщают введенные выше множества Г[ Я].

В работе Ф. И. Салимова [45] показано, что в классы Г[ Я; {д}] замкнуты относительно оператора Ур2. Замкнутость Г[Я;Т] при произвольных конечных Я и Т вытекает из более общей теоремы.

Теорема (Р. М. Колпаков [25]). Пусть С = ,..., — конечное множество несократимых дробей, и Я — совокупность простых множителей, встречающихся в разложении чисел щ,... ,щ. Положим:

Т = {НОД(аь ..., аъ) | аг е {тг,пг - тг}}.

Тогда Ур2(С) = Г[Я; Т].

Эта теорема практически без изменений распространяется (см. [26]) на замыкания бесконечных подмножеств SQ(2), для этого требуется лишь доопределить наибольший общий делитель для бесконечных наборов натуральных чисел. В силу счетности множества SQ(2), таким образом описаны все подмножества Н с SQ(2), для которых выполнено равенство Ур2(Н) = Н: они исчерпываются множествами Г[Щ Т]. Также в [26] установлены отношения включения между различными множествами Г[Щ Т] и доказано, что Г[Я; Т] конечно порожденное тогда и только тогда, когда Я — конечно. Это обобщает ранее доказанное Ф. И. Салимовым в [42] утверждение о бесконечной порожденности множества SQ(2).

Для итеративных систем, порождаемых набором операций В = Р2 практически все имеющиеся результаты относятся к конечной порожден-ности классов Г[Д]. Даже если Я — конечное множество простых чисел, класс Г[Д], конечно порожденный относительно Ур2, может оказаться бесконечно порожденным относительно оператора Ув для более слабой системы В.

Один из «естественных» способов конструирования конечных порождающих множеств — составление их из наборов простых дробей со знаменателем г: А(г) = { ™ | 0 < т < г}. Такой подход, однако, не всегда приводит к нужному результату.

Среди различных систем булевых функций, отличных от Р2, наибольшее внимание уделялось системе {&, V}. Это обусловлено ее связью с бесповторными параллельно-последовательными контактными схемами. В работах [47,48] Р. Л. Схиртладзе (а также независимо и существенно позже Дж. Браком и др. в [97,98,101,102]) доказано, что У{&М(А(2)) = Г[2], У{&М(А(3)) = Г[3], и для всех простых г > 3 выполнено строгое включение (А(г)) с Г[г]. В работе Р. Л. Схиртладзе [48] также высказана гипотеза, что для простых г > 3 не существует такого конечного множества С, что У{&у}(С) = Г[г]. Эта гипотеза до настоящего момента не подтверждена и не опровергнута.

Р. М. Колпаков установил [17], что если г1,... ,г3 — простые и в ^ 2, то класс Г[г1,... ,г8] конечно порожден относительно оператора Более

того, если среди г1,... ,г8 содержится число 2 или 3, в качестве порождающей системы можно взять множество А(г1 • • • г3) (см. [19, 20]). Некоторые следствия из этого утверждения также независимо доказаны в работах Дж. Брака и др. [101,102].

Если г1,... ,г3 не содержит ни 2, ни 3, то, как показано в [20], множество Г[г1,... ,г3] также является конечно порожденным относительно однако не порождается совокупностью А(г1 • • • г3). Явное описание порождающей системы приведено в [20].

Проблема конечной порожденности множеств Г[г], остающаяся открытой для простых г > 3 при преобразованиях системой {&, V}, решена для некоторых более сильных систем. Система {&, -}, рассматривавшаяся в

работах [89,90] М. Д. Риделя и др., формально будучи сильнее чем {&, V}, в отношении конечной порожденности имеет те же возможности. Для системы В = {(ж1&ж2) V (-(ж1)&ж3),с0,с1} Ф. И. Салимовым в [40,41,45] установлено равенство Ув ^ |=) А(г^ = Г[г1,... ,г3], из которого, в частности,

следует, что Ув(А(г)) = Г[г].

Одно из естественных обобщений системы {&, V}, рассматриваемой как функции проводимости бесповторных параллельно-последовательных контактных схем, — рассмотрение множества Вкс функций проводимости произвольных бесповторных контактных схем. Р. М. Колпаков в [18] построил такие системы В с Вкс, что классы Г[5] и Г[7] конечно порождены относительно Ув.

Кроме того, Р. М. Колпаков построил в [21] систему В с [{&, V}], не входящую в множество Вкс, для которой при произвольном (не обязательно простом) г выполнено соотношение Ув (А(г)) э Г[г]. Отсюда в частности вытекает, что для любого простого числа г имеет место равенство %&М](Жт)) = Г[г].

Все упомянутые выше конечные порождающие системы, естественно, являются таковыми и относительно оператора Ур2. Кроме того, в работе [24] Р. М. Колпаковым для Ур2 найден критерий порождения множества Г[г1,... ,г3] заданной конечной системой С.

00

Со случайной величиной X е X(С, В) = и Хп, можно связать слож-

п=1

ность ее выражения в итеративной системе, понимаемую обычно как наименьшее такое значение п, что X е Хп. Под сложностью реализации в системе X случайной величины с заданным распределением р, именуемой далее сложность распределения р понимается минимальная сложность случайной величины X е X, удовлетворяющей Р(Х) = р.

Некоторые оценки сложности распределений для итеративных систем булевых случайных величин вида X(С, {&, V}) получены Р. Л. Схиртладзе в [47,49] (позже эти же и некоторые другие оценки независимо получены Дж. Браком и др. в [97,98]). Эти результаты были обобщены Р. М. Колпаковым в [17,19,20,22], где, в частности, построены конечные порождающие системы, для которых найдены точные по порядку значения сложности распределений. Эти оценки частично воспроизведены в работах [101,102] Дж. Брака и др., содержащих также более сильные верхние оценки сложности для некоторых частных случаев. Известны усиления (относительно оценок для систем X(С, {&, V})) верхних оценок сложности для других систем: в частности, с множеством операций {&, -} (см. [89,90]) и {&, V} (см. [21]).

В итеративных системах X(С, Р2) верхние оценки сложности распределений могут быть дополнительно усилены. Для распределений из классов Г[г], г — простое, имеется верхняя оценка, вытекающая из построе-

ний Ф. И. Салимова [45], независимо полученная затем Дж. Браком и др. в [91]. Для этих же классов Р. М. Колпаковым в [23] найдено точное значение функции Шеннона сложности распределений из множества А(гп) в зависимости от п.

Часть результатов о выразимости, конечной порожденности и сложности, полученных для классов рациональных бернуллиевских распределений, переносится на распределения из классов SQ(k) при к > 2. Классы бернуллиевских распределений Г[Я] обобщаются следующим образом. Для набора взаимно простых чисел Я положим:

Р№)[Я] — { (±

/ ¿о 4-1\

ч > о

Еъ- = г;

НОД( г о,..., г ,-1) = 1;

г1,..., Е Я,а1,... ,а8 Е М;

> и {е

(о)

у — У

а\

е

(к-1у

Очевидно, что Г(к)[Я] с SQ(к). Ф. И. Салимов в [42] показал, что если Я содержит только простые числа, то классы Г(к)[ Я] замкнуты относительно Урк, и являются конечно порожденными, если Я конечно. Более того, в [42,43] показано, что при к ^ 3 для Г(к)[Я], где Я — набор простых чисел, существует порождающая относительно Урк система, состоящая из единственного элемента.

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

Г(к)[ Я; Т ]

— < (т°

тк-1

) Е Г(к) [ Я]

ЭТк-2 с Тк-3 с ... С То с Т

с То с

Ш] = 0(шо^ П

]=о

Ш] = г(шо^ ПО, 0 —

]=о

1ЕТ\Т

Доказательство замкнутости Г(к) [ Я; Т] относительно Урк в частном случае Т — {(}, где 1ЕЯ — простое число, приведено в работах [44,45] Ф. И. Салимова. В [46] им же при некоторых дополнительных условиях установлена конечная порожденность таких классов.

Окончательное описание структуры подклассов SQ(k), замкнутых относительно УРк, получено Р. М. Колпаковым: сначала он в [27] описал множества УРк({р}) для удовлетворяющих условию |д(р)| — 2 распределений р Е SQ(k), а затем получил описание замыкания произвольного конечного подмножества С с SQ(k).

Теорема (Р. М. Колпаков [28, 30]). Пусть задано конечное множество распределений С — ^(1),..., gw} с SQ(k). Для р — ,..., е SQ(k)

поло-

1

жим т (р) = {НОД (Ш0,... ,т3-1,т]+1,... ,тк-1)}3=0..,к-1 и пусть

Т = {НОД(й1, ... ,аь) | а, е г(g(г ))},

а множество Я состоит из всех простых множителей, встречающихся в разложениях знаменателей компонент распределений g(г ), г = 1,... ,Ь. Тогда выполнено УРк(С) = Г(^[Я; Т].

Аналогичное утверждение выполняется и в случае, если множество начальных распределений С счетно (см. [29]): как и в случае бернуллиевских распределений требуется лишь доопределить НОД для счетных множеств натуральных чисел. Таким образом, множества Г(к) [Я; Т] исчерпывают все подклассы класса SQ(fc), замкнутые относительно Урк. Структура решетки этих подклассов, частично описанная в [44], полностью приводится в [29]. При этом класс Г(^[Д; Т] является конечно порожденным относительно Урк тогда и только тогда, когда Я конечно.

Для рациональных распределений на произвольном конечном множестве почти не рассматривались итеративные системы случайных величин с набором операций, отличным от Рк. Практически единственным исключением оказывается обобщение булевых систем с операциями {&, V}, изучавшееся в работах [75-77] Дж. Брака и др. В них Ек рассматривается как линейно упорядоченное множество с естественным порядком 0 < 1 <...< к — 1, для которого вводятся операции минимума Л и максимума V, обобщающие булевы функции & и V соответственно. Установлено, что при использовании операций {Л, V} с Рк все распределения из класса Г(Л)[г], где г — произвольное (не обязательно простое), порождаются в итеративной сиистеме с множеством начальных распределений С = {е(0),..., е(^—1)} и {(^1, 0,..., 0,1) | г = 2,...,г}. Помимо включения Г(*0[{г}] с У{Л ^}(С) в этих работах доказаны также верхние оценки сложности распределений из класса Г(Л)[г].

Отметим, что задача выразимости рассматривалась практически исключительно для случайных величин с рациональными распределениями. Исключением оказывается лишь работа Н. Н. Нурмеева [38], где анонсированы некоторые результаты о распределениях из Ур2 ({р}) для произвольного р е 8(2). Помимо этого итеративные системы булевых случайных величин с начальным множеством из произвольных распределений рассматривались в работах М.Д. Риделя и др. [89, 90], а также Дж. Брака и др. [91]. В обоих случаях решается задача поиска распределения р, порождающего множество Г[Я] относительно Ур2, т. е. удовлетворяющего ({р}) ^ Г[Д]. Отсутствие таких распределений в классе SQ(2) вытекает из результатов Ф. И. Салимова [40].

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

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

Один из первых результатов, касающихся аппроксимируемости случайных величин, был получен Р. Л. Схиртладзе в [48,49]. Он показал, что для произвольного бернуллиевского распределения р е 8(2) \ {е(0),е(1)} выполнено равенство ^{&,у?-}({р}) — 8(2). Таким образом, множество 8(2) оказывается конечно порожденным относительно оператора и,

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

Результат Р. Л. Схиртладзе был независимо воспроизведен а также частично усилен в работах Дж. Брака и др. [101,102], где, в частности, установлено, что для р е 8(2) \ {е(0), е(1)} выполнено W{&;V}({p}) — 8(2). Отметим, что доказательства как в работах Р. Л. Схиртладзе, так и в работах Дж. Брака и др. являются конструктивными, поэтому из них сразу же выводятся верхние оценки сложности аппроксимации произвольного бер-нуллиевского распределения.

Вопросы аппроксимации булевых случайных величин также рассматриваются в работах и Н. Н. Нурмеева [37] и М. Д. Риделя и др. [89]: в обоих случаях исследуется вопрос об оптимальном выборе конечного множества булевых случайных величин ДО для аппроксимации произвольных булевых случайных величин с помощью произвольных операций из Р2.

Из установленного Р. Л. Схиртладзе равенства W{&;V;-}({p}) — 8(2) при р Е Э(2) \ {е(0), е(1)} естественно вытекает равенство WР2({р}) — 8(2) при тех же условиях на распределение р. В случае распределений на /^элементном множестве при к > 2 выполнение равенства WРk({р}) — 8(к) для р Е SQ(k)\{е(0),..., е(к—1)} вытекает из результатов Р. М. Колпакова о строении замкнутых классов рациональных распределений [28,30], однако для произвольных р е 8(к) \ {е(0),..., е(к—1)} вывести это непосредственно из результатов Р. М. Колпакова, вообще говоря, нельзя.

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

Итеративная система конечных случайных величин, порождаемая би-

и и и и 7—I

нарной полугрупповой операцией, заданной на Ек, может быть исследована с помощью аппарата марковских цепей в силу ассоциативности

полугрупповой операции. Соответствующие построения упоминаются в книге У. Гренандера [10], а также исследуются для более общего случая дискретных полугрупп в работе П. Мартина-Лёфа [83]. В терминах замкнутых классов распределений фактически изучается множество ^{0}({р}), где о — полугрупповая операция. При этом из свойств цепей Маркова вытекает, что множество ^{0}({р}) \ ^и({р}) конечно, а если соответствующая цепь эргодическая, то в множестве Ж{0}({р}) имеется единственная предельная точка. Содержательно это соответствует выполнению в соответствующей полугруппе некоторого предельного вероятностного закона. Некоторые результаты о связи между структурой полугруппы и свойствами этого предельного закона рассмотрены, например, в работе Дж. Р. Барнеса и др. [62].

В случае, если операции о является не только полугрупповой, но и групповой, соответствующая цепь Маркова имеет бистохастическую матрицу переходов и при некоторых дополнительных условиях на носитель д(р) единственным предельным распределением соответствующей итеративной системы является равномерное распределение и. Это утверждение наряду с другими свойствами сумм случайных величин в конечных абе-левых группах приводится в работе Н. Н. Воробьева [7]. В настоящее время основные усилия исследователей в этой области нацелены на установление связей между свойствами групп и скоростью сходимости к предельному распределению. Обзор соответствующих результатов приведен в работе Л. Салофф-Коста [92].

Непосредственный перенос результатов о полугруппах на другие операции неосуществим, поскольку снятие требования ассоциативности операций лишает возможности непосредственного сведения к марковским цепям и, как следствие, использования соответствующего аппарата. Однако, даже если марковские цепи не позволяют моделировать все вычисления в итеративной системе, можно рассматривать подмножества случайных величин из итеративной системы, заведомо моделируемых цепями Маркова. Именно таким образом в работе С. Марковски и др. [81] установлены некоторые свойства итеративных систем, порождаемых конечным набором квазигрупповых операций (которые не обязательно ассоциативны). В используемых нами обозначениях одно из утверждений этой работы можно записать как ^{0ь...)0в}({р}) э и, где о1,..., о5 — какие-то квазигрупповые операции.

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

чин.

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

Аппроксимируемость случайных величин в итеративных системах изучена еще меньше, хотя полученные результаты позволяют рассчитывать на более простую (чем для задачи выразимости) структуру замкнутых классов распределений. Хотя бы частичное описание классов распределений, замкнутых относительно оператора Wв для В = Рк позволит не только расширить представления о возможностях аппроксимации конечных случайных величин в итеративных системах, но и даст дополнительную информацию выразимости случайных величин в системах, порождаемых более слабыми системами операций нежели Рк.

Введение диссертации (часть автореферата) на тему «Исследования по теории итеративных систем, порождаемых конечными случайными величинами. Арифметический и комбинаторно-логический подход»

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

Цели и задачи работы

1. Обобщение результата Р. Л. Схиртладзе об аппроксимируемости булевых случайных величин в системе с операциями {&, V, -} на другие системы булевых и произвольных конечных случайных величин, установление границ возможности подобных обобщений.

2. Исследование условий единственности предельного распределения в итеративной системе, описание различных необходимых и/или достаточных условий.

3. Описание замкнутых классов распределений конечных случайных величин в итеративных системах, порождаемых важными (с арифметической, логической, алгебраической) точки зрения системами операций — клонами булевых функций, кольцами и полями вычетов, группами и их обобщениями.

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

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

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

Практическая и теоретическая значимость. Диссертация носит теоретический характер. Ее результаты могут быть использованы в дискретной математике, теории вероятностей на алгебраических структурах, математической кибернетике и теоретической информатике.

Положения, выносимые на защиту

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

2. Достаточные условия аппроксимационной полноты и критерий аппроксимационной полноты класса многочленов над кольцом вычетов.

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

4. Условия единственности предельного распределения в произвольных итеративных системах случайных величин.

5. Описание классов случайных величин, аппроксимируемых по распределению в итеративных системах булевых случайных величин, порождаемых клонами булевых функций.

6. Конструкции замкнутых классов распределений случайных величин из итеративных систем с операциями конечной цепи.

7. Конструкции замкнутых классов распределений случайных величин из итеративных систем с операциями колец и полей вычетов, а также некоторых их обобщений.

Степень достоверности и апробация результатов. Все результаты диссертации математически строго доказаны. Они многократно докладывались на объединенном семинаре кафедры дискретной математики, кафедры математической теории интеллектуальных систем механико-математического факультета и кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ имени М.В.Ломоносова «Математические вопросы кибернетики», семинаре кафедры высшей алгебры и семинаре «Анализ и физика» кафедры математических и компьютерных методов анализа механико-математического

факультета МГУ имени М.В.Ломоносова, семинаре «Теоретическая кибернетика» и семинаре имени К.И. Бабенко в ИПМ им.М.В.Келдыша РАН, на семинаре отдела дискретной математики Математического института им. В.А.Стеклова РАН, на семинаре лаборатории дискретного анализа Института математики им. С.Л.Соболева СО РАН, на семинаре «Алгебра, геометрия и квантование» в МФТИ, на международной школе-семинаре «Синтез и сложность управляющих систем» имени академика О. Б. Лупа-нова (Пенза, 2009 г.), международном семинаре «Дискретная математика и ее приложения» имени академика О.Б. Лупанова (Москва, 2010, 2016, 2019 гг.), международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011 г.; Пенза, 2017 г.), международной конференции LOOPS по квазигруппам и лупам (Трешт, Чехия, 2011 г.; Будапешт, Венгрия, 2019 г.) молодежной школе по дискретной математике и ее приложениям (Москва, 2011 и 2013 гг.), Индо-Российской конференции по алгебре, теории чисел, дискретной математике и приложениям (Москва, МГУ, 2014 г.), международной конференции «Дискретные модели в теории управляющих систем» (Красновидово, 2015 и 2018 гг.), конференции Ломоносовские чтения (2016, 2018, 2019, 2020 гг.), конференции AAA'95 по общей алгебре (Братислава, Словакия, 2018 г.), всероссийской конференции по алгебре и теории алгоритмов (Иваново, 2018 г.), международной алгебраической конференции памяти А.Г. Куроша (Москва, 2018 г.), международной конференции по алгебраическим структурам, математической логике, теории чисел памяти Э.Артина (Ереван, Армения, 2018 г.), Мальцевских чтениях (Новосибирск, 2016 и 2018 гг.), международной конференции «Вероятностные методы в дискретной математике» (Петрозаводск, 2019 г.), международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории» (Тула, 2015 и 2019 гг.).

Содержание диссертации

Диссертация состоит из введения, четырех глав и заключения. Утверждения, уравнения и рисунки нумеруются внутри каждой главы отдельно, их номера предваряются номером главы. Внутри главы для всех утверждений (лемм, теорем, следствий) нумерация сплошная.

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

В Главе 1 приводится ряд определений и простейших утверждений, связанных с выразимостью и аппроксимируемостью в итеративных системах конечных случайных величин. Помимо уже введенных выше обозначений и понятий, вводятся обозначения с0,с\,... ,ск—\ для константных функций со значениями 0,1,... ,к — 1, и хк для сложения иумно-

жения шо^, Л и V для минимума и максимума относительно порядка 0 < 1 < ••• < к - 1.В частном случае к = 2 операция +2 обозначается также как 0, а операция Л — как &. Булевы функции у хг&х^ обозначаются йп(х1,..., хп). Для множеств распределений Н с 8(к) определяются аффинная и выпуклая оболочки:

t-i } h(0),...,h(t-i) g H, $>i = И ,

i=0 J

t-1 Л

h(0),...,h(t-i) g H, £>i = 1,«o ^ 0,...,at-i ^ 0\ ,

=0

(t-i

Aff (H) = E «ih(i) L i=o ft-i

Conv(H) = ^ E «ih(i) =0

где умножение распределений h(i ) на числа ai и их последующее сложение выполняется как для элементов Rk.

Совокупность предельных точек множества распределений G обозначается через A(G). Для введенных ранее операторов VB(G) и WB(G) в случае одноэлементного G = {g} принимается соглашение о записи VB (g) и Wb (g).

Также вводятся обозначения некоторых замкнутых и бесповторно замкнутых классов функций из Pk, необходимых для дальнейшего изложения. В частности, для булевых функций принимаются следующие обозначения: L = [{ci, 0}], М = [{со, ci,&, V}], To = [{0,&}], S = [{d3, -}], ОИ = [{-(ж) V у, d,+i}], О- = [{-(ж) Vy}], К = [{со, Ci, &}], D = [{со, сь V}], U = [{со, -}]. Кроме того, классы, двойственные к T0, ОИ и О- обозначаются через Ti, Iй и I— соответственно. Классы, получающиеся в результате пересечения, обозначаются записью подряд пересекаемых классов, при этом пересечение с T0 и Ti обозначается нижним индексом 0 или 1 соответственно, т.е. М n 13 nTi = Mi3.

Класс функций, выразимых многочленами mod к, обозначается Ak (в случае составного к он отличен от Pk), класс функций, имеющих не более одной существенной переменной, обозначается Pk. Для каждого из непустых подмножеств Т С Ek определяются следующие классы: Cq—константные функции со значениями в Т; Sq— функции с не более, чем одной существенной переменной, являющиеся перестановками на Т; Qi— класс функций (с точностью до добавления несущественных переменных), у которых любая 1-подфункция лежит в классе Sj; Q- — класс функций, у которых какая-то 1-подфункция лежит в классе Sj.

Помимо определений и обозначений Глава 1 содержит ряд утверждений о свойствах индуцированных функций и замкнутых относительно операторов VB, WB классов распределений. Эти свойства используются далее в работе для доказательства основных утверждений.

В Главе 2 рассматриваются условия, при которых система преобразующих операций В с Pk обладает свойствами аналогичным системе булевых функций {&, V, -}, т. е. порождает итеративную систему, в которой

любая случайная величина аппроксимируется по распределению. Вводится понятие аппроксимационной полноты системы функций В с Рк, понимаемое как выполнение равенства Wв (р) = 8(Л) для некоторой совокупности распределений р. Выделяется три типа аппроксимационной полноты: слабая, если равенство Wв(р) = 8(Л) выполняется для некоторого р, удовлетворяющего д(р) = Ек; стандартная, если то же равенство верно для любых р, удовлетворяющих д(р) = Ек; сильная, если то же равенство выполнено для любых р, удовлетворяющих |д(р)| > 1.

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

Следствие 2.3. Если для некоторого множества Т С Ек, Т = 0, система В с Рк удовлетворяет В с О^, то В не является слабо аппроксимационно полной.

Из этого утверждения вытекает аппроксимационная неполнота классов булевых функций К, Р и Ь.

Для наиболее сильной преобразующей системы В = Рк в Главе 2 доказывается (в теореме 2.19) ее сильная аппроксимационная полнота в смысле определения данного выше.

Достаточные условия аппроксимационной полноты системы В с Рк представлены в весьма общей форме в теореме 2.22. Использование этих условий позволяет дополнить операции кольца вычетов (Ек; {+£, хк}) и конечной цепи (Ек; {V, Л}) до аппроксимационно полной (в стандартном смысле) системы. Из этих теорем, кроме того, вытекает существование конечных сильно аппроксимационно полных систем операций.

Теорема 2.23. Система В = {с0,...,ск-1, +к, хк,^(х)} с Рк, где 7(х) — функция, принимающая ровно два значения 0 и 1, аппроксимационно полна.

Теорема 2.25. Система В = {с0,... ,ck-l, V, Л,7(ж)} с Рк, где 7(х) функция, принимающая ровно два значения 0 и к - 1, аппроксимационно полна.

Наконец, важным результатом Главы 2 является критерий аппрокси-мационной полноты класса многочленов Лк.

Теорема 2.29. Класс Лк аппроксимационно полон тогда и только тогда, когда к — степень простого числа.

В Главе 3 исследуются условия, при которых у случайных величин из итеративной системы имеется единственное предельное распределение,

т. е. фактически в итеративной системе выполняется некоторый предельный вероятностный закон. Такие итеративные системы характеризуются выполнением равенства |А(Ув(С))| = 1 для порождающей системы функций В и множества начальных распределений С.

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

Первый из результатов Главы 3 касается итеративных систем булевых случайных величин с конечным множеством распределений (и, как следствие, с пустым множеством предельных распределений).

Теорема 3.4. Пусть для конечного множества бернуллиевских распределений С с [0; 1] и множества булевых функций В выполнено Ув (С) = С. Тогда имеет место по крайней мере одно из следующих утверждений:

1. С с {0,1}.

2. В С и.

3. С = {р}, р е (0; 1).

4. С С {0,1,1}, В С Ь.

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

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

£(0) = К, £( 1) = Ь и £(1) = В.

Теорема 3.7. Пусть множество бернуллиевских распределений С с [0; 1] имеет единственную предельную точку q е [0; 1] и для некоторой системы булевых функций В выполнено Ув (С) = С. Тогда либо В с ми, либо выполнено q е {0,1, 1} и В с В(д).

Наконец, установлено, что за исключением (в определенном смысле) тривиального случая В с и, итеративная система булевых случайных величин X(С, В) не может иметь конечное число предельных распределений большее 1.

Теорема 3.13. Пусть для С с [0; 1] и В с Р2 выполнено Ув(С) = С. Если при этом Х(С) конечно, то либо В с и, либо |А(С)| < 2.

Обобщение теоремы 3.7 с систем булевых случайных величин на произвольные конечные случайные величины опирается на свойства итеративных систем, порождаемых операциями с квазигрупповыми свойста-ми. В Главе 3 доказывается ряд утверждений об аппроксимируемости равномерно распределенных случайных величин в итеративных системах с квазигрупповыми операциям. Одним из наиболее общих результатов в этом направлении является следующая теорема. Фигурирующие в ней Т-поглощающие квазигрупповые операции составляют класс, ранее обозначенный как Qт. Такие классы обобщают фигурировавшие в теореме 3.7 классы К,Ь,И с Р2, поскольку для Т С Е2 выполнены равенства Q{o} = К, ^0,1} = L, Q{1} = И.

Теорема 3.28. Пусть задано множество Т С Ек, функция /(х1} ...,хг) е Рк,

I , -А — I/ I/ ЬУ

являющаяся г-арной, Ь > 1, Т-поглощающей квазигрупповои операцией и распределение g е Э(к), удовлетворяющее условию д(g) э Т. Тогда \(У{^(g)) с {д}, где = Т и дг = щ для г е Т.

В отличие от случая к = 2 полностью охарактеризовать (по аналогии с теоремой 3.7) все итеративные системы с единственным предельным распределением в случае произвольного к не удается, однако «исключительные» итеративные системы, в которых единственность предельной точки не обязательно влечет ограничения на множество операций, можно описать в терминах «геометрии» классов распределений.

В формулировке следующей теоремы, обобщающей теорему 3.7, используются следующие определения. Множество распределений С с 8(к) называется существенно плоским, если для любого конечного С' с С выполнено Aff(G\С') Э 8(к). Множество С с Э(к) называетсяX-множеством, если найдутся такие множества С1 и С2, что С = С1 и С2 и при этом

Ай^С^ Э Э(к), Aff(G2) э Э(к).

Теорема 3.31. Пусть множество распределений С с 8(к) не является ни существенно плоским, ни X-множеством и имеет единственную предельную точку д. Если В с Рк — некоторое множество операций, удовлетворяющее равенству Ув(С) = С, то выполнено В с Qм(q) и СЕк, а если В \ Рк = 0, то дг = для всех г е д(а) и дг = 0 для всех г е Мч), т.е. д — равномерное на д(ц) распределение.

В Главе 4 исследуется задача аппроксимируемости случайных величин в итеративных системах, порождаемых некоторыми специальными системами операций, а именно — клонами булевых функций, конечными цепями, кольцами и полями вычетов, и некоторыми схожими с ни-

ми системами. Для означенных систем строятся семейства классов распределений, замкнутых относительно оператора Wв (в отдельных случаях вплоть до полного описания решетки замкнутых классов распределений). Это позволяет частично решать задачу аппроксимируемости случайных величин, указывая в каждом случае множество случайных величин, которые заведомо не могут быть аппроксимированы, и, в частности, доказывать аппроксимационную неполноту некоторых систем.

Первая часть результатов Главы 4 относится к итеративным системам булевых случайных величин, порождаемых клонами булевых функций. В теореме 4.15 получено описание всех классов распределений 1№А(р), где А — какой-то клон и р е (0; 1). На основе этой теоремы полностью описана решетка классов распределений, замкнутых относительно операторов WA, где А — клон, не содержащийся в К, И или Ь.

Теорема 4.16. Пусть А с Р2 — клони А с К, И, Ь. Тогда совокупность непустых замкнутых классов распределений С с [0; 1], удовлетворяющих №а(С) = С, исчерпывается следующими множествами:

1. {0,1}, [0; 1] для любого клона А.

2. {0} если А с То, {1} если А с Ть

3. {1} если А с 5.

4. [0; р], где р < 1 - 1, если А с I1, [р; 1] где р ^ 1 если А с Ом.

Для классов распределений, замкнутых относительно WA, где А — под-клон одного из клонов К, И или Ь, также доказывается набор критериальных свойств (теорема 4.17), однако они не позволяют эффективно описать всю решетку замкнутых классов распределений, подобно тому, как это делается в теореме 4.16.

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

Затем в Главе 4 рассматривается класс итеративных систем конечных случайных величин, порождаемых операциями конечной цепи, а именно Л и V, обозначающими соответственно минимум и максимум относительно линейного порядка на множестве Ек. Эти системы — одно из естественных обобщений булевой системы {&, V}.

Вводятся следующие два семейства множеств распределений, завися-

щие от числа а> 1 и индекса г е Ek:

L(i,a) = jp = (po,...,pk-i) е S(k)

U(i,a) = i p = (Po,...,Pk-i) е S(k)

i-i

Epj ^ j=0

-i k-i

E Pj < E Pj

j=i+i \ j=i

)"} ■

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

Теорема 4.26. Для любого а > 1 и любого i е Ek выполнены соотношения

W{v,A}(L(i,aO) = L(i,a) и W{v^}(U(i,a)) = U(i,a).

Теорема 4.26, позволяет, во-первых, установить аппроксимационную неполноту системы {Л, V}, а, во-вторых, может быть использована для ограничения снизу некоторых замкнутых классов распределений, т. е. описания распределений, заведомо входящих в W^)V}(G) для некоторых множеств G с S(k). В частности, доказывается

Теорема 4.28. Пусть p е S(k) удовлетворяет д(р) = Ek. Тогда для всех i е Ek \ {0} выполнено Conv(e(i-1), e(i )) с W{vA}(p)

Далее в Главе 4 исследуются итеративные системы случайных величин, порождаемые операциями колец и полей вычетов. В теореме 4.33 описываются некоторые выпуклые классы распределений, замкнутые относительно W{+kx}, где +k, xk — сложение и умножение в поле вычетов mod к, к — простое. Затем, за счет усложнения конструкции классов распределений, эти построения обобщаются на случай колец вычетов mod&, т. е. распространяются на случай произвольного к. Для набора распределений g(1),..., g(t) е S(k) и подмножества М с Ek определяются следующие классы распределений:

K = {e(j) X (g(* ) + e( s)) | s е Ek} U {e(0)}, K (M) = {h(ijl) +k • • • +k h(i jm) | {ji, ...,Jm} = M, h(^) е Щг}, K(g(1),..., g(t); M) = {j(1) +k • • • + j(t) | j(1) е Ki(M),..., j(t) е K(M)}.

С использованием этих конструкций описываются семейства выпуклых классов распределений, замкнутых относительно W{+k,Xfc}. Эти утверждения могут быть распространены и на итеративные системы случайных величин, порожденные другими конечными кольцами. В частности, доказывается следующая теорема, выполненная как для колец вычетов mod к, так и для других ассоциативных колец с единицей.

Теорема4.38. Пусть (Ек; {+к, хк}) — ассоциативное кольцо с единицей, 0 е Ек — его нулевой элемент, и с Ек — группа обратимых элементов. Обозначим через Z множество Ек \ (и и {0}). Для заданных распределений g(1),..., g(t) е 8(к), положим:

I = {е^ Хк (^г ) +к е( 5)) \зеи,8 еЕк ,г = 1,..., 1}

и Н = Сопу(1 и К^(1),..., g(t); Z)) Тогда ^}(Н) = Н.

Наконец, в Главе 4 рассматриваются итеративные системы случайных величин, порождаемые операциями о и •, которые обобщают операции +к и хк поля вычетов modк ( к —простое). Предложены конструкции семейств классов распределений (в том числе невыпуклых), замкнутых относительно оператора ^{о,.}. В утверждениях ниже предполагается, что о — квазигрупповая операция на Ек, удовлетворяющая тождествам х о 0 =

0 ох = х, а • — квазигрупповая операция на Ек \ {0}, удовлетворяющая тождествам х • 0 = 0 •х = 0.

Для распределений х = (х0,... ,хк-1) е 8(к) вводятся величины е(х) =

1 - х0 и 5г(х) = хг - е(х)/(к - 1), г = 1,... ,к - 1, с помощью которыхопре-деляются следующие классы распределений:

На,ъ = {х е Э(к): е(х) ^ Ь} П ^ Ц {х е 8(к): \й(х)\ ^ ^-т}^ , КаАс = Пг=о {х е 8(к): \8г(х)\ ^ а - а(е - к), \й(х)\ ^ а + а(е - к)} ,

-1

, (х е : \дг(х)\ ^ а - т(£ - к), \дг(х)\ ^ а '

где к = к-11, иа,а,Ь,с ^ 0 — параметры. Доказываются теоремы:

Теорема 4.44. Пусть параметр а удовлетворяет условиям 0 < а ^ 1, положим К = К а,к(к-1)а2,н. Тогда Ж{о,.}(К) = К.

Теорема 4.45. Для любого к ^ 3 найдется такое а0(к), что при всех а ^ ао(к) множества 1а = (Н«Л и Ка,к(к-1)а2,к(к-1)а2), где а = удовлетворяют равенству W{о•^}(Ia) = I«.

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

Глава 1

Итеративные системы конечных случайных величин

В настоящей главе представлены определения и простейшие утверждения, связанные с алгебраическими преобразованиями конечных случайных величин. Вначале рассматривается применение одной операции к набору независимых случайных величин и свойства возникающих в этом случае преобразований распределений случайных величин (разделы 1.11.3), а затем вводится понятие итеративной системы конечных случайных величин, формулируется задача аппроксимируемости конечных случайных величин в итеративной системе и демонстрируется связь этой задачи с описанием замкнутых классов распределений (разделы 1.4,1.5). Некоторые из приводимых в настоящей главе утверждений, по-видимому, надо считать «фольклорными», однако в тех случаях, где было возможно установить первоисточник утверждения или понятия, он указан явно.

1.1 Случайные величины и индуцированные функции

1.1.1 Определения

Будем рассматривать (здесь и далее везде) случайные величины на некотором вероятностном пространстве, принимающие значения в заданном конечном множестве. Для дальнейшего удобства будем считать, что к-элементное множество значений случайной величины состоит из элементов 0,1,... ,к - 1 и будем обозначать его Ек.

Распределение конечной случайной величины X со значениями в Ек полностью определяется набором вероятностей событий {X = г} для всех % е Ек, т. е. рг = Р{Х = г}. Эти вероятности образуют ^-мерный вектор р, компоненты которого нумеруются элементами множества Ек, т. е. р = (ро,... ,рк—1). Далее под распределением конечной случайной величины X будем понимать именно вектор р, не делая дополнительных оговорок. Для обозначения распределения случайной величины X будем использовать символ Р(Х), т. е. полагать Р(Х) = р.

Каждый вектор р является элементом множества Кк, дополнительно удовлетворяющим условиям:

к-1

"^Рг = 1, Р0 > 0,...,Рк-1 > 0. (1.1)

¡=0

Эти условия задают в пространстве Кк симплекс размерности к — 1, который мы будем обозначать 8(к) и называть стохастическим симплексом. Его элементы называют стохастическими векторами, мы будем также использовать термины вектор распределения и просто распределение, в тех случаях когда это не приводит к двусмысленностям. Носителем вектора р е 8(к) будем называть множество д(р) = {г е Ек | рг > 0}.

Для распределений, являющихся вершинами стохастического симплекса 8(к), будем использовать обозначения е(0) = (1,0,..., 0), е(1) = (0,1,0,..., 0), ..., е(к—1) = (0,..., 0,1). Также будем использовать обозначение и для равномерного распределения (1,..., 1) е 8(к). Схематическое изображение стохастического симплекса приведено на Рис. 1.1.

е(1) = (0,1, 0,..., 0)

е(°) = (1

е(к-1) = (0,..., 0,1)

Рис. 1.1. Стохастический симплекс

Случайные величины, принимающие значения из двухэлементного множества Е2 = {0,1}, будем называть булевыми случайными величинами, а их распределения (элементы симплекса Э(2)) — бернуллиевскими распределениями1. При к = 2 стохастические вектора имеют вид (ро,р1), при этом

1Для случайных величин, принимающих ровно два значения — 0 и 1, также используется термин бер-

• • ' к,

р0 + р1 = 1, откуда легко видеть, что каждый двухкомпонентныи стохастический вектор в действительности полностью определяется одной из своих компонент. Для определенности будем считать, что это компонента р1, тогда элементы Э(2) представляются в виде (1 — р, р), где 0 < р < 1. Это устанавливает очевидное взаимно однозначное соответствие между элементами 8(2) и действительными числами из отрезка [0; 1], что позволяет в дальнейшем, говоря о распределениях булевых случайных величин, оперировать числами из отрезка [0;1]. Фактически эти числа выражают вероятность того, что соответствующая случайная величина принимает значение 1 е Е2. Графическое изображение соответствия между Э(2) и отрезком [0; 1] приведено на Рис. 1.2.

Пусть Хг,... ,Хп — независимые в совокупности случайные величины со значениями в множестве Ек с распределениями р(1),..., р(п) е 8(к) соответственно, а /(хь... ,хп) — некоторая функция, отображающая ЕП в Ек>. Тогда /(Х1,..., Хп) — случайная величина со значениями в Ек'. Ее распределение — вектор из к ), который зависит от р(1),..., р(п). Для заданного набора распределений р(1),..., р(п) и функции / обозначим распределение случайной величины /(Хь ... ,Хп) через /(р(1),..., р(п)) и будем говорить, что функция /(хь... ,хп): Е% ^ Ек' индуцирует функцию /(р(1),...,р(п)), отображающую (8(к))п ^ 8(к). При этом ¿-я компонента вектор-функции / для % е Ек с учетом независимости Х1,... ,Хп в совокупности, удовлетворяет равенствам:

(Др(1),..., р(п)))г = Р{ / (Х1,..., Хп) = *} = ^ Р{Х1 = 01,..., Хп = *п} = = Е Р{Х = Р{Х„ = 0„} = £ рЦ ■■■ р£>.

/(а1,...,ап)=г /(сть...,ст„)=г

нуллиевские случайные величины (см. [34,55]), однако во избежание смешения этого понятия со случайными величинами, возникающими в испытаниях Бернулли, мы будем придерживаться термина «булева случайная величина», сохраняя для распределений название «бернуллиевские».

Оставляя в этой цепочке равенств только первое и последнее выражение, получаем соотношения для всех i е Ек, которые фактически можно считать определением индуцированной функции:

(f(p(1),..., pW))i= £ $ ••• (1.2)

(аь...,а„:

Пусть Pk(п) = {/ | / : ^ Ек} — множество n-местных функций на

00

Ек и Рк = U Рк(п). Функции из множества Р2 называются булевыми. Для

Список литературы диссертационного исследования доктор наук Яшунский Алексей Дмитриевич, 2021 год

Литература

[1] Артамонов В. А. Квазигруппы и их приложения // Чебышевский сб. 2018. Т. 19, вып. 2. С. 111-122.

[2] Ашманов С. А. Линейное программирование. М.: Наука, 1981.

[3] Белоусов В. Д. Основы теории квазигрупп и луп. М.: Наука, 1967.

[4] Белоусов В.Д. n-Арные квазигруппы. Кишинев: Штиинца, 1972.

[5] Бухараев Р. Г. Об управляемых генераторах случайных величин // Вероятностные методы и кибернетика. II, Сборник работ НИИММ им. Н. Г. Чеботарева при Казанском университете, Учен. зап. Казан. унта., 123, № 6, ред. Р. Г. Бухараев, Изд-во Казанского ун-та, Казань, 1963.-С.68-87.

[6] Бухараев Р. Г. Вероятностные автоматы // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет. 1978. Т. 15. С. 79-122.

[7] Воробьев Н. Н. Сложение независимых случайных величин на конечных абелевых группах//Матем. сб. 1954. Т. 34(76), № 1. С. 89-126.

[8] Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1, &, V, -} //Дискретная математика. 2005. Т. 17, №2. С. 139-143.

[9] Выхованец В. С. Алгебраическая декомпозиция дискретных функций // Автоматика и телемеханика. 2006. № 3. С. 20-53.

[10] Гренандер У. Вероятности на алгебраических структурах. — М.: Мир, 1965.

[11] Гиндикин С. Г., Мучник А. А. Решение проблемы полноты для систем функций алгебры логики с ненадежной реализацией//Проблемы кибернетики. Вып. 15. М.: Наука, 1965. С. 65-84.

[12] Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. — М.: Наука, 1981.

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

[14] Захаров В. М., Салимов Ф. И. К вопросу синтеза преобразователей вероятности // Вероятностные методы и кибернетика. Вып. 15. — Казань, 1978. — С. 47-50.

[15] Зубков О. В. Нахождение и оценка числа бесповторных булевых функций в базисе {&, V, —} // Известия вузов. Математика. 2008. №10. С. 17-24.

[16] Калужнин Л. А., СущанскийВ. И. Преобразования и перестановки. — М.: Наука, 1979.

[17] Колпаков Р. М. О порождении некоторых классов рациональных чисел ^-сетями // Вестник МГУ. Серия 1. Математика. Механика. 1991. № 2. С. 27-30.

[18] Колпаков Р. М. О порождении рациональных чисел вероятностными контактными сетями//Вестник МГУ. Серия 1. Математика. Механика. 1992. № 5. С. 46-52.

[19] Колпаков Р. М. Об оценках сложности порождения рациональных чисел вероятностными контактными ^-сетями // Вестник МГУ. Серия 1. Математика. Механика. 1992. № 6. С. 62-65.

[20] Колпаков Р. М. О порождении рациональных чисел вероятностными контактными ^-сетями//Дискретная математика. 1994. Т. 6, вып. 3. С. 18-38.

[21] Колпаков Р. М. О порождении рациональных чисел монотонными функциями // Теоретические и прикладные аспекты математиче-скихисследований: Сб. науч. тр. М.: Изд-во Моск. ун-та, 1994. С. 1317.

[22] Колпаков Р. М. О верхних оценках сложности порождения рациональных чисел вероятностными ^-сетями // Вестник МГУ. Серия 1. Математика. Механика. 1995. № 5. С. 99-102.

[23] Kolpakov R. M. On the complexity of generation of rational numbers by Boolean functions//Fundamenta Informaticae. 1995. V. 22, N 3. P. 289298.

[24] Колпаков Р. М. Критерий порождения множеств рациональных вероятностей в классе булевых функций // Дискретный анализ и исследование операций. 1999. Т. 6, № 2. С. 41-61.

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

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

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

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

[29] Колпаков Р. М. Замкнутые классы конечных распределений рациональных вероятностей//Дискретный анализ и исследование операций. 2004. Т. 11, № 3. С. 16-31.

[30] Колпаков Р. М. О многозначных преобразованиях конечных множеств бинарных распределений с рациональными вероятностями // Дискретная математика. 2005. Т. 17, вып. 1. С. 102-128.

[31] Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр. МИАН СССР, Т. 51, Изд-во АН СССР, М., 1958, С. 186-225.

[32] Макаревич Л. В. О реализуемости вероятностных операторов в логических сетях//Дискретный анализ. Вып.15. 1969. С. 35-56.

[33] Мальцев А. И. Алгебраические системы. М.: Наука, 1970.

[34] Манита А. Д. Теория вероятностей и математическая статистика: Учебное пособие. М.: Издат. отдел УНЦ ДО, 2001.

[35] Марченков С. С. Основы теории булевых функций. М.: ФИЗМАТЛИТ, 2014. 136 с.

[36] Маршалл А., Олкин И. Неравенства. Теория мажоризации и ее приложения. М.: Мир, 1983.

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

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

[39] Перязев Н. А. Реализация булевых функций бесповторными формулами//Дискретная математика. 1995. Т. 7, № 3. С. 61-68.

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

[41] Салимов Ф. И. Об одной системе образующих для алгебр над случайными величинами//Изв. вузов. Матем. 1981. № 5. С. 78-82.

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

[43] Салимов Ф. И. О шефферовых элементах в алгебрах распределений // III Всесоюзн. симпозиум по вероятност. автоматам и их прилож. Тезисы докл. — Казань, 1983. С. 104.

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

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

[46] Салимов Ф. И. Конечная порожденность алгебр распределений // Дискретный анализ и исследование операций. Сер. 1.1997. Т. 4, № 2. С. 43-50.

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

[48] Схиртладзе Р. Л. Моделирование случайных величин функциями алгебры логики. Автореферат канд. дис. Тбилиси, 1966.

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

[50] Угольников А. Б. Классы Поста. М.: Изд-во ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова, 2008. 64 с.

[51] Феллер В. Введение в теорию вероятностей и ее приложения. Тт.1-2. М.: Мир, 1984.

[52] Черемушкин А. В. Бесповторная декомпозиция сильно зависимых функций//Дискретная математика. 2004. Т. 16, № 3. С. 3-42.

[53] Черемушкин А. В. К вопросу о линейной декомпозиции двоичных функций//Прикладная дискретная математика. 2016. № 1(31). С. 46-56.

[54] Черемушкин А. В. О линейной разложимости двоичных функций // Прикладная дискретная математика. 2018. № 40. С. 10-22.

[55] Ширяев А. Н. Вероятность: В 2-х кн. 4-е изд., переработ. и доп. М.: МЦНМО, 2007.

[56] ШтефкаЙ. Преобразователи вероятности //Kybernetika. Прага, 1971. Т. 7, вып. 3. С. 218-226.

[57] Яблонский С. В. Введение в дискретную математику. — М.: 2001.

[58] Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

[59] Яковлев В. В., Федоров Р. Ф. Стохастические вычислительные машины. — Л.: Машиностроение, 1974.

[60] Янов Ю. И., Мучник А. А. О существовании £;-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127, №1. С. 44-46.

[61] Яшунский А. Д. О вероятностях значений случайных булевых выражений: Дис____канд. физ.-мат. наук. Москва, МГУ имени М. В. Ломоносова, 2006.

[62] Barnes G. R., Cerrito P. B., Levi I. Random walks on finite semigroups // J. Appl. Probab. 1998. V. 35, N 4. P. 824-832.

[63] Bernstein S. Demonstration du theoreme de Weierstrass fondee sur le calcul des probabilitees // Commun. Soc. Math. Kharkov. 1912. Vol. 13. P. 1-2.

[64] Brodsky A., Pippenger N. The Boolean functions computed by random Boolean formulas or how to grow the right function // Random Structures and Algorithms. 2005. V. 27. P. 490-519.

[65] Chakrapani L., Korkmaz P., Akgul B., Palem K. Probabilistic system-on-a-chip architecture // ACM Transactions on Design Automation of Electronic Systems. 2007. 12(3). Pp. 1-28.

[66] Flajolet Ph., Odlyzko A. M. Singularity analysis of generating functions // SIAM J. on Algebraic and Discrete Methods. 1990. Vol. 3, No 2. P. 216240.

[67] Flajolet Ph., Sedgewick R. Analytic combinatorics. Cambridge Univ. Press, New York, NY, USA. 2009.

[68] Frankl P. On Sperner families satisfying an additional condition // J. Comb. Theory (A). 1976. V. 20. P. 1-11.

[69] Gill A. Synthesis of probability transformers // Journal of the Franklin Institute. 1962. Vol. 274, no. 1. P. 1-19.

[70] Gill A. On a weight distribution problem, with application to the design of stochastic generators // Journal of the ACM. 1963. Vol. 10, no. 1. Pp. 110-121.

[71] GolumbicM. C., GurvichV. A. Read-once functions//Boolean Functions: Theory, Algorithms and Applications / Eds. Crama Y., Hammer P. L. Cambridge: Cambridge University Press, 2011. Pp. 448-486.

[72] Hall M. An Existence Theorem for Latin Squares // Bull. Amer. Math. Soc. 1945. V. 51, N6. P. 387.

[73] Knuth D. E., Yao A. C. The Complexity of Nonuniform Random Number Generation // Algorithms and Complexity. Academic Press, New York, 1976. Pp. 31O-428.

[74] Laski J. The analysis and synthesis of probability transformers // Journal of Engineering Mathematics, Vol. 7, No. 4, October 1973. Pp. 289-295.

[75] Lee D., Bruck J. Generating Probability Distributions using Multivalued Stochastic Relay Circuits//Paradise, ETR106, February, 2011.

[76] Lee D., Bruck J. Generating Probability Distributions using Multivalued Stochastic Relay Circuits // IEEE International Symposium on Information Theory Proceedings (ISIT), 2011. Pp. 308-312. DOI 10.1109/ISIT.2011.6034134

[77] Lee D.T., Bruck J. Algorithms for generating probabilities with multivalued stochastic relay circuits // IEEE Trans. Comp. 2015. Vol. 64, No. 12. P. 3376-3388.

[78] Lindqvist B. Ergodic Markov chains with finite convergence time // Stochastic Processes and their Applications. 1981. V. 11. P. 91-99.

[79] Loh P., Zhou H., Bruck J. The robustness of stochastic switching networks. Proc. IEEE ISIT (2009). pp. 2066-2070.

[80] Lorenc A. A. On the synthesis of generators of stable probability distributions // Information and control. 1974. V. 24. - P. 212-230.

[81] Markovski S., Gligoroski D., Bakeva V. Ouasigroup String Processing: Part 1 // Proc. of Maked. Academ. of Sci. and Arts for Math. And Tech. Sci. XX. 1-2. 1999. P. 13-28.

[82] Markovski S. Design of crypto primitives based on quasigroups // Ouasigroups and Related Systems. 2015. Vol. 23, No 1. P. 41-90.

[83] Martin-Lof P. Probability theory on discrete semigroups // Z. Wahrscheinlichkeitstheorie und Verw. Gebiete. 1965. Vol. 4. P. 78102.

[84] Moore E.F., Shannon C.E. Reliable circuits using less reliable relays // Journal of the Franklin Institute. 1956. V. 262, N 3. P. 191-208.

[85] von Neumann J. Various techniques used in connection with random digits //Appl. Math. Ser., Notes by G.E. Forstyle, Nat. Bur. Stand. 1951. Vol. 12. P. 36-38.

[86] Parker K. P., McCluskey E. J. Probabilistic treatment of general combinational networks // IEEE Transactions on Computers, 1975. Vol. 24, no. 6, Pp. 668-670.

[87] Post E. L. The two-valued iterative systems of mathematical logic. Annals of Mathematics studies, no. 5. Princeton University Press, Princeton, 1941. 122 pp.

[88] Rado R. An Inequality// J. London Math. Soc. 1952. V. 27, N 1.

[89] Oian W., Riedel M.D., Barzagan K., Lilja D. The Synthesis of Combinational Logic to Generate Probabilities // Proc. Int'l Conf. Computer-Aided Design, 2009. P. 367-374.

[90] Oian W., Riedel M. D., Bazargan K., Lilja D. J. Synthesizing combinational logic to generate probabilities: Theories and algorithms // Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer New York, 2011. Pp. 337-357. DOI: 10.1007/978-1-4419-7518-8_18

[91] Oian W., Riedel M. D., Zhou H., Bruck J. Transforming probabilities with combinational logic // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 2011. Vol. 30. P. 1279-1292.

[92] Saloff-Coste L. Random walks on finite groups // Probability on discrete structures. Encyclopaedia Math. Sci., 110. Springer, Berlin, 2004. P. 263346.

[93] ScerbacovV. Ouasigroups in cryptology//Comp. Sci. J. of Moldova. 2009. Vol. 17, No 2 (50). P. 193-228.

[94] Shaltiel R. An Introduction to Randomness Extractors // Automata, Languages and Programming. ICALP 2011. Aceto L., Henzinger M., Sgall J. (eds) LNCS V. 6756. Springer, Berlin, Heidelberg. P. 21-41.

[95] Sheng C. L. Threshold logic elements used as a probability transformer, Journal of the ACM, vol. 12, no. 2, pp. 262-276, April, 1965.

[96] Warfield J. N. Synthesis of Switching Circuits to yield prescribed probability relations // Symp. on Switching and Logical Design, Ann. Arbor, Mich. Oct. 6-8, 1965. P. 303-309.

[97] Wilhelm D., Bruck J. Stochastic switching circuit synthesis // Proc. IEEE International Symposium on Information Theory (ISIT). 2008. Pp. 13881392.

[98] Wilhelm D., Bruck J. Stochastic Switching Circuit Synthesis // Paradise, ETR089, September, 2008 [revised May 19, 2009].

[99] Wilhelm D., Bruck J., Oian L. Probabilistic Switching Circuits in DNA// Proc. Nat. Acad. Sci. U.S.A. 2018. Vol. 115. P. 903-908.

[100] Oian W., Riedel M. D. Synthesis of Polynomial Functions // Stochastic Computing: Techniques and Applications. Eds. Gross W. J., Gaudet V. C. Springer, 2019. Pp. 103-120.

[101] Zhou H., Bruck J. On the expressibility of stochastic switching circuits // Proc. IEEE ISIT (2009). P. 2061-2065.

[102] Zhou H., Loh P., Bruck J. The Synthesis and Analysis of Stochastic Switching Circuits//https://arxiv.org/abs/1209.0715v1 (2012)

Публикации по теме диссертации

Статьи в рецензируемых научных изданиях, рекомендованных для защиты в диссертационном совете МГУ по специальности 01.01.06

[103] Yashunsky A. D. Asymptotics of the probability of values of random Boolean expressions // Journal of Applied and Industrial Mathematics. 2007. Vol. 1, No. 4. P. 509-531.

[104] Яшунский А. Д. О равномерном приближении непрерывных функций функциями вероятности булевых базисов//Вестник МГУ. Серия 1. Математика. Механика. 2007. № 2. С. 37-43. (Перевод: Yashunskii A. D. Uniform approximation of continuous functions by probability functions of Boolean bases // Moscow Univ. Math. Bull. 2007. Vol. 62, No 2. P. 78-84.)

[105] Яшунский А. Д. О преобразованиях распределений вероятностей бесповторными квазигрупповыми формулами // Дискретная математика. 2013. Т. 25, № 2. С. 149-159. (Перевод: Yashunskii A. D. On transformations of probability distributions by read-once quasigroup formulae // Discrete Mathematics and Applications. 2013. Vol. 23, no. 2. P. 211-223.)

[106] Яшунский А. Д. О бесповторных преобразованиях случайных величин над конечными полями // Дискретная математика. 2015. Т. 27, № 3. С. 145-157. (Перевод: Yashunsky A. On read-once transformations of random variables over finite fields // Discrete Mathematics and Applications. 2015. Vol. 25, no. 5. P. 311-321.)

[107] Яшунский А. Д. Выпуклые многогранники распределений, сохраняемые операциями конечного поля//Вестник МГУ. Серия 1. Математика. Механика. 2017. № 4. С. 54-58. (Перевод: Yashunskii A.D. Convex polyhedra of distributions preserved by operations over a finite field // Moscow Univ. Math. Bull. 2017. Vol. 72, No. 4. P. 165-168.)

[108] Яшунский А. Д. Конечные алгебры бернуллиевских распределений // Дискретная математика. 2018. Т. 30, №2. С. 148-161. (Перевод: Yashunsky A. D. Finite algebras of Bernoulli distributions//Discrete Mathematics and Applications. 2019. Vol. 29, no. 4. P. 267-276.)

[109] Yashunsky A. D. Algebras of probability distributions on finite sets //

Proceedings of the Steklov Institute of Mathematics. 2018. Vol.301, no. 1. P. 304-318.

[110] Yashunsky A. D. Clone-induced approximation algebras of Bernoulli distributions//Algebra Universalis. 2019. Vol. 80, no. 1.

[111] Яшунский А. Д. Выпуклые алгебры вероятностных распределений, индуцированные конечными ассоциативными кольцами // Дискретная математика, 2019. Т. 31, № 1. С. 133-142.

[112] Яшунский А. Д. Алгебры бернуллиевских распределений с единственной предельной точкой // Вестник МГУ. Серия 1. Математика. Механика. 2019. № 4. С. 3-9. (Перевод: Yashunskii A.D. Algebras of Bernoulli distributions with a single limit point // Moscow Univ. Math. Bull. 2019. Vol. 74, No. 4. P. 135-140.)

[113] Яшунский А. Д. Полиномиальные преобразования случайных величин на конечных множествах//Матем. заметки. 2019. Т. 106, вып. 6. С. 951-954. (Перевод: Yashunskii A. D. Polynomial Transformations of Random Variables on Finite Sets // Math. Notes. 2019. Vol. 106, No. 6. P. 1024-1027.)

[114] Yashunsky A. D. Limit Points of Bernoulli Distribution Algebras Induced by Boolean Functions // Lobachevskii Journal of Mathematics. 2019. Vol.40, No. 9. P. 1423-1432.

[115] Еременко А. Р., Яшунский А. Д. О весе функций, заданных бесповторными И/ИЛИ формулами // Интеллектуальные системы. Теория и приложения. 2019. Т. 23, № 3. С. 41-55.

[116] Яшунский А. Д. О необходимых условиях предельных вероятностных теорем в конечных алгебрах // Доклады РАН. Математика, информатика, процессы управления. 2020, T. 493, № 1. С. 47-50.

[117] Яшунский А. Д. Об аппроксимации случайных величин над конечной цепью // Дискретный анализ и исследование операций. 2020. Т. 27, № 3. С. 109-125.

[118] Yashunsky A. D. On Necessary Conditions of Finite-valued Random Variable Algebraic Approximation // Lobachevskii Journal of Mathematics. 2021. Vol. 42, No. 1. P. 216-220.

Прочие публикации

[119] Яшунский А. Д. О преобразованиях вероятности бесповторными булевыми формулами // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г.) — М.: Изд-во механико-математического факультета МГУ, 2006. — С. 150-155.

[120] Яшунский А.Д. Об одном семействе распределений вероятностей, порождаемом бесповторными формулами над конечными полями // Материалы IX молодежной научной школы по дискретной математике и ее приложениям. 2013. С. 127-130.

[121] Яшунский А.Д. О множествах распределений вероятностей, сохраняемых операциями конечного поля // Препринты ИПМ им. М. В. Келдыша. 2014. № 51. 20 с.

[122] Яшунский А.Д. Об операциях с независимыми случайными величинами над конечным линейно упорядоченным множеством // Труды IX Международной конференции «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 20-22 мая 2015 г.) М.: МАКС Пресс, 2015. С. 272-274.

[123] Яшунский А.Д. О преобразованиях случайных величин над линейно упорядоченным трехэлементным множеством//Алгебра, теория чисел и дискретная геометрия: современные проблемы и приложения: Материалы XIII Междунар. конф., посвященной 85-летию со дня рождения профессора Сергея Сергеевича Рышкова. Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н.Толстого, 2015. С. 206-208.

[124] Яшунский А. Д. О выпуклых многогранниках распределений, сохраняемых операциями конечного поля // Препринты ИПМ им. М.В. Келдыша. 2016. № 11. 10 с.

[125] Яшунский А. Д. Преобразования бернуллиевских распределений булевыми функциями из замкнутых классов // Препринты ИПМ им. М.В. Келдыша. 2016. № 38. 23 с.

[126] Яшунский А. Д. Приближения вероятностных распределений функциями ^-значной логики//Препринты ИПМ им. М.В.Келдыша. 2016. № 58. 7 с.

[127] Яшунский А. Д. О преобразованиях дискретных случайных величин многочленами//Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.) : Материалы. М. : МАКС Пресс, 2017. С. 268-271.

[128] Яшунский А. Д. Конечные системы операций для аппроксимации дискретных вероятностных распределений // Препринты ИПМ им. М.В. Келдыша. 2017. № 10. 7 с.

[129] Яшунский А. Д. О конечных алгебрах бернуллиевских распределений // Препринты ИПМ им. М. В. Келдыша. 2018. № 34. 19 с.

[130] Яшунский А.Д. О подалгебрах вероятностных распределений над конечными кольцами // Препринты ИПМ им. М.В.Келдыша. 2018. №84. 14 с.

[131] Яшунский А. Д. Алгебры бернуллиевских распределений с единственной предельной точкой // Препринты ИПМ им. М.В. Келдыша. 2018. №135. 16 с.

[132] Яшунский А.Д. О предельных точках алгебр бернуллиевских распределений // Препринты ИПМ им. М.В.Келдыша. 2018. № 270. 16 с.

[133] Яшунский А. Д. Конечные алгебры бернуллиевских распределений // Дискретные модели в теории управляющих систем. Труды X Международной конференции. 2018. С. 288-291.

[134] Яшунский А. Д. О необходимых условия алгебраической аппроксимации случайных величин на конечном множестве // Вероятностные методы в дискретной математике. Расширенные тезисы докладов X Международной Петрозаводской конференции. 2019. С. 121123.

[135] Яшунский А. Д. О предельных точках в алгебрах дискретных вероятностных распределений // Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории. Материалы XVII Международной конференции, посвящённой 100-летию со дня рождения профессора Н. И. Фельдмана и 90-летию со дня рождения профессоров А. И. Виноградова, А. В. Малышева и Б. Ф. Скубенко. 2019. С.68-72.