Determining the majority: The biased case. (English) Zbl 0876.68057

Summary: 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.


68Q25 Analysis of algorithms and problem complexity
90C15 Stochastic programming
93E20 Optimal stochastic control
90C40 Markov and semi-Markov decision processes
Full Text: DOI


[1] ALONSO, L., CHASSAING, P. and SCHOTT, R. 1996. A coin-weighing problem. Random Structures Algorithms 9 1 14. Z. · Zbl 0856.68070
[2] ALONSO, L., REINGOLD, E. R. and SCHOTT, R. 1993. Determining the majority. Inform. Process. Lett. 47 253 255. Z. · Zbl 0780.68051
[3] ALONSO, L., REINGOLD, E. R. and SCHOTT, R. 1994. The average-case complexity of determining the majority. SIAM J. Comput. To appear. Z. · Zbl 0868.68066
[4] ANDREWS, G. E. 1976. The theory of partitions. In Ency clopedia of Mathematics 2. AddisonWesley, London. Z. · Zbl 0371.10001
[5] BERTSEKAS, D. P. 1987. Dy namic Programming: Deterministic and Stochastic Models. PrenticeHall, Englewood Cliffs, NJ. Z.
[6] BOLLOBAS, B. 1985. Random Graphs. Academic Press, London. Z.
[7] CHASSAING, P. 1993. Optimality of move-to-front for self-organizing data structures with locality of references. Ann. Appl. Probab. 3 1219 1240. Z. · Zbl 0799.68052
[8] CUNTO, W. and MUNRO, J. I. 1984. Average case selection. In Proceedings of the 16th Annual ACM Sy mposium on Theory of Computing 369 375. · Zbl 0674.68030
[9] HAKIMI, S. L. and SCHMEICHEL, E. F. 1984. An adaptive algorithm for sy stem level diagnosis. J. Algorithms 5 526 530.Z. · Zbl 0555.94020
[10] HARDY, G. H. and RAMANUJAN, S. 1918. Asy mptotic formulae in combinatory analysis. In Z. Collected Papers of S. Ramanujan 276 309. Chelsea, New York 1962. Z. · JFM 46.0198.02
[11] KNUTH, D. E. 1973. The Art of Computer Programming 3: Sorting and Searching. AddisonWesley, Reading, MA. Z. · Zbl 1178.68372
[12] PREPARATA, F., METZE, G. and CHIEN, R. T. 1967. On the connection assignment problem of diagnosable sy stems. IEEE Trans. Comput. 16 848 854. Z. · Zbl 0189.16904
[13] SAKS, M. R. and WERMAN, M. 1991. On computing the majority by comparisons. Combinatorica 11 383 387. Z. · Zbl 0739.05006
[14] SCHMEICHEL, E., HAKIMI, S. L., OTSUKA, M. and SULLIVAN, G. 1990. A parallel fault identification algorithm. J. Algorithms 11 231 241. · Zbl 0705.68021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.