All proofs
Project-declaredLean 4.8.0 · mathlib@b5eba5954288

Alice pr le

alice_pr_le

Plain-language statement

Honest Alice has error ≥ e with probability ≤ q

Exact Lean statement

lemma alice_pr_le (o : Oracle) (i : OracleId) (e0 : 0 < e) (q0 : 0 < q) (y : Vector Bool n) :
    ((alice' e q i _ y).prob' o).pr (λ p ↦ e ≤ |p - (o _ y).prob true|) ≤ q

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma alice_pr_le (o : Oracle) (i : OracleId) (e0 : 0 < e) (q0 : 0 < q) (y : Vector Bool n) :    ((alice' e q i _ y).prob' o).pr (λ p  e  |p - (o _ y).prob true|)  q := by  simp only [alice', Comp.prob', Comp.prob_estimate, Comp.prob_query]  refine le_trans (chernoff_estimate_abs_le (o _ y) (samples e q) (le_of_lt e0)) ?_  have le : -2 * ↑(samples e q) * e^2  -2 * samples' e q * e^2 :=    mul_le_mul_of_nonneg_right (mul_le_mul_of_nonpos_left (le_samples _ _) (by norm_num))      (sq_nonneg _)  refine le_trans (mul_le_mul_of_nonneg_left (Real.exp_le_exp.mpr le) (by norm_num)) ?_; clear le  simp only [samples', div_eq_inv_mul, mul_assoc, mul_inv]; norm_num  simp only [mul_comm _ (e^2), mul_assoc, mul_inv_cancel (pow_ne_zero _ (ne_of_gt e0)), one_mul]  rw [Real.exp_log]; ring_nf; rfl; positivity
Project
debate
License
Apache-2.0
Commit
de3a6e500ae1
Source
Debate/Details.lean:40-50

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.8.0

Alice steps cost

alice_steps_cost

Plain-language statement

Alice makes few queries, regardless of Bob and Vera

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record
Project-declaredLean 4.8.0

Alices close

alices_close

Plain-language statement

Alice produces (p,y) with p close to o.probs y with good probability

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record
Project-declaredLean 4.8.0

Alices success

alices_success

Plain-language statement

Alice produces (p,y) with p close and y true with good probability, since if we condition on Alice being close she does as least as well as a close oracle.

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record