Хитрое тестирование

Немного тервера. Предположим, Вам надо протестировать воду нескольких водоёмов на чистоту, точнее, отсутствие в ней определённого редкого химиката (вероятность  p того, что он «загрязнит» водоём мала). У Вас есть супер-тест, который по пробе воды определяет в ней наличие химиката (со 100%-й точностью). Вы взяли пробы воды из N водоёмов и должны точно указать, в каких водоёмах он есть.

Первый способ решения (примитивный). Последовательно протестировать N проб (из всех водоёмов). Так Вы гарантированно найдёте все загрязнённые.

Второй способ — попытаться сократить число тестов. Если вероятность загрязнения p очень мала, то есть шанс, что все водоёмы чистые. Давайте сделаем одну общую пробу воды (сольём по чуть-чуть из каждой пробы) и протестируем её. С вероятностью

мы ничего не обнаружим, иначе придётся всё-таки последовательно тестировать все пробы (или сделать умнее, см. дальше).

Итак, ожидаемое число тестов во втором способе

Попробуем оценить, когда выгоден второй способ (это число меньше N).

Интуитивно ясно, что если химикат очень-очень редкий (вероятность p совсем маленькая), то второй способ явно лучше, т.к. он сводится просто к тому, чтобы убедиться, что все водоёмы чистые. Поэтому должна получиться какая-то оценка на p.

Единица на N в степени единица на N это страшно, поэтому, чтобы избежать громоздких выражений часто приближённо оценивают так

С такой оценкой, конечно, проще работать, но всё-таки надо понимать, к чему приводят такие оценки — см. рис.

Функции разных оценок.

Даже когда число водоёмов переваливает за сотню, оценки могут различаться на порядок! Так что, осторожнее с приближениями… А вот если Вы вторую оценку замените на 1/N, то разницы от изменения Вы не почувствуете (скажем, 0.01 или 0.0099).

Что делать, когда химикат не очень редкий? Тогда высока вероятность, что первый тест будет положительным, а следовательно, лишним. Всё равно можно попытаться сократить число тестов, разбив водоёмы на группы и сделав общие пробы всех групп. Если группа «чистая», то не надо отдельно тестировать её представителей. Кстати, этот метод был реально предложен Р.Дорфманом при тестировании на сифилис военнослужащих США и позволил сократить число тестов в пять раз! Можете это доказать, заодно определить оптимальный размер групп (такая задача есть во многих учебниках по ТВ).

В книге М.Б. Лагутина говорится про выигрыш в 5 раз (это доказывается прямым подсчётом), в двухтомнике В. Феллера (с. 254) говорится про экономию на 80% (возможно, Р.Дорфман выбрал неоптимальные размеры групп). В различных научных статьях методика была улучшена (введением большего числа этапов — разбиений на группы).

В анализе данных я столкнулся с тестированием, которое можно изложить в такой интерпретации (без вероятностей). Пусть у нас вода в водоёмах или абсолютно грязная или абсолютно чистая. Когда мы организуем объединённую пробу из нескольких водоёмов, то из каждого мы можем брать воду в одном объёме, скажем 1л, а тест говорит нам сколько литров грязной воды в пробе. Например, тестируем воду семи водоёмов, тест показал «2 литра», значит 2 из 7 грязные (какие именно — пока неизвестно). Вопрос: как организовать тестирование, чтобы делать поменьше тестов?

Интересно, что в худшем случае надо всё-таки сделать N тестов для N водоёмов, но вдруг повезёт… скажем, если для группы из 4х водоёмов тест показал 4л., то они все грязные, 0л. — они все чистые. Если 1л. или 3л. — то ровно один чистый/грязный и за логарифм от N тестов (ещё 2 теста) он находится. Хуже всего, когда 2л. — есть шанс сделать 4 теста для этих 4х водоёмов.

Самое забавное, что на практике число тестов в несколько раз меньше N (при N ~ 300), а сами тесты можно делать чуть ли не по случайным подгруппам водоёмов (главное — правильно обрабатывать результаты, см. рис). Если кто-то знает здесь оптимальную стратегию — пишите.