AFTD Auto-Formalizing Theoretical Domains

biased_bit_vulnerability_ge_one_sub_mul_moment

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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|].

  1. 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.

    lines 3–6

      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
  2. 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).

    lines 7–45

    uses Summable.of_nonneg_of_le, le_rfl

      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)
  3. 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).

    lines 46–72

    uses Equiv.tsum_eq, Equiv.subRight, Equiv.subRight_apply, if_pos, if_neg

      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)]
  4. 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.

    lines 73–92

    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_right

      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)
  5. 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).

    lines 93–116

    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_neg

      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 _ _
  6. 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.

    lines 117–131

    uses tsum_mul_left, tsum_nonneg

      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
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).

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

/-- 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
See it in the graphDiscuss this resultChallenge it