Equality of sets when minimizing Shannon's Entropy 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)
$$
 A: 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)$.
