Maintain Entropy for a Streaming Distribution

A stream emits categorical observations one at a time. After each observation, report the empirical Shannon entropy of all observations seen so far: `H = -sum(p_i * log(p_i))`, where `p_i` is the observed frequency of category `i` divided by the total count. Use natural logarithms. Design an update algorithm that does not rescan every category after each arrival. Explain the state you maintain, derive the update formula, and discuss numerical behavior. Categories may be arbitrary hashable identifiers. ### Constraints & Assumptions - The stream is initially empty; entropy after the first item is zero. - Exact integer category counts fit in the chosen integer type. - Small floating-point rounding differences are acceptable. - The output is required after every insertion. ### Clarifying Questions to Ask - Is the logarithm base prescribed? Natural log for this problem. - Are deletions or a sliding window required? Not initially. - Is an approximate sketch acceptable? No for the base problem. ### What a Strong Answer Covers - Algebraic reformulation using counts - Constant expected update time plus hash-map storage - Correct treatment of a new category and count zero - Numerical and concurrency considerations ### Follow-up Questions - Support deletion of an observation. - Maintain entropy over a fixed-size sliding window. - Merge summaries computed independently on several stream partitions.