Главная

Добро пожаловать на веб-страницу курса Цепи Маркова в НИУ ВШЭ, 2025/26.

Программа

Лекции

(Обновляются после каждой лекции)

  • Лекция 1: История, обоснования, примеры. Первые определения цепей Маркова (вероятности на пространстве траекторий, марковское свойство, переходные вероятности, начальное распределение). До раздела Цепи Маркова: Определения, но замечания по теории меры можно проигнорировать (Колмогоров, фильтрация). Вам настоятельно рекомендуется решить упражнения на лекциях.
  • Лекция 2: Обзор обозначений. Свойство Маркова и строгое свойство Маркова. Примеры (содержание до конца первой главы, за исключением абстрактной формулировки, включая упражнения). - Лекция 3: Марковский оператор. Вероятности попадания и линейные уравнения. Мы не доказывали утверждение о следе в главе 2, но оно в любом случае поможет вам при выполнении задания.
  • Лекция 4/5: Эквивалентные определения взаимодействующих классов и рекуррентности/транзиентности.
  • Лекция 6: Кратковременность и повторяемость простых блужданий в \(\mathbb{Z}^d\). К настоящему моменту рассмотрены первые четыре главы конспекта лекций.
  • Лекция 7/8: Инвариантные меры и рекуррентность. Аргумент связи в пользу сходимости положительно-рекуррентных апериодических неприводимых цепей. В этом месте рассматриваются первые пять глав конспекта лекций.
  • Лекция 9: Теорема Перрона-Фробениуса и экспоненциальная сходимость.
  • Лекция 10: Формализм in-arborescence: цепь Маркова последнего прохода на древовидных структурах и инвариантная мера.
  • Лекция 11/12: Дерево Гальтона-Уотсона.
  • Лекция 12/13/14: Количественные предельные теоремы: флуктуации эмпирических мер на вершинах и ребрах.
  • Лекция 15: (Запланировано) MCMC и Метрополис-Хастингс.

Первоначальный план

(Гибкий, в зависимости от уровня подготовки и интересов студентов)

  • Цепи Маркова с конечным и счётным пространством состояний.
  • Стационарные состояния и их существование.
  • Теорема Перрона–Фробениуса.
  • Эргодические теоремы для цепей Маркова (решётчатых и нерешётчатых).
  • Применения эргодической теоремы. Закон больших чисел для цепей Маркова.
  • Известные примеры: дерево Гальтона-Уотсона, PageRank Google.
  • Производные цепи Маркова (перестановки, остовные деревья).

Библиография

Связанные предварительные

  • Краткое, самодостаточное современное введение в Теорию меры. Оно содержит гораздо больше, чем необходимо для этого курса, и это хорошее чтение, если вам нужно освежить свои знания по Теории меры.
  • Краткое, несамостоятельное справочное пособие по Теории вероятностей. Оно содержит гораздо больше, чем необходимо для этого курса, и вы можете обратиться к нему, если у вас возникнут сомнения.
  • Л.Коралов, Я.Г.Синай (2007). Теория вероятностей и случайных процессов [EN|RU]. Общее введение в теорию вероятностей, доступное на русском и английском языках.

Книги

  • J.R.Norris (1997). Markov Chains. Классический и широко используемый учебник, известный своими четкими объяснениями и прочной теоретической основой. Остается очень актуальным и сегодня.

  • T.Konstantopoulos (2009). Markov Chains and Random Walks. Хорошие лекционные заметки.

  • P.Brémaud (2017). Discrete Probability Models and Methods: Probability on Graphs and Trees, Markov Chains and Random Fields, Entropy and Coding. Современный взгляд на некоторые аспекты цепей Маркова, с мягким введением.

  • R.Douc, É.Moulines, P.Soulier (2018). Markov Chains: Theory and Applications. Прочная продвинутая теоретическая основа.

  • D.A.Levin, Y.Peres (2017). Markov Chains and Mixing Times. Весьма уважаемый ресурс, особенно за его глубокое освещение времен перемешивания, важнейшего понятия для понимания сходимости цепей Маркова.

  • N.Privault (2018). Markov Chains: Examples and Applications. Хорошая подборка теории, примеров и тематических исследований для иллюстрации практической полезности цепей Маркова в различных областях.

  • Б.В.Гнеденко (1988). Курс теории вероятностей. Классическая, хотя и устаревшая, книга на русском языке.

  • М.Я.Кельберт, Ю.М.Сухов (2001). Вероятность и статистика в примерах и задачах: Марковские цепи как отправная точка теории случайных процессов и их приложения. Старая книга на русском языке, с упражнениями.

Конспекты лекций

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

Упражнения

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

Домашние задания

Контрольная работа

Оценка

Оценка определяется следующими значениями:

  • K: Один основной контрольный тест, на 30.10, оценка \([0,10]\). Вы можете пересдать этот тест 20 декабря (дата будет уточнена), если вы не смогли принять участие или что-то пошло не так.
  • L1: Первое задание сдать 15.10, оценка \([0,10]\).
  • L2: Второе задание сдать 18.11, оценка \([0,10]\).
  • B: Бонус за активное участие, оценка \(\{0,1,2\}\).
  • M: Минимальный тест, оценка \(\{0,1\}\). (не обязателен для всех студентов, см. ниже).
  • U: Устный экзамен, оценка \([-2,11]\). \(U> 10\) и \(U<0\) следует считать исключением (не обязательным для всех студентов, см. ниже).
  • I: Итоговая оценка, которую вы получите за курс, в \(\{4,5,6,7,8,9,10\}\).

Семестровая оценка: \(S=K/2+(L1+L2)/4+B\).

  1. Если \(S< 3.5\) (после пересдачи K), вам необходимо пересдать экзамен в январе.
  2. Если \(S \in [3.5,5.0)\), вам необходимо сдать минимальный тест. Если \(M=1\), то \(I=\lfloor S+0.5 \rfloor\).
  3. Если \(S\ge 10.5\) и \(B=2\), то \(I=10\).
  4. Во всех остальных случаях вы можете сдать устный экзамен (не сдача устного экзамена означает \(U=0\)), и итоговая оценка составит \(\min(10, \lfloor 0.65*S+0.35*U +0.5 \rfloor)\).

Темы устного экзамена

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

Основные темы

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

Избранные темы

Эти предметы считаются более сложными. Для получения высокой оценки на экзамене необходимо их знать. Студенты второго курса бакалавриата могут рассматривать главы 7.1 и 7.3 как факультативные.

Навигация по сайту

Если у вас возникли проблемы с HTML-версией сайта, вы можете скачать PDF-версию (ссылка на боковой панели) каждой страницы, содержащей раздел «Математика». В правом верхнем углу находится функция поиска по кодам математических символов (в латексе), а также кнопка переключения тем. Скорость воспроизведения и загрузки видео оптимизирована для относительно новых браузеров (>2022). Некоторые страницы содержат интерактивные элементы shinylive, загрузка которых может занять некоторое время (если вы очистили историю браузера с момента последнего просмотра страницы shinylive).