An upper bound on the weight-balanced testing procedure with multiple testers

This paper presents the performance of the Weight-Balanced Testing (WBT) algorithm with multiple testers. The WBT algorithm aims to minimize the expected number of (round of) tests and has been proposed for coding, memory storage, search and testing applications. It often provides reasonable results if used with a single tester. Yet, the performance of the WBT algorithm with multiple testers and particularly its upper bound have not been previously analyzed, despite the large body of literature that exists on the WBT algorithm, and the recent papers that suggest its use in various testing applications. Here we demonstrate that WBT algorithm with multiple testers is far from being the optimal search procedure. The main result of this paper is the generalization of the upper bound on the expected number of tests previously obtained for a single-tester WBT algorithm. For this purpose, we first draw an analogy between the WBT algorithm and alphabetic codes; both being represented by the same Q-ary search tree. The upper bound is then obtained on the expected path length of a Q-ary tree, which is constructed by the WBT algorithm. Applications to the field of testing and some numerical examples are presented for illustrative purposes.
1. Introduction In this paper we analyze the Weight-Balanced Testing (WBT) algorithm with multiple testers. We start by exemplifying the sequential search problem as presented in Ahlswede and Wegner (1987) [...]