AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_adaptive_cost_aux

def

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

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
See it in the graphDiscuss this resultChallenge it