Parametrically Retargetable Decision-Makers Tend To Seek Power — part 8/13

Cleaned-text code points [108618, 124362). Bibliography omitted here; source.md includes it.

Item 3 . Apply the reasoning in item 1 with inner function h ( X ∣ C , 𝐮 ) ≔ 𝟙 ∃ 𝐱 ∈ X : ∀ 𝐜 ∈ C : 𝐱 ⊤ ​ 𝐮 ≤ 𝐜 ⊤ ​ 𝐮 h(X\mid C,\mathbf{u})\coloneqq\mathbbm{1}_{\exists\mathbf{x}\in X\mathrel{\mathop{\ordinarycolon}}\forall\mathbf{c}\in C\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\top}\mathbf{u}\leq\mathbf{c}^{\top}\mathbf{u}} .

Item 4 . Let X ⊆ C X\subseteq C . Boltzmann T ​ ( X ∣ C , 𝐮 ) \mathrm{Boltzmann}_{T}\left(X\mid C,\mathbf{u}\right) is the expectation of an EU function: Boltzmann T ​ ( X ∣ C , 𝐮 ) \displaystyle\mathrm{Boltzmann}_{T}\left(X\mid C,\mathbf{u}\right) = g T ​ ( [ 𝐱 ⊤ ​ 𝐮 ] 𝐱 ∈ X ⏞ V X , [ 𝐜 ⊤ ​ 𝐮 ] 𝐜 ∈ C ⏞ V C ) \displaystyle=g_{T}\left(\overbrace{\left[\mathbf{x}^{\top}\mathbf{u}\right]_{\mathbf{x}\in X}}^{V_{X}},\overbrace{\left[\mathbf{c}^{\top}\mathbf{u}\right]_{\mathbf{c}\in C}}^{V_{C}}\right) (60) ≔ ∑ v ∈ V X e v / T ∑ v ∈ V C e v / T . \displaystyle\coloneqq\frac{\sum_{v\in V_{X}}e^{v/T}}{\sum_{v\in V_{C}}e^{v/T}}. (61) Therefore, by Lemma B.11 , Boltzmann T ​ ( X ∣ C , 𝐮 ) \mathrm{Boltzmann}_{T}\left(X\mid C,\mathbf{u}\right) is invariant to joint permutation by the ϕ i \phi_{i} .

Inspecting eq. 61 , we see that g g is continuous on 𝐮 \mathbf{u} (and therefore measurable), and bounded [ 0 , 1 ] [0,1] since X ⊆ C X\subseteq C and the exponential function is positive. Therefore, by Lemma B.5 , the expectation version is also invariant to joint permutation for all permutations ϕ ∈ S d \phi\in S_{d} : Boltzmann T ​ ( X ∣ C , 𝒟 any ) = Boltzmann T ​ ( ϕ ⋅ X ∣ ϕ ⋅ C , ϕ ⋅ 𝒟 any ) \mathrm{Boltzmann}_{T}\left(X\mid C,\mathcal{D}_{\text{any}}\right)=\mathrm{Boltzmann}_{T}\left(\phi\cdot X\mid\phi\cdot C,\phi\cdot\mathcal{D}_{\text{any}}\right) .

