Symmetry of W and (2), proof of Theorem 1, p. 5 — W is symmetric and E T⟨σ, σ⟩ splits into passive/active parts
ProvedRendezvousKn.Sym.W_symmbilinear-formp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rendezvous-search
Fix . (i) The function is symmetric: for all tactics ,
(ii) For every strategy with probability vector , write , where is restricted to passive tactics and is restricted to active tactics (both zero elsewhere), and let . Then
The symmetry of is what lets the two mixed terms of the bilinear form be merged in (2), the decomposition on which the proof of Theorem 1 rests.
Formalization Note In Lean is expWait x y, which is defined for arbitrary real vectors. As in the paper (p. 5), is supported on the passive tactics, the set the paper denotes .
Differences from the source:
- encoding: strategy σ ∈ Σ_n, a probability distribution on the tactics [n] → [n]; E T⟨σ_A, σ_B⟩ with independent draws → σ ∈ stdSimplex ℝ (Fin n → Fin n); expWait σ_A σ_B = Σ_{τ_A, τ_B} σ_A(τ_A) σ_B(τ_B) W(τ_A, τ_B); reason: a distribution on a finite set is its probability vector; the double sum is the expectation over independent τ_A ~ σ_A, τ_B ~ σ_B, π uniform (the paper's E T⟨σ_A, σ_B⟩ = Φ⟨a, b⟩, p. 4)
- 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 W_symm (n : ℕ) (hn : 2 ≤ n) :
(∀ τA τB : Tactic n, W τA τB = W τB τA) ∧
(∀ σ : Tactic n → ℝ, σ ∈ stdSimplex ℝ (Tactic n) →
expWait σ σ =
expWait (fun τ => if IsPassive τ then σ τ else 0) (fun τ => if IsPassive τ then σ τ else 0) +
expWait (fun τ => if IsPassive τ then 0 else σ τ) (fun τ => if IsPassive τ then 0 else σ τ) +
2 * expWait (fun τ => if IsPassive τ then σ τ else 0)
(fun τ => if IsPassive τ then 0 else σ τ)) := 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. 5 (PDF 6), proof of Theorem 1, 'As W(·,·) is a symmetric function', equation (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.