Увеличение энтропии случайной прогулки

Question

Пусть $ p $ будет матрицей перехода случайной прогулки в неисправен (не может регулярно) График $ G $. Пусть $ pi $ будет распределением на $ v (g) $. Энтропия Шеннона $ pi $ определяется

$$ H ( pi) =- sum_ {v in v (g)} pi_v cdot log ( pi_v). $$

Как доказать, что $ h (p pi) ge h ( pi) $?

Answer 1

Это даже правда? Рассмотрим неизорированный график, который является звездой. То есть центральная вершина $ v_0 $ подключена ко всем другим вершинам $ v_1, v_2, dots, v_ {n-1} $, и на графике нет других ребра. Затем, если вы начнете с равного распределения на $ V_1, V_2, ldots, v_ {n-1} $, после одного шага весь вес на центральной вершине $ v_0 $. Таким образом, на один шаг энтропия перешла от $ log (n-1) $ до $ 0 $.