I need an algorithm to do a binary search when the test at each step may give the wrong result.
Background:
I need to place students on the most appropriate of 12 difficulty levels. The current approach is brute force and asks 60 4-answer multiple choice questions of increasing difficulty, stopping after three wrong, and places the student at level: floor((score - 1) / 5) + 1 with a minimum of 1.
We're concerned that customers are turned off when they face a test with up to 60 questions before they can actually use the program, so we would like to minimize the number of questions asked in the test. We're also concerned that customers are skipping the placement test (because it seems long) and then abandoning the program because it seems too easy.
The median placement is actually on level 2, so 50+% of students score <11 (i.e. answer < 14 questions). Anecdotally, this may be because they get bored and stop taking the questions seriously (they're young children).
Proposed Solution: Implement the test as a binary search over twelve items starting with a question at difficulty level 6/7 and proceeding based on whether they get the question right or wrong. In theory, this could find the appropriate difficulty level for them in 3-4 questions.
The Problem: As you might guess from the existing test only ending after three wrong answers and using 60 questions to choose between 12 levels, we want to make allowance for students fluking correct answers (which they should do 25% of the time) or accidentally giving incorrect answers (fat fingers, misreading question etc). This is even more important with a binary search because fluking a right answer on the first question could place you in the top half of difficulty levels even if you get every other question wrong.
So is there a recognized algorithm for a binary search where you can't guarantee that an individual test is accurate?
Naively I might try best of 3 or 5 questions at each step, and, since the early questions have a bigger effect on the final result than the later questions, maybe add these additional questions only to the early steps and not the later ones. Is there more to it than that?
