stochastic_mst_strategy_cost
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₁