**Informal description:** You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few tests as possible (on average). Each test is applied to a subset $S$ (of your choice) of the samples and returns positive if at least one of the samples is infected ($P \cap S \neq \varnothing$). What's the optimal way to choose the subsets to test to determine $P$ as efficiently as possible?

**Formal description:**

Let $n\in\mathbb{N}$. A **test protocol** $\mathscr{T}$ for subsets of $\{1,\ldots,n\}$ is a finite binary tree in which each non-leaf node $x$ is labeled by a subset $S_x$ of $\{1,\ldots,n\}$ and the two edges descending from the node $x$ are labeled “positive” and “negative”. For a test protocol $\mathscr{T}$ and a subset $P \subseteq \{1,\ldots,n\}$, we define a branch $\mathscr{B}_P = (x_0,\ldots,x_r)$ in the tree (= path from the root $x_0$ to a leaf $x_r$) as follows: $x_0$ is the root and, so long as $x_i$ is not a leaf, we let $x_{i+1}$ be the node attained by following the edge $(x_i, x_{i+1})$ labeled “positive” resp. “negative” according as $P \cap S_{x_i} \neq \varnothing$ resp. $P \cap S_{x_i} = \varnothing$. (In other words, the test tells us to test $S_{x_0}$ where $x_0$ is the root of $\mathscr{T}$, then test $S_{x_1}$ where $x_1$ is the node reached from $x_0$ by following the positive or negative branch according as $P \cap S_{x_0}$ is inhabited or empty, and so on until we reach a leaf $x_r$.) Calling $x_P$ the leaf (previously denoted $x_r$) where the branch $\mathscr{B}_P$ associated to $P$ terminates, we say that the test protocol $\mathscr{T}$ is **decisive** when $P \mapsto x_P$ is a bijection between subsets of $\{1,\ldots,n\}$ and leaves of $\mathscr{T}$, i.e., $P \mapsto \mathscr{B}_P$ is a bijection between subsets of $\{1,\ldots,n\}$ and branches of $\mathscr{T}$. The length $r$ of the branch $\mathscr{B}_P$ is then called the **testing length** $\ell(P)$ of the subset $P$ for the decisive protocol $\mathscr{T}$.

Now let $0<p<1$ be given: what is $\ell_{\mathrm{min}}$ (in function of $n$ and $p$) the smallest possible expected value $\sum_{P\subseteq\{1,\ldots,n\}} p^{\#P}\,(1-p)^{(n-\#P)}\,\ell(P)$, for a decisive protocol $\mathscr{T}$, of the testing length $\ell(P)$ of a subset $P$ that is drawn by choosing whether $i \in P$ using a Bernoulli distribution with probability $p$ independently for each $i$?

**Examples:**

The simplest decisive test protocol consists of testing each sample on its own, i.e., create a balanced binary tree with depth $n$ and $S_{x_i} = \{i+1\}$ for $x_i$ a node at depth $i$. This has $\ell(P) = n$ for every subset $P$ and provides a trivial upper bound on $\ell_{\mathrm{min}}$.

If $p$ is very small, we can create a test protocol which starts by testing whether any sample is infected, i.e., $S_{x_0} = \{1,\ldots,n\}$, so the negative branch can conclude immediately that $P = \varnothing$, whereas in the positive branch we use, say, the trivial test described above (pruning the cases where $n-1$ samples have tested negative and we know there is a positive). This provides an upper bound of $(1-p)^n + (n+1)(1-(1-p)^n) = 1 + n(1-(1-p)^n)$ on $\ell_{\mathrm{min}}$.

A *lower* bound on $\ell_{\mathrm{min}}$ comes from information theory: the subset $P$ has $n(-p\,\log_2 p - (1-p)\,\log_2(1-p))$ bits of information, so $\ell_{\mathrm{min}}$ must be at least this value. (But clearly this lower bound is not optimal since when $p\to 0$ this tends to $0$ whereas we can't do less than $1$ test.)

However, when $p=\frac{1}{2}$, the lower bound just given coincides with the trivial upper bound of $n$, so $\ell_{\mathrm{min}} = n$.