Как найти матрицу переходов: цепь Маркова по шагам

Дано: переходы абонентов между тремя тарифами за месяц. Из 500 человек на тарифе A остались 400, перешли на B 75 и на C 25; из 300 на тарифе B перешли на A 60, остались 210, ушли на C 30; из 200 на тарифе C перешли на A 20, на B 30, остались 150. Найти: матрицу переходов, доли тарифов через 3 месяца и предельные доли.

Матрица переходов получается делением каждой строки наблюдений на её итог, дальше распределение считается умножением вектора на матрицу. Ответ: строки матрицы равны (0,80; 0,15; 0,05), (0,20; 0,70; 0,10) и (0,10; 0,15; 0,75); через три месяца доли тарифов составят 46,0 %, 32,8 % и 21,3 %, а предельные доли равны 44,4 %, 33,3 % и 22,2 %. Калькулятор сверху пересчитает матрицу и всю траекторию сходимости под другие числа наблюдений.

Решение по шагам

Дано. Таблица наблюдений: сколько абонентов было в каждом тарифе в начале месяца и куда они перешли к концу.

Найти: матрицу переходов $P$, распределение $p^{(3)}$ и стационарное распределение $\pi$.

Шаг 1. Считаем итог по каждой строке. Итог строки $i$ - это все, кто в начале месяца был в состоянии $i$, независимо от того, куда они ушли:

$$n_1 = 400 + 75 + 25 = 500, \qquad n_2 = 60 + 210 + 30 = 300, \qquad n_3 = 20 + 30 + 150 = 200.$$

Числа сошлись с исходными размерами групп, значит ни один абонент не потерян и не посчитан дважды.

Шаг 2. Делим строку на её итог. Элемент матрицы переходов $p_{ij}$ - это условная вероятность оказаться в состоянии $j$ при условии, что сейчас процесс в состоянии $i$:

$$p_{ij} = \frac{n_{ij}}{n_i}, \qquad n_i = \sum_j n_{ij}.$$

Делим построчно: $400/500 = 0{,}80$, $75/500 = 0{,}15$, $25/500 = 0{,}05$ для первой строки, $60/300 = 0{,}20$, $210/300 = 0{,}70$, $30/300 = 0{,}10$ для второй, $20/200 = 0{,}10$, $30/200 = 0{,}15$, $150/200 = 0{,}75$ для третьей. Собираем результат в матрицу:

$$P = \begin{pmatrix} 0{,}80 & 0{,}15 & 0{,}05 \\ 0{,}20 & 0{,}70 & 0{,}10 \\ 0{,}10 & 0{,}15 & 0{,}75 \end{pmatrix}.$$

Шаг 3. Проверяем стохастичность. Каждая строка обязана суммироваться к единице: $0{,}80 + 0{,}15 + 0{,}05 = 1$, $0{,}20 + 0{,}70 + 0{,}10 = 1$, $0{,}10 + 0{,}15 + 0{,}75 = 1$. Проверка прошла. Столбцы к единице не сводятся, и это нормально: сумма по столбцу смысла не имеет.

Шаг 4. Записываем начальное распределение. В начале месяца абоненты распределены так же, как итоги строк, всего их $500 + 300 + 200 = 1000$:

$$p^{(0)} = \left( \frac{500}{1000},\ \frac{300}{1000},\ \frac{200}{1000} \right) = (0{,}5;\ 0{,}3;\ 0{,}2).$$

Шаг 5. Делаем первый шаг. Умножаем вектор-строку на матрицу: доля состояния $j$ собирается из всех, кто мог в него прийти, то есть $p_j^{(1)} = \sum_i p_i^{(0)} p_{ij}$:

$$\begin{aligned} p_{\text{A}}^{(1)} &= 0{,}5 \cdot 0{,}80 + 0{,}3 \cdot 0{,}20 + 0{,}2 \cdot 0{,}10 = 0{,}480, \\ p_{\text{B}}^{(1)} &= 0{,}5 \cdot 0{,}15 + 0{,}3 \cdot 0{,}70 + 0{,}2 \cdot 0{,}15 = 0{,}315, \\ p_{\text{C}}^{(1)} &= 0{,}5 \cdot 0{,}05 + 0{,}3 \cdot 0{,}10 + 0{,}2 \cdot 0{,}75 = 0{,}205. \end{aligned}$$

Сумма равна $0{,}480 + 0{,}315 + 0{,}205 = 1$ - распределение осталось распределением.

Шаг 6. Повторяем ещё два раза. Второй месяц считается по тем же правилам, но стартовым вектором служит уже $p^{(1)}$:

