stochastic_mst_priority_cost_aux
For a simple graph G on a finite vertex type V with decidable adjacency, p : Sym2 V → ℝ and a list pi of edges (List (Sym2 V)), the expected number of further queries of the priority strategy for pi from the state (Z, D) of finite edge sets (Finsets of Sym2 V), with fuel k : ℕ: it is 0 when k = 0, and also 0 when no element of pi satisfies stochastic_mst_query_eligible G Z D; otherwise, for e the first element of pi (List.find?) with stochastic_mst_query_eligible G Z D e, it is 1 + p e * value(k-1, Z, insert e D) + (1 - p e) * value(k-1, insert e Z, D).
Statement
noncomputable def stochastic_mst_priority_cost_aux {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) (π : List (Sym2 V)) : ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ
- Defined in
- arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 3, ExecuteTutteStrategy(pi): query edges in the order pi, skipping those that are loops or bridges of the current minor
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- stochastic_mst_query_eligibleFor a simple graph G on a vertex type V, finite sets Z and D of edges (Finsets of Sym2 V: Z the edges queried with weight 0, which are…
- Used by 2
- stochastic_mst_priority_costFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ, P(G,p) is the infimum (sInf in ℝ) of the set…
- stochastic_mst_adaptive_cost_le_priority_costFor every finite simple graph G and every p with 0 <= p_e <= 1 on the edges, A(G,p) <= P(G,p): every fixed-priority strategy is an…
Read back from the Lean
stochastic_mst_priority_cost_aux defines a function taking:
- a type V with a Fintype V instance,
- a simple graph G on V with a DecidableRel G.Adj instance,
- a function p : Sym2 V → ℝ,
- a list π : List (Sym2 V),
- a natural number k : ℕ (recursion depth),
- two finite sets of unordered pairs of vertices Z, D : Finset (Sym2 V),
and returning a real number ℝ.
It is defined by recursion on k:
- If k = 0, it returns 0 (for any Z and D).
- If k + 1, it searches the list π for the first element e such that stochastic_mst_query_eligible G Z D e holds (using classical decidability):
- If no such element exists in π, it returns 0.
- If such an element e is found, it returns:
1 + p e * stochastic_mst_priority_cost_aux G p π k Z (insert e D) + (1 - p e) * stochastic_mst_priority_cost_aux G p π k (insert e Z) D.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
noncomputable def stochastic_mst_priority_cost_aux {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) (π : List (Sym2 V)) : ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ := fun | 0, _, _ => 0 | k + 1, Z, D => open Classical in match π.find? (fun e => decide (stochastic_mst_query_eligible G Z D e)) with | none => 0 | some e => 1 + p e * stochastic_mst_priority_cost_aux G p π k Z (insert e D) + (1 - p e) * stochastic_mst_priority_cost_aux G p π k (insert e Z) D