miniaturadeimagen|400x400px|Ilustración del problema de la bombilla: se busca una bombilla rota entre seis bombillas. En este caso, las tres primeras están conectadas a una fuente de alimentación y se encienden (A). Esto indica que la bombilla rota debe ser una de las tres últimas (B). Si, por el contrario, las bombillas no se encendieran, se podría estar seguro de que la bombilla rota estaba entre las tres primeras. Continuando con este procedimiento, se puede localizar la bombilla rota en un máximo de tres pruebas, en comparación con un máximo de seis si se revisan las bombillas individualmente. En estadística y matemáticas combinatorias, las pruebas de grupo son procedimientos que dividen la tarea de identificar determinados objetos en pruebas sobre grupos de elementos, en lugar de sobre elementos individuales. Estudiada por primera vez por Robert Dorfman en 1943, la comprobación de grupos es un campo relativamente nuevo de la matemática aplicada que puede aplicarse a un amplio abanico de aplicaciones prácticas y es un área activa de investigación en la actualidad.
Un ejemplo conocido de prueba de grupos es el de una serie de bombillas conectadas en serie de las que se sabe que una está rota. El objetivo es encontrar la bombilla estropeada con el menor número posible de pruebas (donde una prueba es cuando alguna de las bombillas está conectada a una fuente de alimentación). Un método sencillo consiste en probar cada bombilla por separado. Sin embargo, cuando hay un gran número de bombillas, sería mucho más eficaz agruparlas. Por ejemplo, conectando la primera mitad de las bombillas a la vez, se puede determinar en qué mitad está la bombilla estropeada, descartando la mitad de las bombillas en una sola prueba.
Los esquemas para llevar a cabo las pruebas en grupo pueden ser simples o complejos y las pruebas implicadas en cada etapa pueden ser diferentes. Los esquemas en los que las pruebas de la etapa siguiente dependen de los resultados de las etapas anteriores se denominan procedimientos adaptativos, mientras que los esquemas diseñados para que todas las pruebas se conozcan de antemano se denominan procedimientos no adaptativos. La estructura del esquema de las pruebas implicadas en un procedimiento no adaptativo se conoce como diseño de agrupación.
Las pruebas de grupo tienen muchas aplicaciones, como la estadística, la biología, la informática, la medicina, la ingeniería y la ciberseguridad. El Proyecto Genoma Humano ha reavivado el interés moderno por estos esquemas de pruebas.Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, p. 574, Section 46: Pooling Designs,
Descripción básica y términos A diferencia de muchas áreas de las matemáticas, los orígenes de las pruebas de grupo se remontan a un único informeDorfman, Robert (Diciembre 1943), "The Detection of Defective Members of Large Populations", The Annals of Mathematical Statistics, 14 (4): 436–440, doi:10.1214/aoms/1177731363, JSTOR 2235930 escrito por una sola persona: Robert Dorfman.Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. . La motivación surgió durante la Segunda Guerra Mundial, cuando el Servicio de Salud Pública de Estados Unidos y el Servicio Selectivo se embarcaron en un proyecto a gran escala para eliminar a todos los hombres sifilíticos llamados a filas. La prueba de la sífilis consiste en extraer una muestra de sangre y analizarla para determinar la presencia o ausencia de sífilis. En aquella época, la realización de esta prueba era cara, y analizar a cada soldado individualmente habría sido muy costoso e ineficaz.
Suponiendo que haya 𝑛 soldados, este método de análisis conduce a 𝑛 pruebas separadas. Si una gran proporción de personas están infectadas, este método sería razonable. Sin embargo, en el caso más probable de que sólo una proporción muy pequeña de los hombres estén infectados, se puede lograr un esquema de pruebas mucho más eficaz. La viabilidad de un plan de pruebas más eficaz depende de la siguiente propiedad: los soldados pueden agruparse y en cada grupo se pueden combinar las muestras de sangre. La muestra combinada puede analizarse para comprobar si al menos un soldado del grupo tiene sífilis. Esta es la idea central de las pruebas en grupo. Si uno o más de los soldados de este grupo tiene sífilis, se desperdicia una prueba (hay que realizar más pruebas para averiguar de qué soldado o soldados se trata). Por otro lado, si nadie del grupo tiene sífilis, entonces se ahorran muchas pruebas, ya que todos los soldados de ese grupo pueden ser eliminados con una sola prueba.
Los elementos que hacen que un grupo dé positivo se denominan generalmente elementos defectuosos (son las bombillas rotas, los hombres sifilíticos, etc.). A menudo, el número total de elementos se denota como 𝑛 y 𝑑 representa el número de defectuosos si se supone que es conocido.
Clasificación de los problemas de pruebas en grupo Existen dos clasificaciones independientes para los problemas de pruebas en grupo; cada problema de pruebas en grupo es adaptativo o no adaptativo, y probabilístico o combinatorio.
En los modelos probabilísticos, se supone que los elementos defectuosos siguen alguna distribución de probabilidad y el objetivo es minimizar el número esperado de pruebas necesarias para identificar la defectuosidad de cada elemento. En cambio, en las pruebas combinatorias de grupo, el objetivo es minimizar el número de pruebas necesarias en el peor de los casos, es decir, crear un algoritmo de minimización, y no se supone que se conozca la distribución de los elementos defectuosos.
La otra clasificación, la adaptabilidad, se refiere a la información que puede utilizarse para elegir los elementos que se agrupan en una prueba. En general, la elección de qué elementos probar puede depender de los resultados de pruebas anteriores, como en el problema de la bombilla anterior. Un algoritmo que realiza una prueba y luego utiliza el resultado (y todos los resultados anteriores) para decidir qué prueba realizar a continuación se denomina adaptativo. Por el contrario, en los algoritmos no adaptativos, todas las pruebas se deciden de antemano. Esta idea puede generalizarse a los algoritmos multietapa, en los que las pruebas se dividen en etapas, y cada prueba de la etapa siguiente debe decidirse de antemano, con sólo el conocimiento de los resultados de las pruebas de las etapas anteriores. Aunque los algoritmos adaptativos ofrecen mucha más libertad en el diseño, se sabe que los algoritmos adaptativos de pruebas en grupo no mejoran a los no adaptativos en más de un factor constante en el número de pruebas necesarias para identificar el conjunto de elementos defectuosos.Atia, George Kamal; Saligrama, Venkatesh (Marzo 2012). "Boolean compressed sensing and noisy group testing". IEEE Transactions on Information Theory. 58 (3): 1880–1901. arXiv:0907.1061. doi:10.1109/TIT.2011.2178156. S2CID 8946216. Además de esto, los métodos no adaptativos suelen ser útiles en la práctica porque se puede proceder con pruebas sucesivas sin analizar primero los resultados de todas las pruebas anteriores, lo que permite distribuir eficazmente el proceso de pruebas.
Variaciones y ampliaciones Hay muchas formas de ampliar el problema de las pruebas de grupo. Una de las más importantes se denomina pruebas en grupo ruidosas, y aborda un gran supuesto del problema original: que las pruebas no contienen errores. Un problema de pruebas en grupo se denomina ruidoso cuando existe alguna posibilidad de que el resultado de una prueba en grupo sea erróneo (por ejemplo, que salga positivo cuando la prueba no contenía ningún defecto). El modelo de ruido Bernoulli asume que esta probabilidad es una constante, 𝑞, pero en general puede depender del número real de defectuosos en la prueba y del número de elementos probados.Chun Lam Chan; Pak Hou Che; Jaggi, Sidharth; Saligrama, Venkatesh (1/09/2011). "Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms". 49th Annual Allerton Conference on Communication, Control, and Computing. pp. 1832–9. arXiv:1107.4540. doi:10.1109/Allerton.2011.6120391. . S2CID 8408114. Por ejemplo, el efecto de la dilución puede modelarse diciendo que un resultado positivo es más probable cuando hay más defectuosos (o más defectuosos como fracción del número probado), presentes en la prueba.Hung, M.; Swallow, William H. (Marzo 1999). "Robustness of Group Testing in the Estimation of Proportions". Biometrics. 55 (1): 231–7. doi:10.1111/j.0006-341X.1999.00231.x. PMID 11318160. S2CID 23389365. Un algoritmo ruidoso siempre tendrá una probabilidad distinta de cero de cometer un error (es decir, etiquetar mal un elemento).
Las pruebas de grupo pueden ampliarse considerando escenarios en los que hay más de dos resultados posibles de una prueba. Por ejemplo, una prueba puede tener los resultados y , correspondientes a que no haya ningún defectuoso, un único defectuoso o un número desconocido de defectuosos mayor que uno. En términos más generales, es posible considerar que el conjunto de resultados de una prueba es para algún
Otra extensión consiste en considerar restricciones geométricas sobre los conjuntos que pueden someterse a prueba. El problema de la bombilla es un ejemplo de este tipo de restricción: sólo se pueden probar las bombillas que aparecen consecutivamente. Del mismo modo, los elementos pueden disponerse en un círculo o, en general, en una red, donde las pruebas son caminos disponibles en el grafo. Otro tipo de restricción geométrica sería el número máximo de elementos que pueden probarse en un grupo,[a] o que el tamaño de los grupos sea par, etcétera. De forma similar, puede ser útil considerar la restricción de que un elemento determinado sólo pueda aparecer en un número determinado de pruebas.
Hay infinitas formas de seguir remezclando la fórmula básica de las pruebas de grupo. Las siguientes elaboraciones darán una idea de algunas de las variantes más exóticas. En el modelo "bueno-mediocre-malo", cada elemento es "bueno", "mediocre" o “malo”, y el resultado de una prueba es el tipo del "peor" elemento del grupo. En las pruebas de grupo con umbral, el resultado de una prueba es positivo si el número de elementos defectuosos del grupo es superior a algún valor umbral o proporción.Chen, Hong-Bin; Fu, Hung-Lin (Abril 2009). "Nonadaptive algorithms for threshold group testing". Discrete Applied Mathematics. 157 (7): 1581–1585. doi:10.1016/j.dam.2008.06.003 Las pruebas de grupo con inhibidores son una variante con aplicaciones en biología molecular. En este caso, existe una tercera clase de elementos denominados inhibidores, y el resultado de una prueba es positivo si contiene al menos un elemento defectuoso y ningún inhibidor.De Bonis, Annalisa (20 Julio 2007). "New combinatorial structures with applications to efficient group testing with inhibitors". Journal of Combinatorial Optimization. 15 (1): 77–94. doi:10.1007/s10878-007-9085-1. S2CID 207188798.
Historia y desarrollo
Invención y primeros avances