1
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ I'm still confused about what you mean by "identify". Given $s$ numbers (that we both already know, and presumably for which we already both know the order relation), the number of bits that are needed to identify the minimum is zero, isn't it? $\endgroup$
    – Neal Young
    Nov 15, 2022 at 23:27
  • 2
    $\begingroup$ Maybe you mean the following game? You choose a prefix-free set of $n$ binary codewords. I then choose a subset of $s$ of those codewords. You pay me the length of the smallest codeword among those $s$. (Your goal is to minimize the payment, mine is to maximize it.) If that's what you mean, your optimal solution is a prefix-free set of codewords that minimizes the length of the $s$th largest codeword. I think the answer for that is easy to determine. (I think it is exactly $\lceil \log_2 (n-s+1)\rceil$.) $\endgroup$
    – Neal Young
    Nov 16, 2022 at 2:04
  • 1
    $\begingroup$ I think it would be helpful to have a precise (perhaps combinatorial?) definition of the quantity you are asking about. You say "that's essentially the right interpretation", but per your comment it's not right, and I'm not sure how you would amend it to make it correct. $\endgroup$
    – Neal Young
    Nov 16, 2022 at 13:33
  • 1
    $\begingroup$ I'm confused. Assuming the second player knows $f$, the game as described is trivial. The first player loses iff $S\subseteq [n] \setminus f([k])$, so the first player should choose any $f$ such that $|f([k])\cap [n]| = k$, and then the second player has a winning strategy iff $s \le n - k$. That is, the first player wins iff $k \ge n - s + 1$. So $W(n, s) = n - s + 1$. Am I misunderstanding the game? Also, what does this have to do with "information required to identify..." anything? $\endgroup$
    – Neal Young
    Nov 16, 2022 at 21:01
  • 1
    $\begingroup$ The question is ambiguous. If we take the question of the title ("How much information does it take ...") you get a different answer the log of $W$ as specified in your third paragraph. (See my answer.) Which question do you want to know the answer to? $\endgroup$ Nov 17, 2022 at 22:50

2 Answers 2

4
$\begingroup$

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$

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Peter, can you clarify something I'm confused about? Namely, what exactly does it mean to "specify a number chosen from a subset of two of them"? There must be some underlying assumptions about how the subset and number are chosen, and what the people who are sending and receiving the communication know. But I don't see this made explicit anywhere, so the question seems ambiguous. Do you have a particular interpretation? $\endgroup$
    – Neal Young
    Nov 17, 2022 at 23:19
  • $\begingroup$ @Neal: Here's my interpretation. We're playing a game. There are three numbers, $\{1, 2, 3\}$. The referee gives me a subset of two of them (which we might as well assume is random). I then send you a message, and you send the referee one of the three numbers. We win if the number you send is one of the two numbers I received. The question is: how much information must I transmit (on average) so that we win every time. $\endgroup$ Nov 18, 2022 at 0:17
  • $\begingroup$ Okay so for you a strategy is a function $f$ from $\{S\subseteq [n] : |S| =s\}$ to $[n]$ such that $f(S)\in S$ for all inputs $S$, and the goal is to minimize the entropy of the r.v. $f(S)$ where $S$ is an input selected uniformly at random? For $s=2$ surely one can show this has value $\sum_{i=1}^{n-1} (i/{n\choose 2}) \ln ({n\choose 2}/{i})$, as attained by taking, say, $f(S) = \min S$? For any other (non-isomorphic) strategy there is a local improvement that can be made, because of the concavity of the entropy function (I think ?). $\endgroup$
    – Neal Young
    Nov 18, 2022 at 3:10
  • 1
    $\begingroup$ @NealYoung: That's right. It seems to me like this is a reasonable interpretation of the question in the title. And I'm pretty sure your proof works. $\endgroup$ Nov 18, 2022 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.