Conjecture on Brownian tracking horizon for geometric matchings

From papers

Let nn particles move in dd dimensions, sampled at intervals of length δ\delta, and let π^k\widehat{\pi}_k be the estimator at time step kk. Let TmaxT_{\max} denote the maximum tracking time before the estimator incurs a macroscopic number of errors. "Brownian tracking conjecture." Suppose that d2d\geq2 and δ=nξ/d\delta=n^{-\xi/d} for some ξ[2,4]\xi\in[2,4]. Then

Tmaxδ1d/2nf(n)=nξ/2ξ/d1f(n),T_{\max}\sim\frac{\delta^{1-d/2}}{n}f(n)=n^{\xi/2-\xi/d-1}f(n),

for some 1/polylog(n)f(n)polylog(n)1/\operatorname{polylog}(n)\leq f(n)\leq\operatorname{polylog}(n). The heuristic is based on Brownian displacements between snapshots and is explicitly not expected to apply in dimension one, where particle collisions dominate the tracking error; the conjectured behavior remains unproved for the stated higher-dimensional regime.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dmitriy Kunisky and Jonathan Niles-Weed, “Strong recovery of geometric planted matchings”, arXiv:2107.05567 (2021).

Solutions 0

No solutions have been posted yet.