Lemma 1, p. 11 — a left stochastic matrix is non-expansive in ℓ1 on distributions
ProvedPipelineInterv.Welfare.lemma_1markov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pipeline-interventionstochastic-matrix
Let be a left stochastic matrix (nonnegative entries, every column summing to one) and let be probability distributions on . Then
Applying a transition matrix cannot increase the distance between two distributions. This is what lets the dynamic program track distributions on a finite net with an error that does not grow from one layer to the next.
Formalization Note. is written out as .
Preamble
import Mathlib import Definitions.Def_PipelineInterv_Welfare_Model
Formal statement
namespace PipelineInterv.Welfare
open Matrix
theorem lemma_1 {w : ℕ} (M : Matrix (Fin w) (Fin w) ℝ) (hM : M ∈ colStochastic ℝ (Fin w))
(D D' : Fin w → ℝ) (hD : IsDist D) (hD' : IsDist D') :
l1 (M *ᵥ D - M *ᵥ D') ≤ l1 (D - D') := by sorry
end PipelineInterv.Welfare
Source
Arunachaleswaran, Kannan, Roth, Ziani, Pipeline Interventions, arXiv:2002.06592v2, p. 11, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.