Optimal Policies Tend to Seek Power — part 8/16
Cleaned-text code points [108627, 124570). Bibliography omitted here; source.md includes it.
Suppose that 𝒟 bound \mathcal{D}_{\text{bound}} is such that 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] < 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]<\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] . 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \displaystyle\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] ≤ 𝔼 𝐫 ∼ ϕ 2 ⋅ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \displaystyle\leq\opE_{\mathbf{r}\sim\phi^{2}\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] (38) = 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] (39) < 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \displaystyle<\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] (40) ≤ 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] . \displaystyle\leq\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (41) Equation 38 follows by applying Lemma E.21 with permutation ϕ \phi and A ′ ≔ ND ( A ) A^{\prime}\coloneqq\text{{ND}}\left(A\right) . Equation 39 follows because involutions satisfy ϕ − 1 = ϕ \phi^{-1}=\phi , and ϕ 2 \phi^{2} is therefore the identity. Equation 40 follows because we assumed that 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] < 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]<\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] . Equation 41 follows by applying Lemma E.21 with permutation ϕ \phi and and A ′ ≔ ND ( A ) A^{\prime}\coloneqq\text{{ND}}\left(A\right) . By Lemma E.16 , eq. 37 holds.
Suppose g g is strictly increasing and ND ( B ) ∖ B ′ \text{{ND}}\left(B\right)\setminus B^{\prime} is non-empty. Let ϕ ′ ∈ S | 𝒮 | \phi^{\prime}\in S_{\left|\mathcal{S}\right|} . 𝔼 𝐫 ∼ ϕ ′ ⋅ 𝒟 X - iid [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \displaystyle\opE_{\mathbf{r}\sim\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] = 𝔼 𝐫 ∼ 𝒟 X - iid [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right] (42) < 𝔼 𝐫 ∼ ϕ ⋅ 𝒟 X - iid [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \displaystyle<\opE_{\mathbf{r}\sim\phi\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] (43) = 𝔼 𝐫 ∼ ϕ ′ ⋅ 𝒟 X - iid [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] . \displaystyle=\opE_{\mathbf{r}\sim\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right]. (44)
Equation 42 and eq. 44 hold because 𝒟 X - iid \mathcal{D}_{X\text{-}\textsc{iid}} distributes reward identically across states: ∀ ϕ x ∈ S | 𝒮 | : ϕ x ⋅ 𝒟 X - iid = 𝒟 X - iid \forall\phi_{x}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\phi_{x}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}=\mathcal{D}_{X\text{-}\textsc{iid}} . By Lemma E.22 , ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ( 𝒟 X - iid ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{X\text{-}\textsc{iid}}) . Therefore, apply Lemma E.21 with A ′ ≔ ND ( A ) A^{\prime}\coloneqq\text{{ND}}\left(A\right) to conclude that eq. 43 holds.
Therefore, ∀ ϕ ′ ∈ S | 𝒮 | : 𝔼 𝐫 ∼ ϕ ′ ⋅ 𝒟 X - iid [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] < 𝔼 𝐫 ∼ ϕ ′ ⋅ 𝒟 X - iid [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \forall\phi^{\prime}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\opE_{\mathbf{r}\sim\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]<\opE_{\mathbf{r}\sim\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] , and so 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐚 ∈ A 𝐚 ⊤ 𝐫 ) ] ≱ most : 𝔇 bound 𝔼 𝐫 ∼ 𝒟 bound [ g ( max 𝐛 ∈ B 𝐛 ⊤ 𝐫 ) ] \opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{a}\in A}\mathbf{a}^{\top}\mathbf{r}\right)\right]\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\opE_{\mathbf{r}\sim\mathcal{D}_{\text{bound}}}\left[g\left(\max_{\mathbf{b}\in B}\mathbf{b}^{\top}\mathbf{r}\right)\right] by definition 6.5 . ∎
###### Definition E.25 (Indicator function) .
Let L L be a predicate which takes input x x . 𝟙 L ( x ) \mathbbm{1}_{L(x)} is the function which returns 1 when L ( x ) L(x) is true, and 0 otherwise.
###### Lemma E.26 (Optimality probability inclusion relations) .
Let X , Y ⊊ ℝ | 𝒮 | X,Y\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite and suppose Y ′ ⊆ Y Y^{\prime}\subseteq Y . p 𝒟 any ( X ≥ Y ) ≤ p 𝒟 any ( X ≥ Y ′ ) ≤ p 𝒟 any ( X ∪ ( Y ∖ Y ′ ) ≥ Y ) . p_{\mathcal{D}_{\text{any}}}\left(X\geq Y\right)\leq p_{\mathcal{D}_{\text{any}}}\left(X\geq Y^{\prime}\right)\leq p_{\mathcal{D}_{\text{any}}}\left(X\cup\left(Y\setminus Y^{\prime}\right)\geq Y\right). (45)
If ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) , X ⊆ Y X\subseteq Y , and ND ( Y ) ∩ ( Y ∖ Y ′ ) \text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right) is non-empty, then the second inequality is strict.
###### Proof.
p 𝒟 any ( X ≥ Y ) \displaystyle p_{\mathcal{D}_{\text{any}}}\left(X\geq Y\right) ≔ 𝔼 𝐫 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y 𝐲 ⊤ 𝐫 ] \displaystyle\coloneqq\opE_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y}\mathbf{y}^{\top}\mathbf{r}}\right] (46) ≤ 𝔼 𝐫 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ 𝐲 ⊤ 𝐫 ] \displaystyle\leq\opE_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}}\right] (47) ≤ 𝔼 𝐫 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X ∪ ( Y ∖ Y ′ ) 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ 𝐲 ⊤ 𝐫 ] \displaystyle\leq\opE_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X\cup(Y\setminus Y^{\prime})}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}}\right] (48) = 𝔼 𝐫 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X ∪ ( Y ∖ Y ′ ) 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ ∪ ( Y ∖ Y ′ ) 𝐲 ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X\cup(Y\setminus Y^{\prime})}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}\cup(Y\setminus Y^{\prime})}\mathbf{y}^{\top}\mathbf{r}}\right] (49) = 𝔼 𝐫 ∼ 𝒟 any [ 𝟙 max 𝐱 ∈ X ∪ ( Y ∖ Y ′ ) 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y 𝐲 ⊤ 𝐫 ] \displaystyle=\opE_{\mathbf{r}\sim\mathcal{D}_{\text{any}}}\left[\mathbbm{1}_{\max_{\mathbf{x}\in X\cup(Y\setminus Y^{\prime})}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y}\mathbf{y}^{\top}\mathbf{r}}\right] (50) ≕ p 𝒟 any ( X ∪ ( Y ∖ Y ′ ) ≥ Y ) . \displaystyle\eqqcolon p_{\mathcal{D}_{\text{any}}}\left(X\cup\left(Y\setminus Y^{\prime}\right)\geq Y\right). (51) Equation 47 follows because ∀ 𝐫 ∈ ℝ | 𝒮 | : 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y 𝐲 ⊤ 𝐫 ≤ 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ 𝐲 ⊤ 𝐫 \forall\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y}\mathbf{y}^{\top}\mathbf{r}}\leq\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}} since Y ′ ⊆ Y Y^{\prime}\subseteq Y ; note that eq. 47 equals p 𝒟 any ( X ≥ Y ′ ) p_{\mathcal{D}_{\text{any}}}\left(X\geq Y^{\prime}\right) , and so the first inequality of eq. 45 is shown. Equation 48 holds because ∀ 𝐫 ∈ ℝ | 𝒮 | : 𝟙 max 𝐱 ∈ X 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ 𝐲 ⊤ 𝐫 ≤ 𝟙 max 𝐱 ∈ X ∪ ( Y ∖ Y ′ ) 𝐱 ⊤ 𝐫 ≥ max 𝐲 ∈ Y ′ 𝐛 ⊤ 𝐫 \forall\mathbf{r}\in\mathbb{R}^{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\mathbbm{1}_{\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}}\leq\mathbbm{1}_{\max_{\mathbf{x}\in X\cup(Y\setminus Y^{\prime})}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{y}\in Y^{\prime}}\mathbf{b}^{\top}\mathbf{r}} .
Suppose ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) , X ⊆ Y X\subseteq Y , and ND ( Y ) ∩ ( Y ∖ Y ′ ) \text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right) is non-empty. Let 𝐲 ∗ ∈ ND ( Y ) ∩ ( Y ∖ Y ′ ) \mathbf{y}^{*}\in\text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right) . By Proposition E.20 , 𝐲 ∗ \mathbf{y}^{*} is strictly optimal on a subset of supp ( 𝒟 any ) \optSupp(\mathcal{D}_{\text{any}}) with positive measure under 𝒟 any \mathcal{D}_{\text{any}} . In particular, for a set of 𝐫 ∗ \mathbf{r}^{*} with positive measure under 𝒟 any \mathcal{D}_{\text{any}} , we have 𝐲 ∗ ⊤ 𝐫 ∗ > max 𝐲 ∈ Y ′ 𝐲 ⊤ 𝐫 ∗ . \mathbf{y}^{*\top}\mathbf{r}^{*}>\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}^{*}.
Then eq. 48 is strict, and therefore the second inequality of eq. 45 is strict as well. ∎
###### Lemma E.27 (Optimality probability of similar linear functional sets) .
Let A , B , C ⊊ ℝ | 𝒮 | A,B,C\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite, and let Z ⊆ ℝ | 𝒮 | Z\subseteq\mathbb{R}^{\left|\mathcal{S}\right|} be such that ND ( C ) ⊆ Z ⊆ C \text{{ND}}\left(C\right)\subseteq Z\subseteq C . If ND ( A ) \text{{ND}}\left(A\right) is similar to B ′ ⊆ B B^{\prime}\subseteq B via ϕ \phi such that ϕ ⋅ ( Z ∖ ( B ∖ B ′ ) ) = Z ∖ ( B ∖ B ′ ) \phi\cdot\left(Z\setminus\left(B\setminus B^{\prime}\right)\right)=Z\setminus\left(B\setminus B^{\prime}\right) , then p 𝒟 any ( A ≥ C ) ≤ p ϕ ⋅ 𝒟 any ( B ≥ C ) . p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\leq p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(B\geq C\right). (52) If B ′ = B B^{\prime}=B , then eq. 52 is an equality. If ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) , B ′ ⊆ C B^{\prime}\subseteq C , and ND ( C ) ∩ ( B ∖ B ′ ) \text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right) is non-empty, then eq. 52 is strict.
###### Proof.
p 𝒟 any ( A ≥ C ) \displaystyle p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right) = p 𝒟 any ( A ≥ Z ) \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(A\geq Z\right) (53) = p 𝒟 any ( ND ( A ) ≥ Z ) \displaystyle=p_{\mathcal{D}_{\text{any}}}\left(\text{{ND}}\left(A\right)\geq Z\right) (54) ≤ p 𝒟 any ( ND ( A ) ≥ Z ∖ ( B ∖ B ′ ) ) \displaystyle\leq p_{\mathcal{D}_{\text{any}}}\left(\text{{ND}}\left(A\right)\geq Z\setminus\left(B\setminus B^{\prime}\right)\right) (55) = p ϕ ⋅ 𝒟 any ( ϕ ⋅ ND ( A ) ≥ ϕ ⋅ Z ∖ ( B ∖ B ′ ) ) \displaystyle=p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(\phi\cdot\text{{ND}}\left(A\right)\geq\phi\cdot Z\setminus\left(B\setminus B^{\prime}\right)\right) (56) = p ϕ ⋅ 𝒟 any ( B ′ ≥ Z ∖ ( B ∖ B ′ ) ) \displaystyle=p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(B^{\prime}\geq Z\setminus\left(B\setminus B^{\prime}\right)\right) (57) ≤ p ϕ ⋅ 𝒟 any ( B ′ ∪ ( B ∖ B ′ ) ≥ Z ) \displaystyle\leq p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(B^{\prime}\cup\left(B\setminus B^{\prime}\right)\geq Z\right) (58) = p ϕ ⋅ 𝒟 any ( B ≥ C ) . \displaystyle=p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(B\geq C\right). (59)
Equation 53 and eq. 59 follow by Lemma E.12 ’s item 2 with X ≔ C X\coloneqq C , X ′ ≔ Z X^{\prime}\coloneqq Z . Similarly, eq. 54 follows by Lemma E.12 ’s item 2 with X ≔ A X\coloneqq A , X ′ ≔ ND ( A ) X^{\prime}\coloneqq\text{{ND}}\left(A\right) . Equation 55 follows by applying the first inequality of Lemma E.26 with X ≔ ND ( A ) , Y ≔ Z , Y ′ ≔ Z ∖ ( B ∖ B ′ ) X\coloneqq\text{{ND}}\left(A\right),Y\coloneqq Z,Y^{\prime}\coloneqq Z\setminus(B\setminus B^{\prime}) . Equation 56 follows by applying Lemma E.17 to eq. 53 with permutation ϕ \phi .
Equation 57 follows by our assumptions on ϕ \phi . Equation 58 follows because by applying the second inequality of Lemma E.26 with X ≔ B ′ , Y ≔ ND ( C ) , Y ′ ≔ ND ( C ) ∖ ( B ∖ B ′ ) X\coloneqq B^{\prime},Y\coloneqq\text{{ND}}\left(C\right),Y^{\prime}\coloneqq\text{{ND}}\left(C\right)\setminus(B\setminus B^{\prime}) .
Suppose B ′ = B B^{\prime}=B . Then B ∖ B ′ = ∅ B\setminus B^{\prime}=\emptyset , and so eq. 55 and eq. 58 are trivially equalities. Then eq. 52 is an equality.
Suppose ∃ b < c : ( b , c ) | 𝒮 | ⊆ supp ( 𝒟 any ) \exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\mathcal{D}_{\text{any}}) ; note that ( b , c ) | 𝒮 | ⊆ supp ( ϕ ⋅ 𝒟 any ) (b,c)^{\left|\mathcal{S}\right|}\subseteq\optSupp(\phi\cdot\mathcal{D}_{\text{any}}) , since such support must be invariant to permutation. Further suppose that B ′ ⊆ C B^{\prime}\subseteq C and that ND ( C ) ∩ ( B ∖ B ′ ) \text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right) is non-empty. Then letting X ≔ B ′ , Y ≔ Z , Y ′ ≔ Z ∖ ( B ∖ B ′ ) X\coloneqq B^{\prime},Y\coloneqq Z,Y^{\prime}\coloneqq Z\setminus(B\setminus B^{\prime}) and noting that ND ( ND ( Z ) ) = ND ( Z ) \text{{ND}}\left(\text{{ND}}\left(Z\right)\right)=\text{{ND}}\left(Z\right) , apply Lemma E.26 to eq. 58 to conclude that eq. 52 is strict. ∎
###### Lemma E.28 (Optimality probability superiority lemma) .
Let A , B , C ⊊ ℝ | 𝒮 | A,B,C\subsetneq\mathbb{R}^{\left|\mathcal{S}\right|} be finite, and let Z Z satisfy ND ( C ) ⊆ Z ⊆ C \text{{ND}}\left(C\right)\subseteq Z\subseteq C . If B B contains a copy B ′ B^{\prime} of ND ( A ) \text{{ND}}\left(A\right) via ϕ \phi such that ϕ ⋅ ( Z ∖ ( B ∖ B ′ ) ) = Z ∖ ( B ∖ B ′ ) \phi\cdot\left(Z\setminus\left(B\setminus B^{\prime}\right)\right)=Z\setminus\left(B\setminus B^{\prime}\right) , then p 𝒟 any ( A ≥ C ) ≤ most : 𝔇 any p 𝒟 any ( B ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) .
If B ′ ⊆ C B^{\prime}\subseteq C and ND ( C ) ∩ ( B ∖ B ′ ) \text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right) is non-empty, then the inequality is strict for all 𝒟 X - iid ∈ 𝔇 c/b/ iid \mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}} and p 𝒟 any ( A ≥ C ) ≱ most : 𝔇 any p 𝒟 any ( B ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) .
###### Proof.
Suppose 𝒟 any \mathcal{D}_{\text{any}} is such that p 𝒟 any ( B ≥ C ) < p 𝒟 any ( A ≥ C ) p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)<p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right) . p ϕ ⋅ 𝒟 any ( A ≥ C ) \displaystyle p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(A\geq C\right) = p ϕ − 1 ⋅ 𝒟 any ( A ≥ C ) \displaystyle=p_{\phi^{-1}\cdot\mathcal{D}_{\text{any}}}\left(A\geq C\right) (60) ≤ p 𝒟 any ( B ≥ C ) \displaystyle\leq p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right) (61) < p 𝒟 any ( A ≥ C ) \displaystyle<p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right) (62) ≤ p ϕ ⋅ 𝒟 any ( B ≥ C ) . \displaystyle\leq p_{\phi\cdot\mathcal{D}_{\text{any}}}\left(B\geq C\right). (63)