Since ϕ i ⋅ C = C \phi_{i}\cdot C=C , Lemma B.10 shows that f ⁡ ( X ∣ 𝒟 any ) ≔ Boltzmann T ​ ( X ∣ C , 𝒟 any ) f(X\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{Boltzmann}_{T}\left(X\mid C,\mathcal{D}_{\text{any}}\right) is also invariant under joint permutation by the ϕ i \phi_{i} . Furthermore, if X ′ ⊆ X X^{\prime}\subseteq X , then f ⁡ ( X ′ ∣ 𝒟 any ) ≤ f ⁡ ( X ∣ 𝒟 any ) f(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f(X\mid\mathcal{D}_{\text{any}}) . Then apply Lemma B.9 to conclude that Boltzmann T ( B ∣ C , 𝒟 any ) ≕ f ( B ∣ 𝒟 any ) ≥ most : 𝔇 any n f ( A ∣ 𝒟 any ) ≔ Boltzmann T ( A ∣ C , 𝒟 any ) \mathrm{Boltzmann}_{T}\left(B\mid C,\mathcal{D}_{\text{any}}\right)\eqqcolon f(B\mid\mathcal{D}_{\text{any}})\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}f(A\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{Boltzmann}_{T}\left(A\mid C,\mathcal{D}_{\text{any}}\right) .

Item 5 . Let involution ϕ ∈ S d \phi\in S_{d} fix C C ( i . e ., ϕ ⋅ C = C \phi\cdot C=C ). best-of- ​ k ​ ( X ∣ C , 𝐮 ) \displaystyle\textrm{best-of-}k(X\mid C,\mathbf{u}) (62) ≔ 𝔼 𝐚 1 , … , 𝐚 k ∼ unif ​ ( C ) [ FracOptimal ⁡ ( X ∩ { 𝐚 1 , … , 𝐚 k } ∣ { 𝐚 1 , … , 𝐚 k } , 𝐮 ) ] \displaystyle\coloneqq\!\!\opE_{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\sim\text{unif}(C)}\left[\mathrm{FracOptimal}\left(X\cap\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\}\mid\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\},\mathbf{u}\right)\right] (63) = 𝔼 𝐚 1 , … , 𝐚 k ∼ unif ​ ( C ) [ FracOptimal ⁡ ( ( ϕ ⋅ X ) ∩ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } ∣ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } , ϕ ⋅ 𝐮 ) ] \displaystyle=\!\!\opE_{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\sim\text{unif}(C)}\left[\mathrm{FracOptimal}\left((\phi\cdot X)\cap\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\}\!\mid\!\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\},\phi\cdot\mathbf{u}\right)\right] (64) = 𝔼 ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k ∼ unif ​ ( ϕ ⋅ C ) [ FracOptimal ⁡ ( ( ϕ ⋅ X ) ∩ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } ∣ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } , ϕ ⋅ 𝐮 ) ] \displaystyle=\!\!\opE_{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\sim\text{unif}(\phi\cdot C)}\left[\mathrm{FracOptimal}\left((\phi\cdot X)\cap\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\}\!\mid\!\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\},\phi\cdot\mathbf{u}\right)\right] (65) ≕ best-of- ​ k ​ ( ϕ ⋅ X ∣ ϕ ⋅ C , ϕ ⋅ 𝐮 ) . \displaystyle\eqqcolon\textrm{best-of-}k(\phi\cdot X\mid\phi\cdot C,\phi\cdot\mathbf{u}). (66) By the proof of item 2 , FracOptimal ⁡ ( X ∩ { 𝐚 1 , … , 𝐚 k } ∣ { 𝐚 1 , … , 𝐚 k } , 𝐮 ) = FracOptimal ⁡ ( ( ϕ ⋅ X ) ∩ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } ∣ { ϕ ⋅ 𝐚 1 , … , ϕ ⋅ 𝐚 k } , ϕ ⋅ 𝐮 ) ; \mathrm{FracOptimal}\left(X\cap\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\}\mid\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\},\mathbf{u}\right)=\\ \mathrm{FracOptimal}\left((\phi\cdot X)\cap\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\}\mid\{\phi\cdot\mathbf{a}_{1},\ldots,\phi\cdot\mathbf{a}_{k}\},\phi\cdot\mathbf{u}\right); thus, eq. 64 holds. Since ϕ ⋅ C = C \phi\cdot C=C and since the distribution is uniform, eq. 65 holds. Therefore, best-of- ​ k ​ ( X ∣ C , 𝐮 ) \textrm{best-of-}k(X\mid C,\mathbf{u}) is invariant to joint permutation by the ϕ i \phi_{i} , which are involutions fixing C C .

