1
$\begingroup$

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 :)

$\endgroup$
8
  • $\begingroup$ Here are a few topics that I think are relevant - Thompson Sampling - Multi-Armed Bandits $\endgroup$
    – psiyumm
    Mar 5, 2020 at 23:18
  • $\begingroup$ Are the results of the mock exams considered to be independent? $\endgroup$ Mar 6, 2020 at 0:47
  • $\begingroup$ @DonWalpola Could you elaborate on your question? The answers are in fact deterministic, and there is only one true answer for each of the $k$ questions. I said they are independently distributed with a half-half probability of being either yes or no because initially, the student does not know the answers or their relationship, so they are random and independent from his perspective. $\endgroup$
    – nalzok
    Mar 6, 2020 at 0:52
  • $\begingroup$ Sure, I'm just a little unclear about the precise statement of the scenario. Are the mock exams identical to either each other or the true exam? If not, are there a fixed number of candidate exams, or a fixed set of candidate questions which are randomly drawn for each exam, or both? You have described a Bayesian perspective of the student's uncertainty, but what other sources of randomness are there in this situation? $\endgroup$ Mar 6, 2020 at 0:56
  • $\begingroup$ @DonWalpola The questions and answers in mock exams are identical to each other and the true exam. Essentially, the student's uncertainty is the only randomness involved. $\endgroup$
    – nalzok
    Mar 6, 2020 at 1:12

1 Answer 1

2
+200
$\begingroup$

I've tried to hint but not solve.

Let $\mathfrak{m}$ be the fixed but unknown marking scheme, i.e. the yes/no assignments that are correct for each of the $k$ questions. A priori, before you get your first mock paper results, there are (how many?) equally-likely possible values of $\mathfrak{m}$. Put another way: the entropy of $\mathcal{M}$, the process that generated the marking scheme, is (how many?) bits.

Write $H_t(\mathcal{M})$ for the entropy of $\mathcal{M}$ conditional upon the scores from the first $t$ mock tests, and $n_t$ for the number of $\mathfrak{m}$ compatible with those first $t$ tests. (How are $H_t(\mathcal{M})$ and $n_t$ related?)

Each time you get a mock paper score, you learn more about $\mathfrak{m}$. With enough scores, $n_t$ drops to $1$ and you learn $\mathfrak{m}$ in its entirety. Equivalently, $H_t(\mathcal{M})$ drops to $0$.

Entropy comes into play in a more interesting way when you think about how to modify your answers in each mock exam. Let's say you answered "yes" to everything in the first mock; so it's a question of how to pick the "no" questions in future exams.

A greedy algorithm is to pick the "no" questions to minimise, on average, the proportion of $\mathfrak{m}$ possibilities that survive from one exam to the next, i.e. $n_{t+1}/n_t$. This is exactly the approach you took in your earlier post, as it is equivalent to minimising the expected value of $\log(n_{t+1})$ (why log? - consider the cumulative effect). In turn, $\mathbb{E}(\log(n_{t+1}))$ s is directly related to the entropy of the mock exam score (hint: if $p_x$ is the probability of scoring $x$, then it relates (how?) to the total number of $\mathfrak{m}$ possibilities compatible with $x$).

Hope that helps.


Here's a transcript of the procedure run on an exam with $k=13$ questions. Notice how $H_t(\mathcal{M})$ drops by the information content, $I$, of the score from the most recent guess. That's why you want to maximise the entropy of the mock exam score: it's the expected value of those $I$'s.

Marking scheme m = 1100000101011
A priori #survivors = 8192

----------------------------------------

Round 1: guess 0000000000000
The guess scored 7
Now #survivors = 1716  : conditional entropy 10.744833837499547

Best guess for next round is 1111110000000
with score distribution
  *  score  1 : count 7     : I = 7.937
  *  score  3 : count 126   : I = 3.768
  *  score  5 : count 525   : I = 1.709
  *  score  7 : count 700   : I = 1.294
  *  score  9 : count 315   : I = 2.446
  *  score 11 : count 42    : I = 5.353
  *  score 13 : count 1     : I = 10.745
and entropy 1.9456755990162689

----------------------------------------

Round 2: guess 1111110000000
The guess scored 5
Now #survivors = 525  : conditional entropy 9.036173612553485

Best guess for next round is 1110001110000
with score distribution
  *  score  1 : count 3     : I = 7.451
  *  score  3 : count 45    : I = 3.544
  *  score  5 : count 165   : I = 1.670
  *  score  7 : count 210   : I = 1.322
  *  score  9 : count 90    : I = 2.544
  *  score 11 : count 12    : I = 5.451
