4
$\begingroup$

First question on this Stack, so I hope this is appropriate. This is not for homework, but a personal question related to a machine learning problem I am working on. However, I don't have enough knowledge of probability theory to answer it. So thanks in advance!

You are given a multiple choice test of p=100 questions and q=6 choices per question. You can take the test as often as you would like. The questions are always given in the same order. Each time you take the test you are given your score, such as 75% accurate, but do not know which 75% is correct. How many times do you have to take the test in order to be guaranteed a score > 90%?

Each time you take the test, there should be a reduction in entropy. For example, if you received 0%, you could eliminate all those choices from the next submission. I'm not looking for the answer per se, but where would I start to find the solution.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ A simpler version, with $q=2$ and a $100\%$ target, was discussed here: mathoverflow.net/questions/151390/… $\endgroup$
    – Douglas Zare
    Mar 11, 2014 at 15:22
  • 1
    $\begingroup$ Perhaps some ideas from coding or sphere-packing can help give a lower bound (I suspect you cannot do much better than brute-force search...). There is some target codeword in $\mathbb{Z}_q^p$ (the string of correct answers), your goal is to find a word within Hamming distance $0.1p$ of this target, and your only tool is to make Hamming-distance queries (how far is $x$ from the target?). $\endgroup$
    – usul
    Mar 11, 2014 at 19:53
  • $\begingroup$ @usul: I'm not sure what you mean by brute force. A ball of radius $10$ takes up about $1/(4\times10^{57})$ of the possibilities. You don't need anything like $4 \times 10^{57}$ guesses. It's easy to get the exact answer in under $600$ tries by altering only one answer at a time. However, if you can get a few bits of information per try, you can do better. Asymptotically, for any fixed $q$, I think you should expect something like $c p/\log p$ guesses to find out all answers. $\endgroup$
    – Douglas Zare
    Mar 11, 2014 at 20:42
  • $\begingroup$ Douglas, you're right - by exhaustively trying permutations, it should be possible in $(q+1)(p-1)$ tries. I suspect it should be a lot less, but that is only intuition. $\endgroup$
    – David Wihl
    Mar 11, 2014 at 21:26
  • $\begingroup$ @DouglasZare, by brute force I meant the ~$qp$ approach of finding one answer at a time. $\endgroup$
    – usul
    Mar 11, 2014 at 23:53

1 Answer 1

Reset to default
2
$\begingroup$

Here are some nonconstructive estimates on the number of tries needed to find the exact answer, not just to get $90\%$ or more correct. See this paper by Erdős and Rényi for similar analysis of a related problem. This is also connected to the game Mastermind.

Consider guessing randomly $k$ times. What is the expected number of pairs of possibilities which are not distinguished from the answer? If we choose $k$ so that the expected number is less than $1$, this means there is some arrangement of guesses which distinguishes all pairs.

Let $B(r) = 5^r {100 \choose r}$ be the size of the sphere of radius $r$. There are $\frac{1}{2} 6^{100} B(r)$ pairs of distance $r$ from each other.

The probability $p(r)$ that a uniformly random guess has the same results for possibilities of distance $r \gt 0$ is at most $\frac{2}{3}$, with equality when $r=1$. In general it is the coefficient of $x^r$ in $(\frac{1}{6} + \frac{2}{3} x + \frac{1}{6} x^2)^r$.

After $k$ random tries, the expected number of pairs which are not distinguished is $\sum_r \frac{1}{2}6^{100} B(r) p(r)^k.$ When $k=456$, the expected number of pairs is $0.82$ so there is some configuration of $456$ guesses so that the exact answer can be determined from the results.

We can do better. Most of the guesses were required because of the case $r=1$. The chance to get the same score for pairs which differ by $1$ is $\frac{2}{3}$, but for every other distance the chance to get the same score is at most $\frac{1}{2}$. While there are relatively few pairs of distance $1$, there are still a lot in absolute terms. These pairs are not necessarily essentially different. If AAAA... is not distinguished from BAAA..., this means that all of the guesses did not have an A or B in the first coordinate. Then we also can't distinguish ACCC... from BCCC..., or any of $6^{99}$ pairs. We can get better estimates by grouping these possibilities into one essential pair $(A???...?,B???...?)$. The number of essential pairs which disagree in $r$ locations is $\frac{1}{2}{100\choose r}(6\times 5)^r$. We need to choose $k$ large enough so that $\sum_r \frac{1}{2} {100 \choose r} 30^r p(r)^k \lt 1$. This first happens at $k=130$, where the sum is $0.20$. So, some choice of $130$ tries will distinguish each pair of possibilities (and in fact, $80\%$ of random choices will work).

Figuring out which answer is consistent with a collection of guesses and scores might be hard. Some variants of this problem in Mastermind are known to be NP-complete.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your analysis. I'm going to try exploring Shannon Entropy and post back here if I find something interesting. $\endgroup$
    – David Wihl
    Mar 13, 2014 at 22:03
  • $\begingroup$ @David Wihl: Information theory gives you some lower bounds. I'm not sure how to get upper bounds out of its results. The idea that random guesses are usually efficient parallels a proof from information theory, that random codes are asymptotically optimal. $\endgroup$
    – Douglas Zare
    Mar 14, 2014 at 4:14

Your Answer

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

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