Minimum average-case queries of q + 1 -ary search game with small sets

摘要

Given a search space S={1,2,...,n}, an unknown element x~*∈S and fixed integers ?≥1 and q≥1, a q+1-ary ?-restricted query is of the following form: which one of the set {A 0_,A _1,...,A _q} is the x* in?, where (A _0,A _1,...,A _q) is a partition of S and | ~(Ai)|≤? for i=1,2,...,q. The problem of finding x* from S with q+1-ary size-restricted queries is called as a q+1-ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when x~* satisfies the uniform distribution on S.