stochastic_mst_adaptive_cost_aux
For 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), the optimal expected number of further queries 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 edge of G.edgeFinset satisfies stochastic_mst_query_eligible G Z D; otherwise it is the minimum, over the edges e of G.edgeFinset with stochastic_mst_query_eligible G Z D e, of 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_adaptive_cost_aux {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ
- Defined in
- arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Lemma 2.2 (a partial realization certifies an MST iff its minor has only loops and bridges) and Lemmas 3.1-3.2 (an optimal adaptive strategy queries only non-loop non-bridge edges, i.e. is a Tutte strategy): the optimal adaptive cost as a recursion over states
- 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_adaptive_costFor 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…
- 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_aux is a noncomputable function taking:
* a type V with a Fintype V instance,
* a simple graph G on V with decidable adjacency ([DecidableRel G.Adj]),
* an edge probability/weight function p : Sym2 V → ℝ,
* a step bound k : ℕ,
* and two finite sets of edges Z, D : Finset (Sym2 V),
and returning a real number (ℝ), defined by recursion on k:
* **Base case (k = 0)**: returns 0 for any Z and D.
* **Step case (k + 1)**: considers the finite set of edges e ∈ G.edgeFinset satisfying stochastic_mst_query_eligible G Z D e.
* If this set is nonempty (witnessed by h), it returns the infimum (minimum) over all e in this set of:
1 + p e * stochastic_mst_adaptive_cost_aux G p k Z (insert e D) + (1 - p e) * stochastic_mst_adaptive_cost_aux G p k (insert e Z) D.
* If this set is empty, it returns 0.
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_aux {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ := fun | 0, _, _ => 0 | k + 1, Z, D => open Classical in if h : (G.edgeFinset.filter (fun e => stochastic_mst_query_eligible G Z D e)).Nonempty then (G.edgeFinset.filter (fun e => stochastic_mst_query_eligible G Z D e)).inf' h (fun e => 1 + p e * stochastic_mst_adaptive_cost_aux G p k Z (insert e D) + (1 - p e) * stochastic_mst_adaptive_cost_aux G p k (insert e Z) D) else 0