Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Distributions of the selfish-mining chain over time, Cesàro averages, and time-averaged revenues

Definition
BitcoinSelfishErgodic

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoincesaroergodicformal-verificationlong-run-averagemarkov-chainmathlibrenewalselfish-mining

Names over the selfish-mining missions' chain (State, P, stateSum, poolExpGain, othersExpGain).

delta t — the point mass at state ttt. dist α γ μ — one step of the chain on a distribution: (dist μ)(s)=∑tμ(t) P(t,s)(\mathrm{dist}\,\mu)(s) = \sum_t \mu(t)\, P(t, s)(distμ)(s)=∑t​μ(t)P(t,s) through stateSum. distN α γ μ n — nnn steps. IsDist μ — nonnegative, summable on the leads, total mass 1. cesaro α γ μ n — the average 1n∑k<ndistN μ k\frac1n \sum_{k<n} \mathrm{distN}\,\mu\,kn1​∑k<n​distNμk (the expected fraction of the first nnn times spent in each state).

expPoolGain α γ μ, expOthersGain α γ μ — expected blocks credited per step when the state has distribution μ\muμ. avgPoolGain α γ n, avgOthersGain α γ n — expected blocks per step over the first nnn steps from zero; avgRelativeRevenue α γ n — their ratio, the pool's time-averaged revenue share (real division, 0 when the denominator is 0).

kill μ — the distribution with the mass at zero removed. taboo α γ t n — the sub-distribution of the chain from ttt killed on hitting zero at times ≥1\ge 1≥1. firstPassage α γ t n — the probability of first hitting zero at time n+1n+1n+1 from ttt. returnProb α γ n — P(Xn=zero∣X0=zero)P(X_n = \text{zero} \mid X_0 = \text{zero})P(Xn​=zero∣X0​=zero). noPassage α γ t n — the probability of not having hit zero by time nnn.

Formalization Note. Imports Mathlib and the two selfish-mining missions' definitions. Real division by zero is 0.

Definition code
import Definitions.Def_BitcoinSelfishMining
import Definitions.Def_BitcoinSelfishUnique

/-!
# Selfish mining: the chain started at a state, its `n`-step distributions, Cesàro averages and
time-averaged revenues

This file sets up the dynamics of the Eyal–Sirer selfish-mining chain of
`Definitions/Def_BitcoinSelfishMining.lean` (states `zero | tie | lead n`, one-step transition
probabilities `P α γ s t`, sums over the countable state space `stateSum`) as an evolution of
distributions on the state space, so that the ergodic statements can be formulated:

* `delta t` is the point mass at the state `t`, `dist α γ μ` is the distribution after one step
  of the chain started with distribution `μ` (`(dist μ) s = Σ_t μ t · P(t → s)`), and
  `distN α γ μ n` the distribution after `n` steps.
* `IsDist μ` says that `μ` is a probability distribution on the states (nonnegative, summable on
  the leads, total mass one). `BitcoinSelfishUnique.IsStationary α γ μ` is `IsDist μ` plus
  invariance under `dist`.
* `cesaro α γ μ n` is the Cesàro average `(1/n) Σ_{k<n} distN α γ μ k` of the first `n`
  distributions of the chain started at `μ`.
* `expPoolGain α γ μ` and `expOthersGain α γ μ` are the expected numbers of blocks credited to the
  pool / to the honest miners at one step of the chain whose current state has distribution
  `μ` (so `poolRevenue α γ = expPoolGain α γ (stationary α)` by definition).
* `avgPoolGain α γ n` and `avgOthersGain α γ n` are the expected numbers of blocks per step
  credited to the pool / to the honest miners, averaged over the first `n` steps of the chain
  started at `zero`, and `avgRelativeRevenue α γ n` is the corresponding time-averaged relative
  revenue of the pool. The theorems of `Solutions/Sol_BitcoinSelfishErgodic_all.lean` show that
  these converge to the paper's stationary quantities `poolRevenue`, `othersRevenue` and
  `relativeRevenue`, which makes the paper's revenue analysis a statement about long-run averages.
