Практический тест по цепям Маркова и стохастическим процессам с пошаговым интерактивным уроком
Используйте вопросы ниже на странице, чтобы отработать цепи Маркова и стохастические процессы: марковское свойство, стохастические по строкам матрицы переходов, обновления распределений \(pP\), степени \(P^n\), закон Чепмена-Колмогорова, стационарные распределения \(\pi P=\pi\), поглощающие состояния и замкнутые классы, неприводимость, возвратность и транзиентность, период и апериодичность, сходимость конечных цепей, мартингалы, субмартингалы, супермартингалы, фильтрации и моменты остановки. Если нужно повторить материал, откройте урок: там есть понятные примеры и короткие проверки.
Ответьте на набор вопросов и разберите ошибки в конце.
Как работает эта практика по цепям Маркова и стохастическим процессам
1. Выполните набор практики: ответьте на вопросы о переходных вероятностях, стационарных распределениях, возвратности, периодичности, мартингалах и моментах остановки.
2. Откройте урок: повторите стохастические по строкам матрицы, структуру классов, долгосрочное поведение, поглощающие цепи и инструменты условного ожидания.
3. Попробуйте снова: вернитесь к набору вопросов и решите, нужно ли вычислить элемент матрицы, решить \(\pi P=\pi\), классифицировать состояние или проверить условное ожидание.
Что вы изучите в уроке по цепям Маркова и стохастическим процессам
Законы переходов и степени матриц
Читайте \(P_{ij}\) как вероятность перейти из состояния \(i\) в состояние \(j\) за один шаг.
Обновляйте распределения-строки по \(p_{n+1}=p_nP\) и \(p_n=p_0P^n\).
Используйте закон Чепмена-Колмогорова: \(P^{m+n}=P^mP^n\).
Стационарное и долгосрочное поведение
Решайте \(\pi P=\pi\) вместе с \(\sum_i\pi_i=1\).
Распознавайте \(\pi\) как левый собственный вектор с собственным значением \(1\).
Знайте, когда конечные неприводимые апериодические цепи сходятся к строкам стационарного распределения.
Структура классов конечных цепей
Классифицируйте сообщающиеся классы, замкнутые классы и поглощающие состояния.
Отличайте возвратные состояния от транзиентных состояний в конечных цепях.
Вычисляйте периоды как НОД возможных времен возврата.
Процессы, мартингалы и моменты остановки
Используйте фильтрации \(\mathcal F_n\), чтобы представлять информацию, известную к моменту \(n\).
Проверяйте мартингалы с помощью \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Помните, что моменты остановки должны определяться по прошлой и текущей информации, а не по невидимым будущим данным.
Цель: Построить надежный набор инструментов для конечных цепей Маркова и близких идей стохастических процессов. Вы будете читать матрицы переходов, вычислять многошаговые вероятности, находить стационарные распределения, классифицировать состояния, распознавать периодическое поведение и связывать условное ожидание с мартингалами и моментами остановки.
Критерии успеха
Формулировать марковское свойство: при условии текущего состояния будущему не требуется более раннее прошлое.
Проверять, что конечная матрица переходов строково-стохастическая: элементы неотрицательны, а сумма каждой строки равна \(1\).
Обновлять распределения-строки по \(p_{n+1}=p_nP\) и читать \(P^n_{ij}\) как \(n\)-шаговую вероятность.
Использовать закон Чепмена-Колмогорова: \(P^{m+n}=P^mP^n\).
Решать \(\pi P=\pi\) с \(\sum_i\pi_i=1\) для стационарных распределений.
Классифицировать поглощающие состояния, сообщающиеся классы, неприводимость, возвратность и транзиентность.
Находить периоды по временам возврата и знать, почему петля в состоянии принуждает период \(1\).
Формулировать картину сходимости для конечной неприводимой апериодической цепи.
Распознавать мартингалы, субмартингалы, супермартингалы и моменты остановки с помощью условного ожидания и информации, доступной к текущему моменту.
Ключевая лексика
Стохастический процесс: последовательность случайных величин, например \(X_0,X_1,X_2,\dots\).
Цепь Маркова: стохастический процесс, в котором закон следующего состояния зависит от текущего состояния, а не от всего прошлого.
Матрица переходов: \(P_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), где каждая строка является распределением вероятностей.
Стационарное распределение: распределение \(\pi\), для которого \(\pi P=\pi\).
Сообщающийся класс: состояния, достижимые друг из друга.
Период: НОД возможных времен возврата в состояние.
Мартингал: процесс с \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Момент остановки: случайный момент времени, определяемый по информации, доступной до этого момента включительно.
Быстрая предварительная проверка
Предварительная проверка: В цепи Маркова после условия на текущее состояние от чего зависит будущее на один шаг?
Подсказка: прошлое может влиять на будущее через текущее состояние, но когда текущее состояние известно, более ранние состояния не добавляют информации для закона следующего шага.
Строки кодируют одношаговые вероятности
Цель обучения: Читать конечную матрицу переходов и вычислять одношаговые или многошаговые распределения, не теряя вероятностную конвенцию.
Ключевая идея
При конвенции строковых векторов текущее распределение \(p_n\) обновляется по правилу \(p_{n+1}=p_nP\). Элемент \(P_{ij}\) — это вероятность перейти из состояния \(i\) в состояние \(j\) за один шаг.
Правила для матриц
Каждый элемент удовлетворяет \(P_{ij}\ge0\).
Сумма каждой строки равна \(1\), потому что следующее состояние должно быть каким-то состоянием.
У детерминированного перехода один элемент строки равен \(1\), а остальные \(0\).
Поглощающее состояние \(i\) имеет \(P_{ii}=1\).
Если \(p_0\) — распределение, то \(p_0P^n\) — распределение после \(n\) шагов.
Чепмен-Колмогоров
Многошаговые переходы композиционно складываются: \[P^{m+n}=P^mP^n.\] Поэлементно это суммирование по всем возможным промежуточным состояниям.
Разобранный пример
Пример: Пусть \(P=\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}\) и \(p_0=(1,0)\). Чему равно \(p_1\)?
Умножайте справа: \[p_1=p_0P=(1,0)\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}=(1/2,1/2).\] Если начать в состоянии \(1\), следующее распределение — это просто строка \(1\) матрицы \(P\).
Попробуйте
Попробуйте: Как следует классифицировать строку \((1/4,3/4)\) в матрице переходов?
Подсказка: проверьте неотрицательность и сумму строки.
Стационарное распределение не меняется за один шаг
Цель обучения: Распознавать и решать стационарные уравнения для конечных цепей.
Ключевая идея
Распределение-строка \(\pi\) стационарно, когда \(\pi P=\pi\). На языке линейной алгебры \(\pi\) — левый собственный вектор \(P\) с собственным значением \(1\), нормированный так, что его элементы неотрицательны и в сумме дают \(1\).
Контрольный список решения
Запишите \(\pi=(\pi_1,\dots,\pi_k)\).
Решите \(\pi P=\pi\).
Добавьте нормировку \(\pi_1+\cdots+\pi_k=1\).
Проверьте, что элементы неотрицательны.
В приводимых цепях стационарные распределения могут быть неединственными.
Прием для двух состояний
Для \(P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}\) с положительным \(a+b\) стационарное распределение пропорционально \((b,a)\), поэтому \(\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)\).
Разобранный пример
Пример: Найдите стационарное распределение для \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\).
Обе строки равномерны. Умножение любого распределения на \(P\) дает \((1/2,1/2)\), поэтому \(\pi=(1/2,1/2)\) стационарно.
Попробуйте
Попробуйте: Что означает \(\pi P=\pi\)?
Подсказка: один переход оставляет распределение точно таким же.
Достижимость управляет структурой цепи
Цель обучения: Использовать достижимость в графе для классификации состояний и сообщающихся классов.
Ключевая идея
Говорят, что \(i\) достигает \(j\), если \((P^n)_{ij}>0\) для некоторого \(n\ge0\). Состояния сообщаются, когда каждое достижимо из другого. Неприводимая конечная цепь имеет один сообщающийся класс.
Язык классификации
Замкнутый класс: после входа в него цепь не может выйти из класса.
Поглощающее состояние: одноэлементный замкнутый класс, что эквивалентно \(P_{ii}=1\).
Возвратное состояние: возврат в него происходит с вероятностью \(1\).
Транзиентное состояние: посещается лишь конечное число раз с вероятностью \(1\).
Неприводимая цепь: каждое состояние сообщается с каждым другим.
Факты о конечных цепях
В конечной неприводимой цепи каждое состояние возвратно. В конечной приводимой цепи состояния вне замкнутых классов часто транзиентны, потому что вероятность со временем переходит в замкнутый класс и остается там.
Разобранный пример
Пример: Для \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\) какое состояние является поглощающим?
Состояние \(1\) поглощающее, потому что строка \(1\) равна \((1,0)\), значит \(P_{11}=1\). Состояние \(2\) может перейти в состояние \(1\), но состояние \(1\) не может вернуться в состояние \(2\), поэтому цепь не является неприводимой.
Попробуйте
Попробуйте: Что значит неприводимость для конечной цепи Маркова?
Подсказка: думайте об ориентированном графе со стрелкой \(i\to j\), когда переход имеет положительную вероятность.
Арифметика времен возврата определяет апериодичность
Цель обучения: Вычислять простые периоды и знать, почему апериодичность важна для сходимости.
Ключевая идея
Период состояния \(i\) — это НОД всех положительных \(n\), для которых \((P^n)_{ii}>0\). Состояние с периодом \(1\) апериодично. В неприводимой цепи все состояния имеют один и тот же период.
Картина сходимости
Если конечная цепь неприводима и апериодична, у нее есть единственное стационарное распределение \(\pi\).
Для такой цепи \(P^n\) сходится к матрице, все строки которой равны \(\pi\).
Если цепь периодична, стационарное распределение может существовать, но \(P^n\) все равно осциллирует.
Если цепь приводима, предельное поведение зависит от достижимых замкнутых классов.
Петли
Петля \(P_{ii}>0\) дает возможный возврат за один шаг, поэтому НОД времен возврата включает \(1\). Это принуждает период \(1\).
Разобранный пример
Пример: Для \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\) что происходит после двух шагов?
Цепь меняет состояние на каждом шаге. Поэтому \(P^2=I\), возвраты происходят в четные моменты, и каждое состояние имеет период \(2\).
Попробуйте
Попробуйте: Каков период цепи с \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)?
Подсказка: начните из состояния и посчитайте моменты, в которые возможен возврат.
Замкнутые состояния превращают вероятностные вопросы в уравнения
Цель обучения: Составлять простые уравнения для вероятностей попадания и времен попадания при поглощающем поведении.
Ключевая идея
Поглощающее состояние удерживает цепь после входа в него. В более общем виде замкнутый сообщающийся класс нельзя покинуть. Вопросы попадания спрашивают, войдет ли процесс в выбранное множество и когда это произойдет.
Уравнения попадания
Для вероятности попадания \(h_i\) используйте граничные значения \(h_i=1\) на цели и \(h_i=0\) на невозможных замкнутых классах.
Для остальных состояний используйте \(h_i=\sum_j P_{ij}h_j\).
Для ожидаемого времени попадания \(t_i\) используйте \(t_i=0\) на цели и \(t_i=1+\sum_jP_{ij}t_j\) вне ее.
Делайте уравнения небольшими, используя симметрию или очевидные поглощающие состояния.
Замкнутые классы
Поглощающий класс — это сообщающийся класс, который нельзя покинуть. Одно поглощающее состояние — наименьший пример этой идеи.
Разобранный пример
Пример: Для \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\), если начать из состояния \(2\), чему равно ожидаемое время до попадания в состояние \(1\)?
Пусть \(t_1=0\). Из состояния \(2\): \[t_2=1+\frac12t_1+\frac12t_2=1+\frac12t_2.\] Следовательно, \(t_2=2\).
Попробуйте
Попробуйте: Если цепь Маркова начинается в поглощающем состоянии, где она будет после одного шага?
Подсказка: поглощающее состояние имеет \(P_{ii}=1\).
Условное ожидание отслеживает честный дрейф
Цель обучения: Связать интуицию цепей Маркова с более широким языком стохастических процессов, фильтраций, мартингалов и моментов остановки.
Ключевая идея
Стохастический процесс — это любое индексированное семейство случайных величин. Фильтрация \((\mathcal F_n)\) фиксирует информацию, доступную к моменту \(n\). Утверждения о мартингалах являются условными ожиданиями относительно этой информации.
Словарь условного ожидания
Мартингал: \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Субмартингал: \(E[X_{n+1}\mid\mathcal F_n]\ge X_n\), поэтому условный дрейф неотрицателен.
Супермартингал: \(E[X_{n+1}\mid\mathcal F_n]\le X_n\), поэтому условный дрейф неположителен.
Это утверждения об условных средних, а не о том, что каждая траектория возрастает или убывает.
Моменты остановки
Момент остановки \(\tau\) должен быть решаем по информации, доступной до момента \(n\), когда проверяется, выполнено ли \(\tau\le n\). Например, первый момент, когда процесс достигает \(5\), является моментом остановки; последний момент до завтра, когда он достигает \(5\), зависит от будущей информации.
Разобранный пример
Пример: Пусть \(S_n\) — честное случайное блуждание с независимыми шагами \(+1\) или \(-1\), каждый с вероятностью \(1/2\). Почему \(S_n\) является мартингалом?
При известной текущей информации следующий шаг имеет условное среднее \(0\). Поэтому \(E[S_{n+1}\mid\mathcal F_n]=S_n+0=S_n\).
Подсказка: у мартингала нулевой условный дрейф от текущего значения.
Большинство ошибок смешивает конвенции или игнорирует предположения
Цель обучения: Завершить, отделив факты о матрицах переходов, факты о долгосрочном поведении и факты об условном ожидании.
Типичные ошибки
Строковая и столбцовая конвенции: в этом уроке используются распределения-строки \(pP\). Для распределений-столбцов формулы транспонируются.
Недопустимые строки матрицы: вероятности должны быть неотрицательными, а сумма каждой строки должна быть \(1\).
Стационарность не является поглощением: \(\pi P=\pi\) описывает распределение, а не обязательно фиксированное состояние.
Приводимые цепи могут иметь много стационарных распределений: каждый замкнутый класс может нести стационарную массу.
Период может блокировать сходимость: двухсостоянийное переключение имеет стационарное распределение, но \(P^n\) осциллирует.
Прием с петлей: \(P_{ii}>0\) дает период \(1\) для этого возвратного класса.
Транзиентность — свойство в итоге: транзиентное состояние может посещаться несколько раз, но лишь конечное число раз с вероятностью \(1\).
Моменты остановки используют доступную информацию: они не могут зависеть от невидимых будущих исходов.
Мартингал означает честное условное среднее: это не означает, что траектория остается постоянной.
Разобранный пример
Пример: Допустима ли строка \((1/4,1/4)\) как полная строка переходов?
Нет. Она неотрицательна, но сумма ее элементов равна \(1/2\), а не \(1\). Полная строка переходов должна задавать суммарную вероятность \(1\) по всем следующим состояниям.
Попробуйте
Попробуйте: От чего не может зависеть момент остановки?
Подсказка: в момент \(n\) решение должно основываться на информации, доступной к моменту \(n\).
Итоговое повторение
Марковское свойство: закон следующего состояния зависит от текущего состояния, если текущее состояние известно.
Матрица переходов имеет неотрицательные элементы и строки с суммой \(1\).
При строковых векторах \(p_n=p_0P^n\).
Чепмен-Колмогоров: \(P^{m+n}=P^mP^n\).
Стационарные распределения решают \(\pi P=\pi\) и \(\sum_i\pi_i=1\).
Поглощающее состояние имеет \(P_{ii}=1\); замкнутый класс нельзя покинуть.
Неприводимость означает, что каждое состояние может достичь каждого другого.
Период — это НОД возможных времен возврата; петля дает период \(1\).
Конечные неприводимые апериодические цепи сходятся к стационарным строкам.
Моменты остановки определяются по прошлой и текущей информации, а не по невидимым будущим данным.
Следующий шаг: Закройте этот урок и попробуйте пройти тест снова. В каждом вопросе сначала определите, спрашивают ли вас об одном шаге, многих шагах, стационарном распределении, классификации состояния, периоде или условном ожидании.
Набор практики
Практические вопросы по теме Markov Chains & Stochastic Processes с мгновенным результатом
Ответьте на все 10 вопросов ниже, затем получите итоговый результат и разбор ошибок, чтобы точно понять, что улучшить.
0/10отвечено
Вопрос 1Нет ответа
Марковское свойство означает, что будущее зависит от:
Правильный ответ: A. Текущего состояния
Объяснение: При заданном текущем состоянии прошлое не добавляет информации.
Вопрос 2Нет ответа
В матрице переходов конечной марковской цепи сумма элементов каждой строки обычно равна:
Правильный ответ: C. \(1\)
Объяснение: Строки задают вероятности всех следующих состояний, поэтому их сумма равна \(1\).
Вопрос 3Нет ответа
Переходные вероятности должны быть:
Правильный ответ: B. Неотрицательными
Объяснение: Вероятности неотрицательны и не превосходят \(1\).
Вопрос 4Нет ответа
Стационарное распределение \(\pi\) удовлетворяет:
Правильный ответ: D. \(\pi P=\pi\)
Объяснение: Стационарность означает, что один переход не меняет распределение.
Вопрос 5Нет ответа
У поглощающего состояния \(i\) переходная вероятность \(P_{ii}\) равна:
Правильный ответ: B. \(1\)
Объяснение: Попав в поглощающее состояние, цепь уже не покидает его.
Вопрос 6Нет ответа
Если \(P=\begin{pmatrix}1&0\\0&1\end{pmatrix}\), оба состояния являются:
Правильный ответ: D. Поглощающими
Объяснение: Каждое состояние переходит в себя с вероятностью \(1\).
Вопрос 7Нет ответа
Цепь неприводима, когда:
Правильный ответ: D. Из каждого состояния можно достичь любого другого
Объяснение: Неприводимость означает, что все состояния сообщаются друг с другом.
Вопрос 8Нет ответа
Если текущее распределение равно \(p\), то следующее распределение обычно равно:
Правильный ответ: A. \(pP\)
Объяснение: При соглашении о строковых векторах один шаг получается умножением справа на \(P\).
Вопрос 9Нет ответа
Для \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\) какое распределение является стационарным?
Правильный ответ: B. \((1/2,1/2)\)
Объяснение: Равномерное распределение остается равномерным после умножения на эту матрицу.
Вопрос 10Нет ответа
В конечной марковской цепи сумма компонент распределения вероятностей должна быть равна:
Правильный ответ: D. \(1\)
Объяснение: Распределение задает полную вероятность \(1\) по всем состояниям.
