The one-step stay probability of the coordinate-replacement walk
DefinitionTwoFoldOPI_Supplement_stayProbcoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Let be nonempty, let be uniform on , and obtain by replacing a uniformly chosen coordinate of by an independent uniform symbol of . Then
where is with coordinate set to .
This is the quantity estimated in Theorem 10.11.
Formalization Note Meaningful for , , which hold in every use (large ).
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
open Classical in
/-- **The one-step stay probability of the coordinate-replacement walk on a set `T ⊆ [n]^m`.**
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: "Let X be uniform on T, and obtain X′ by replacing a uniformly
chosen coordinate of X by an independent uniform symbol in [n]. … Then Pr[X′ ∈ T] = …".
`stayProb T = (1/|T|) Σ_{x ∈ T} (1/m) Σ_{i} (1/n) Σ_{a ∈ [n]} 1[x with coordinate i set to a ∈ T]`
`= Pr[X′ ∈ T]`.
**Formalization Note.** Meaningful for `T ≠ ∅`, `m ≥ 1`, `n ≥ 1`; statements using it are for
large `n`, where these hold. -/
noncomputable def stayProb {m n : ℕ} (T : Finset (Fin m → Fin n)) : ℝ :=
(T.card : ℝ)⁻¹ * ∑ x ∈ T, ((m : ℝ)⁻¹ * ∑ i : Fin m, ((n : ℝ)⁻¹ * ∑ a : Fin n,
if Function.update x i a ∈ T then (1 : ℝ) else 0))
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