* `taboo α γ t n` is the sub-distribution of the chain started at `t` and killed when it hits
  `zero`, `firstPassage α γ t n` the probability that this first hit happens at time `n + 1`,
  `noPassage α γ t n` the probability of no hit up to time `n`, and `returnProb α γ n` the
  renewal sequence `P(X_n = zero | X_0 = zero)`. They are used to prove the convergence of the
  `n`-step distributions themselves (not only of their Cesàro averages) to `stationary α`.
-/

namespace BitcoinSelfishErgodic

open BitcoinSelfishMining

/-- The state space is countable (`zero ↦ 0`, `tie ↦ 1`, `lead n ↦ n + 2`). -/
instance : Countable State :=
  Function.Injective.countable (f := fun s : State => match s with
    | .zero => 0
    | .tie => 1
    | .lead n => n + 2) (by
    intro s t h
    cases s <;> cases t <;> simp_all)

/-- The point mass at the state `t`. -/
noncomputable def delta (t : State) : State → ℝ := fun s => if s = t then 1 else 0

/-- One step of the chain acting on distributions: `(dist α γ μ) s = Σ_t μ t · P α γ t s`. -/
noncomputable def dist (α γ : ℝ) (μ : State → ℝ) : State → ℝ :=
  fun s => stateSum (fun t => μ t * P α γ t s)

/-- The distribution of the chain after `n` steps, started with distribution `μ`. -/
noncomputable def distN (α γ : ℝ) (μ : State → ℝ) : ℕ → State → ℝ
  | 0 => μ
  | n + 1 => dist α γ (distN α γ μ n)

/-- A probability distribution on the states: nonnegative, summable on the leads (so that
`stateSum μ` is a genuine sum), of total mass one. -/
structure IsDist (μ : State → ℝ) : Prop where
  nonneg : ∀ s, 0 ≤ μ s
  summable : Summable (fun n : ℕ => μ (.lead n))
  mass : stateSum μ = 1

/-- The Cesàro average `(1/n) Σ_{k<n} distN α γ μ k` of the first `n` distributions of the chain
started at `μ` (the expected fraction of the times `0, …, n-1` spent in each state). -/
noncomputable def cesaro (α γ : ℝ) (μ : State → ℝ) (n : ℕ) : State → ℝ :=
  fun s => (1 / (n : ℝ)) * ∑ k ∈ Finset.range n, distN α γ μ k s

/-- Expected number of blocks credited to the pool at one step of the chain, when the current
state has distribution `μ`: `Σ_s μ s · poolExpGain α γ s`. -/
noncomputable def expPoolGain (α γ : ℝ) (μ : State → ℝ) : ℝ :=
  stateSum (fun s => μ s * poolExpGain α γ s)

/-- Expected number of blocks credited to the honest miners at one step of the chain, when the
current state has distribution `μ`. -/
noncomputable def expOthersGain (α γ : ℝ) (μ : State → ℝ) : ℝ :=
  stateSum (fun s => μ s * othersExpGain α γ s)

/-- The expected number of blocks per step credited to the pool over the first `n` steps of the
chain started at `zero`: `(1/n) Σ_{k<n} Σ_s P(X_k = s) · poolExpGain α γ s`. -/
noncomputable def avgPoolGain (α γ : ℝ) (n : ℕ) : ℝ :=
  (1 / (n : ℝ)) * ∑ k ∈ Finset.range n,
    stateSum (fun s => distN α γ (delta .zero) k s * poolExpGain α γ s)

/-- The expected number of blocks per step credited to the honest miners over the first `n` steps
of the chain started at `zero`. -/
noncomputable def avgOthersGain (α γ : ℝ) (n : ℕ) : ℝ :=
  (1 / (n : ℝ)) * ∑ k ∈ Finset.range n,
    stateSum (fun s => distN α γ (delta .zero) k s * othersExpGain α γ s)

