Graph-Theoretic Generalization of the Best-Choice Problem: Randomized Analysis of a Simple Effective Algorithm for k-ary Trees

Description

We consider the following on-line decision problem. The vertices of a graph which is a complete rooted directed k-ary tree are being observed one by one in some random order by a selector. At time t the selector examines the t-th vertex and knows the graph induced by the t vertices that have already been examined. The selector's aim is to choose the root by taking the currently examined vertex. We propose and analyze a simple deterministic algorithm for the selector to follow. Using randomized techniques it is shown that its probability of the right choice tends to 1 as k tends to infinity. A multiple randomization is introduced and applied to find the asymptotic probability of success of this algorithm. It is shown that for the binary tree this asymptotic probability is equal to 2 ln(2)-1 with the height of the tree tending to infinity.