$$\begin{aligned} p_{\text{A}}^{(2)} &= 0{,}480 \cdot 0{,}80 + 0{,}315 \cdot 0{,}20 + 0{,}205 \cdot 0{,}10 = 0{,}46750, \\ p_{\text{B}}^{(2)} &= 0{,}480 \cdot 0{,}15 + 0{,}315 \cdot 0{,}70 + 0{,}205 \cdot 0{,}15 = 0{,}32325, \\ p_{\text{C}}^{(2)} &= 0{,}480 \cdot 0{,}05 + 0{,}315 \cdot 0{,}10 + 0{,}205 \cdot 0{,}75 = 0{,}20925. \end{aligned}$$

Третий месяц:

$$\begin{aligned} p_{\text{A}}^{(3)} &= 0{,}46750 \cdot 0{,}80 + 0{,}32325 \cdot 0{,}20 + 0{,}20925 \cdot 0{,}10 \approx 0{,}4596, \\ p_{\text{B}}^{(3)} &= 0{,}46750 \cdot 0{,}15 + 0{,}32325 \cdot 0{,}70 + 0{,}20925 \cdot 0{,}15 \approx 0{,}3278, \\ p_{\text{C}}^{(3)} &= 0{,}46750 \cdot 0{,}05 + 0{,}32325 \cdot 0{,}10 + 0{,}20925 \cdot 0{,}75 \approx 0{,}2126. \end{aligned}$$

Шаг 7. Ищем предельные доли. Стационарное распределение $\pi$ не меняется при умножении на матрицу, поэтому его находят из системы $\pi P = \pi$ вместе с условием нормировки:

$$\begin{cases} \pi_1 = 0{,}80\,\pi_1 + 0{,}20\,\pi_2 + 0{,}10\,\pi_3, \\ \pi_2 = 0{,}15\,\pi_1 + 0{,}70\,\pi_2 + 0{,}15\,\pi_3, \\ \pi_3 = 0{,}05\,\pi_1 + 0{,}10\,\pi_2 + 0{,}75\,\pi_3, \\ \pi_1 + \pi_2 + \pi_3 = 1. \end{cases}$$

Переносим всё в одну сторону в первом и третьем уравнениях и умножаем на 10 и на 20 соответственно:

$$2\pi_1 = 2\pi_2 + \pi_3, \qquad 5\pi_3 = \pi_1 + 2\pi_2.$$

Подставляем $\pi_3 = 2\pi_1 - 2\pi_2$ во второе соотношение: $10\pi_1 - 10\pi_2 = \pi_1 + 2\pi_2$, откуда $9\pi_1 = 12\pi_2$ и $\pi_1 = \tfrac{4}{3}\pi_2$. Тогда $\pi_3 = \tfrac{2}{3}\pi_2$, а условие нормировки даёт $\left(\tfrac{4}{3} + 1 + \tfrac{2}{3}\right)\pi_2 = 3\pi_2 = 1$:

$$\pi = \left( \frac{4}{9};\ \frac{1}{3};\ \frac{2}{9} \right) \approx (0{,}4444;\ 0{,}3333;\ 0{,}2222).$$

Ответ. Матрица переходов имеет строки (0,80; 0,15; 0,05), (0,20; 0,70; 0,10) и (0,10; 0,15; 0,75). Через три месяца доли тарифов равны 46,0 %, 32,8 % и 21,3 %, предельные доли - 44,4 %, 33,3 % и 22,2 %. Задача типична для курса теории вероятностей и исследования операций.

Формула и откуда она берётся

Цепь Маркова описывает процесс, у которого будущее зависит только от текущего состояния, а не от всей предыстории. Поэтому одного шага достаточно, чтобы задать процесс целиком: набор чисел $p_{ij}$ и есть матрица переходов. Строка $i$ - это полное распределение того, куда процесс уйдёт из состояния $i$, поэтому она неотрицательна и суммируется к единице. Матрицы с таким свойством называют стохастическими по строкам.

Распределение через $n$ шагов записывается компактно: каждое умножение на матрицу продвигает процесс на один шаг, значит

$$p^{(n)} = p^{(0)} P^{\,n}.$$

Это ровно то, что мы делали в шагах 5 и 6, только записанное одной строкой. Матричная запись удобна тем, что $P^n$ можно посчитать сразу, минуя промежуточные векторы, а её элемент $(i, j)$ даёт вероятность попасть из $i$ в $j$ ровно за $n$ шагов. Почему степень матрицы вообще работает как «переход за много шагов», объясняют уравнения Чепмена-Колмогорова: длинный переход разбивается по всем промежуточным состояниям, и сумма произведений оказывается обычным матричным умножением.

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

Если данные заданы не таблицей наблюдений

В контрольных условие формулируют по-разному, но всё сводится к одной и той же матрице.

Вероятности даны словами. «Клиент остаётся на тарифе с вероятностью 0,8, а оставшиеся уходят поровну на два других» - это готовая строка (0,8; 0,1; 0,1). Приём общий: сначала записывают вероятность остаться, потом распределяют дополнение до единицы.

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