/-- The pool's time-averaged relative revenue over the first `n` steps of the chain started at
`zero`: expected pool blocks divided by expected total blocks. -/
noncomputable def avgRelativeRevenue (α γ : ℝ) (n : ℕ) : ℝ :=
  avgPoolGain α γ n / (avgPoolGain α γ n + avgOthersGain α γ n)

/-- Killing at `zero`: the mass at `zero` is removed, every other state is kept. -/
noncomputable def kill (μ : State → ℝ) : State → ℝ := fun s => if s = .zero then 0 else μ s

/-- The taboo sub-distributions of the chain started at `t` and killed when it hits `zero` (at a
time `≥ 1`): `taboo α γ t n s = P(X_n = s, X_1 ≠ zero, …, X_n ≠ zero | X_0 = t)`. -/
noncomputable def taboo (α γ : ℝ) (t : State) : ℕ → State → ℝ
  | 0 => delta t
  | n + 1 => kill (dist α γ (taboo α γ t n))

/-- `firstPassage α γ t n` is the probability that the chain started at `t` hits `zero` for the
first time (among the times `≥ 1`) at time `n + 1`. For `t = zero` this is the distribution of
the first return time to `zero`. -/
noncomputable def firstPassage (α γ : ℝ) (t : State) (n : ℕ) : ℝ :=
  dist α γ (taboo α γ t n) .zero

/-- The renewal sequence of the state `zero`: `returnProb α γ n = P(X_n = zero | X_0 = zero)`. -/
noncomputable def returnProb (α γ : ℝ) (n : ℕ) : ℝ := distN α γ (delta .zero) n .zero

/-- `noPassage α γ t n` is the probability that the chain started at `t` has not hit `zero` at
any of the times `1, …, n` (the total mass of `taboo α γ t n`). -/
noncomputable def noPassage (α γ : ℝ) (t : State) (n : ℕ) : ℝ := stateSum (taboo α γ t n)

end BitcoinSelfishErgodic
Source
I. Eyal, E. G. Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, Financial Cryptography 2014, arXiv:1311.0243, Section 4 (the revenue as a long-run share); the selfish-mining missions BitcoinSelfishMining (chain, revenues, threshold) and BitcoinSelfishUnique (uniqueness of the stationary distribution); standard Markov-chain theory (Cesàro limits, renewal equation)
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: Def_BitcoinSelfishErgodic (definition file)

This file imports the selfish-mining model file and the stationary-distribution file. The imported objects used below are unfolded in the section Imported objects, unfolded at the end. All parameters α,γ\alpha, \gammaα,γ appearing below are arbitrary real numbers: no definition in this file restricts α\alphaα or γ\gammaγ. The imported predicate "stationary distribution" (a function that is nonnegative, summable on the lead states, has Σ=1\Sigma = 1Σ=1 and satisfies μ(s)=Σ(t↦μ(t)Pα,γ(t,s))\mu(s) = \Sigma(t \mapsto \mu(t)P_{\alpha,\gamma}(t,s))μ(s)=Σ(t↦μ(t)Pα,γ​(t,s)) for every sss) is not used by any definition in this file.

Declarations, in order

1. Countability of the state space. The file registers the fact that the state space SSS is countable, witnessed by the injective map zero↦0\mathsf{zero} \mapsto 0zero↦0, tie↦1\mathsf{tie} \mapsto 1tie↦1, leadm↦m+2\mathsf{lead}_m \mapsto m + 2leadm​↦m+2 into N\mathbb{N}N. This is a typeclass fact only; it does not define any number or function used elsewhere.

2. Point mass δt\delta_tδt​. For a state ttt, δt:S→R\delta_t : S \to \mathbb{R}δt​:S→R is defined by δt(s)=1\delta_t(s) = 1δt​(s)=1 if s=ts = ts=t and δt(s)=0\delta_t(s) = 0δt​(s)=0 otherwise.

