On Adaptive Tree Polling Algorithms

This paper proposes three different algorithms for polling a finite set of users to determine the binary state of each user. The states are assumed to be described by i.i.d. Bernoulli random variables with parameter . The algorithms differ in the responses offered by the users to queries and how the responses from several users are combined by the channel to produce a composite feedback signal which is received by all users. For each algorithm, the average number of transmissions required to determine the states of all users is determined as a function of the parameter .