Suppose you can ask one question to identify an unknown number. Which question should you ask? Expected information gain (EIG) scores a question by how much it is expected to reduce uncertainty. It helps you choose what to observe before you know what the answer will be. section 13.7 section 13.8
Entropy measures uncertainty in a probability distribution. To calculate EIG, start with the entropy of your current belief. For each possible answer, calculate the entropy of the updated belief, then average those entropies using the answers’ probabilities. Subtract that expected posterior entropy from the prior entropy: EIG(x) = H(θ) − Eᵧ[H(θ | x, y)], where θ is the unknown, x is the proposed experiment, and y is its outcome. section 13.10 section 13.7
Where should you split the search?
Assume each integer from 1 to 100 is equally likely. Asking “Is it greater than 50?” gives two equally likely answers. The prior entropy is about 6.64 bits; either answer leaves 5.64 bits, so EIG is 1 bit. Asking “Is it greater than 90?” leaves an expected 6.17 bits, for EIG of only 0.47 bits. Splitting the possibilities evenly is the better question. section 13.7
The same calculation can score every threshold in Python. For N equally likely numbers, a threshold x gives answer probabilities x/N and (N−x)/N. Using math.log2(n) for the entropy of n equally likely possibilities, subtract the probability-weighted entropy of the two remaining ranges from math.log2(N). The highest-scoring threshold is the midpoint. section 13.7
Beyond binary search, the procedure is a loop: propose experiments, rank them by EIG, run the most informative one, update your belief, and repeat. An experiment can also have many possible outcomes. Calculating a posterior for every outcome may then be expensive; an equivalent mutual-information formulation can sometimes calculate EIG more efficiently through the forward model. section 13.8 section 13.10
For continuous unknowns, differences in differential entropy can still express information gain, even though an absolute differential-entropy value is less meaningful on its own. EIG can also be understood as the expected KL divergence between prior and posterior beliefs: a measure of how much an observation is expected to change what you believe. section 13.9






