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 parameterp. 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 parameterp.