Сеточные методы в эвентологии

Helgus ~ µастер ~ Kласс: Это незавершённая статья по ивентологии и её применениям

Сетки событий и сеточные методы в эвентологии

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

Сетка событий, или эвентологическая сетка (Э-сетка)

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

Для "одномерной" Э-задачи простейшим примером Э-сетки является равновероятное разбиение пространства элементарных событий на $N$ равновероятных событий, вероятность которых равна $1/N$ (равновероятная Э-сетка). Равновероятные события Э-сетки называются Э-террасками сетки (Э-узлами сетки), а их вероятности называют также Э-шагами сетки. Совокупность Э-террасок образует множество событий, где определены Э-сеточные распределения.

Несмотря на кажущуюся простоту, вопрос о выборе Э-сетки заслуживает внимания. С одной стороны, количество событий-террасок желательно брать большим, т.е. пользоваться мелкими, подробными Э-сетками. Точнее передавая при этом область изменения Э-аргумента, мы интуитивно рассчитываем лучше аппроксимировать искомое Э-распределение Э-сеточными распределениями. С другой стороны, практические соображения, и в первую очередь ограниченность быстродействия и объема памяти компьютеров, заставляют обращаться к Э-сеткам со сравнительно небольшим числом Э-террасок. Такие Э-сетки называются "грубыми" или "реальными".

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

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

Э-сеточные распределения и Э-сеточные пространства событий

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

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

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

Э-сеточная аппроксимация Э-распределений

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

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

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

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

Искусство выбора Э-сетки заключается в выборе такого Э-сеточного множества случайных событий, чтобы порожденные им Э-сеточные события-терраски (Э-ячейки) образовывали разбиение пространства элементарных событий, наиболее удобное для определения каждого условного распределений исходного множества случайных событий при условии, что наступило данное Э-сеточное событие-терраска.

Погрешность Э-сеточной аппроксимации

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

Постановка Э-сеточной задачи

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

Пусть исходное Э-распределение $p$ порождено исходным множеством случайных событий $\mathfrak{X} \subset \mathcal{F}$, Выбранных из алгебры вероятностного пространства $(\Omega, \mathcal{F}, \mathbf{P})$. Исходное множество случайных событий $\mathfrak{X}$ считается произвольным, так что ему разрешается разбивать пространство элементарных событий $\Omega$ на произвольное число исходных событий-террасок, вплоть до максимально возможного числа $2^{|\mathfrak{X}|}$.

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

Сеточное Э-распределение $q$ порождено Э-сеточным множеством случайных событий $\mathcal{S} \subset \mathcal{F}$, выбранных из той же алгебры $\mathcal{F}$. Э-сеточное множество случайных событий $\mathcal{S}$ состоит из непересекающихся событий, образующих разбиение $\Omega$.

Э-сетка

Определение (Э-сетка)

Э-сетка $\mathcal{S}$ - Это множество $\mathcal{S} \subset \mathcal{F}$ непересекающихся случайных событий, выбранных из алгебры $\mathcal{F}$ вероятностного пространства $(\Omega, \mathcal{F}, \mathbf{P})$ и образующих разбиение пространства элементарных событий $\Omega$.

Следующие понятия эквивалентны:

• Э-сетка $\mathcal{S}$,
• сеточное множество случайных событий $\mathcal{S}$,
• сеточное Э-распределение множества $\mathcal{S}$.

Таким образом, Э-сетка $\mathcal{S}$ (сеточное множество случайных событий $\mathcal{S}$, сеточное Э-распределение множества $\mathcal{S}$) определена т.т.т., когда

• выбрано множество $\mathcal{S} \subseteq \mathcal{F}$ непересекающихся

случайных событий, образующих разбиение $\Omega = \sum_{s \in \mathcal{S}} s,$

• задан набор вероятностей:

$q(s) = \mathbf{P}(s), \ \ \ s \in \mathcal{S}.$

При этом $\sum_{s \in \mathcal{S}} q(s) = 1$, так как сеточные события образуют разбиение пространства элементарных событий $\Omega$.

Выбор Э-сетки

Чтобы вообще имело смысл говорить об Э-сеточной аппроксимации исходного множества случайных событий $\mathfrak{X}$, Э-сетка $\mathcal{S}$ должна выбираться так, чтобы количество Э-сеточных событий в $\mathcal{S}$ было меньше числа непустых исходных событий-террасок, порождаемых исходным множеством случайных событий $\mathfrak{X}$, т.е.

$|\mathcal{S}| < 2^{|\mathfrak{X}|}.$

Во многих практических задачах мощность исходного множества случайных событий $\mathfrak{X}$ настолько велика, что исходное Э-распределение невычислимо, а работа с множеством исходных событий-террасок превращается в так называемую $NP$-трудную проблему. В подобных случаях требуется вынужденно выбирать такую Э-сетку, мощность которой

$|\mathcal{S}| \ll 2^{|\mathfrak{X}|},$

