How much information does it take to specify, not each member of a group, but any one member?

Question

It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ numbers. Suppose instead we wished to specify not all $s$ numbers, but merely any one of them. How much information would this take?

Let's formalize this as a two-player game $\mathcal{G}(n,s,k).$ The first player chooses a function $f$ and shows it. The second player chooses a subset $S\subset\{1,2,\ldots,n\}$ with $s$ elements and shows it. The first player chooses a number $m\in\{1,2,\ldots,k\}$. If $f(m)\in S$, the first player wins

Define $W(n,s)$ as the smallest $k$ such that the first player has a winning strategy. What is $W(n,s)$, that is, how much information is needed to specify at least one of the $s$ elements? Note that $W(n,1)=n$ and $W(n,s)=W(n,n-s).$

A trivial upper bound is $W(n,s) \le n-s+1$, by noting that least one of the first $n-s+1$ numbers must be among the $s$.

For a lower bound, you could break the $n$ numbers into groups of $s$ and note that the second player could choose $S$ as any of the $\lfloor n/s\rfloor$ groups and hence $W(n,s) \ge \lfloor n/s\rfloor$ if the first player is to distinguish between them.

Answer 1

This answer continues Peter's. It assumes Peter's interpretation of the problem and verifies that with that interpretation the function $f(S)=\min S$ is optimal, as Peter suggested. Here's the problem statement:

Fix integers $s\ge 1$ and $n\ge s$. Let $\mathcal S_s = \{S\subseteq [n] : |S| = s\}$ contain the size-$s$ subsets of $[n]$. The goal is to determine the minimum, over all functions $f:\mathcal S_s\to[n]$ such that $f(S)\in S$ for all $S\in\mathcal S_s$, of the entropy of the distribution of the random variable $f(S)$ where $S$ is drawn uniformly at random from $\mathcal S_s$.

Before we begin, here's a formula for the entropy for an arbitrary $f$. For $i\in [n]$ let $f^{-1}(i) = \{S\in \mathcal S_s : f(S) = i\}$ contain the sets that $f$ maps to $i$. For the random choice of $S$ described above, for each $i$, the entropy of $f(S)$ is $$\begin{align} {} \sum_{i=1}^n -\Pr[f(S) = i] \ln \Pr[f(S) = i] & {} =\sum_{i=1}^n -\frac{|f^{-1}(i)|}{n\choose s} \ln \frac{|f^{-1}(i)|}{n\choose s} \\ & {} =\ln {n\choose s} - {n\choose s}^{-1}\sum_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|.~~~~~~(1) \end{align} $$

Note that for the particular function $\hat f(S) = \min S$ we have $|\hat f^{-1}(i)| = {n-i\choose s-1}$ so for this $\hat f$ the entropy in question is $$ \sum_{j=s-1}^{n-1} \frac{j\choose s-1}{n\choose s} \ln \frac{n\choose s}{j\choose s-1} = \ln {n\choose s} - {n\choose s}^{-1}\sum_{j=s}^{n-1} {j\choose s-1}\ln {j\choose s-1}.$$

For example, when $s=2$, the entropy is $\ln {n\choose 2} - {n\choose 2}^{-1}\displaystyle\sum_{j=2}^{n-1} j \ln j = \ln(n/2)+1/2 \pm o(1)$.

When $s=2$ and $n=3$, the entropy is $\ln 3 - (2/3)\ln 2 = H(1/3)$.

Lemma 1. The function $\hat f(S) = \min S$ is optimal.

Proof.

1. Let $f$ be any optimal function.

2. By symmetry assume without loss of generality that $|f^{-1}(1)| \ge |f^{-1}(2)| \ge \cdots \ge |f^{-1}(n)|$.

3. Assume for contradiction that $f\not\equiv \hat f$.

4. Fix an $S'\in \mathcal S_s$ such that $f(S') \ne \min S'$.

5. Let $m = \min S'$ and $p=f(S')$. Because $p\in S'\setminus\{m\}$ we have $p > m$.

6. Let $a = |f^{-1}(m)|$ and $b=|f^{-1}(p)|\ge 1$. By Steps 2 and 5 we have $a \ge b \ge 1$.

7. Consider modifying $f$ by changing $f(S')$ to $i$.

8. This changes $\sum_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|$ by an additive $$[a \ln a + b\ln b] - [(a+1)\ln(a+1) + (b-1)\ln (b-1)].$$

9. Because $x \mapsto x\ln x$ is strictly convex and $a\ge b$, this change is strictly positive.

10. So, by Equation (1) before the lemma, this change decreases the entropy.

11. This contradicts the optimality of $f$. $~~~~~\Box$

Answer 2

This is a request for clarification and a partial answer, but I'm posting it as an answer because there is no way for it to fit in a comment.

Is the OP asking for how much information you need to send, or the smallest number of possibilities that you need to use in order to answer? These are two distinct questions. His definition of $W$ would point to the second question, but the title of his question points to the first,

Suppose you have three numbers, and we want to specify a number chosen from a subset of two of them. How much information do we need?

Let's use the following strategy: the two players choose a random seed, and generate a pseudorandom permutation of the three numbers each time. The second player sends the first player "$1$" if the first element of the permutation is in the subset, and "$2$" otherwise.

The player is then sending "$1$" two-thirds of the time, and "$2$" one-third of the time. The amount of information needed for this is $$H\left(\frac{1}{3}\right) = -\frac{1}{3} \log_2 \frac{1}{3} -\frac{2}{3} \log_2 \frac{2}{3} = .9183 \mathrm{\ bits},$$ which is less than the log of the number $W$ of distinct responses you need to send (namely $1 = \log_2 2$).

I believe this is the optimal strategy for accomplishing this task, although since I don't have a proof, I might easily be wrong.

This strategy is generalizable to a subset of $k$ chosen from a set of $n$, although it may take some work to give a nice formula for how much information is needed.