We now show that best-of- ​ k ​ ( X ∣ C , 𝐮 ) \textrm{best-of-}k(X\mid C,\mathbf{u}) is measurable on 𝐮 \mathbf{u} . best-of- ​ k ​ ( X ∣ C , 𝐮 ) \displaystyle\textrm{best-of-}k(X\mid C,\mathbf{u}) (67) ≔ 𝔼 𝐚 1 , … , 𝐚 k ∼ unif ​ ( C ) [ FracOptimal ⁡ ( X ∩ { 𝐚 1 , … , 𝐚 k } ∣ { 𝐚 1 , … , 𝐚 k } , 𝐮 ) ] \displaystyle\coloneqq\opE_{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\sim\text{unif}(C)}\left[\mathrm{FracOptimal}\left(X\cap\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\}\mid\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\},\mathbf{u}\right)\right] (68) = 1 | C | k ​ ∑ ( 𝐚 1 , … , 𝐚 k ) ∈ C k FracOptimal ⁡ ( X ∩ { 𝐚 1 , … , 𝐚 k } ∣ { 𝐚 1 , … , 𝐚 k } , 𝐮 ) . \displaystyle=\frac{1}{\left|C\right|^{k}}\sum_{\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\right)\in C^{k}}\mathrm{FracOptimal}\left(X\cap\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\}\mid\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\},\mathbf{u}\right). (69) Equation 69 holds because FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is measurable on 𝐮 \mathbf{u} by item 2 , and measurable functions are closed under finite addition and scalar multiplication. Then best-of- ​ k ​ ( X ∣ C , 𝐮 ) \textrm{best-of-}k(X\mid C,\mathbf{u}) is measurable on 𝐮 \mathbf{u} .

Let g ⁡ ( X ∣ 𝐮 ) ≔ best-of- ​ k ​ ( X ∣ C , 𝐮 ) g(X\mid\mathbf{u})\coloneqq\textrm{best-of-}k(X\mid C,\mathbf{u}) . Since ϕ i ⋅ C = C \phi_{i}\cdot C=C , Lemma B.10 shows that g ⁡ ( X ∣ 𝐮 ) g(X\mid\mathbf{u}) is also invariant to joint permutation by ϕ i \phi_{i} . Since g g is measurable and bounded [ 0 , 1 ] [0,1] , apply Lemma B.5 to conclude that f ⁡ ( X ∣ 𝒟 any ) ≔ 𝔼 𝐮 ∼ 𝒟 any [ g ⁡ ( X ∣ C , 𝐮 ) ] f(X\mid\mathcal{D}_{\text{any}})\coloneqq\opE_{\mathbf{u}\sim\mathcal{D}_{\text{any}}}\left[g(X\mid C,\mathbf{u})\right] is also invariant to joint permutation by ϕ i \phi_{i} .

Furthermore, if X ′ ⊆ X ⊆ C X^{\prime}\subseteq X\subseteq C , then f ⁡ ( X ′ ∣ 𝒟 any ) ≤ f ⁡ ( X ∣ 𝒟 any ) f(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f(X\mid\mathcal{D}_{\text{any}}) . So apply Lemma B.9 to conclude that best-of- k ( B ∣ C , 𝒟 any ) ≕ f ( B ∣ 𝒟 any ) ≥ most : 𝔇 any n f ( A ∣ 𝒟 any ) ≔ best-of- k ( A ∣ C , 𝒟 any ) \textrm{best-of-}k(B\mid C,\mathcal{D}_{\text{any}})\eqqcolon f(B\mid\mathcal{D}_{\text{any}})\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}f(A\mid\mathcal{D}_{\text{any}})\coloneqq\textrm{best-of-}k(A\mid C,\mathcal{D}_{\text{any}}) .

Item 6 . Satisfice t ​ ( X ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) is an EU-determined function: Satisfice t ​ ( X ∣ C , 𝐮 ) \displaystyle\mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) = g t ​ ( [ 𝐱 ⊤ ​ 𝐮 ] 𝐱 ∈ X ⏞ V X , [ 𝐜 ⊤ ​ 𝐮 ] 𝐜 ∈ C ⏞ V C ) \displaystyle=g_{t}\left(\overbrace{\left[\mathbf{x}^{\top}\mathbf{u}\right]_{\mathbf{x}\in X}}^{V_{X}},\overbrace{\left[\mathbf{c}^{\top}\mathbf{u}\right]_{\mathbf{c}\in C}}^{V_{C}}\right) (70) ≔ ∑ v ∈ V X 𝟙 v ≥ t ∑ v ∈ V C 𝟙 v ≥ t , \displaystyle\coloneqq\frac{\sum_{v\in V_{X}}\mathbbm{1}_{v\geq t}}{\sum_{v\in V_{C}}\mathbbm{1}_{v\geq t}}, (71) with the function evaluating to 0 0 if the denominator is 0 0 . Then applying Lemma B.11 , Satisfice t ​ ( X ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) is invariant under joint permutation by the ϕ i \phi_{i} .

