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

Для цепи Маркова P (классическое) ''среднее время достижения'' относительно M может быть выражено в терминах ''матрицы блужданий с утечкой'' <math>P_M</math>, которая получается из P путем удаления всех строк и столбцов, индексированных состояниями M. Обозначим за h(x, M) ожидаемое время достижения M из x, а за <math>v_i, ...., v_{N - |M|}, \lambda_1, ..., \lambda_{N - |M|}</math> – (нормализованные) собственные векторы и соответствующие собственные значения <math>P_M</math>. Обозначим за <math>d : S \to \mathbf{R}^+</math> начальное распределение, а за d' – его ограничение на S \ M. Тогда <math>h := \sum_{x \in S} d(x) h(x, M) = \sum_{k = 1}^{N - |M|} \frac{|v_k, d'|^2}{1 - \lambda_k}</math>. Хотя матрица блужданий с утечкой <math>P_M</math> не является стохастической, можно рассмотреть матрицу ''поглощающих блужданий'' P0 = [ pJf, °], где P00 – матрица, полученная из P удалением столбцов, индексированных M, и строк, индексированных S n M:P0 ведет себя аналогично P, но поглощается первым помеченным состоянием, которого оно достигает. Рассмотрим квантование WP0 из P0 и определим квантовое время достижения, H, множества M как наименьшее m, для которого \W™<j)o - фо\ > 0:1, где фо := Px2S p1/Njxijpxi (которое является стационарным для WP). Заметим, что стоимость построения WP0 пропорциональна 17+ С