Randomized full-information ranking estimator
DefinitionRankingQueryCost_Joint_Supplement_FullEstimatorp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
A full-information estimator receives only a complete answer table and chooses a continuous estimate in according to a probability distribution :
The distribution may depend on the table but cannot depend on which of its compatible orders is the actual order. All probability distributions on are allowed. This separates randomized actual estimation from the deterministic compatible-set radius. Since the table domain is finite, a table-indexed family of probability measures is exactly a Markov kernel from tables to .
Definition code
import Definitions.Def_RankingQueryCost_Joint_Interaction
set_option autoImplicit false
noncomputable section
namespace RankingQueryCost.Joint.Supplement
/-- A full-information randomized estimator sees precisely the complete answer table.
Its output distribution is an arbitrary probability measure on the continuous Q.
The table space is finite, so no further table-measurability restriction is needed. -/
structure FullEstimator (n : ℕ) where
law : Tournament n → MeasureTheory.Measure {q // q ∈ estimateSet n}
probability : ∀ T, MeasureTheory.IsProbabilityMeasure (law T)
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), §2.2, p. 4, PDF p. 5