and entropy 1.9607272705044019

----------------------------------------

Round 3: guess 1110001110000
The guess scored 7
Now #survivors = 210  : conditional entropy 7.714245517666122

Best guess for next round is 1101001001100
with score distribution
  *  score  1 : count 2     : I = 6.714
  *  score  3 : count 19    : I = 3.466
  *  score  5 : count 64    : I = 1.714
  *  score  7 : count 81    : I = 1.374
  *  score  9 : count 38    : I = 2.466
  *  score 11 : count 6     : I = 5.129
and entropy 2.0229622152648568

----------------------------------------

Round 4: guess 1101001001100
The guess scored 7
Now #survivors = 81  : conditional entropy 6.339850002884625

Best guess for next round is 1000111101010
with score distribution
  *  score  2 : count 3     : I = 4.755
  *  score  4 : count 15    : I = 2.433
  *  score  6 : count 29    : I = 1.482
  *  score  8 : count 24    : I = 1.755
  *  score 10 : count 8     : I = 3.340
  *  score 12 : count 2     : I = 5.340
and entropy 2.138877221251309

----------------------------------------

Round 5: guess 1000111101010
The guess scored 8
Now #survivors = 24  : conditional entropy 4.584962500721157

Best guess for next round is 0101101011010
with score distribution
  *  score  2 : count 1     : I = 4.585
  *  score  4 : count 4     : I = 2.585
  *  score  6 : count 9     : I = 1.415
  *  score  8 : count 7     : I = 1.778
  *  score 10 : count 2     : I = 3.585
  *  score 12 : count 1     : I = 4.585
and entropy 2.160762106246821

----------------------------------------

Round 6: guess 0101101011010
The guess scored 6
Now #survivors = 9  : conditional entropy 3.1699250014423126

Best guess for next round is 1011100011100
with score distribution
  *  score  2 : count 2     : I = 2.170
  *  score  4 : count 2     : I = 2.170
  *  score  6 : count 3     : I = 1.585
  *  score  8 : count 1     : I = 3.170
  *  score 10 : count 1     : I = 3.170
and entropy 2.1971597234241496

----------------------------------------

Round 7: guess 1011100011100
The guess scored 4
Now #survivors = 2  : conditional entropy 1.0

Best guess for next round is 0100000000000
with score distribution
  *  score  6 : count 1     : I = 1.000
  *  score  8 : count 1     : I = 1.000
and entropy 1.0

----------------------------------------

Round 8: guess 0100000000000
The guess scored 8
Now #survivors = 1  : conditional entropy 0.0

*** FINISHED ***
$\endgroup$
8
  • $\begingroup$ Thanks for the answer, Creosote! That's really insightful, but can you elaborate on why "the average number of mock exams required" is a function of "the total number of possibilities that remain"? I mean, the set of possible answers may have different structures even when they have the same number of elements. $\endgroup$
    – nalzok
    Mar 7, 2020 at 21:43
  • $\begingroup$ Also, in the second paragraph, are you implying that the conditional entropy is the logarithm of the total number of possibilities that remain? I'm not sure which processes are you referring to by $\mathfrak{m}$ and $\mathfrak{M}$, and it would be awesome if you can explain them in greater detail. Looks like you are saying $\mathfrak{m}$ is the deterministic correct answer, but doesn't deterministic stuff have zero entropy? $\endgroup$
    – nalzok
    Mar 7, 2020 at 21:47
  • $\begingroup$ I've reworded things. To your first question: I'm not tackling the problem of minimising the total number of exams required (too hard!), just analysing the greedy algorithm. To your second: $\mathcal{M}$ is the process that created the fixed but unknown marking scheme $\mathfrak{m}$ -- sorry if the notation was unclear. $\endgroup$
    – Creosote
    Mar 8, 2020 at 8:57
  • $\begingroup$ Thanks for the clarification! The second question has been resolved now, but the first one hasn't. Intuitively, having fewer possibilities does indicate fewer mock exams to take on average, but can you prove it? If two situations have the same number of possibilities, do they always require the same number of mock exams on average? $\endgroup$
    – nalzok
    Mar 8, 2020 at 9:12
  • 1
    $\begingroup$ Right, because the average number required looks too hard to answer. So, as you did in your earlier post, I'm trying a greedy heuristic instead. By trying to minimise $\log(n_1/n_0)$ then $\log(n_2/n_1)$ etc., you heuristically (greedily) hope that this is nearly the same as minimising $\log(n_t)$ for any $t$, which in turn would eventually find the smallest $t$ with $n_t=1$. $\endgroup$
    – Creosote
    Mar 8, 2020 at 9:31

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.