18. Случайные процессы и временные ряды. Понятие стационарности. Ковариационная (корреляционная функция). Теорема Карунена-Лоэва. Спектральная плотность случайных процессов.

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

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

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

Понятие стационарности. Случайный процесс считается стационарным, если его статистические свойства не меняются со временем. Существуют два типа стационарности:

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

• Широкая стационарность. Процесс является стационарным в широком смысле, если его первые моменты (среднее и дисперсия) постоянны, а автокорреляционная функция зависит только от разности моментов времени.

Ковариационная и корреляционная функция. Ковариационная функция – это мера взаимосвязи двух случайных переменных в разные моменты времени случайного процесса. Она количественно определяет, как значения в один момент времени взаимосвязаны со значениями в другой момент времени. Ковариационная функция определяется как:

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

Корреляционная функция является нормализованной версией ковариационной функции, которая принимает значения от -1 до 1. Она определяется как:

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

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

Пусть – стационарный случайный процесс в широком смысле, определенный на промежутке с нулевым средним и автокорреляционная функцией , где и – момент времени и величина сдвига по времени.

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

где – численные коэффициенты, в свою очередь, определяемые как:

– интегральный оператор Гильберта-Шмидта, его собственные функции и числа находятся решением следующего однородного интегрального уравнения:

В данном уравнении, автокорреляционная функция получила второе название – Ядро Мерсера (см. теорема Джеймса Мерсера).

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

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

Пусть – широко стационарный случайный процесс с автокорреляционной функцией , где и - момент времени и величина сдвига по времени.

Тогда спектральная плотность случайного процесса определяется как преобразование Фурье от автокорреляционной функции:

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

19. Графы. Основные понятия: ориентированность графа, степени вершины, связность, цепи и циклы (Эйлеров, Гамильтонов). Подграфы и клики. Способы представления графа: матрицы и списки инцидентности и смежности. Важные частные случаи: деревья, направленные ациклические графы, двудольные графы.

Графы. Графы – это фундаментальное понятие в математике и информатике, которое используется для представления отношений между объектами. Он состоит из набора вершин (также известных как узлы) и набора ребер (также известных как дуги), которые соединяют пары вершин.

Основные понятия: ориентированность графа, степени вершины, связность, цепи и циклы (Эйлеров, Гамильтонов). В графе ребра могут быть направленными или ненаправленными. В ненаправленном графе ребра не имеют определенного направления и могут быть пройдены в любом направлении. С другой стороны, в направленном графе каждое ребро имеет определенное направление, указывающее, что его можно пройти только в одном направлении.

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

Связность относится к тому, насколько хорошо связан граф. Граф считается связным, если существует путь между каждой парой вершин. Если между как минимум двумя вершинами нет пути, граф считается несвязным. Кроме того, концепция сильной связности применяется к направленным графам, где существует направленный путь между каждой парой вершин. Ориентированный граф называется слабо-связным, если является связным неориентированным графом, полученным из него заменой ориентированных рёбер неориентированными.

Полный граф – простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный ориентированный граф – ориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями.

Путь в графе – это последовательность вершин, где каждая последующая пара соединена ребром. Длина пути – это количество ребер, которые он содержит.

Цикл – это путь, который начинается и заканчивается в одной вершине, без повторяющихся ребер или вершин (за исключением начальной и конечной вершины).

Эйлеровы и Гамильтоновы пути и циклы – это особые типы путей и циклов:

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

Каждая вершина этого графа имеет чётную степень, поэтому этот граф – эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл.

• Гамильтонов путь – это путь, который посещает каждую вершину в графе ровно один раз. Гамильтонов цикл – это Гамильтонов путь, который начинается и заканчивается в одной вершине.

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

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

Список смежности – это структура данных, которая хранит каждую вершину вместе со списком ее смежных вершин.

Важные частные случаи: деревья, направленные ациклические графы, двудольные графы. Наконец, мы кратко упоминаем некоторые важные особые случаи графов:

• Дерево – это связный граф без циклов. Отсюда следует, что он имеет ребер, где – количество вершин.

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

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