Даны проценты или доли рынка. Проценты переводят в доли делением на 100 до всех вычислений: перемножать 80 и 15 вместо 0,8 и 0,15 бессмысленно, ответ вырастет на порядки.

Векторы записаны столбцами. Часть учебников использует столбцовую запись: тогда стохастичны столбцы, а формула принимает вид $p^{(n)} = P^n p^{(0)}$, где $p^{(0)}$ - столбец. Это та же матрица, только транспонированная; смешивать две записи в одной задаче нельзя. Отдельно стоит следить за омонимом: матрица перехода от одного базиса к другому относится к линейной алгебре, к вероятностям отношения не имеет, и её столбцы к единице не суммируются.

Как проверить ответ

Три проверки закрывают почти все ошибки в этой задаче.

Сумма строк. Каждая строка $P$ и любой её степени $P^n$ обязана давать единицу. Если после возведения в степень сумма поехала, ошибка была уже в исходной матрице.

Сумма распределения. Вектор $p^{(n)}$ на каждом шаге суммируется к единице: у нас $0{,}4596 + 0{,}3278 + 0{,}2126 = 1$. Это самая дешёвая проверка, её стоит делать после каждого умножения.

Подстановка стационарного вектора. Умножаем найденное $\pi$ на матрицу и убеждаемся, что вектор не изменился: $\tfrac{4}{9} \cdot 0{,}80 + \tfrac{1}{3} \cdot 0{,}20 + \tfrac{2}{9} \cdot 0{,}10 = \tfrac{4}{9}$. Совпало, значит система решена верно. Дополнительный аргумент в пользу ответа даёт сам ход вычислений: доли $0{,}480 \to 0{,}4675 \to 0{,}4596$ монотонно приближаются к $0{,}4444$, и график в калькуляторе сверху показывает эту сходимость целиком.

Частые ошибки

• Делят на итог столбца, а не строки. Матрица переходов строится по строкам: знаменатель - сколько объектов было в состоянии $i$ до перехода. Деление на столбцовый итог даёт бессмысленные числа, у которых строки не суммируются к единице.
• Умножают матрицу на вектор не с той стороны. При строчной записи распределение - вектор-строка слева: $p^{(1)} = p^{(0)} P$. Произведение $P p^{(0)}$ в этой записи даст другой, неверный вектор.
• Возводят элементы матрицы в степень поэлементно. $P^3$ - это матричное произведение $P \cdot P \cdot P$, а не куб каждого числа. Ошибка сразу видна по сумме строки: она перестаёт равняться единице.
• Округляют слишком рано. Если после первого шага оставить два знака, к третьему шагу расхождение доходит до десятых долей процента. Промежуточные значения держат минимум с четырьмя знаками, округляют только ответ.
• Забывают условие нормировки. Система $\pi P = \pi$ вырождена: одно из трёх уравнений линейно зависимо, и без $\pi_1 + \pi_2 + \pi_3 = 1$ у неё бесконечно много решений. Нулевой вектор формально ей удовлетворяет, но распределением не является.
• Путают стационарное распределение с распределением на конкретном шаге. Через три шага доли равны 46,0 %, 32,8 % и 21,3 %, а предельные - 44,4 %, 33,3 % и 22,2 %. Это разные ответы, и в задаче обычно просят оба.

FAQ

Как построить матрицу переходов по данным наблюдений? Свести переходы в квадратную таблицу «откуда - куда», посчитать итог каждой строки и поделить каждый элемент строки на этот итог. Полученные числа и есть вероятности перехода за один шаг.

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

Всегда ли существует стационарное распределение? Для конечной цепи, у которой из любого состояния достижимо любое другое, стационарное распределение существует и единственно. Сходимость $p^{(n)}$ к нему требует ещё и апериодичности: если цепь строго чередует состояния, вектор будет колебаться, хотя стационарное решение системы всё равно найдётся.

Сколько шагов считать, если в условии спрашивают про далёкое будущее? Не считать вовсе: при большом $n$ распределение практически совпадает со стационарным, поэтому решают систему $\pi P = \pi$. Пошаговое умножение имеет смысл до тех пор, пока номер шага мал и изменения заметны.

Коротко

1. Сводим переходы в таблицу «откуда - куда» и считаем итог каждой строки: 500, 300 и 200.
2. Делим каждый элемент строки на её итог и получаем матрицу со строками (0,80; 0,15; 0,05), (0,20; 0,70; 0,10) и (0,10; 0,15; 0,75).
3. Проверяем стохастичность: сумма любой строки равна единице.
4. Начальное распределение $(0{,}5;\ 0{,}3;\ 0{,}2)$ трижды умножаем на матрицу справа и получаем через три месяца 46,0 %, 32,8 % и 21,3 %.
5. Решаем систему $\pi P = \pi$ с условием нормировки и находим предельные доли 44,4 %, 33,3 % и 22,2 %.