Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PεP^\varepsilonPε is irreducible and aperiodic and has a unique stationary distribution

Proved
YoungConventions.RiskDominance.perturbed_irreducible_aperiodic

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

markov-chainp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-stability

Let Γ\GammaΓ be a finite nnn-person game with nonempty strategy sets, let 1≤k≤m1\le k\le m1≤k≤m, let ppp be a best-reply distribution for sample size kkk, and let (λ,q)(\lambda,q)(λ,q) be an admissible experimentation (λi>0\lambda_i>0λi​>0, qi(⋅∣h)q_i(\cdot\mid h)qi​(⋅∣h) of full support). Let ε>0\varepsilon>0ε>0 with ελi≤1\varepsilon\lambda_i\le1ελi​≤1 for all iii. Then the perturbed process PεP^\varepsilonPε of (2) satisfies:

  1. PεP^\varepsilonPε is a stochastic matrix (nonnegative entries, rows summing to 111);
  2. (Pε)hh′m>0(P^\varepsilon)^m_{hh'}>0(Pε)hh′m​>0 for all states h,h′h,h'h,h′ (all players may experiment for mmm periods in succession), so PεP^\varepsilonPε is irreducible;
  3. (Pε)hhm+1>0(P^\varepsilon)^{m+1}_{hh}>0(Pε)hhm+1​>0 for every state hhh; together with item 2 the process returns to hhh in exactly mmm and in exactly m+1m+1m+1 periods, so it is aperiodic;
  4. PεP^\varepsilonPε has exactly one stationary distribution με\mu^\varepsilonμε, μεPε=με\mu^\varepsilon P^\varepsilon=\mu^\varepsilonμεPε=με.

This makes the stationary distribution με\mu^\varepsilonμε in the definition of stochastic stability well defined.

Preamble
import Mathlib
import Definitions.Def_YoungConventions_AdaptivePlay_History
import Definitions.Def_YoungConventions_RiskDominance_IsBestReplyDistribution
import Definitions.Def_YoungConventions_RiskDominance_IsExperimentation
import Definitions.Def_YoungConventions_RiskDominance_perturbed
import Definitions.Def_YoungConventions_RiskDominance_IsStationaryDistribution

open Filter Topology
Formal statement
namespace YoungConventions.RiskDominance

/-- **`P^ε` is a regular (irreducible, aperiodic) chain with a unique stationary distribution.**
Young (1993), The Evolution of Conventions, Econometrica 61:57–84, §6, pp. 67–68 (PDF pp. 12–13): "Let `h` and `h′` be two distinct states. If `P^ε` is in state
`h` at time `t`, there is a positive probability that all players will experiment for `m` periods in
succession. Thus there is a positive probability that the process arrives at state `h′` at time
`t + m`, so `P^ε` is irreducible. It is aperiodic because the process can move from `h` to `h` in
exactly `m` periods, and also in exactly `m + 1` periods. Hence `P^ε` has a unique stationary
distribution `μ^ε` satisfying the equation `μ^εP^ε = μ^ε`."

For every game, `1 ≤ k ≤ m`, best-reply distribution `p`, admissible `(λ, q)` and `ε > 0` with
`ελᵢ ≤ 1`: `P^ε` is row-stochastic, every entry of `(P^ε)^m` is positive, every diagonal entry of
`(P^ε)^{m+1}` is positive, and `P^ε` has exactly one stationary distribution.

**Formalization Note.** "Irreducible" is stated in the form the page proves, `(P^ε)^m_{hh′} > 0` for
all `h, h′` (including `h = h′`), and "aperiodic" as the return to `h` in exactly `m` and `m + 1`
steps; together these say `P^ε` is primitive. The admissible range of `ε` is `0 < ε` with
`ελᵢ ≤ 1` for all `i`, the range on which (2) is a transition matrix. -/
theorem perturbed_irreducible_aperiodic {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*} [∀ i, Fintype (S i)]
    [∀ i, DecidableEq (S i)] [∀ i, Nonempty (S i)]
    (u : ι → ((i : ι) → S i) → ℝ) (k m : ℕ) [NeZero m] (hk : 1 ≤ k) (hkm : k ≤ m)
    (p q : (i : ι) → YoungConventions.AdaptivePlay.History S m → S i → ℝ) (lam : ι → ℝ)
    (hp : IsBestReplyDistribution u k p) (hq : IsExperimentation lam q)
    (ε : ℝ) (hε : 0 < ε) (hεlam : ∀ i, ε * lam i ≤ 1) :
    perturbed p q lam ε ∈ Matrix.rowStochastic ℝ (YoungConventions.AdaptivePlay.History S m) ∧
    (∀ h h' : YoungConventions.AdaptivePlay.History S m, 0 < (perturbed p q lam ε ^ m) h h') ∧
    (∀ h : YoungConventions.AdaptivePlay.History S m, 0 < (perturbed p q lam ε ^ (m + 1)) h h) ∧
    ∃! μ : YoungConventions.AdaptivePlay.History S m → ℝ, IsStationaryDistribution μ (perturbed p q lam ε) := by sorry

end YoungConventions.RiskDominance
Source
Young (1993), The Evolution of Conventions, Econometrica 61:57–84, §6, pp. 67–68
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