A Fun Application of the Probabilistic Method

April 12, 2025

2025-04-14 Update Part 2: I have been able to improve the constant to $3 \log_2 n / \log_2 (27/23) \approx 12.97$ from the previous $~15.57$.

2025-04-14 Update: There was an error in my previous writeup. It has been fixed in the version below. Kyle also shared with me that this problem is an example of non-adaptive group testing, a well-studied subject. I also improved the constant from $4\log_2 n / \log_2(8/7) \approx 20.76$ to $3\log_2 n / \log_2(8/7) \approx 15.57$, by improving the second union bound

Background

After sharing with Kyle (my advisor) that I had looked at a few leetcode questions for fun, he mentioned he always loved going to interview during the end of his Ph.D. because they had fun questions. He shared with me the following:

Poisoned Bottle Problem

Suppose there are $n$ bottles, 1 of which is poisoned. You have to do a single round of testing to find out which bottle is poisoned. That is, you must send $l$ people to go test various bottles. Each person can drink from as many bottles as you wish, and if they drink from the poisoned bottle, no matter how little, they will die in 10 minutes.

The question is: what is the minimal number $l$ of testers required to locate the poisoned bottle?

The answer is: $l = \lceil \log_2 n \rceil$. It is done as follows: put the bottles in order, and number them sequentially: $0, 1, 2, \ldots$. Now, for person $k,$ $k = 1, 2, \ldots, \lceil \log_2 n \rceil$, they will drink from bottle $l$ if it contains a $1$ in the $k$-th digit of its binary expansion.

Then, each subset of people who die corresponds exactly to which bottle was poisoned. If, say, person 1 and 3 die, then you know that bottle number $101_2 = 5$ was poisoned.

Notice that this solution is optimal. That is, you would need a surjective map from $\{0,1\}^l \to \{1, 2, \ldots, n\}$. That is, $2^l \geq n$, so that $l \geq \log_2 (n)$.

$d$-Poisoned Bottle Problem

The above problem was pretty straightforward. Here’s a fun extension: suppose that $2$ of the bottles are poisoned (or more generally, $d$ bottles). What is the minimal number of people required to detect which bottle was poisoned?

It wasn’t immediately obvious how to tackle this problem. At first, I thought about breaking the group down iteratively into groups of 3, using 2 people to test each block:

But this doesn’t work for the problem, as you would have to subsequently test all 3 blocks (because you have to do only a single round of testing).

Then, tinkering around at the board for a second, I realized that a random configuration should work well. With this thought, I moved forward with the probabilistic method.

Probabilistic Method

Recall that the probabilistic method comes from the following situation. You want to find out that an object $X$ with property $Y$ exists. If you can pick a random such object and show that $$ \mathbb{P}(X \text{ has property } Y) > 0, $$ then you know such an $X$ exists. So to this end, let $\xi_i \in \{0,1\}^n$ be (random) testers. That is, $\xi_i$ drinks from bottle $j$ if $(\xi_i)_j=1$. Then we have that $$\mathbb{P}((\xi_i, i = 1, 2, \ldots, l) \text{ can detect every pair of bottles})$$ $$= 1 - \mathbb{P}(\exists \text{ a poisoned pair s.t. } (\xi_i) \text{ cannot correctly detect})$$ $$\geq 1 - \binom{n}{2}\mathbb{P}((\xi_i) \text{ cannot detect when } (1,2) \text{ is the poisoned pair} ).$$

However, we can think of $(\xi_i)$ detecting the poisoned pair as being able to correctly conclude that every pair $(i,j) \neq (1,2)$ is not the poisoned pair. Notice that for any $(i,j) \neq (1,2)$, we may assume by a union bound that $i = 3$. $$\mathbb{P}((\xi_i) \text{ cannot detect when } (1,2) \text{ is the poisoned pair} ).$$ $$\leq n \mathbb{P}_{(1,2)}((\xi_i) \text{ cannot declare that } (3,j) \text{ is not poisoned} )$$

Notice that if there exists a tester which tests bottle $3$, but not bottles $1$ or $2$, this tester will live, and we can conclude that the poisoned pair does not contain a 3. Therefore, we have: $$\mathbb{P}_{(1,2)}((\xi_i) \text{ cannot declare that } (3,j) \text{ is not poisoned} )$$ $$\mathbb{P}_{(1,2)}(\forall i, (\xi_i)|_3 \neq (0,0,1)) = \left(\frac{23}{27}\right)^{l},$$ where we now choose the $\xi_i$ to be Bernoulli$(1/3)$, in order to minimize the probability being exponentiated by $l$.

Putting this all together, we have: $$\mathbb{P}((\xi_i, i = 1, 2, \ldots, l) \text{ can detect every pair of bottles})$$ $$\geq 1 - n^3 \left( \frac{23}{27} \right)^l > 0$$ whenever $l > \frac{3 \log_2 n}{\log_2 27/23}$. This solution is optimal up to the $3 / \log_2 27/23$, as there needs to be a unique mapping from every pair of bottles to the subsets of $\{1, 2, \ldots, l\}$. That is, $\binom{n}{2} \leq 2^{l}$, so that $l \geq \log_2 \binom{n}{2} \sim 2 \log_2 n$.

Algorithms

While this result doesn’t give you a deterministic algorithm, it does imply, for instance, that if you take $13\log_2 n$ random testers, you expect with high probability $(1 - o(1))$ that you will be able to deduce any pair of poisoned bottles. While you can use the above method to get a result for any $d$ which is logarithmic in $n$, we don’t necessarily expect this solution to be optimal in asymptotics in $d$, given the information-theoretic lower bound.

Conclusion

This was a fun use of the probabilistic method to determine an upper bound on how many testers you need to solve the $2$-poisoned bottle problem. A similar approach can be used to get a bound for the $d$-poisoned bottle problem.