Equality of sets when minimizing Shannon's Entropy

Question

Let $P = \{p_1, \ldots, p_n\}$ be a set of probabilities, i.e., $0 \leq p_i \leq 1$. $P$ is such that $\sum_{p_i \in P} p_i = 1$.

I have a set of actions $\mathcal{A} = \{a_1, \ldots, a_N\}$ that can be performed on $P$. Each time an action $a_i$ is performed, some of the probabilities $p_i \in P$ are deleted from $P$, and $P$ is normalized so that the summation is again 1.

Let $H(P)$ be the (Shannon's) entropy of the original set of probabilities in $P$.

Performing one action. $H_a(P)$ is the (Shannon's) entropy of the set of probabilities $P$ after:

• $a$ is performed and some of the probabilities are deleted
• $P$ is normalized

Performing two actions. $H_a(P|b) = H(P|a,b)$ is the (Shannon's) entropy after:

• $b$ is performed on $P$ and some of the probabilities are deleted
• $P$ is normalized to sum up to 1
• $a$ is performed on the new $P$
• $P$ is again normalized

Claim. Let $a_1^* = \arg \min_{a \in \mathcal{A}} H_a(P)$. Prove that the following two sets are equal: $$ \{a_1^*, \arg \min_{a \in \mathcal{A}\setminus a_1^*} H_a(P|a_1^*) \} = \arg \min_{\{a, b\} \in \mathcal{A}} H(P|a,b) $$

Answer 1

This doesn't seem to be true, if I understand your definitions correctly. Here's a counterexample: Let $P = \lbrace p_1, \dots, p_9 \rbrace$ where each $p_i$ is equal to $1/9$. Let $\mathcal{A} = \lbrace a_1, a_2, a_3 \rbrace$ be such that:

• $a_1$ restricts to the set $\lbrace p_1, p_2, p_3, p_4 \rbrace$;
• $a_2$ restricts to the set $\lbrace p_1, p_2, p_5, p_6, p_9 \rbrace$;
• $a_3$ restricts to the set $\lbrace p_3, p_4, p_7, p_8, p_9 \rbrace$.

It's evident that after performing any number of actions in $\mathcal{A}$, the entropy is $\log(n)$ where $n$ is the number of elements remaining. Since $a_1$ restricts to the smallest number of elements, $$ \arg \min_{a \in \mathcal{A}} H_a(P) = a_1. $$ But the smallest double intersection is given by taking $a_2$ and $a_3$, so that $$ \arg \min_{\lbrace a, b \rbrace \in \mathcal{A} \times \mathcal{A}} H(P|a, b) = \lbrace a_2, a_3 \rbrace $$ In particular, we have $H(P | a_2, a_3) = 0$, whereas $H(P|a_1, a_2) = H(P|a_1, a_3) = \log(2)$.