A museum guide robot keeps its belief about where it is in a long gallery as a list belief of probabilities over cells 0 to n - 1 (they add up to 1). Before it announces "you are standing at the Rembrandt", it checks how sure it is, in two ways.
Entropy. The entropy of the belief, in bits, is
where cells with p_i = 0 add nothing (take 0 \log_2 0 = 0). A robot that is certain has H = 0; one spread evenly over 2^m cells has H = m bits: it would take m yes/no questions to find out where it is.
Mass near the best guess. The best guess best is the cell with the largest probability; when several cells tie, it is the one with the smallest index. The mass near it is the total probability of the cells j with |j - best| <= k (the gallery has ends; it does not wrap round).
Write how_sure(belief, k) that returns the tuple (H, best, mass).
Examples
Input: belief = [0.5, 0.25, 0.25, 0], k = 1
Output: (1.5, 0, 0.75)
Explanation: H = 0.5 * 1 + 0.25 * 2 + 0.25 * 2 = 1.5 bits. Cells 0 and 1 lie within
one cell of cell 0.
Input: belief = [0.125] * 8, k = 2
Output: (3.0, 0, 0.375)
Explanation: eight equally likely cells are 3 bits of doubt; all cells tie, so the
best guess is cell 0, and only cells 0, 1, 2 lie within two cells of it.
Input: belief = [0, 0, 1.0], k = 0
Output: (0.0, 2, 1.0)
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Measure the spread of a belief with its entropy in bits
- Find the best guess with a stated tie-break
- Add up the probability within a few cells of the best guess