Глава 4. Поиск больных (метод Дорфмана)

Забудь про умозрительные примеры с кубиками. Сейчас будет суровый жизненный расклад.

Представь: Вторая мировая, призывной пункт США. Нужно проверить $n = 1000$ призывников на сифилис (реакция Вассермана). Каждый тест стоит денег, лаборатория зашивается. Если тестировать каждого «в лоб» — уйдёт ровно $1000$ пробирок и тестов.

В 1943 году экономист Роберт Дорфман придумал тему: зачем проверять каждого отдельного пацана, если можно сливать пробы в один котёл?

Схема развода лаборатории (суть метода)

Берём всех $n$ призывников и разбиваем на пачки по $k$ человек в каждой.

1. Берём капельку крови у каждого из $k$ человек, сливаем в одну общую пробирку и делаем 1 тест.
2. Вариант А (вся пачка чистая): тест отрицательный. Одной проверкой оправдали сразу $k$ человек.
3. Вариант Б (кто-то залетел): тест положительный (в смеси есть хотя бы один больной). Найти виновного «вслепую» нельзя — берём индивидуальные пробы у всех $k$ из пачки и делаем ещё $k$ тестов. Итого на эту пачку: $1 + k$ тестов.

   [Пачка из k человек]
            │
     (1 общий тест)
      ╱          ╲
 [Чисто]        [Есть больной]
 (0 доп.)       (k доп. тестов)
    │                 │
 Всего: 1          Всего: k + 1

Где подвох? Если болезнь редкая ($p$ маленькое), большинство пачек будут полностью здоровыми и проскочат за $1$ тест.

Разбираем формулу по кирпичикам

Пусть $p$ — вероятность, что случайный призывник болен. Тогда $1 - p$ — что он здоров.

Результаты независимы (схема Бернулли из главы 3). Вероятность, что вся пачка из $k$ человек здорова:

Вводим случайную величину $X_j$ — число проверок для $j$-й группы:

Матожидание затрат на одну группу $\mathbf{M}X_j$

Формула матожидания из главы 2 (значение × вероятность):

Раскрываем скобки:

Общее число тестов $\mathbf{M}Z$

Групп примерно $n/k$. Общее число проверок $Z = X_1 + \dots + X_{n/k}$. По линейности матожидания:

Удельные затраты (доля от $n$ «лобовых» тестов):

Если $H(k) = 0{,}2$ — потратим 20% от первоначального числа тестов (экономия примерно в 5 раз).

Пощупай руками (симуляция Монте-Карло)

Проверим теорию в коде: $n = 1000$, $p = 0{,}01$ (1% больных), $k = 10$.

Оптимизация: какую группу $k$ выбрать?

Если $k$ слишком большой (например $k = 100$ при $p = 0{,}01$), то с вероятностью $1 - (1-0{,}01)^{100} \approx 63\%$ в группе окажется больной — почти всегда доплатим ещё $100$ тестов.

Если $k$ слишком маленький ($k = 2$), теряем выгоду от группировки.

При малых $p$ оптимальный размер приближённо:

При $p = 0{,}01$: $k_{\text{опт}} \approx 1/\sqrt{0{,}01} = 10$, и затраты около $20\%$ от «лобового» плана.

Покрути график удельных затрат $H(x) = 1 + 1/x - (1-p)^x$ при $p = 0{,}01$ (то есть $0{,}99^x$). Минимум около $x = 10$, линия $y = 1$ — уровень «тестируем всех в лоб».

Проверь себя