3. One step Dα,γD_{\alpha,\gamma}Dα,γ​. For real α,γ\alpha,\gammaα,γ and any μ:S→R\mu : S \to \mathbb{R}μ:S→R (no sign, summability or normalization required), Dα,γμ:S→RD_{\alpha,\gamma}\mu : S \to \mathbb{R}Dα,γ​μ:S→R is

(Dα,γμ)(s)=Σ(t↦μ(t) Pα,γ(t,s))=μ(zero)P(zero,s)+μ(tie)P(tie,s)+∑m≥0μ(leadm)P(leadm,s),(D_{\alpha,\gamma}\mu)(s) = \Sigma\big(t \mapsto \mu(t)\,P_{\alpha,\gamma}(t,s)\big) = \mu(\mathsf{zero})P(\mathsf{zero},s) + \mu(\mathsf{tie})P(\mathsf{tie},s) + \sum_{m\ge0}\mu(\mathsf{lead}_m)P(\mathsf{lead}_m,s),(Dα,γ​μ)(s)=Σ(t↦μ(t)Pα,γ​(t,s))=μ(zero)P(zero,s)+μ(tie)P(tie,s)+m≥0∑​μ(leadm​)P(leadm​,s),

with Σ\SigmaΣ and PPP as unfolded below. For a fixed target sss at most two lead states ttt have P(t,s)≠0P(t,s)\neq 0P(t,s)=0, so the lead series is a finite sum and the "000 if not summable" clause of Σ\SigmaΣ never applies here.

4. nnn steps Dα,γnD^n_{\alpha,\gamma}Dα,γn​. Defined by recursion on n∈Nn \in \mathbb{N}n∈N: D0μ=μD^0\mu = \muD0μ=μ and Dn+1μ=Dα,γ(Dnμ)D^{n+1}\mu = D_{\alpha,\gamma}(D^n\mu)Dn+1μ=Dα,γ​(Dnμ).

5. Distribution predicate. A function μ:S→R\mu : S \to \mathbb{R}μ:S→R is a distribution exactly when all three hold: (i) μ(s)≥0\mu(s) \ge 0μ(s)≥0 for every state sss; (ii) the real sequence (μ(leadm))m≥0\big(\mu(\mathsf{lead}_m)\big)_{m\ge0}(μ(leadm​))m≥0​ is summable; (iii) Σμ=μ(zero)+μ(tie)+∑m≥0μ(leadm)=1\Sigma\mu = \mu(\mathsf{zero}) + \mu(\mathsf{tie}) + \sum_{m\ge0}\mu(\mathsf{lead}_m) = 1Σμ=μ(zero)+μ(tie)+∑m≥0​μ(leadm​)=1. It involves no α,γ\alpha,\gammaα,γ.

6. Cesàro average CnC_nCn​. For real α,γ\alpha,\gammaα,γ, μ:S→R\mu : S\to\mathbb{R}μ:S→R, n∈Nn \in \mathbb{N}n∈N and a state sss,

(Cnμ)(s)=1n∑k=0n−1(Dα,γkμ)(s).(C_n\mu)(s) = \frac{1}{n}\sum_{k=0}^{n-1}(D^k_{\alpha,\gamma}\mu)(s).(Cn​μ)(s)=n1​k=0∑n−1​(Dα,γk​μ)(s).

Real division by 000 is 000, and the sum is empty for n=0n=0n=0, so C0μC_0\muC0​μ is the zero function.

7. Expected pool credit Eα,γpool(μ)E^{\mathrm{pool}}_{\alpha,\gamma}(\mu)Eα,γpool​(μ). For μ:S→R\mu : S\to\mathbb{R}μ:S→R,

Epool(μ)=Σ(s↦μ(s) gα,γ(s))=μ(tie)(2α+(1−α)γ)+∑m≥0μ(leadm) g(leadm),E^{\mathrm{pool}}(\mu) = \Sigma\big(s\mapsto\mu(s)\,g_{\alpha,\gamma}(s)\big) = \mu(\mathsf{tie})\big(2\alpha+(1-\alpha)\gamma\big) + \sum_{m\ge0}\mu(\mathsf{lead}_m)\,g(\mathsf{lead}_m),Epool(μ)=Σ(s↦μ(s)gα,γ​(s))=μ(tie)(2α+(1−α)γ)+m≥0∑​μ(leadm​)g(leadm​),