много меньшая мощности $2^\mathfrak{X}$, прежде всего позволяет строить вычислимую Э-сеточную аппроксимацию исходного невычислимого Э-распределения.

На погрешность Э-аппроксимации влияет ряд факторов, которые разделяются на две основные группы, которые мы назовем

• мощность Э-сетки,
• структура Э-сетки.

Мощность Э-сетки

Чем меньше мощность Э-сетки $\mathcal{S}$, тем

• удобнее с ней работать,
• вообще говоря, больше погрешность Э-сеточной аппроксимации.

Так что мощность выбираемой Э-сетки - это компромисс между удобством Э-сетки и обеспечиваемой этой Э-сеткой погрешностью аппроксимации.

Удобная структура Э-сетки

На первый взгляд, структура любой Э-сетки настолько проста, что, вообще, о какой-то ее структуре, которая характеризовалась бы еще чем-то, кроме мощности, говорить, вряд ли, уместно. По определению любая Э-сетка - это некоторое множество $\mathcal{S} \subset \mathcal{F}$ непересекающихся случайных событий, выбранных из алгебры $\mathcal{F}$ вероятностного пространства $(\Omega, \mathcal{F}, \mathbf{P})$ и образующих разбиение пространства элементарных событий $\Omega$. Поэтому может показаться, что число сеточных событий (мощность множества $\mathcal{S}$) и вероятности сеточных событий $s \in\mathcal S$ - это все, что определяет Э-сетку $\mathcal{S}$. Но так может показаться всего лишь на первый взгляд.

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

Определение (одномерно-"удобная" Э-сетка)

Говорят, что Э-сетка $\mathcal{S} \subset \mathcal{F}$ мощности $M$ имеет одномерно-"удобную" структуру т.т.т., когда множество событий $\mathcal{S} \subseteq \mathcal{F}$ определено таким образом, что разуму удобно анализировать события из $\mathcal{S}$.

Определение (многомерно-"удобная" Э-сетка)

Говорят, что Э-сетка $\mathcal{S} \subset \mathcal{F}$ мощности $M=M_1 \cdot \ldots \cdot M_n$ имеет $n$-мерно-"удобную" структуру т.т.т., когда

$\mathcal{S} = \left( \bigcap_{i=1}^n \right) \mathcal{S}_i = \mathcal{S}_1 (\cap) \ldots (\cap) \mathcal{S}_n$

- Э-сетка $\mathcal{S}$ представима в виде пересечения по Минковскому $n$ одномерно-"удобных" Э-сеток $\mathcal{S}_1, \ldots, \mathcal{S}_n \subset \mathcal{F}$ мощности $M_1, \ldots, M_n$ соответственно.

{\sf Определение (удобная мощность Э-сетки)}. Удобной мощностью многомерно-"удобной" Э-сетки

$\mathcal{S} = \left( \bigcap_{i=1}^n \right) \mathcal{S}_i = \mathcal{S}_1 (\cap) \ldots (\cap) \mathcal{S}_n$

называется величина

$\|\mathcal{S}\| = \sum_{i=1}^n |\mathcal{S}_i|,$

равная сумме мощностей одномерно-"удобных" Э-сеток, порождающих Э-сетку $\mathcal{S}$.

Другие определения и обозначения

Обозначим

$\mathfrak{X}_s = \{ x \in \mathfrak{X}: \ x \cap s \ne \emptyset \} \subseteq \mathfrak{X}$

