On the functional equation arising in a single user selection algorithm

The distributed single and/or multiple user selection problems are strongly related to that of partitioning a sample with binary-type questions. Although several algorithms have been proposed for user selection, the comprehensive view of designing the optimal algorithm has not been fully investigated yet. In this paper, we reformulated a splitting based selection algorithm by introducing a new parameter, called the "selection factor". Asymptotic analysis of the algorithm leads to a functional equation, similar to that encountered in the analysis of the collision resolution algorithms. Consequently, we see that there is an intimate relation between the splitting based selection algorithms and collision resolution algorithms. A surprisingly simple solution to the functional equation, which provides a helpful method for optimally designing the algorithm, is found. By jointly optimizing the algorithm's parameters, numerical results show that the performance can be improved.