We now show that Satisfice t ​ ( X ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) is measurable on 𝐮 \mathbf{u} . Satisfice t ​ ( X ∣ C , 𝐮 ) \displaystyle\mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) = { ∑ 𝐱 ∈ X 𝟙 𝐱 ∈ { 𝐱 ′ ∈ ℝ d ∣ 𝐱 ′ ⁣ ⊤ ​ 𝐮 ≥ t } ∑ 𝐜 ∈ C 𝟙 𝐜 ∈ { 𝐱 ′ ∈ ℝ d ∣ 𝐱 ′ ⁣ ⊤ ​ 𝐮 ≥ t } ∃ 𝐜 ∈ C : 𝐜 ⊤ ​ 𝐮 ≥ t , 0 else . \displaystyle=\begin{cases}\frac{\sum_{\mathbf{x}\in X}\mathbbm{1}_{\mathbf{x}\in\left\{\mathbf{x}^{\prime}\in\mathbb{R}^{d}\mid\mathbf{x}^{\prime\top}\mathbf{u}\geq t\right\}}}{\sum_{\mathbf{c}\in C}\mathbbm{1}_{\mathbf{c}\in\left\{\mathbf{x}^{\prime}\in\mathbb{R}^{d}\mid\mathbf{x}^{\prime\top}\mathbf{u}\geq t\right\}}}&\exists\mathbf{c}\in C\mathrel{\mathop{\ordinarycolon}}\mathbf{c}^{\top}\mathbf{u}\geq t,\\ 0&\text{ else}.\end{cases} (72) Consider the two cases. ∃ 𝐜 ∈ C : 𝐜 ⊤ ​ 𝐮 ≥ t ⇔ 𝐮 ∈ ⋃ 𝐜 ∈ C { 𝐮 ′ ∈ ℝ d ∣ 𝐜 ⊤ ​ 𝐮 ≥ t } . \exists\mathbf{c}\in C\mathrel{\mathop{\ordinarycolon}}\mathbf{c}^{\top}\mathbf{u}\geq t\iff\mathbf{u}\in\bigcup_{\mathbf{c}\in C}\left\{\mathbf{u}^{\prime}\in\mathbb{R}^{d}\mid\mathbf{c}^{\top}\mathbf{u}\geq t\right\}. The right-hand set is the union of finitely many halfspaces (which are measurable), and so the right-hand set is also measurable. Then the casing is a measurable function of 𝐮 \mathbf{u} . Clearly the zero function is measurable. Now we turn to the first case.

In the first case, eq. 72 ’s indicator functions test each 𝐱 , 𝐜 \mathbf{x},\mathbf{c} for membership in a closed halfspace with respect to 𝐮 \mathbf{u} . Halfspaces are measurable sets. Therefore, the indicator function is a measurable function of 𝐮 \mathbf{u} , and so are the finite sums. Since the denominator does not vanish within the case, the first case as a whole is a measurable function of 𝐮 \mathbf{u} . Therefore, Satisfice t ​ ( X ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) is measurable on 𝐮 \mathbf{u} .

Since Satisfice t ​ ( X ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathbf{u}\right) is measurable and bounded [ 0 , 1 ] [0,1] (as X ⊆ C X\subseteq C ), apply Lemma B.5 to conclude that Satisfice t ​ ( X ∣ C , 𝒟 any ) = Satisfice t ​ ( ϕ ⋅ X ∣ ϕ ⋅ C , ϕ ⋅ 𝒟 any ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathcal{D}_{\text{any}}\right)=\mathrm{Satisfice}_{t}\left(\phi\cdot X\mid\phi\cdot C,\phi\cdot\mathcal{D}_{\text{any}}\right) . Next, let f ⁡ ( X ∣ 𝒟 any ) ≔ Satisfice t ​ ( X ∣ C , 𝒟 any ) f(X\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{Satisfice}_{t}\left(X\mid C,\mathcal{D}_{\text{any}}\right) . Since we just showed that Satisfice t ​ ( X ∣ C , 𝒟 any ) \mathrm{Satisfice}_{t}\left(X\mid C,\mathcal{D}_{\text{any}}\right) is invariant to joint permutation by the involutions ϕ i \phi_{i} and since ϕ i ⋅ C = C \phi_{i}\cdot C=C , f ⁡ ( X ∣ 𝒟 any ) f(X\mid\mathcal{D}_{\text{any}}) is also invariant to joint permutation by ϕ i \phi_{i} .

Furthermore, if X ′ ⊆ X X^{\prime}\subseteq X , we have f ⁡ ( X ′ ∣ 𝒟 any ) ≤ f ⁡ ( X ∣ 𝒟 any ) f(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f(X\mid\mathcal{D}_{\text{any}}) . Then applying Lemma B.9 , Satisfice t ( B ∣ C , 𝐮 ) ≕ f ( B ∣ 𝒟 any ) ≥ most : 𝔇 any n f ( A ∣ 𝒟 any ) ≔ Satisfice t ( A ∣ C , 𝐮 ) \mathrm{Satisfice}_{t}\left(B\mid C,\mathbf{u}\right)\eqqcolon f(B\mid\mathcal{D}_{\text{any}})\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}f(A\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{Satisfice}_{t}\left(A\mid C,\mathbf{u}\right) .

Item 7 . Suppose P P is uniform over C C and consider any of the involutions ϕ i \phi_{i} . M q , P ​ ( C ∣ 𝐮 ) \displaystyle M_{q,P}(C\mid\mathbf{u}) ≔ inf { M ∈ ℝ ∣ ℙ 𝐱 ∼ P ( 𝐱 ⊤ ​ 𝐮 > M ) ≤ q } \displaystyle\coloneqq\inf\left\{M\in\mathbb{R}\mid\Prb_{\mathbf{x}\sim P}\left(\mathbf{x}^{\top}\mathbf{u}>M\right)\leq q\right\} (73) = inf { M ∈ ℝ ∣ ℙ 𝐱 ∼ P ( ( 𝐏 ϕ i ​ 𝐱 ) ⊤ ​ ( 𝐏 ϕ i ​ 𝐮 ) > M ) ≤ q } \displaystyle=\inf\left\{M\in\mathbb{R}\mid\Prb_{\mathbf{x}\sim P}\left((\mathbf{P}_{\phi_{i}}\mathbf{x})^{\top}(\mathbf{P}_{\phi_{i}}\mathbf{u})>M\right)\leq q\right\} (74) = inf { M ∈ ℝ ∣ ℙ 𝐱 ∼ ϕ i ⋅ P ( 𝐱 ⊤ ​ ( 𝐏 ϕ i ​ 𝐮 ) > M ) ≤ q } \displaystyle=\inf\left\{M\in\mathbb{R}\mid\Prb_{\mathbf{x}\sim\phi_{i}\cdot P}\left(\mathbf{x}^{\top}(\mathbf{P}_{\phi_{i}}\mathbf{u})>M\right)\leq q\right\} (75) = inf { M ∈ ℝ ∣ ℙ 𝐱 ∼ P ( 𝐱 ⊤ ​ ( 𝐏 ϕ i ​ 𝐮 ) > M ) ≤ q } \displaystyle=\inf\left\{M\in\mathbb{R}\mid\Prb_{\mathbf{x}\sim P}\left(\mathbf{x}^{\top}(\mathbf{P}_{\phi_{i}}\mathbf{u})>M\right)\leq q\right\} (76) ≕ M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) . \displaystyle\eqqcolon M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u}). (77) Equation 74 follows by the orthogonality of permutation matrices. Equation 76 follows because if 𝐱 ∈ supp ⁡ ( P ) = C \mathbf{x}\in\optSupp(P)=C , then ϕ i ⋅ 𝐱 ∈ C = supp ⁡ ( P ) \phi_{i}\cdot\mathbf{x}\in C=\optSupp(P) , and furthermore P ⁡ ( 𝐱 ) = P ⁡ ( 𝐏 ϕ i ​ 𝐱 ) P(\mathbf{x})=P(\mathbf{P}_{\phi_{i}}\mathbf{x}) by uniformity.

