DETERMINING THE MAJORITY: THE BIASED CASE
成果类型：
Article
署名作者：
Chassaing, Philippe
署名单位：
Universite de Lorraine
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1997
页码：
523-544
关键词：
摘要：
We are given a set of n elements, some of them red, the others blue, but their colors are hidden. We are to determine the composition of this set, or to determine an element of the majority color, by making pairwise comparisons of elements from which we obtain the information the colors of these two elements are the same,'' or they are different.'' Let tau(n), respectively, mu(n), be the optimal average number of comparisons needed to solve these two problems. We give an explicit expression of the limit of tau(n)/n, respectively, of mu(n)/n, in terms of the probabilities of being red or blue. We also discuss quasi-optimal algorithms in both cases: when these probabilities are known and when they are unknown.