Symmetric rendezvous, discrete model: (lower half of the HDVZ conjecture)
OpenSymmetricRendezvousLine.discrete_symmetric_rendezvous_value_ge_seventeen_quartersConjecture (lower half of Han–Du–Vera–Zuluaga). In the discrete model of the symmetric rendezvous problem on the line, the value is at least :
Here is the infimum of the expected meeting time over the mixed strategies all of whose paths are integer zigzags (paths starting at that move at full speed and change direction only at integer times), both players using the same with independent randomisations and independent fair-coin orientations, starting at distance (see the definition file). Equivalently: every mixed strategy over integer zigzags, used by both players, has expected meeting time at least .
Combined with the Han–Du–Vera–Zuluaga reduction , this is the lower half of the conjecture (Han, Du, Vera and Zuluaga; Open Problem Garden). The best proved lower bound is , obtained by Han, Du, Vera and Zuluaga from a finite-horizon relaxation of the discrete problem solved as a semidefinite program; closing the gap to is open.
Formalization Note Values live in ; is the extended-real literal . The infimum ranges over all mixed strategies supported on integer zigzags, including those that delay meeting indefinitely (their expected meeting time may be ).
import Definitions.Def_SymmetricRendezvousLine_defs
namespace SymmetricRendezvousLine
theorem discrete_symmetric_rendezvous_value_ge_seventeen_quarters :
17 / 4 ≤ discreteSymmetricRendezvousValue := by sorry
end SymmetricRendezvousLine