- подмножество исходных событий, которые имеют непустое пересечение с сеточным событием $s \in\mathcal S$. Ясно, что любые два таких подмножества $\mathfrak{X}_s$ и $\mathfrak{X}_{s'}$ вполне могут иметь непустое пересечение. Тогда

$\bigcup_{s \in \mathcal{S}} \mathfrak{X}_s \subseteq \mathfrak{X}.$

Предположение о минимальности Э-сетки

Иногда будем дополнительно предполагать, что Э-сетка $\mathcal{S}$ выбрана таким образом, что каждое сеточное событие $s \in\mathcal S$ имеет непустое пересечение хотя бы с одним исходным событием $x \in \mathfrak{X}$, тогда

$\bigcup_{s \in \mathcal{S}} \mathfrak{X}_s = \mathfrak{X}.$

Такие Э-сетки будем называть минимальными относительно исходного множества событий $\mathfrak{X}$.

Э-сеточная задача

Интрига задачи Э-сеточной аппроксимации заключается в том, что исходное Э-распределение $p$ обычно неизвестно, а сеточное Э-распределение $q$ известно. Требуется построить Э-сеточную аппроксимацию $p^{\#q}$ исходного неизвестного Э-распределения $p$ относительно Э-сетки $q$.

Э-сеточная аппроксимация Э-распределений первого порядка

Предположим, что

• каждое исходное событие $x \in \mathfrak{X}$ имеет непустое

пересечение только с одним сеточным событием $s \in\mathcal S$, которое обозначается $s_x$;

• каждое сеточное событие $s \in\mathcal S$ имеет непустое

пересечение не более, чем с одним исходным событием (если такое есть, оно обозначается $x_s$).

Тогда

1. $|\mathfrak{X}| \le |\mathcal{S}|$,
2. исходные события содержатся в соответствующих сеточных событиях:

$x \subseteq s_x, \ \ \ x \in \mathfrak{X},$

$x_s \subseteq s, \ \ \ s \in \mathcal{S},$

3. исходные события попарно не пересекаются:

$x \cap y = \emptyset \ \ \ \Longleftrightarrow \ \ \ x \ne y.$

Следовательно, исходное множество случайных событий имеет неизвестное нам исходное Э-распределение первого порядка $p$. Для того чтобы оценить его на основе Э-сеточного распределения $q$ (т.е. чтобы построить его Э-сеточную аппроксимацию $p^{\#q}$ исходного Э-распределения $p$ относительно Э-сетки $q$), необходимо оценить условные вероятности

$\mathbf{P}\left(x | s_x\right) = \frac{\mathbf{P}(x \cap s_x)}{\mathbf{P}(s_x)}, x \in \mathfrak{X}.$

Обозначим

$p^{\#q}(x \ | \ s_x) \approx \mathbf{P}\left(x | s_x\right)$

- Э-сеточные оценки этих условных вероятностей, полученные каким-то методом. Заметим, что

$\mathbf{P}\left(x | s_x\right) = \frac{\mathbf{P}(x \cap s_x)}{\mathbf{P}(s_x)} = \frac{\mathbf{P}(x)}{\mathbf{P}(s_x)}, \ \ \ x \in \mathfrak{X},$

так как $\mathbf{P}(x \cap s_x) = \mathbf{P}(x)$, поскольку $x \subseteq s_x$. Отсюда

$\mathbf{P}(x) = \mathbf{P}\left(x | s_x\right) \mathbf{P}(s_x), \ \ \ x \in \mathfrak{X}.$

Обозначим

$p^{\#q}(x) = \mathbf{P}(x), x \in \mathfrak{X},$

- Э-сеточные оценки вероятностей исходных событий $x \in \mathfrak{X}$. Тогда

$p^{\#q}(x) = p^{\#q}(x \ | \ s_x) q(s_x), x \in \mathfrak{X},$

и если еще обозначить

$p^{\#q}(\emptyset) \approx \mathbf{P}\left(\bigcap_{x \in \mathfrak{X}} x^c \right)$

- Э-сеточную оценку вероятности ненаступления ни одного исходного события $x \in \mathfrak{X}$, то поскольку для Э-распределения первого порядка

$\mathbf{P}\left(\bigcap_{x \in \mathfrak{X}} x^c \right) = 1-\sum_{x \in \mathfrak{X}} \mathbf{P}(x),$

то

$p^{\#q}(\emptyset) = 1-\sum_{x \in \mathfrak{X}} p^{\#q}(x \ | \ s_x) q(s_x).$

В результате для исходного Э-распределения первого порядка $p$ построена его Э-сеточная аппроксимация $p^{\#q}$. Погрешность этой аппроксимации целиком определяется погрешностями Э-сеточных оценок условных вероятностей

$p^{\#q}(x \ | \ s_x) \approx \mathbf{P}\left(x | s_x\right), x \in \mathfrak{X}.$

Э-сеточная аппроксимация Э-распределений второго порядка

Предположим, что каждое сеточное событие $s \in\mathcal S$ пересекается только с какими-то двумя событиями $x,y \in \mathfrak{X}$. Тогда $|\mathcal{S}|=C_{|\mathfrak{X}|}^2$, исходные события пересекаются не более, чем попарно, и их парные пересечения содержатся в соответствующих сеточных событиях:

$x \cap y \subseteq s_{xy}, \ \ \ x, y \in \mathfrak{X},$

$(x \cap y)_s \subseteq s, \ \ \ s \in \mathcal{S}.$

где $(x \cap y)_s$ --- парное пересечение исходных событий, которое пересекается с сеточным событием $s \in\mathcal S$.

Следовательно, исходное множество случайных событий имеет Э-распределение второго порядка $p$. Для того чтобы оценить его на основе Э-сеточного распределения $q$, необходимо оценить условные вероятности

$\mathbf{P}\left(x | s_x\right) = \frac{\mathbf{P}(x \cap s_x)}{\mathbf{P}(s_x)} = \frac{\mathbf{P}(x)}{\mathbf{P}(s_x)}, x \in \mathfrak{X}.$

Отсюда

$\mathbf{P}(x) = \mathbf{P}\left(x | s_x\right) \mathbf{P}(s_x), x \in \mathfrak{X},$

а

$\mathbf{P}\left(\bigcap_{x \in \mathfrak{X}} x^c \right) = 1-\sum_{x \in \mathfrak{X}} \mathbf{P}(x),$

и исходное Э-распределение $p$ вполне определено.