#StackBounty: #self-study #algorithms #entropy #information-theory #maximum-entropy How do I prove conditional entropy is a good measur…

Bounty: 200

This question is a follow-up of Does “expected entropy” make sense?, which you don’t have to read as I’ll reproduce the relevant parts. Let’s begin with the statement of the problem

A student has to pass an exam, with $k$ questions to be answered by yes or no, on a subject he knows nothing about. Assume the questions are independently distributed with a half-half probability of being either yes or no. The student is allowed to pass mock exams who have the same questions as the real exam. After each mock exam the teacher tells the student how many right answers he got, and when the student feels ready, he can pass the real exam. How many mock exams on average (a.k.a. take the expectation) must the student take to ensure he can get every single question correct in the real exam, and what should be his optimal strategy?

I have proposed an entropy-based strategy in that question, but for it to work, it must be first established that conditional entropy is a good measure of information to be recovered.

Here is a more concrete statement of my question. Suppose a student Alice has already taken 3 mock exams and got incomplete information about the answers. In a parallel universe, another student Bob has also taken 3 mock exams, but his strategy and insight about the answers may differ from those of Alice. At this point, both Alice and Bob have a conditional distribution of the answers based on outcomes of previous mock exams. I wonder if it can be proved that “the entropy of the conditional distribution from the perspective of Alice is greater or equal than that of Bob” can lead to “the minimum expected number of mock exams to be taken by Alice is greater or equal than that of Bob”.

Intuitively it makes sense because more entropy means more uncertainty and thus more attempts required, but I have no idea how to attack it. As a side note, this will be my bachelor’s thesis, so please just leave hints/pointers instead of spoiling too much 🙂

Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.