(6), §3.3, p. 7 (corrected: event π(τ_A(i)) ≠ τ_B(i), not τ_A(π(i)) ≠ τ_B(i)) — P(no rendezvous) = P(X = 0)
ProvedRendezvousKn.Sym.eq_6p2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1random-permutationrendezvous-search
Fix and tactics ; let and let be the number of pairs with , for a uniformly random binding . Then
This identity translates the no-rendezvous event into the vanishing of the match count , whose moments are then analysed.
Differences from the source:
- correction: no-rendezvous event τ_A(π(i)) ≠ τ_B(i) for all i ∈ [n] → event π(τ_A(i)) ≠ τ_B(i) for all i (noRdvProb), the event of the game's definition on p. 3 and of the proof (Z > n); reason: the printed event makes the statement false: n ≥ 2, τ_A ≡ 1, τ_B ≡ 2 gives printed probability 1 (take β = 1) while W = 1/n + (n+1)(1 − 1/n) = n < n + 1/2 and P(X = 0) = 1 − 1/n
- encoding: expectation over a uniformly random binding π: [n] → [n]; rounds 1, …, n; locations [n] → average over all n! elements of Equiv.Perm (Fin n) (avgPerm); rounds and locations are Fin n, Lean round i being round i + 1; reason: the same finite uniform distribution and the same game; no instance changes
Preamble
import Mathlib import Definitions.Def_RendezvousKn_Sym_Model
Formal statement
namespace RendezvousKn.Sym
theorem eq_6 (n : ℕ) (hn : 2 ≤ n) (τA τB : Tactic n) :
noRdvProb τA τB = probXZero (pairSet τA τB) := by sorry
end RendezvousKn.Sym
Source
Bonamy, Pilipczuk, Sereni, On the effect of symmetry requirement for rendezvous on the complete graph, arXiv:2002.03764v1, p. 7 (PDF 8), §3.3, equation (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.