decision_rule_success_prob_le_vulnerability
For any nonempty alphabet Fin m, nonnegative prior p, probability distribution q on ℤ, and decision rule g : ℤ → Fin m, the success probability of g is at most the posterior Bayes vulnerability.
Statement
lemma decision_rule_success_prob_le_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) (hp_nonneg : ∀ x, 0 ≤ p x) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (g : ℤ → Fin m) : additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q- Source
- arXiv:2611.16066 Proposition 3.1 -- Optimal Additive Integer Masks for One-Guess Vulnerability under an Absolute-Moment Budget
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- additive_noise_success_probThe average one-guess success probability of a decision rule g : ℤ → Fin m for a secret with prior p on Fin m under additive noise with…
- additive_noise_bayes_vulnerabilityThe Bayes vulnerability V(X | S) of a secret X on Fin m with prior p observed under additive noise S = X + Y with integer mask…
- Used by 1
- additive_noise_map_rule_and_bayes_vulnerabilityFor a secret with distribution p on Fin m and independent additive noise Y with distribution q on ℤ, the optimal average one-guess success…
Read back from the Lean
For any positive natural number $m$ (with NeZero m), functions $p : \text{Fin } m \to \mathbb{R}$ and $q : \mathbb{Z} \to \mathbb{R}$, and function $g : \mathbb{Z} \to \text{Fin } m$, if $p(x) \ge 0$ for all $x \in \text{Fin } m$, $q(s) \ge 0$ for all $s \in \mathbb{Z}$, and the infinite sum of $q$ over $\mathbb{Z}$ converges to $1$ (HasSum q 1), then the additive noise success probability with decision rule $g$ is less than or equal to the additive noise Bayes vulnerability:
$$\text{additive\_noise\_success\_prob } m\ p\ q\ g \le \text{additive\_noise\_bayes\_vulnerability } m\ p\ q$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Every decision rule has success probability bounded by the Bayes vulnerability. -/ lemma decision_rule_success_prob_le_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) (hp_nonneg : ∀ x, 0 ≤ p x) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (g : ℤ → Fin m) : additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q := by unfold additive_noise_success_prob additive_noise_bayes_vulnerability have hqsumm : ∀ c : ℤ, Summable (fun s : ℤ => q (s - c)) := by intro c have h := Summable.comp_injective hq_sum.summable (i := fun s : ℤ => s - c) (fun a b hab => by simpa using hab) exact h have hfinsumm : Summable (fun s : ℤ => ∑ x : Fin m, p x * q (s - ↑x)) := by refine summable_sum (fun x _ => ?_) exact Summable.mul_left _ (hqsumm x) have hb_nonneg : ∀ s, 0 ≤ ⨆ x : Fin m, p x * q (s - ↑x) := by intro s exact le_trans (mul_nonneg (hp_nonneg default) (hq_nonneg (s - ↑(default : Fin m)))) (Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) default) have hsup_le_sum : ∀ s, (⨆ x : Fin m, p x * q (s - ↑x)) ≤ ∑ x : Fin m, p x * q (s - ↑x) := by intro s refine ciSup_le (fun x => ?_) simpa using Finset.single_le_sum (f := fun x : Fin m => p x * q (s - ↑x)) (fun i _ => mul_nonneg (hp_nonneg i) (hq_nonneg _)) (Finset.mem_univ x) have hsup_summ : Summable (fun s : ℤ => ⨆ x : Fin m, p x * q (s - ↑x)) := Summable.of_nonneg_of_le hb_nonneg hsup_le_sum hfinsumm have hg_summ : Summable (fun s : ℤ => p (g s) * q (s - ↑(g s))) := Summable.of_nonneg_of_le (fun s => mul_nonneg (hp_nonneg _) (hq_nonneg _)) (fun s => Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) (g s)) hsup_summ exact Summable.tsum_le_tsum (fun s => Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) (g s)) hg_summ hsup_summ