where ggg is the expected per-step pool credit (below; g(zero)=g(lead0)=0g(\mathsf{zero}) = g(\mathsf{lead}_0) = 0g(zero)=g(lead0​)=0, g(lead1)=2(1−α)g(\mathsf{lead}_1) = 2(1-\alpha)g(lead1​)=2(1−α), g(leadm+2)=1−αg(\mathsf{lead}_{m+2}) = 1-\alphag(leadm+2​)=1−α), and the series is 000 if not summable.

8. Expected honest-miner credit Eα,γoth(μ)E^{\mathrm{oth}}_{\alpha,\gamma}(\mu)Eα,γoth​(μ). For μ:S→R\mu : S\to\mathbb{R}μ:S→R,

Eoth(μ)=Σ(s↦μ(s) hα,γ(s))=(1−α) μ(zero)+(1−α)(2−γ) μ(tie),E^{\mathrm{oth}}(\mu) = \Sigma\big(s\mapsto\mu(s)\,h_{\alpha,\gamma}(s)\big) = (1-\alpha)\,\mu(\mathsf{zero}) + (1-\alpha)(2-\gamma)\,\mu(\mathsf{tie}),Eoth(μ)=Σ(s↦μ(s)hα,γ​(s))=(1−α)μ(zero)+(1−α)(2−γ)μ(tie),

since hhh vanishes on every lead state (so the lead series is the zero series).

9. Time-averaged pool credit AnA_nAn​. For real α,γ\alpha,\gammaα,γ and n∈Nn\in\mathbb{N}n∈N,

An(α,γ)=1n∑k=0n−1Σ(s↦(Dkδzero)(s) g(s))=1n∑k=0n−1Epool(Dkδzero),A_n(\alpha,\gamma) = \frac1n\sum_{k=0}^{n-1}\Sigma\big(s\mapsto (D^k\delta_{\mathsf{zero}})(s)\,g(s)\big) = \frac1n\sum_{k=0}^{n-1}E^{\mathrm{pool}}\big(D^k\delta_{\mathsf{zero}}\big),An​(α,γ)=n1​k=0∑n−1​Σ(s↦(Dkδzero​)(s)g(s))=n1​k=0∑n−1​Epool(Dkδzero​),

always starting from the point mass at zero\mathsf{zero}zero; each inner Σ\SigmaΣ uses the "series is 000 if not summable" convention separately, and A0=0A_0 = 0A0​=0 (as 1/0=01/0 = 01/0=0).

10. Time-averaged honest-miner credit BnB_nBn​. For real α,γ\alpha,\gammaα,γ and n∈Nn\in\mathbb{N}n∈N,

Bn(α,γ)=1n∑k=0n−1Σ(s↦(Dkδzero)(s) h(s))=1n∑k=0n−1[(1−α)(Dkδzero)(zero)+(1−α)(2−γ)(Dkδzero)(tie)],B_n(\alpha,\gamma) = \frac1n\sum_{k=0}^{n-1}\Sigma\big(s\mapsto (D^k\delta_{\mathsf{zero}})(s)\,h(s)\big) = \frac1n\sum_{k=0}^{n-1}\Big[(1-\alpha)(D^k\delta_{\mathsf{zero}})(\mathsf{zero}) + (1-\alpha)(2-\gamma)(D^k\delta_{\mathsf{zero}})(\mathsf{tie})\Big],Bn​(α,γ)=n1​k=0∑n−1​Σ(s↦(Dkδzero​)(s)h(s))=n1​k=0∑n−1​[(1−α)(Dkδzero​)(zero)+(1−α)(2−γ)(Dkδzero​)(tie)],

with B0=0B_0 = 0B0​=0.

