(11)–(12) — the sampled estimate ρ d^R + d^Q falls ε|P| below d with probability ≤ (nm)^{−2} and ε|P| above with probability ≤ (nm)^{−4/3}
ProvedClosestString.PTAS.eq_11_12hamming-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrandom-sampling
Let be strings of length , a nonempty set of positions and its complement. Let be a multiset of positions drawn independently and uniformly from (with replacement), , and the number of entries of (with multiplicity) at which and differ. Let and with . Then
In the paper , , and or ; these are the inequalities (11) and (12) of the proof of Fact 2. They say that the sampled distance, rescaled by , is a good estimate of the distance on .
Differences from the source:
- generalization: N = nm, |R| = ⌈(4/ε²) log(nm)⌉, u = s∗, v = t′ or t_i → any real N ≥ 1, any k ≥ (4/ε²) ln N (including k = 0), any strings u, v; reason: the proof uses only |R| ≥ (4/ε²) ln(nm); the paper's choice is the case N = nm
- reading: log(nm) → Real.log, the natural logarithm; reason: (11) needs exp(−ε²|R|/2) ≤ (nm)^{−2}, i.e. |R| ≥ (4/ε²) ln(nm), which is exactly the printed computation with ln
- encoding: R a multiset of uniformly random positions of P, ρ = |P|/|R| → R : Fin k → Fin L with law Measure.pi of k uniform laws on P; ρ = (|P| : ℝ)/k; reason: the paper's sampling with replacement; same law
Preamble
import Mathlib import Definitions.Def_ClosestString_PTAS_Basic
Formal statement
namespace ClosestString.PTAS
open MeasureTheory
/-- **(11)–(12)** (proof of Fact 2, Li, Ma & Wang, arXiv:cs/0002012v1, p. 11): for strings `u, v`
of length `L`, a nonempty position set `P` with complement `Q`, a multiset `R` of `k` independent
uniform positions of `P`, `ρ = |P|/k`, `ε > 0` and `N ≥ 1` with `k ≥ (4/ε²) ln N`:
`Pr(ρ d^R(u,v) + d^Q(u,v) ≤ d(u,v) − ε|P|) ≤ exp(−ε²k/2)` and `≤ N^{−2}`, and
`Pr(ρ d^R(u,v) + d^Q(u,v) ≥ d(u,v) + ε|P|) ≤ N^{−4/3}`. -/
theorem eq_11_12 {A : Type*} [DecidableEq A] {L : ℕ} (u v : Fin L → A) (P : Finset (Fin L))
(hP : P.Nonempty) (k : ℕ) (ε : ℝ) (hε : 0 < ε) (N : ℝ) (hN : 1 ≤ N)
(hk : 4 / ε ^ 2 * Real.log N ≤ k) :
Measure.pi (fun _ : Fin k => (PMF.uniformOfFinset P hP).toMeasure)
{R | (P.card / k : ℝ) * distSample R u v + distOn Pᶜ u v
≤ (hammingDist u v : ℝ) - ε * P.card}
≤ ENNReal.ofReal (Real.exp (-(1 / 2) * ε ^ 2 * k)) ∧
Measure.pi (fun _ : Fin k => (PMF.uniformOfFinset P hP).toMeasure)
{R | (P.card / k : ℝ) * distSample R u v + distOn Pᶜ u v
≤ (hammingDist u v : ℝ) - ε * P.card}
≤ ENNReal.ofReal (N ^ (-(2 : ℝ))) ∧
Measure.pi (fun _ : Fin k => (PMF.uniformOfFinset P hP).toMeasure)
{R | (hammingDist u v : ℝ) + ε * P.card
≤ (P.card / k : ℝ) * distSample R u v + distOn Pᶜ u v}
≤ ENNReal.ofReal (N ^ (-(4 / 3 : ℝ))) := by sorry
end ClosestString.PTAS
Source
Li, Ma & Wang, On the Closest String and Substring Problems, arXiv:cs/0002012v1, p. 11, eqs. (11)–(12) (proof of Fact 2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.