Now we show the invariance of C > M q , P ​ ( C ∣ 𝐮 ) C_{>M_{q,P}(C\mid\mathbf{u})} under joint permutation by ϕ i \phi_{i} : C > M q , P ​ ( C ∣ 𝐮 ) \displaystyle C_{>M_{q,P}(C\mid\mathbf{u})} ≔ { 𝐜 ∈ C ∣ 𝐜 ⊤ ​ 𝐮 > M q , P ​ ( C ∣ 𝐮 ) } \displaystyle\coloneqq\left\{\mathbf{c}\in C\mid\mathbf{c}^{\top}\mathbf{u}>M_{q,P}(C\mid\mathbf{u})\right\} (78) = { 𝐜 ∈ C ∣ ( 𝐏 ϕ i ​ 𝐜 ) ⊤ ​ ( 𝐏 ϕ i ​ 𝐮 ) > M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) } \displaystyle=\left\{\mathbf{c}\in C\mid(\mathbf{P}_{\phi_{i}}\mathbf{c})^{\top}(\mathbf{P}_{\phi_{i}}\mathbf{u})>M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u})\right\} (79) = { 𝐜 ∈ ϕ i ⋅ C ∣ 𝐜 ⊤ ​ ( 𝐏 ϕ i ​ 𝐮 ) > M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) } \displaystyle=\left\{\mathbf{c}\in\phi_{i}\cdot C\mid\mathbf{c}^{\top}(\mathbf{P}_{\phi_{i}}\mathbf{u})>M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u})\right\} (80) ≕ C > M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) . \displaystyle\eqqcolon C_{>M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u})}. (81) Equation 79 follows by the orthogonality of permutation matrices and because M q , P ​ ( C ∣ 𝐮 ) = M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) M_{q,P}(C\mid\mathbf{u})=M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u}) by eq. 77 . A similar proof shows that C = M q , P ​ ( C ∣ 𝐮 ) = C = M q , P ​ ( ϕ i ⋅ C ∣ ϕ i ⋅ 𝐮 ) C_{=M_{q,P}(C\mid\mathbf{u})}=C_{=M_{q,P}(\phi_{i}\cdot C\mid\phi_{i}\cdot\mathbf{u})} .

