Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I want to guess a binary code, where the quality of my guess is provided by an evaluation function. I imagine a safe, where the user enters a binary code by flipping $N$ switches. After pressing a button, the code is evaluated and the error (for simplicity, let's assume Hamming Distance divided by $N$) displayed, for example using some sort of gauge or display.

Now, I want to guess the code by minimizing the number of tries (button presses). A naive approach would be to simply the first switch, press the button, and see if the gauge changes, and repeat that for every switch, so I would need at most $N$ tries.

Qustion: Is there a faster way?
Bonus question: What if the feedback gauge is noisy or the exact evaluation function is not known?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

So, I reckon it is either $N$ or $N-1$, depending on what you know about the gauge.

Call the sequence after $n$ operations $x_n$, let it be $N$ bits long. Let the correct sequence be $x'$ and the Hamming distance be $H$.

Lets say the gauge reads out the value of $H(x,x')$. To discover the value of the sequence $x'$ we need at most $N-1$ switches, because the value of $H(x_{N-1},x')$ tells us the value of the remaining switch. This however assumes requires the knowledge of the gauge other than it changes monotonically with the accuracy - if you do not know this then the best you can do is $N$.

You can justify this in terms of the information gain, as long as you switch different switches each time, you get one bit of information from the increase of decrease in $H$, you need $N$ bits to determine the binary sequence. Then, for the case where you know the function and it's minimum, there is an extra bit of information in whether or not it's absolute value is what you would predict (a yes or no question).

Consider the following sequence:

 Target: 0 0 1 0
Current: 0 1 1 1   H=2

Using the algorithm you describe, we do the following

 Target: 0 0 1 0
Current: 1 1 1 1   H=2
Correct: N         H_so_far = 1


 Target: 0 0 1 0
Current: 1 0 1 1   H=1
Correct: N Y       H_so_far = 1


 Target: 0 0 1 0
Current: 1 0 0 1   H=3
Correct: N Y N     H_so_far = 2

Then we can say that for the state of the first $3$ switches the Hamming distance is $2$ (two Ns), but in total the hamming distance is $3$, so the last switch must be incorrect. We have deduced the sequence in $N-1$ presses. This will apply for any other known functions too, but it isn't as simple.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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