1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 493, № 1, 2020

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 493, № 1, стр. 47-50

О НЕОБХОДИМЫХ УСЛОВИЯХ ПРЕДЕЛЬНЫХ ВЕРОЯТНОСТНЫХ ТЕОРЕМ В КОНЕЧНЫХ АЛГЕБРАХ

А. Д. Яшунский 1, *

1 Институт прикладной математики им. М.В. Келдыша Российской академии наук
Москва, Россия

* E-mail: yashunsky@keldysh.ru

Поступила в редакцию 20.03.2020
После доработки 01.06.2020
Принята к публикации 02.06.2020

Полный текст (PDF)

Аннотация

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

Ключевые слова: конечная алгебра, случайная величина, предельная теорема, квазигруппа, равномерное распределение

Изучение предельного поведения сумм случайных величин является одним из важных вопросов в теории вероятностей. Наиболее значимые результаты в этом направлении, собирательно известные как “центральная предельная теорема”, относятся к суммам действительных случайных величин. Вместе с тем известны обобщения предельных теорем на алгебраические структуры, отличные от аддитивной группы действительных чисел. Одно из естественных обобщений заключается в замене сложения произвольной групповой операцией на некотором множестве: примеры предельных теорем для различных континуальных групп можно найти в книге У. Гренандера [1]. Изучение алгебраических структур на конечных множествах (конечных алгебр) с точки зрения выполнения в них предельных вероятностных теорем не получило столь широкого распространения. Однако уже в работе Н.Н. Воробьева [2] рассматриваются предельные вероятностные теоремы для конечных абелевых групп. Обзор современного состояния исследований по предельным законам в конечных группах имеется в [3]. В настоящее время интерес к задачам об алгебраических преобразованиях случайных величин и, в частности, о предельных свойствах таких преобразований связан с изучением вычислительных систем, построенных на вероятностных принципах [4, 5], а также с моделированием биологических систем [6]. Отметим также, что квазигрупповые преобразования случайных величин, особая роль которых вытекает из результатов настоящей работы, используются в криптографических системах [7].

В алгебрах с ассоциативной (и, в частности, групповой) операцией предельные теоремы могут быть доказаны путем моделирования последовательности сумм подходящей цепью Маркова. Если ${{X}_{1}}, \ldots ,{{X}_{n}}$ – независимые в совокупности одинаково распределенные случайные величины со значениями в некотором конечном множестве, то их “сумма” Sn, получающаяся применением к ним ассоциативной операции ∗ , может быть представлена в виде

(1)
${{S}_{n}} = (...\left( {(({{X}_{1}}*~{{X}_{2}})~*~{{X}_{3}})~*~{{X}_{4}}} \right)~*~ \ldots )~*\,{{X}_{n}},$
откуда, очевидно, ${{S}_{n}} = {{S}_{{n--1}}} * {{X}_{n}}$. Это позволяет рассматривать значения величины Sn как состояния конечной марковской цепи, матрица переходов которой может быть построена по распределению величин Xi. Если используемая операция групповая, то при некоторых естественных условиях на распределения величин Xi выводится, что предельное распределение величин Sn при $n \to \infty $ является равномерным. В действительности, равномерность предельного распределения имеет место для более широкого класса операций. В работе [8] показано, что если операция ∗ в выражении (1) – квазигрупповая (определение см. в [7]), то предельное распределение также является равномерным при выполнении естественных ограничений на распределения случайных величин Xi. Этот результат сохраняется, даже если в (1) вместо одной квазигрупповой операции ∗ рассматривать несколько различных квазигрупповых операций, т.е. положить
(2)
${{S}_{n}} = (...((({{X}_{1}}{{*}_{{{{i}_{1}}}}}~{{X}_{2}}){{*}_{{{{i}_{2}}}}}~{{X}_{3}}){{*}_{{{{i}_{3}}}}}~{{X}_{4}}){{*}_{{{{i}_{4}}}}}~ \ldots ){{*}_{{{{i}_{{n--1}}}}}}~{{X}_{n}},$
где ${{*}_{{{{i}_{1}}}}},{{*}_{{{{i}_{2}}}}}, \ldots ,{{*}_{{{{i}_{{n--1}}}}}}$ – какие-то квазигрупповые операции, определенные на множестве значений величин ${{X}_{1}}, \ldots ,{{X}_{n}}$. Дальнейшее усиление результатов [8] получено в [9], где показано, что на равномерность предельного распределения не влияет расстановка скобок в выражении (2). Поскольку квазигрупповые операции не обязательно ассоциативны, различные расстановки скобок в выражении (2) дают разные распределения для величин Sn, но все эти распределения приближаются к равномерному с ростом n. Таким образом, конечное множество с набором квазигрупповых операций является примером алгебры, в которой наличие предельного вероятностного закона обусловлено, в определенном смысле, алгебраическими свойствами этой системы.

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

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

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

1. ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Формализуем наличие предельного закона в конечной алгебре. Будем рассматривать конечные алгебры на множестве ${{E}_{k}} = \left\{ {0,1,...,k--1} \right\}$ с набором операций B. Без ограничения общности можно считать, что у всех операций из набора B все переменные существенные (напомним, что переменная xi операции $f\left( {{{x}_{1}},...,{{x}_{n}}} \right){\text{:}}\,\,E_{k}^{n} \to {{E}_{k}}$ существенная, если найдутся такие значения ${{a}_{1}},...,{{a}_{n}}$, $b \in {{E}_{k}}$, что

$f({{a}_{1}},...,{{a}_{{i--1}}},{{a}_{i}},{{a}_{{i + 1}}},...,{{a}_{n}}) \ne f({{a}_{1}},...,{{a}_{{i--1}}},b,{{a}_{{i + 1}}},...,{{a}_{n}})).$

Распределения случайных величин на множестве Ek являются k-мерными действительными векторами $({{p}_{0}},...,{{p}_{{k--1}}})$, координаты которых дополнительно  удовлетворяют условиям pi ≥ 0, $i = 0$, ..., k – 1 и $\mathop \sum \limits_{i = 0}^{k--1} ~{{p}_{i}}$ = 1. Множество таких векторов, являющееся (k – 1)-мерным симплексом в k-мерном пространстве ${{\mathbb{R}}^{k}}$, будем обозначать ${{S}^{{\left( k \right)}}}$. Равномерное распределение на Ek – вектор $\left( {\frac{1}{k}, \ldots ,\frac{1}{k}} \right)$.

Будем говорить, что множество распределений $H \subseteq {{S}^{{\left( k \right)}}}$ замкнуто относительно преобразований операциями из B, если при подстановке вместо всех переменных любой операции $f \in B$ независимых в совокупности случайных величин с распределениями из H получается случайная величина, распределение которой также лежит в H.

Рассмотрим всевозможные вычисления над системой операций B, в которых все аргументы – независимые в совокупности случайные величины с распределениями из некоторого конечного множества $G \subseteq {{S}^{{\left( k \right)}}}$. Тогда распределения результатов этих вычислений, очевидно, будут образовывать множество H, содержащее G и замкнутое относительно преобразований операциями из B. Наличию предельного закона в алгебре с набором операций B, а именно, приближению распределений результатов случайных вычислений к некоторому пределу с ростом числа аргументов, будет в точности соответствовать наличие у множества H единственной предельной точки q, т.е. точки, в любой проколотой окрестности которой содержатся элементы множества H. Эта предельная точка q и будет предельным законом для рассматриваемой конечной алгебры. Априори предельный закон зависит не только от операций конечной алгебры, но и от выбора множества G, однако во многих случаях этой зависимости в действительности нет.

Для формулировки основного результата нам также потребуются следующие понятия. Напомним, что аффинной оболочкой множества $H \subseteq {{S}^{{\left( k \right)}}} \subseteq {{\mathbb{R}}^{k}}$ называется множество:

$\begin{gathered} {\text{Aff}}\left( H \right) = \left\{ {\mathop \sum \limits_{i = 1}^s {{\alpha }_{i}}{{h}_{i}}{\text{|}}{{h}_{1}}, \ldots ,{{h}_{s}} \in H,} \right. \\ {{\alpha }_{1}},\,\, \ldots ,\left. {{{\alpha }_{s}} \in \mathbb{R},~\mathop {\,\sum }\limits_{i = 1}^s {{\alpha }_{i}} = 1} \right\}. \\ \end{gathered} $