11. Time-averaged relative revenue RnR_nRn​. Rn(α,γ)=AnAn+BnR_n(\alpha,\gamma) = \dfrac{A_n}{A_n + B_n}Rn​(α,γ)=An​+Bn​An​​, where real division by 000 gives 000; so Rn=0R_n = 0Rn​=0 whenever An+Bn=0A_n + B_n = 0An​+Bn​=0, and in particular R0=0R_0 = 0R0​=0.

12. Killing at zero\mathsf{zero}zero, κ\kappaκ. For μ:S→R\mu : S \to \mathbb{R}μ:S→R, (κμ)(s)=0(\kappa\mu)(s) = 0(κμ)(s)=0 if s=zeros = \mathsf{zero}s=zero and (κμ)(s)=μ(s)(\kappa\mu)(s) = \mu(s)(κμ)(s)=μ(s) otherwise.

13. Taboo functions τnt\tau^t_nτnt​. For real α,γ\alpha,\gammaα,γ and a starting state ttt, defined by recursion on nnn: τ0t=δt\tau^t_0 = \delta_tτ0t​=δt​ (not killed; so τ0zero=δzero\tau^{\mathsf{zero}}_0 = \delta_{\mathsf{zero}}τ0zero​=δzero​ has value 111 at zero\mathsf{zero}zero), and τn+1t=κ(Dα,γτnt)\tau^t_{n+1} = \kappa\big(D_{\alpha,\gamma}\tau^t_n\big)τn+1t​=κ(Dα,γ​τnt​), i.e. one step followed by setting the value at zero\mathsf{zero}zero to 000.

14. First passage fntf^t_nfnt​. For real α,γ\alpha,\gammaα,γ, a state ttt and n∈Nn\in\mathbb{N}n∈N, fnt=(Dα,γτnt)(zero)f^t_n = \big(D_{\alpha,\gamma}\tau^t_n\big)(\mathsf{zero})fnt​=(Dα,γ​τnt​)(zero): the value at zero\mathsf{zero}zero after one step applied to the nnn-th taboo function (before killing). For example f0t=(Dδt)(zero)=Pα,γ(t,zero)f^t_0 = (D\delta_t)(\mathsf{zero}) = P_{\alpha,\gamma}(t,\mathsf{zero})f0t​=(Dδt​)(zero)=Pα,γ​(t,zero).

15. Return sequence rnr_nrn​. For real α,γ\alpha,\gammaα,γ and n∈Nn\in\mathbb{N}n∈N, rn=(Dα,γnδzero)(zero)r_n = \big(D^n_{\alpha,\gamma}\delta_{\mathsf{zero}}\big)(\mathsf{zero})rn​=(Dα,γn​δzero​)(zero); in particular r0=1r_0 = 1r0​=1.

16. No-passage total NntN^t_nNnt​. For real α,γ\alpha,\gammaα,γ, a state ttt and n∈Nn\in\mathbb{N}n∈N, Nnt=Σ τnt=τnt(zero)+τnt(tie)+∑m≥0τnt(leadm)N^t_n = \Sigma\,\tau^t_n = \tau^t_n(\mathsf{zero}) + \tau^t_n(\mathsf{tie}) + \sum_{m\ge0}\tau^t_n(\mathsf{lead}_m)Nnt​=Στnt​=τnt​(zero)+τnt​(tie)+∑m≥0​τnt​(leadm​), with the series set to 000 if not summable. (For n≥1n \ge 1n≥1 the zero\mathsf{zero}zero term is 000 because of the killing; for n=0n = 0n=0 it is δt(zero)\delta_t(\mathsf{zero})δt​(zero).)


Imported objects, unfolded

State space SSS. The states are zero\mathsf{zero}zero, tie\mathsf{tie}tie, and one state leadm\mathsf{lead}_mleadm​ for every natural number m=0,1,2,…m = 0, 1, 2, \dotsm=0,1,2,…; all of these are distinct. (The source comments say that leadm\mathsf{lead}_mleadm​ stands for a private lead of m+1m+1m+1 blocks, so lead0\mathsf{lead}_0lead0​ is "lead 1", lead1\mathsf{lead}_1lead1​ is "lead 2", and so on. Formally these are only labels, and every subscript below is this shifted index.)

