Abstract-Vi studerar grupp testning av en uppsättning N objekt som var och en är defekt med sannolikhet p. Vi fokuserar på den dubbla gränsen för små defekt sannolikhet, p 1, och stort antal variabler, N 1, tar antingen p! 0 efter N! 1 eller p = 1=N med 2 (0; 1=2). I båda inställningarna är det optimala antalet provningar som krävs för att med säkerhet identifiera de defekta genom ett tvåstegsförfarande, T(N;p), känt för att skala som Npj log pj. Här bestämmer vi det skarpa asymptotiska värdet av T(N;p)=(Npj log pj) och konstruerar en klass av tvåstegsalgoritmer över vilka detta optimala värde uppnås. Detta görs genom att välja en korrekt bipartit regelbunden graf (av tester och variabla noder) för det första stadiet av upptäckten. Dessutom bevisar vi att detta optimala värde också uppnås i genomsnitt över en slumpmässig bipartitkurva där alla variabler har samma grad och de tester som är kopplade till en given variabel väljs slumpmässigt med enhetlig fördelning mellan alla tester. Slutligen förbättrar vi de befintliga övre och nedre gränserna för det optimala antalet tester i fallet p = 1 = N med 2 [1=2; 1).
En bipartitgrafstruktur beaktas i REF med en hybriddetektionsmetod i två steg.
Group Testing With Random Pools: Optimal Two-Stage Algorithms
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}