## [Computational Complexity] Is Guessing a good idea?

Expand Messages
• The following is from an Ask Marilyn Column. I paraphrase this since its from memory. READER S LETTER: I have heard of exams where you are penalized for
Message 1 of 1 , Apr 19, 2010
The following is from an Ask Marilyn Column. I paraphrase this since its from memory.

READER'S LETTER: I have heard of exams where you are penalized for guessing. How do they know you are guessing?

ANSWER: These are multiple choice exams where you get (say) 4 points for getting it right but -1 for getting it wrong. If there are 5 choices and you have no idea then you are better off NOT guessing and leaving it blank. If you can eliminate one of the choices then your guessing has expected value of 0, so either guess or don't guess. If you can eliminate more than one then you should guess.

I recently gave an exam where part of it was as follows:
For each of the following 10 languages indicate if it is REGULAR, CONTEXT-FREE BUT NOT REGULAR, or NOT CONTEXT-FREE. You may also leave it blank. You get +3 for a right answer, -3 for a wrong answer, and 0 for leaving it blank. DO NOT GUESS! Really DO NOT GUESS! If your total score is LESS THAN 0 then you will just get a 0. (NOTES TO MY READERS: This is DIFFERENT from the SATs and other exams that use this way to grade. For this post I omit the 10 languages.)
This problem inspires a math problem:

Should a student guess? If a student has NO IDEA how to do ANY of the questions then there is no harm in guessing since leaving all blanks will yield a 0, whereas guessing at random might yield a positive score. (If a student has NO IDEA but can do this reasoning then perhaps he should drop my course and take probability instead.)

What if the student is sure of ONE of the answers? Then should he randomly guess the rest? Randomly guess some of the remaining? What if he is sure of x of the answers? What is the value y so that he should guess y of the remaining but should not guess y+1? For x=0 I think the answer is y=10.

Here is one general question: There are n problems on an exam, each one has c choices. You get A points for getting a problem right, B points for getting a problem wrong, and C for writing DK for Don't Know (I had toyed with the idea of giving 1 points for DK.) If you know x of the answers and are clueless on the rest, how many should you guess (as a function of n,A,B,C,x)? We assume that those that you don't guess you write DK (admitting that you don't know something is helpful here, as in life). You can assume A > 0, B < 0, C &ge 0.

One can ask more general questions by dividing the questions into c categories: Those where you can eliminate 0 options (clueless), 1 option, 2 options, ..., c options (you know you are correct).

If a student can figure out how many to guess on during the exam then they are likely a very good student and should guess 0 of them.

--
Posted By GASARCH to Computational Complexity at 4/19/2010 09:45:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.