Sum over all states. For any f:S→Rf : S \to \mathbb{R}f:S→R,

Σf  =  f(zero)+f(tie)+∑m≥0f(leadm),\Sigma f \;=\; f(\mathsf{zero}) + f(\mathsf{tie}) + \sum_{m \ge 0} f(\mathsf{lead}_m),Σf=f(zero)+f(tie)+m≥0∑​f(leadm​),

where the infinite series is the value of the series when the real sequence (f(leadm))m≥0\big(f(\mathsf{lead}_m)\big)_{m \ge 0}(f(leadm​))m≥0​ is summable (for real sequences: absolutely summable). The series is defined to be 000 when that sequence is not summable.

One-step transition weights Pα,γP_{\alpha,\gamma}Pα,γ​. For arbitrary real numbers α,γ\alpha, \gammaα,γ (the definitions themselves impose no range), there are three outcomes, with weights

qpool=α,qhP=(1−α)γ,qhO=(1−α)(1−γ).q_{\mathrm{pool}} = \alpha, \qquad q_{\mathrm{hP}} = (1-\alpha)\gamma, \qquad q_{\mathrm{hO}} = (1-\alpha)(1-\gamma).qpool​=α,qhP​=(1−α)γ,qhO​=(1−α)(1−γ).

A deterministic successor map step(s,o)\mathrm{step}(s, o)step(s,o) is given by

current stateoutcome pooloutcome hPoutcome hO
zero\mathsf{zero}zerolead0\mathsf{lead}_0lead0​zero\mathsf{zero}zerozero\mathsf{zero}zero
tie\mathsf{tie}tiezero\mathsf{zero}zerozero\mathsf{zero}zerozero\mathsf{zero}zero
lead0\mathsf{lead}_0lead0​lead1\mathsf{lead}_1lead1​tie\mathsf{tie}tietie\mathsf{tie}tie
lead1\mathsf{lead}_1lead1​lead2\mathsf{lead}_2lead2​zero\mathsf{zero}zerozero\mathsf{zero}zero
leadm+2\mathsf{lead}_{m+2}leadm+2​ (m≥0m \ge 0m≥0)leadm+3\mathsf{lead}_{m+3}leadm+3​leadm+1\mathsf{lead}_{m+1}leadm+1​leadm+1\mathsf{lead}_{m+1}leadm+1​

and Pα,γ(s,t)=∑o : step(s,o)=tqoP_{\alpha,\gamma}(s, t) = \sum_{o \,:\, \mathrm{step}(s,o) = t} q_oPα,γ​(s,t)=∑o:step(s,o)=t​qo​ (sum of the weights of the outcomes leading from sss to ttt). Using qhP+qhO=1−αq_{\mathrm{hP}} + q_{\mathrm{hO}} = 1-\alphaqhP​+qhO​=1−α and qpool+qhP+qhO=1q_{\mathrm{pool}} + q_{\mathrm{hP}} + q_{\mathrm{hO}} = 1qpool​+qhP​+qhO​=1, the only entries that can be nonzero are

P(zero,lead0)=α,P(zero,zero)=1−α,P(tie,zero)=1,P(lead0,lead1)=α,P(lead0,tie)=1−α,P(lead1,lead2)=α,P(lead1,zero)=1−α,P(leadm+2,leadm+3)=α,P(leadm+2,leadm+1)=1−α(m≥0),\begin{aligned} &P(\mathsf{zero},\mathsf{lead}_0) = \alpha, && P(\mathsf{zero},\mathsf{zero}) = 1-\alpha, && P(\mathsf{tie},\mathsf{zero}) = 1,\\ &P(\mathsf{lead}_0,\mathsf{lead}_1) = \alpha, && P(\mathsf{lead}_0,\mathsf{tie}) = 1-\alpha, && \\ &P(\mathsf{lead}_1,\mathsf{lead}_2) = \alpha, && P(\mathsf{lead}_1,\mathsf{zero}) = 1-\alpha, && \\ &P(\mathsf{lead}_{m+2},\mathsf{lead}_{m+3}) = \alpha, && P(\mathsf{lead}_{m+2},\mathsf{lead}_{m+1}) = 1-\alpha \quad (m \ge 0), && \end{aligned}​P(zero,lead0​)=α,P(lead0​,lead1​)=α,P(lead1​,lead2​)=α,P(leadm+2​,leadm+3​)=α,​​P(zero,zero)=1−α,P(lead0​,tie)=1−α,P(lead1​,zero)=1−α,P(leadm+2​,leadm+1​)=1−α(m≥0),​​P(tie,zero)=1,​

