BSc: TheoryOfRandomProcesses

Теория случайных процессов

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а): С.В. Самсонов

1. Краткая характеристика дисциплины

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

2. Перечень планируемых результатов обучения

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

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

Общая характеристика результата обучения по дисциплине

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

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

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

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Условные математические ожидания и вероятности	Конструкция условного математического ожидания и условной вероятности относительно сигма-алгебр. Базовые свойства. Напоминания базовых теоретико-множественных конструкций: алгебры, сигма-алгебры.
2.	Случайные процессы: базовые определения.	Определение случайного процесса. Цилиндрическая сигма-алгебра. Конечномерные распределения случайного процесса. Теорема Колмогорова о существовании случайного процесса с заданными конечномерными распределениями
3.	Мартингалы, субмартингалы, супермартингалы. Их свойства.	Мартингалы, субмартингалы, супермартингалы. Базовые свойства. Момент остановки. Теорема Дуба об оптимальной остановке.
4.	Броуновское движение (Винеровский процесс)	Винеровский процесс: определение и конструкция. Характеризация Винеровского процесса в классе гауссовских. Свойства траекторий Винеровского процесса.
5.	Стохастический интеграл Ито по Винеровскому процессу.	Стохастический интеграл от простых функций. Лемма Ито, изометрия Ито. Формула Ито для стохастического интеграла по Винеровскому процессу.
6.	Стохастические дифференциальные уравнения.	Теорема существования решения стохастического дифференциального уравнения. Уравнение Ланжевена, сходимость к инвариантому закону.
7.	Цепи Маркова в дискретном времени с дискретным пространством состояний.	Определения и основные свойства цепей Маркова с конечным или счетным пространством состояний. Марковское и сильное марковское свойство. Неприводимость, апериодичность, возвратность, теорема солидарности. Эргодическая теорема. Численные примеры.
8.	Цепи Маркова в дискретном времени с общим пространством состояний.	Определение и свойства марковского ядра. Инвариантное распределение. Обратимость во времени.
9.	Задача генерации случайных величин с заданным распределением	Метод генерации случайных величин при помощи обратной функции распределения. Алгоритмы MCMC: постановка задачи и примеры. Алгоритм Метрополиса-Хастингса. Численные примеры.
10.	Алгоритмы MCMC на основе динамики Ланжевена и динамики Гамильтона.	Алгоритмы ULA, MALA, их теоретические свойства. Метрика Канторовича-Вассерштейна, ее свойства, сходимость итераций алгоритмов ULA/MALA в метрике Канторовича-Вассерштейна и взвешенном расстоянии по вариации. Численные примеры. Алгоритм HMC (Гамильтонов Монте-Карло). Его свойства.

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Условные математические ожидания и вероятности	Примеры на вычисление условных плотностей, условного математического ожидания, формулы полной вероятности. Обсуждение конструкции УМО.
2.	Случайные процессы: базовые определения.	Алгебры и сигма-алгебры, их свойства, проверка свойств заданной системы множеств. Цилиндрическая сигма-алгебра: примеры и свойства. Конечномерные распределения случайного процесса.
3.	Мартингалы, субмартингалы, супермартингалы. Их свойства.	Примеры мартингалов, проверка мартингального свойства случайных процессов. Задача о разорении, тождества Вальда.
4.	Броуновское движение (Винеровский процесс)	Система функций Хаара, ее полнота. Свойства Винеровского процесса: закон повторного логарифма. Неограниченность полной вариации.
5.	Стохастический интеграл Ито по Винеровскому процессу.	Примеры вычисления стохастического интеграла от простых функций. Невозможность потраекторного построения стохастического интеграла (в смысле Римана-Стилтьеса). Примеры применения формулы Ито.
6.	Стохастические дифференциальные уравнения.	Примеры стохастических дифференциальных уравнений. Геометрическое броуновское движение. Процесс Орнштейна-Уленбека. Свойства динамики Ланжевена.
7.	Цепи Маркова в дискретном времени с дискретным пространством состояний.	Коммуницирующие классы, проверка свойств неприводимости, апериодичности, вычисление инвариантных распределений.
8.	Цепи Маркова в дискретном времени с общим пространством состояний.	Действие марковского ядра на меры и функции, примеры.
9.	Задача генерации случайных величин с заданным распределением	Метод генерации случайных величин при помощи обратной функции распределения. Генерация с отказами (rejection sampling). Примеры алгоритмов MCMC: алгоритм Метрополиса-Гастингса, алгоритм Гиббса, динамика Гамильтона.
10.	Алгоритмы MCMC на основе динамики Ланжевена и динамики Гамильтона.	Практические задачи, связанные с генерацией наблюдений из мультимодальных распределений в высокой размерности.

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

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Условные математические ожидания и вероятности. Случайные процессы: базовые определения.	Домашние работы	В домашние работы включаются задачи, нерешенные во время семинарских занятий.
2.	Мартингалы, субмартингалы, супермартингалы. Их свойства. Броуновское движение (Винеровский процесс)	Домашние работы	В домашние работы включаются задачи, нерешенные во время семинарских занятий.
3.	Стохастический интеграл Ито по Винеровскому процессу. Стохастические дифференциальные уравнения.	Домашние работы	В домашние работы включаются задачи, нерешенные во время семинарских занятий.
4.	Цепи Маркова в дискретном времени с дискретным и общим пространством состояний.	Домашние работы	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Также домашние работы содержат задачи численного моделирования с использованием python.
5.	Задача генерации случайных величин с заданным распределением. Алгоритмы MCMC на основе динамики Ланжевена и динамики Гамильтона.	Домашние работы	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Также домашние работы содержат задачи численного моделирования с использованием python и пакета pyro.

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Условные математические ожидания и вероятности	1. Условное математическое ожидание относительно сигма-алгебры, определение и свойства. 2. Условные вероятности и условные плотности.
2.	Случайные процессы: базовые определения.	3. Случайный процесс. 4. Траектории случайного процесса. Цилиндрическая сигма-алгебра. Теорема Колмогорова
3.	Мартингалы, субмартингалы, супермартингалы.	5. Мартингал, субмартингал, супермартингал. Основные свойства; 6. Разложение Дуба-Мейера; 7. Теорема Дуба об оптимальной остановке; 8. Максимальное неравенство Дуба; 9. Тождества Вальда;
4.	Броуновское движение (Винеровский процесс)	10. Винеровский процесс: определение, теорема существования; 11. УЗБЧ для Винеровского процесса. 12. Свойства траекторий Винеровского процесса;
5.	Стохастический интеграл Ито по Винеровскому процессу.	13. Стохастический интеграл для простых функций; 14. Лемма Ито и изометрия Ито; 15. Формула Ито;
6.	Стохастические дифференциальные уравнения (СДУ).	16. Теорема существования и единственности (сильного) решения СДУ; 17. Примеры: процесс Орнштейна-Уленбека и геометрического Броуновского движения;
7.	Цепи Маркова в дискретном времени с дискретным и общим пространством состояний.	19. Марковская цепь с дискретным пространством состояний: определение. Марковское и сильное марковское свойства. 19. Неприводимость, апериодичность, возвратность, теорема солидарности; 20. Эргодическая теорема; 21. Марковское ядро - определение и свойство. Определение марковской цепи с общим пространством состояний.
8.	Задача генерации случайных величин с заданным распределением.	22. Метод генерации случайных величин при помощи обратной функции распределения. Генерация с отказами (rejection sampling). 23. Примеры алгоритмов MCMC: алгоритм Метрополиса-Гастингса, алгоритм Гиббса.
9.	Алгоритмы MCMC на основе динамики Ланжевена и динамики Гамильтона.	24. Метрика Канторовича-Вассерштейна, ее свойства; 25.Алгоритмы ULA/MALA. Их свойства. 26. Алгоритм HMC. Его свойства.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Условное математическое ожидание относительно сигма-алгебры, определение и свойства.
2. Условные вероятности и условные плотности.
3. Случайный процесс. Траектории случайного процесса. Цилиндрическая сигма-алгебра.
4. Теорема Колмогорова;
5. Мартингал, субмартингал, супермартингал. Основные свойства;
6. Разложение Дуба-Мейера;
7. Теорема Дуба об оптимальной остановке;
8. Максимальное неравенство Дуба;
9. Тождества Вальда;
10. Винеровский процесс: определение, теорема существования;
11. УЗБЧ для Винеровского процесса.;
12. Свойства траекторий Винеровского процесса;
13. Стохастический интеграл для простых функций;
14. Лемма Ито и изометрия Ито;
15. Формула Ито;
16. Теорема существования и единственности (сильного) решения СДУ;
17. Примеры: процесс Орнштейна-Уленбека и геометрического Броуновского движения;
18. Марковская цепь с дискретным пространством состояний: определение. Марковское и сильное марковское свойства.
19. Неприводимость, апериодичность, возвратность, теорема солидарности;
20. Эргодическая теорема;
21. Марковское ядро - определение и свойство. Определение марковской цепи с общим пространством состояний;
22. Метод генерации случайных величин при помощи обратной функции распределения. Генерация с отказами (rejection sampling);
23. Примеры алгоритмов MCMC: алгоритм Метрополиса-Гастингса, алгоритм Гиббса;
24. Метрика Канторовича-Вассерштейна, ее свойства;
25. Алгоритмы ULA/MALA. Их свойства.
26. Алгоритм HMC. Его свойства.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:
1. Булинский, А.В.0 Теория случайных процессов [Электронный ресурс] : учебное пособие / А.В.0 Булинский, А.Н. Ширяев. — Электрон. дан. — Москва : Физматлит, 2005. — 400 с.;
2. Oksendal, B. (2013). Stochastic differential equations: an introduction with applications. Springer Science & Business Media;
3. Baldi, Paolo. Stochastic calculus. Springer International Publishing, 2017;
4. Douc, Randal, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains. Vol. 1. Springer Series in Operations Research and Financial Engineering: Springer International Publishing, 2018.
Список дополнительной литературы:
1. Круглов, В. М. Случайные процессы в 2 ч. Часть 1. Основы общей теории : учебник для вузов / В. М. Круглов. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2024. — 276 с. — (Высшее образование). — ISBN 978-5-534-01748-9;
2. Круглов, В. М. Случайные процессы в 2 ч. Часть 2. Основы стохастического анализа : учебник для вузов / В. М. Круглов. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2024. — 280 с. — (Высшее образование). — ISBN 978-5-534-02086-1.

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Реферат	Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты. Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
Эссе	Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Видеопрезентация	Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
Доклад	Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия	Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Контрольная работа	При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
Тестирование (устное/письменное)	При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
Индивидуальная работа	При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнении домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

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

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

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