stochastic_mst_adaptive_cost
For a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ, A(G,p) := stochastic_mst_adaptive_cost_aux G p applied with fuel G.edgeFinset.card (the number of edges of G) to the empty state Z = ∅, D = ∅: the minimum expected number of edge queries of an adaptive strategy certifying a minimum spanning tree.
Statement
noncomputable def stochastic_mst_adaptive_cost {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℝ
- Defined in
- arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 2-3: the adaptive Stochastic MST-ID problem
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- stochastic_mst_adaptive_cost_auxFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ (p e the probability that edge e has weight 1),…
- Used by 1
- 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_adaptive_cost defines a real number for a finite type V, a simple graph G on V with decidable adjacency, and a function p : Sym2 V → ℝ.
It is defined as stochastic_mst_adaptive_cost_aux G p G.edgeFinset.card ∅ ∅, which computes the optimal expected cost of an adaptive query process using at most |E(G)| steps, starting with empty sets of resolved edges Z = ∅ and D = ∅.
Specifically, stochastic_mst_adaptive_cost_aux G p k Z D is defined recursively on k : ℕ:
- If k = 0, it returns 0.
- If k + 1, it checks whether the set of edges e ∈ G.edgeFinset satisfying stochastic_mst_query_eligible G Z D e is nonempty:
- If nonempty, it takes the infimum (minimum) over all eligible edges e of:
1 + p(e) * aux(k, Z, D ∪ {e}) + (1 - p(e)) * aux(k, Z ∪ {e}, D).
- If empty, it returns 0.
An edge e : Sym2 V is stochastic_mst_query_eligible G Z D e if:
1. e ∈ G.edgeSet,
2. e ∉ Z,
3. e ∉ D, and
4. There exist u, v : V such that e = s(u, v), u and v are not reachable from each other in the graph whose edge set is Z, and u and v are reachable from each other in the graph obtained from G by deleting D ∪ {e}.
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_adaptive_cost {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℝ := stochastic_mst_adaptive_cost_aux G p G.edgeFinset.card ∅ ∅