biased_bit_vulnerability_ge_one_sub_mul_moment
For 1/2 < p < 1 and any probability distribution q on ℤ with finite absolute first moment, the one-guess vulnerability satisfies V_p(q) ≥ 1 - p * E[|Y|].
Statement
theorem biased_bit_vulnerability_ge_one_sub_mul_moment (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (hq_mom : Summable (fun s : ℤ => |(s : ℝ)| * q s)) : biased_bit_vulnerability p q ≥ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s)
- Source
- arXiv:2611.16066, Theorem 5.5
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- biased_bit_vulnerabilityThe one-guess vulnerability V_p(q) of an additive integer mask with distribution q against a secret bit with bias p ∈ (1/2, 1) is the…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- biased_bit_cost_vulnerability_initial_segmentFor real numbers p and c satisfying 1 / 2 < p, p < 1, 0 ≤ c, and c ≤ 1 - p, the optimal vulnerability biased_bit_optimal_vulnerability p c…
Read back from the Lean
For any real number $p$ such that $1/2 < p < 1$ and any function $q : \mathbb{Z} \to \mathbb{R}$ satisfying:
1. $q(s) \ge 0$ for all $s \in \mathbb{Z}$,
2. $\sum_{s \in \mathbb{Z}} q(s) = 1$ (specifically, HasSum q 1), and
3. the sequence $s \mapsto |s| q(s)$ is summable over $\mathbb{Z}$,
the biased bit vulnerability biased_bit_vulnerability p q is greater than or equal to $1 - p \sum_{s \in \mathbb{Z}} |s| q(s)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes a lower bound on the one-guess vulnerability V_p(q) = ∑_{s ∈ ℤ} max(p q(s), (1 - p) q(s - 1)) by replacing the pointwise maximum with a suboptimal decision rule g(s): choose the branch p q(s) when s ≤ 0 and (1 - p) q(s - 1) when s > 0. Summing g(s) over ℤ and reindexing yields 1 - p P(S > 0) - (1 - p) P(S < 0). Because p > 1/2, the coefficient 1 - p is strictly smaller than p, allowing the sum to be bounded from below by 1 - p P(S ≠ 0). Finally, Markov's bound on the non-zero probability P(S ≠ 0) ≤ E[|S|] produces the desired bound 1 - p E[|S|].
The goal reduces to proving 1 - p * ∑_{s ∈ ℤ} |s| q(s) ≤ ∑_{s ∈ ℤ} max(p q(s), (1 - p) q(s - 1)), with 0 < p and 0 ≤ 1 - p.
Unfolding the definition of biased_bit_vulnerability reformulates the target inequality as bounding the infinite sum of the pointwise maximum from below. Linear arithmetic on 1/2 < p < 1 yields 0 < p and 0 ≤ 1 - p.
change (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) have hp0 : 0 < p := by linarith have h1p : 0 ≤ 1 - p := by linarith
The distribution q, its shift s ↦ q(s - 1), and its indicator restrictions to non-positive, positive, strictly negative, non-negative, and non-zero integers are all summable.
The series ∑ q(s) converges by assumption. Shifting indices preserves summability since s ↦ s - 1 is injective. Each indicator restriction is non-negative and bounded pointwise by either q or the shifted sequence, so all restricted series converge by the comparison test (Summable.of_nonneg_of_le).
uses
Summable.of_nonneg_of_le,le_rflhave hq : Summable q := hq_sum.summable have hqshift : Summable (fun s : ℤ => q (s - 1)) := hq.comp_injective (fun a b hab => by simpa using hab) have hqm : Summable (fun s : ℤ => if s ≤ 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqpos : Summable (fun s : ℤ => if 0 < s then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqneg : Summable (fun s : ℤ => if s < 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqge : Summable (fun s : ℤ => if 0 ≤ s then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqnz : Summable (fun s : ℤ => if s ≠ 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqsh : Summable (fun s : ℤ => if 0 < s then q (s - 1) else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hqshift · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg (s - 1)
The probability sums satisfy ∑_{s ≤ 0} q(s) = 1 - ∑_{s > 0} q(s) and ∑_{s ≥ 0} q(s) = 1 - ∑_{s < 0} q(s), while reindexing gives ∑_{s > 0} q(s - 1) = ∑_{s ≥ 0} q(s).
Because {s ≤ 0} and {0 < s} partition ℤ and the total sum of q is 1, additivity of convergent series shows that the non-positive sum is 1 minus the positive sum. The same reasoning partitions ℤ into {0 ≤ s} and {s < 0}. Substituting t = s - 1 via the bijection Equiv.subRight 1 maps the condition 0 < s to 0 ≤ t, establishing the equivalence of the shifted sum with the non-negative sum (Equiv.tsum_eq).
uses
Equiv.tsum_eq,Equiv.subRight,Equiv.subRight_apply,if_pos,if_neghave hqm_split : (∑' s : ℤ, if s ≤ 0 then q s else 0) = 1 - ∑' s : ℤ, (if 0 < s then q s else 0) := by have heq : (fun s : ℤ => (if s ≤ 0 then q s else 0) + (if 0 < s then q s else 0)) = q := by funext s by_cases h : s ≤ 0 · simp [h, not_lt.mpr h] · simp [h, not_le.mp h] have h := hqm.tsum_add hqpos rw [heq, hq_sum.tsum_eq] at h linarith have hqge_split : (∑' s : ℤ, if 0 ≤ s then q s else 0) = 1 - ∑' s : ℤ, (if s < 0 then q s else 0) := by have heq : (fun s : ℤ => (if 0 ≤ s then q s else 0) + (if s < 0 then q s else 0)) = q := by funext s by_cases h : 0 ≤ s · simp [h, not_lt.mpr h] · simp [h, not_le.mp h] have h := hqge.tsum_add hqneg rw [heq, hq_sum.tsum_eq] at h linarith have hqsh_eq : (∑' s : ℤ, if 0 < s then q (s - 1) else 0) = (∑' s : ℤ, if 0 ≤ s then q s else 0) := by have h := Equiv.tsum_eq (Equiv.subRight (1:ℤ)) (fun t : ℤ => if 0 ≤ t then q t else 0) rw [← h] congr 1 funext s simp only [Equiv.subRight_apply] by_cases hs : 0 < s · rw [if_pos hs, if_pos (show (0:ℤ) ≤ s - 1 from by omega)] · rw [if_neg hs, if_neg (show ¬ (0:ℤ) ≤ s - 1 from by omega)]
The probability of the non-zero integers splits into the positive and negative parts and is bounded above by the absolute first moment: ∑_{s ≠ 0} q(s) ≤ ∑_{s ∈ ℤ} |s| q(s).
By trichotomy (lt_trichotomy), non-zero integers partition into positive and negative integers. For any non-zero integer s, |s| ≥ 1 (Int.one_le_abs). Since q(s) ≥ 0, we have q(s) ≤ |s| q(s) for all s ≠ 0 (and 0 ≤ 0 at s = 0). Summing term-by-term (Summable.tsum_le_tsum) bounds the non-zero probability by the absolute first moment.
uses
lt_trichotomy,le_of_lt,ne_of_lt,ne_of_gt,Summable.tsum_le_tsum,Int.cast_abs,Int.one_le_abs,mul_le_mul_of_nonneg_righthave hqnz_split : (∑' s : ℤ, if s ≠ 0 then q s else 0) = (∑' s : ℤ, if 0 < s then q s else 0) + (∑' s : ℤ, if s < 0 then q s else 0) := by rw [← hqpos.tsum_add hqneg] congr 1 funext s rcases lt_trichotomy s 0 with h | h | h · rw [if_neg (not_lt.mpr (le_of_lt h)), if_pos h, if_pos (ne_of_lt h)]; ring · subst h; simp · rw [if_pos h, if_neg (not_lt.mpr (le_of_lt h)), if_pos (ne_of_gt h)]; ring have hqnz_le : (∑' s : ℤ, if s ≠ 0 then q s else 0) ≤ (∑' s : ℤ, |(s:ℝ)| * q s) := by apply Summable.tsum_le_tsum (fun s => ?_) hqnz hq_mom by_cases h : s = 0 · subst h; simp · rw [if_pos h] have h1 : (1:ℝ) ≤ |(s:ℝ)| := by rw [← Int.cast_abs] have := Int.one_le_abs h exact_mod_cast this calc q s = 1 * q s := by ring _ ≤ |(s:ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s)
The piecewise test function g(s) = if s ≤ 0 then p * q(s) else (1 - p) * q(s - 1) is summable and its sum is bounded above by the vulnerability sum ∑_{s ∈ ℤ} max(p q(s), (1 - p) q(s - 1)).
The test function g is decomposed as the sum of two scaled, convergent indicator series, making it summable. The pointwise maximum is non-negative and bounded above by p * q(s) + (1 - p) * q(s - 1), so it is also summable (Summable.of_nonneg_of_le). Since g(s) ≤ max(p q(s), (1 - p) q(s - 1)) holds for all s (le_max_left, le_max_right), the sum of g lower-bounds the vulnerability sum (Summable.tsum_le_tsum).
uses
Summable.of_nonneg_of_le,mul_nonneg,le_trans,le_max_left,max_le,le_add_of_nonneg_right,le_add_of_nonneg_left,le_max_right,Summable.tsum_le_tsum,if_pos,if_neghave hpt : (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = (fun s : ℤ => p * (if s ≤ 0 then q s else 0) + (1 - p) * (if 0 < s then q (s - 1) else 0)) := by funext s by_cases h : s ≤ 0 · rw [if_pos h, if_pos h, if_neg (not_lt.mpr h)]; ring · rw [if_neg h, if_neg h, if_pos (not_le.mp h)]; ring have hsumm_g : Summable (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := by rw [hpt] exact (hqm.mul_left p).add (hqsh.mul_left (1 - p)) have hsumm_max : Summable (fun s : ℤ => max (p * q s) ((1 - p) * q (s - 1))) := by have hrhs : Summable (fun s : ℤ => p * q s + (1 - p) * q (s - 1)) := (hq.mul_left p).add (hqshift.mul_left (1 - p)) apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hrhs · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s) exact le_trans ha (le_max_left _ _) · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s) have hb : 0 ≤ (1 - p) * q (s - 1) := mul_nonneg h1p (hq_nonneg (s - 1)) exact max_le (le_add_of_nonneg_right hb) (le_add_of_nonneg_left ha) have h_g_max : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := by apply Summable.tsum_le_tsum (fun s => ?_) hsumm_g hsumm_max by_cases h : s ≤ 0 · rw [if_pos h]; exact le_max_left _ _ · rw [if_neg h]; exact le_max_right _ _
The sum of the test function evaluates to p * (1 - ∑_{s > 0} q(s)) + (1 - p) * (1 - ∑_{s < 0} q(s)), which is at least 1 - p * ∑_{s ∈ ℤ} |s| q(s), concluding the proof.
Factoring constants out of the sum of g gives p * ∑_{s ≤ 0} q(s) + (1 - p) * ∑_{s > 0} q(s - 1), which rewrites to p * (1 - ∑_{s > 0} q(s)) + (1 - p) * (1 - ∑_{s < 0} q(s)) = 1 - p * ∑_{s > 0} q(s) - (1 - p) * ∑_{s < 0} q(s). Since p > 1/2, 1 - p < p, so replacing 1 - p with p decreases the expression to 1 - p * ∑_{s ≠ 0} q(s) ≥ 1 - p * E[|Y|]. Chaining these inequalities with the lower bound on the vulnerability completes the theorem.
uses
tsum_mul_left,tsum_nonneghave h_tsum_g : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = p * (∑' s : ℤ, if s ≤ 0 then q s else 0) + (1 - p) * (∑' s : ℤ, if 0 < s then q (s - 1) else 0) := by rw [hpt, (hqm.mul_left p).tsum_add (hqsh.mul_left (1 - p)), tsum_mul_left, tsum_mul_left] have h_g_value : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by rw [h_tsum_g, hqm_split, hqsh_eq, hqge_split] have hPn0 : 0 ≤ (∑' s : ℤ, (if s < 0 then q s else 0)) := tsum_nonneg (fun s => by split_ifs <;> simp [hq_nonneg]) have hkey : (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by nlinarith [hqnz_split, hqnz_le, hPn0, hp, hp1] calc (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := hkey _ = (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := h_g_value.symm _ ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := h_g_max
lt_trichotomy- In a linearly ordered type, any two elements satisfy a < b, a = b, or b < a.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
ne_of_lt- A strict inequality a < b implies a ≠ b.
ne_of_gt- A strict inequality b < a implies a ≠ b.
Equiv.tsum_eq- Reindexing an infinite series by a bijection preserves its sum.
Equiv.subRight- The bijection on an additive group given by subtracting a constant on the right (x ↦ x - a).
Equiv.subRight_apply- Evaluating the subtraction bijection Equiv.subRight a at b yields b - a.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
Summable.tsum_le_tsum- Pointwise inequality between two summable functions implies the same inequality between their infinite sums.
Int.cast_abs- The real cast of the absolute value of an integer equals the absolute value of the cast integer.
Int.one_le_abs- Any non-zero integer has absolute value at least 1.
mul_le_mul_of_nonneg_right- Multiplying an inequality on the right by a non-negative quantity preserves the inequality.
mul_nonneg- The product of two non-negative numbers is non-negative.
le_trans- The inequality relation is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_max_left- Any element a is at most max(a, b).
le_max_right- Any element b is at most max(a, b).
max_le- If a ≤ c and b ≤ c, then max(a, b) ≤ c.
le_add_of_nonneg_right- Adding a non-negative number to a value results in an equal or larger value.
le_add_of_nonneg_left- Adding a value to a non-negative number results in an equal or larger value.
tsum_mul_left- A constant scalar factor can be factored out of an infinite sum.
tsum_nonneg- The infinite sum of a non-negative function is non-negative.
Summable.of_nonneg_of_le- A non-negative function bounded pointwise by a summable function is summable (comparison test).
le_rfl- The inequality relation ≤ is reflexive (a ≤ a).
- The key inequality in step 6 (line 127) relies on non-linear arithmetic automation (`nlinarith`), which automatically combines the conditions 1/2 < p < 1, the non-negativity of probabilities, and the partition of the non-zero probability to deduce the moment lower bound.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- General lower bound on one-guess vulnerability in terms of the absolute first moment. -/theorem biased_bit_vulnerability_ge_one_sub_mul_moment (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (hq_mom : Summable (fun s : ℤ => |(s : ℝ)| * q s)) : biased_bit_vulnerability p q ≥ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) := by change (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) have hp0 : 0 < p := by linarith have h1p : 0 ≤ 1 - p := by linarith have hq : Summable q := hq_sum.summable have hqshift : Summable (fun s : ℤ => q (s - 1)) := hq.comp_injective (fun a b hab => by simpa using hab) have hqm : Summable (fun s : ℤ => if s ≤ 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqpos : Summable (fun s : ℤ => if 0 < s then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqneg : Summable (fun s : ℤ => if s < 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqge : Summable (fun s : ℤ => if 0 ≤ s then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqnz : Summable (fun s : ℤ => if s ≠ 0 then q s else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg s have hqsh : Summable (fun s : ℤ => if 0 < s then q (s - 1) else 0) := by apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hqshift · split_ifs <;> simp [hq_nonneg] · split_ifs with h · exact le_rfl · exact hq_nonneg (s - 1) have hqm_split : (∑' s : ℤ, if s ≤ 0 then q s else 0) = 1 - ∑' s : ℤ, (if 0 < s then q s else 0) := by have heq : (fun s : ℤ => (if s ≤ 0 then q s else 0) + (if 0 < s then q s else 0)) = q := by funext s by_cases h : s ≤ 0 · simp [h, not_lt.mpr h] · simp [h, not_le.mp h] have h := hqm.tsum_add hqpos rw [heq, hq_sum.tsum_eq] at h linarith have hqge_split : (∑' s : ℤ, if 0 ≤ s then q s else 0) = 1 - ∑' s : ℤ, (if s < 0 then q s else 0) := by have heq : (fun s : ℤ => (if 0 ≤ s then q s else 0) + (if s < 0 then q s else 0)) = q := by funext s by_cases h : 0 ≤ s · simp [h, not_lt.mpr h] · simp [h, not_le.mp h] have h := hqge.tsum_add hqneg rw [heq, hq_sum.tsum_eq] at h linarith have hqsh_eq : (∑' s : ℤ, if 0 < s then q (s - 1) else 0) = (∑' s : ℤ, if 0 ≤ s then q s else 0) := by have h := Equiv.tsum_eq (Equiv.subRight (1:ℤ)) (fun t : ℤ => if 0 ≤ t then q t else 0) rw [← h] congr 1 funext s simp only [Equiv.subRight_apply] by_cases hs : 0 < s · rw [if_pos hs, if_pos (show (0:ℤ) ≤ s - 1 from by omega)] · rw [if_neg hs, if_neg (show ¬ (0:ℤ) ≤ s - 1 from by omega)] have hqnz_split : (∑' s : ℤ, if s ≠ 0 then q s else 0) = (∑' s : ℤ, if 0 < s then q s else 0) + (∑' s : ℤ, if s < 0 then q s else 0) := by rw [← hqpos.tsum_add hqneg] congr 1 funext s rcases lt_trichotomy s 0 with h | h | h · rw [if_neg (not_lt.mpr (le_of_lt h)), if_pos h, if_pos (ne_of_lt h)]; ring · subst h; simp · rw [if_pos h, if_neg (not_lt.mpr (le_of_lt h)), if_pos (ne_of_gt h)]; ring have hqnz_le : (∑' s : ℤ, if s ≠ 0 then q s else 0) ≤ (∑' s : ℤ, |(s:ℝ)| * q s) := by apply Summable.tsum_le_tsum (fun s => ?_) hqnz hq_mom by_cases h : s = 0 · subst h; simp · rw [if_pos h] have h1 : (1:ℝ) ≤ |(s:ℝ)| := by rw [← Int.cast_abs] have := Int.one_le_abs h exact_mod_cast this calc q s = 1 * q s := by ring _ ≤ |(s:ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s) have hpt : (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = (fun s : ℤ => p * (if s ≤ 0 then q s else 0) + (1 - p) * (if 0 < s then q (s - 1) else 0)) := by funext s by_cases h : s ≤ 0 · rw [if_pos h, if_pos h, if_neg (not_lt.mpr h)]; ring · rw [if_neg h, if_neg h, if_pos (not_le.mp h)]; ring have hsumm_g : Summable (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := by rw [hpt] exact (hqm.mul_left p).add (hqsh.mul_left (1 - p)) have hsumm_max : Summable (fun s : ℤ => max (p * q s) ((1 - p) * q (s - 1))) := by have hrhs : Summable (fun s : ℤ => p * q s + (1 - p) * q (s - 1)) := (hq.mul_left p).add (hqshift.mul_left (1 - p)) apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hrhs · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s) exact le_trans ha (le_max_left _ _) · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s) have hb : 0 ≤ (1 - p) * q (s - 1) := mul_nonneg h1p (hq_nonneg (s - 1)) exact max_le (le_add_of_nonneg_right hb) (le_add_of_nonneg_left ha) have h_g_max : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := by apply Summable.tsum_le_tsum (fun s => ?_) hsumm_g hsumm_max by_cases h : s ≤ 0 · rw [if_pos h]; exact le_max_left _ _ · rw [if_neg h]; exact le_max_right _ _ have h_tsum_g : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = p * (∑' s : ℤ, if s ≤ 0 then q s else 0) + (1 - p) * (∑' s : ℤ, if 0 < s then q (s - 1) else 0) := by rw [hpt, (hqm.mul_left p).tsum_add (hqsh.mul_left (1 - p)), tsum_mul_left, tsum_mul_left] have h_g_value : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) = p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by rw [h_tsum_g, hqm_split, hqsh_eq, hqge_split] have hPn0 : 0 ≤ (∑' s : ℤ, (if s < 0 then q s else 0)) := tsum_nonneg (fun s => by split_ifs <;> simp [hq_nonneg]) have hkey : (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by nlinarith [hqnz_split, hqnz_le, hPn0, hp, hp1] calc (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s)) ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := hkey _ = (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := h_g_value.symm _ ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := h_g_max