Proof of Theorem 10, p. 362 — an invariant row vector on an ergodic set that vanishes at one state vanishes on the set
ProvedHordijkKallenbergLP.ExtremePoint.invariant_vanishes_on_ergodiclinear-algebramarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a stochastic matrix on a finite set and the ergodic set of a recurrent state. If a real vector satisfies
then for every .
This is the fact from the theory of Markov chains (Chung, Markov Chains with Stationary Transition Probabilities, p. 33) that the paper applies to to conclude in the proof of Theorem 10: on a closed communicating class the invariant row vectors form a one-dimensional space spanned by a strictly positive vector.
Formalization Note. No sign condition is imposed on . The ergodic set is the set of states accessible from the recurrent state.
Preamble
import Mathlib import Definitions.Def_MarkovDecisionProcesses_AverageReward import Definitions.Def_BlackwellDiscreteDP_NearOne_LimitMatrix import Definitions.Def_HordijkKallenbergLP_ExtremePoint_Model open Matrix MarkovDecisionProcesses BlackwellDiscreteDP.NearOne
Formal statement
namespace HordijkKallenbergLP.ExtremePoint
/-- **Proof of Theorem 10, p. 362 (unnumbered; Chung [2, p. 33]): an invariant row vector on an
ergodic set that vanishes at one state vanishes on the set.** Let `P` be a Markov matrix and
`C = E_k` the ergodic set of a recurrent state `l`. If `z` satisfies
`z_i = ∑_{l' ∈ C} z_{l'} p_{l' i}` for every `i ∈ C`, and `z_{i₀} = 0` for some `i₀ ∈ C`, then
`z_i = 0` for every `i ∈ C`.
Hordijk and Kallenberg, Linear Programming and Markov Decision Chains, Management Sci.
25(4):352–362 (1979), DOI 10.1287/mnsc.25.4.352, p. 362, proof of Theorem 10
("ȳ¹_i − ȳ²_i = Σ_{l∈E_k} (ȳ¹_l − ȳ²_l) p_li, i ∈ E_k, ȳ¹_{i(k)} − ȳ²_{i(k)} = 0. Then it follows
from the theory of Markov chains (e.g. Chung [2, p. 33]) that ȳ¹ = ȳ².").
**Formalization Note.** The paper applies the fact to `z = ȳ¹ − ȳ²`; this is the Markov-chain
fact it cites, stated for an arbitrary real `z` (no sign condition). The ergodic set is
`ergodicSet P l`, the states accessible from the recurrent state `l`. -/
theorem invariant_vanishes_on_ergodic {n : Type*} [Fintype n] [DecidableEq n]
(P : Matrix n n ℝ) (hP : IsMarkovMatrix P) (l : n) (hl : IsRecurrent P l) (z : n → ℝ)
(hz : ∀ i ∈ ergodicSet P l, z i = ∑ k ∈ ergodicSet P l, z k * P k i)
(i₀ : n) (hi₀ : i₀ ∈ ergodicSet P l) (hz₀ : z i₀ = 0) :
∀ i ∈ ergodicSet P l, z i = 0 := by sorry
end HordijkKallenbergLP.ExtremePoint
Source
Hordijk and Kallenberg, Linear Programming and Markov Decision Chains, Management Sci. 25(4):352–362 (1979), DOI 10.1287/mnsc.25.4.352, p. 362, proof of Theorem 10 (citing Chung [2, p. 33])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.