量化的群試

Abstract

摘要

群試包含了從具有n個物品的集合N中找出最多d的瑕疵品的研究。在傳統的群試問題中，我們要調查所有可能包含於集合N裡的非空集合S。從形式上來看，我們用Q(S) = 1來表示集合S內至少包含了一個瑕疵品(但是我們不知道是哪個)；假如集合S內並未包含任何瑕疵品，那麼Q(S) = 0。如果我們可以在每一次的測試中得知本次測試的物品裡瑕疵品的數量，那麼我們用Q(S) = t來表示集合S中具有t件瑕疵品。為了方便起見，這類的群試被稱作量化群試。我們在本論文研究的正是這種類型的測試問題。 根據在眾多領域的實際運用，S集合的大小有其樣本數量的限制。舉例來說，Dorfman曾經在1943年提出關於血液測試的問題，我們每次大約從數百甚至數千個樣本中抽出10個來進行測試。這也激發了我們去研究測試具有偵測數量限制(the pool size in bounded)時所造成的影響。 這個研究的主要目的是確認從件物品中找到d件瑕疵品所耗費的猜測次數〈使用有關猜法檢測〉。因此，我們首先要做的就是提供一個會隨著n與d的數值改變的上界〈在最糟糕的情況下所耗費的猜測數量〉，然後我們也會探討使用有關猜法所耗費的猜測次數之「平均值」。

Abstract Group testing involves identifying at most d defective items out of a set N of n items. In classical group testing problems, queries on all possible non-empty subsets S of N are used. Formally for the pool S, we use Q(S) = 1 to denote that there exists at least one defective in S ( but we don’t know which ones ) and Q(S) = 0 otherwise. If we are able to determine the number of t positives in a test, then Q(S) = t is used to denote the outcome. For convenience, this type of group testing is referred to as a group testing with quantitative outcome. This is the kind of testing we study in this thesis. Based on pratical applications in many fields, the size of S has its limitation comparing to the number of items. For example, in blood testing problem proposed by Dorfman (1943), we test around 10 items each time for hundreds and thousands to be tested. This also motivates us to study the effect when the pool size in bounded. The main focus of the study is to determine the number of tests ( adaptive algorithm ) we need in identifying d positives out of a set of n items. So, we first provide an upper bound of this number in worst case for various n and d, and then we also study the average number of tests we need in an adaptive algorithm.