Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 10, p. 362 — every solution of (7) has x^T = β^T P* and y^T = β^T D + y^T P*

Proved
HordijkKallenbergLP.ExtremePoint.system7_solution

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebralinear-programmingmarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let PPP be a stochastic matrix on a finite set, P∗P^*P∗ its Cesàro limit matrix and D=(I−P+P∗)−1−P∗D=(I-P+P^*)^{-1}-P^*D=(I−P+P∗)−1−P∗ its deviation matrix, and let β\betaβ be any vector. If row vectors x,yx,yx,y solve the system

xT(I−P)=0,xT+yT(I−P)=βT,(7)x^T(I-P)=0,\qquad x^T+y^T(I-P)=\beta^T, \qquad (7)xT(I−P)=0,xT+yT(I−P)=βT,(7)

then

xT=βTP∗andyT=βTD+yTP∗.x^T=\beta^TP^*\qquad\text{and}\qquad y^T=\beta^TD+y^TP^*.xT=βTP∗andyT=βTD+yTP∗.

In the proof of Theorem 10 this pins down the xxx-part of any feasible point sharing the zero pattern of a pure representative, and reduces the yyy-part to a vector that is invariant under PPP up to a known term.

Formalization Note. Row vectors are functions acting by vecMul. P∗P^*P∗ and DDD are the published limitMatrix and deviationMatrix; their identities are Blackwell's Lemma 1(a), 1(d) and are not hypotheses here.

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): every solution of system (7).** Let `P` be a
Markov matrix with limit matrix `P*` and deviation matrix `D = (I − P + P*)⁻¹ − P*`. If row
vectors `x, y` solve
`x^T(I − P) = 0`, `x^T + y^T(I − P) = β^T`  (7),
then `x^T = β^T P*` and `y^T = β^T D + y^T P*`.

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, display (7) and the two lines after it.

**Formalization Note.** Row vectors are functions `n → ℝ` acting by `vecMul` (`x ᵥ* P` is
`x^T P`). Neither positivity of `β` nor any MDP structure is needed. `limitMatrix` and
`deviationMatrix` are the published Blackwell definitions; their identities
(`PP* = P*P = P*P* = P*`, `(I − P)D = I − P*`, `P*D = DP* = 0`) are Blackwell's Lemma 1(a), 1(d)
(Hordijk–Kallenberg's Theorem 2), not hypotheses here. -/
theorem system7_solution {n : Type*} [Fintype n] [DecidableEq n] (P : Matrix n n ℝ)
    (hP : IsMarkovMatrix P) (β x y : n → ℝ) (h3 : x ᵥ* (1 - P) = 0)
    (h4 : x + y ᵥ* (1 - P) = β) :
    x = β ᵥ* limitMatrix P ∧ y = β ᵥ* deviationMatrix P + y ᵥ* limitMatrix P := 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, (7)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me