and every other entry is 000. These identities hold for every real α,γ\alpha, \gammaα,γ: the transition weights do not depend on γ\gammaγ, each row sums to 111, and all entries are ≥0\ge 0≥0 exactly when 0≤α≤10 \le \alpha \le 10≤α≤1.

Per-step credits. Blocks credited at a transition from state sss under outcome ooo (natural numbers, cast to reals):

current statepool credit (pool / hP / hO)others credit (pool / hP / hO)
zero\mathsf{zero}zero0 / 0 / 00 \,/\, 0 \,/\, 00/0/00 / 1 / 10 \,/\, 1 \,/\, 10/1/1
tie\mathsf{tie}tie2 / 1 / 02 \,/\, 1 \,/\, 02/1/00 / 1 / 20 \,/\, 1 \,/\, 20/1/2
lead0\mathsf{lead}_0lead0​0 / 0 / 00 \,/\, 0 \,/\, 00/0/00 / 0 / 00 \,/\, 0 \,/\, 00/0/0
lead1\mathsf{lead}_1lead1​0 / 2 / 20 \,/\, 2 \,/\, 20/2/20 / 0 / 00 \,/\, 0 \,/\, 00/0/0
leadm+2\mathsf{lead}_{m+2}leadm+2​ (m≥0m\ge0m≥0)0 / 1 / 10 \,/\, 1 \,/\, 10/1/10 / 0 / 00 \,/\, 0 \,/\, 00/0/0

The expected per-step credits are the weight-averages gα,γ(s)=∑oqo⋅(pool credit)g_{\alpha,\gamma}(s) = \sum_o q_o \cdot(\text{pool credit})gα,γ​(s)=∑o​qo​⋅(pool credit) and hα,γ(s)=∑oqo⋅(others credit)h_{\alpha,\gamma}(s) = \sum_o q_o \cdot(\text{others credit})hα,γ​(s)=∑o​qo​⋅(others credit) with the (possibly negative, if α,γ\alpha,\gammaα,γ are out of range) weights qoq_oqo​ above. Explicitly, for all real α,γ\alpha,\gammaα,γ:

g(zero)=0,g(tie)=2α+(1−α)γ,g(lead0)=0,g(lead1)=2(1−α),g(leadm+2)=1−α;h(zero)=1−α,h(tie)=(1−α)(2−γ),h(leadm)=0 for all m.\begin{aligned} &g(\mathsf{zero}) = 0,\quad g(\mathsf{tie}) = 2\alpha + (1-\alpha)\gamma,\quad g(\mathsf{lead}_0) = 0,\quad g(\mathsf{lead}_1) = 2(1-\alpha),\quad g(\mathsf{lead}_{m+2}) = 1-\alpha;\\ &h(\mathsf{zero}) = 1-\alpha,\quad h(\mathsf{tie}) = (1-\alpha)(2-\gamma),\quad h(\mathsf{lead}_m) = 0 \text{ for all } m. \end{aligned}​g(zero)=0,g(tie)=2α+(1−α)γ,g(lead0​)=0,g(lead1​)=2(1−α),g(leadm+2​)=1−α;h(zero)=1−α,h(tie)=(1−α)(2−γ),h(leadm​)=0 for all m.​
Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 30, 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