The stay probability
DefinitionTwoFoldOPI_Supplement_pStaycoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Fix load data , weights , a mean load and a tilt , and write for the probability of under . Let and be independent with
The stay probability is
It is the limit of the probability that one coordinate-replacement step keeps a uniform word of a load set inside the set (Theorem 10.11), and it governs the rate thresholds of Theorems 11.3, 11.9 and 12.2.
Formalization Note The module defines the two factors (srcStay, tarStay) and their product. The event is false at , a value of probability .
Definition code
import Mathlib
import Definitions.Def_TwoFoldOPI_Supplement_tiltPoiss
namespace TwoFoldOPI
namespace Supplement
open Classical in
/-- **The stay probability `p_stay = Pr[K_src − 1 ∈ B_{I_src}] · Pr[K_tar + 1 ∈ B_{I_tar}]`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §10.2, Theorem 10.11, p.56: "Define independent random variables (I_src, K_src) and
(I_tar, K_tar) by Pr[I_src = r ∧ K_src = k] = (α_r/η) k Pr_{K∼TiltPoiss_{ν,B_r}}[K = k],
(I_tar, K_tar) ∼ TiltPoiss_{ν,{B_r},{α_r}}. Then Pr[X′ ∈ T] = Pr[K_src − 1 ∈ B_{I_src}]
Pr[K_tar + 1 ∈ B_{I_tar}] + O(n^{−1/2})"; §5.4, Definition 5.36, p.33 (the multi-class law
Pr[I = i ∧ K = k] = α_i p^{(i)}_k); Theorem 11.9, p.62 and Theorem 12.2, p.65
("p_stay = Pr[K_src − 1 ∈ B_{I_src}] Pr[K_tar + 1 ∈ B_{I_tar}]").
With `p^{(r)}_k = tiltPoiss ν (B r) k`:
* `srcStay = Σ_r Σ_{k ≥ 1, k−1 ∈ B_r} (α_r/η) · k · p^{(r)}_k` (the size-biased source law);
* `tarStay = Σ_r Σ_{k+1 ∈ B_r} α_r · p^{(r)}_k` (the multi-class tilted Poisson law);
* `pStay = srcStay · tarStay` (the two pairs are independent).
**Formalization Note.** `K_src − 1 ∈ B` is false at `K_src = 0` (`B ⊆ ℤ_{≥0}`); that term has
weight `0` anyway. The size-biased weights sum to `1` exactly when the mixture mean is `η`
(admissibility, Definition 10.9), which every statement using `pStay` assumes. -/
noncomputable def srcStay {R : ℕ} (B : Fin R → Set ℕ) (α : Fin R → ℝ) (η ν : ℝ) : ℝ :=
∑ r, ∑' k : ℕ,
if 1 ≤ k ∧ k - 1 ∈ B r then α r / η * (k : ℝ) * tiltPoiss ν (B r) k else 0
open Classical in
/-- `Pr[K_tar + 1 ∈ B_{I_tar}]` for `(I_tar, K_tar) ∼ TiltPoiss_{ν,{B_r},{α_r}}`
(Theorem 10.11, p.56; Definition 5.36, p.33). -/
noncomputable def tarStay {R : ℕ} (B : Fin R → Set ℕ) (α : Fin R → ℝ) (ν : ℝ) : ℝ :=
∑ r, ∑' k : ℕ, if k + 1 ∈ B r then α r * tiltPoiss ν (B r) k else 0
/-- `p_stay = Pr[K_src − 1 ∈ B_{I_src}] · Pr[K_tar + 1 ∈ B_{I_tar}]` (Theorems 10.11, 11.9, 12.2). -/
noncomputable def pStay {R : ℕ} (B : Fin R → Set ℕ) (α : Fin R → ℝ) (η ν : ℝ) : ℝ :=
srcStay B α η ν * tarStay B α ν
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §10.2, Theorem 10.11, p. 56; §5.4, Definition 5.36, p. 33; Theorems 11.9 (p. 62) and 12.2 (p. 65)