AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_strategy_cost

def

For an edge probability function p assigning each edge e the probability that e has weight 1, the expected number of queries of a strategy is 0 at a leaf, and at a query node on edge e with children s₀ and s₁, it is 1 + (1 - p e) * cost(s₀) + p e * cost(s₁).

Statement

def stochastic_mst_strategy_cost {α : Type*} (p : α → ℝ) : StochasticMstStrategy α → ℝ
Defined in
arXiv:2610.40844 Section 3
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
Used by 1
  • is_optimal_stochastic_mst_strategyA strategy T is an optimal strategy solving the adaptive MST identification problem for graph G with edge probabilities p if T solves the…

Read back from the Lean

Given a type α, a function p : α → ℝ, and a strategy tree s : StochasticMstStrategy α, stochastic_mst_strategy_cost p s is the real number defined by structural recursion on s: - If s is leaf, the value is 0. - If s is query e s₀ s₁ (querying an element e : α with continuation strategies s₀ and s₁), the value is 1 + (1 - p e) * stochastic_mst_strategy_cost p s₀ + p e * stochastic_mst_strategy_cost p s₁.

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

/-- The expected number of queries made by an adaptive strategy under edge probability vector p. -/
def stochastic_mst_strategy_cost {α : Type*} (p : α → ℝ) : StochasticMstStrategy α → ℝ
| StochasticMstStrategy.leaf => 0
| StochasticMstStrategy.query e s₀ s₁ =>
    1 + (1 - p e) * stochastic_mst_strategy_cost p s₀ + p e * stochastic_mst_strategy_cost p s₁
See it in the graphDiscuss this resultChallenge it