Recall that Q q , P ​ ( X ∣ C , 𝐮 ) ≔ ∑ 𝐱 ∈ X P ⁡ ( 𝐱 ) q ​ ( 𝟙 𝐱 ∈ C > M q , P ​ ( C ∣ 𝐮 ) + 𝟙 𝐱 ∈ C = M q , P ​ ( C ∣ 𝐮 ) P ⁡ ( C = M q , P ​ ( C ∣ 𝐮 ) ) ​ ( q − P ⁡ ( C > M q , P ​ ( C ∣ 𝐮 ) ) ) ) . \displaystyle Q_{q,P}(X\mid C,\mathbf{u})\coloneqq\sum_{\mathbf{x}\in X}\frac{P(\mathbf{x})}{q}\left(\mathbbm{1}_{\mathbf{x}\in C_{>M_{q,P}(C\mid\mathbf{u})}}+\frac{\mathbbm{1}_{\mathbf{x}\in C_{=M_{q,P}(C\mid\mathbf{u})}}}{P\left(C_{=M_{q,P}(C\mid\mathbf{u})}\right)}\left(q-P\left(C_{>M_{q,P}(C\mid\mathbf{u})}\right)\right)\right). (82) Q q , P ​ ( X ∣ C , 𝐮 ) = Q q , P ​ ( ϕ i ⋅ X ∣ ϕ i ⋅ C , ϕ i ⋅ 𝐮 ) Q_{q,P}(X\mid C,\mathbf{u})=Q_{q,P}(\phi_{i}\cdot X\mid\phi_{i}\cdot C,\phi_{i}\cdot\mathbf{u}) , since Q Q is the sum of products of ϕ i \phi_{i} -invariant quantities.

P ⁡ ( 𝐱 ) P(\mathbf{x}) is non-negative because P P is a probability distribution, and q q is assumed positive. The indicator functions 𝟙 \mathbbm{1} are non-negative. By the definition of M q , P M_{q,P} , P ⁡ ( C > M q , P ​ ( C ∣ 𝐮 ) ) ≤ q P\left(C_{>M_{q,P}(C\mid\mathbf{u})}\right)\leq q . Therefore, eq. 82 is the sum of non-negative terms. Thus, if X ′ ⊆ X X^{\prime}\subseteq X , then Q q , P ​ ( X ′ ∣ C , 𝐮 ) ≤ Q q , P ​ ( X ∣ C , 𝐮 ) Q_{q,P}(X^{\prime}\mid C,\mathbf{u})\leq Q_{q,P}(X\mid C,\mathbf{u}) .