Определение 1. Множество распределений $H \subseteq {{S}^{{\left( k \right)}}}$ называется существенно неплоским, если для любого конечного подмножества $H{\kern 1pt} ' \subseteq H$ выполнено ${\text{Aff}}(H{\backslash }H{\kern 1pt} ') \supseteq {{S}^{{\left( k \right)}}}$ и существенно плоским в противном случае.

Определение 2. Множество распределений $H \subseteq {{S}^{{\left( k \right)}}}$ называется X-множеством, если H представляется в виде $H = {{H}_{1}} \cup {{H}_{2}}$, где

${\text{Aff}}\left( {{{H}_{1}}} \right) \supseteq {\text{/ }}{{S}^{{\left( k \right)}}}{\text{и}}\quad {\text{Aff}}\left( {{{H}_{2}}} \right) \supseteq {\text{/ }}{{S}^{{\left( k \right)}}}.$

Определение 3. Для заданного подмножества $Q \subseteq {{E}_{k}}$ n-арная операция $f\left( {{{x}_{1}},...,{{x}_{n}}} \right)$ на множестве Ek называется Q-поглощающей квазигрупповой, если для любого $i = 1,...,n$ и любых ${{a}_{1}},...,{{a}_{{n--1}}} \in {{E}_{k}}$ унарная операция

$\varphi (x) = ~f\left( {{{a}_{1}},...,{{a}_{{i--1}}},x,{{a}_{i}},...,{{a}_{{n--1}}}} \right)$
является перестановкой на множестве Q и определена произвольным образом на ${{E}_{k}}{\backslash }Q$. Все нульарные операции по определению считаются Q-поглощающими квазигрупповыми операциями для любого множества Q.

Частным случаем Q-поглощающей квазигрупповой n-арной операции при Q = Ek являются $n$‑арные квазигрупповые операции в обычном понимании этого термина (см. [7]).

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

Теорема. Если множество распределений H замкнуто относительно преобразований операциями из B и при этом имеет единственную предельную точку $q \in {{S}^{{\left( k \right)}}}$, то выполнено одно из следующих утверждений:

1) либо H является существенно плоским;

2) либо H является X-множеством;

3) либо существует такое $Q \subseteq {{E}_{k}}$, что все операции из B являются Q-поглощающими квазигрупповыми операциями, и если не все операции из B унарные, то распределение $q = ({{q}_{0}}, \ldots ,{{q}_{{k--1}}})$ удовлетворяет условиям

${{q}_{i}} = \frac{1}{{\left| Q \right|}}\quad при\quad i \in Q,$

${{q}_{i}} = 0\quad при\quad i \in {{E}_{k}}{\backslash }Q.$

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

Эта теорема обобщает ранее полученный результат для случая k = 2, характеризующий алгебры на множестве {0, 1}, обладающие предельным вероятностным законом [10].

Список литературы

  1. Гренандер У. Вероятности на алгебраических структурах. М.: Наука, 1965. 271 с.

  2. Воробьев Н.Н. // Матем. сб. 1954. Т. 34 (76). № 1. С. 89–126.

  3. Saloff-Coste L. / In: Probability on discrete structures. H. Kesten (Ed.) Encyc. Math. Sci. V. 110. Berlin: Springer, 2004. P. 263–346.

  4. Qian W., Riedel M.D., Zhou H., Bruck J. // IEEE Trans. CAD Integrated Circuits and Systems. 2011. V. 30. № 9. P. 1279–1292.

  5. Lee D.T., Bruck J. // IEEE Trans. Comp. 2015. V. 64. № 12. P. 3376–3388.

  6. Wilhelm D., Bruck J., Qian L. // Proc. Nat. Acad. Sci. USA. 2018. V. 115 (5). P. 903–908.

  7. Markovski S. // Quasigroups and Related Systems. 2015. V. 23. № 1. P. 41–90.

  8. Markovski S., Gligoroski D., Bakeva V. // Proc. Maked. Acad. Sci. and Arts for Math. and Tech. Sci. 1999. V. 20. P. 13–28.

  9. Яшунский А.Д. // Дискрет. матем. 2013. Т. 25. № 2. С. 149–159.

  10. Яшунский А.Д. // Вестн. Моск. ун-та. Сер. 1. Матем., мех. 2019. № 4. С. 3–9.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал