We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all item-colour assignments where the total number of items in $S$ tinted with each colour $c\in C$ is equal to $\frac{n}{m}$ (assume that $n$ is a multiple of $m$).

We play a sequential game, where an item-colour assignment is (hiddenly) selected uniformly at random from $\mathcal{A}$ and at the beginning no information is known about the colour of any item. At each time step, we choose a pair $(i,c)$ where $i\in S$ and $c\in C$, and we receive the "binary information bit" representing whether $i$ is tinted with colour $c$ or not.

Question: How can we prove that, if we receive $\frac{nm}{8}$ such binary information bits, then there exists a constant $a>0$ such that in expectation it is not possible to find the colours of at least $(a\!\cdot\! n)$-many items in $S$?

  • $\begingroup$ Out of curiosity, what's the context for this question? $\endgroup$ – Pat Devlin May 10 '19 at 19:11
  • 1
    $\begingroup$ I am working on problems related to combinatorics and information theory, I would say the context of the problem here is the problem itself. $\endgroup$ – Penelope Benenati May 10 '19 at 21:55
  • $\begingroup$ The more I think on it, the trickier it sounds... I’d like to say (1) with high probability, nothing “weird” happens. (2) If nothing weird happens, then every question has low entropy unless you ask about an item that you’ve already asked at least k/10 questions about. But of course it’s not clear what “weird” should be here. $\endgroup$ – Pat Devlin May 10 '19 at 21:56

Not a full answer, but some thoughts...

(First off, if $m$ is way too small or way too big, something weird might happen. So let's think of $m$ and $n/m$ both sufficiently large. For instance, if $m=1$, the problem is silly.)

Well... Clearly we can discover colors for at least $n/8$ of the items (in fact, we could promise at least this well even in the worst case by just asking about every color on each of the first $n/8$ items). We could probably do better, and the best constant might be $n/4$ or so.

Here are two heurisitcs (neither exact). Since neither of the below are the honest-to-God truth, I'm not bothering super much being exact in what follows. I wouldn't be surprised if there's a very nice way to view the problem so as to make it very clear, but I coudln't see it right away.

Quick and dirty approach: Suppose the coloring is actually selected where each item is given a uniformly random color and (simplifying assumption) suppose these assignments are independent. Then the best algorithm would be to just sequentially go down the line and ask about each item one at a time until you know what it is (then move to the next one). [Proving that this is literally the best algorithm is (1) probably not hard, and (2) also probably true...]

Suppose we use this algorithm. Let $X_i$ be the color used for item $i$, and let $Y_i = \begin{cases} X_i, \qquad &\text{if } X_i < m\\ m-1, \qquad &\text{if } X_i = m\end{cases}$ (so $Y_i$ is the number of questions we would need to determine the color of item $i$). Then each $X_i$ is independently uniformly distributed over $\{1,2, \ldots ,m\}$, and we want to know the greatest value of $T$ such that $Y_1 + Y_2 + \ldots + Y_T \leq nm/8$. The expected value of $T$ is therefore equal to $$ \mathbb{E}[T] = \sum_{j=1} ^{\infty} \mathbb{P}\left( Y_1 + Y_2 + \cdots + Y_j \leq \frac{nm}{8}\right) $$

To simply some more, this is approximately asking how many continuous uniform on $[0,1]$ i.i.d. random variables are needed to sum to a total of $n/8$ (only approximately since $X_i \neq Y_i$ and since $X_i$ is not continuous, but this will be pretty close if $m$ isn't too small). This has probably been worked out (and it's given by the infinite summation and integral over the cube given above), and I bet it involves a Taylor series for $e$. But if $n/8$ is big enough, then $T$ is (on average) something like $n/4$. In fact, this would be related to the law of large numbers (and/or the central limit theorem to get more exact stuff).

Entropy approach: (This would probably work if you push on it hard enough.) Here, I'll use binary entropy, and $\lg(x)$ will denote the log base $2$. First off, the number of ``item-color assignments" is exactly equal to

$$N = {n \choose \frac{n}{m}, \frac{n}{m}, \ldots , \frac{n}{m}} = \dfrac{n!}{(\frac{n}{m}!)^{m}}.$$

At a first pass, an estimate for $\lg(N)$ is (say) $\lg(N) \approx n \lg(m)$ [thinking $N \approx m^n$], but (i) we'll only need a lower bound on $\lg(N)$, and (ii) you can get as exact as you want. Now the initial entropy of the selection is exactly equal to $\lg(N)$ (since it was made uniformly at random), which is about $n \lg(m)$.

Now the issue is in figuring out how much entropy each question has on average. You just need an upper bound on this, and it could perhaps be true that a greedy strategy (like above) would be the best algorithm to minimize the entropy of what's left.

In any case, the entropy of the first question is exactly $\log(m) - (1- \frac{1}{m-1}) \lg(m-1) \approx \lg(m)/m$. The questions you ask in the middle of the process will be hard to analyze of course, but let's say (as seems reasonable) that the average entropy per question should still be in the ballpark of $c \lg(m) / m$ for some constant $c$ that's not too big.

If we had such a bound on the average entropy of each question, we could say that after $nm/8$ questions, the average entropy went down by at most $(nm/8) c \lg(m) /m = n\lg(m) c/8$. So after the questions, the entropy of the coloring is still (on average) at least $n \lg(m) (1 - c/8)$. And if $1 - c/8 = a > 0$, then this means there are still at least $na$ items whose colors are unknown (since the entropy of a distribution is at most the log of its support, and if there are only $M$ unknown positions at the end, this would have entropy at most $\lg(m^M) = M \lg(m)$).

I have an idea to make the entropy argument more rigorous, but I'll hold off in case a much simpler argument comes along. [My idea is to perhaps divide questions into two types. Type 1 questions have low entropy (e.g., they ask about an item for which the distribution over its colors is pretty close to uniform [e.g., at most $m/10$ colors have been ruled out]). Type 2 questions are those with high entropy. And hopefully it's not possible to ask too many questions of high entropy (or at least, there must have been a bunch of questions of low entropy for every question of high entropy).]

| cite | improve this answer | |
  • $\begingroup$ $k$ should be $m$, but this is not a serious reason to edit this post. $\endgroup$ – Alex M. May 10 '19 at 18:56
  • $\begingroup$ Thank you Pat Devlin. I personally found the "Quick and dirty approach" to be too vague. There are several points I do not understand, e.g. when you talk about a "best algorithm" (why is it the best?). I do not even understand the "Entropy approach", e.g. the use a logarithm (base 2). For instance, each colour can be codified with $\log_2 m$ bits, but this does not imply that $\log_2 m$ "colour-item tests" are sufficient to find the colour of an item $i$, because you cannot operate like with a binary search in the colour sequence. You can just test whether $i$ is tinted with colour $c$ or not. $\endgroup$ – Penelope Benenati May 10 '19 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.