Approximately Jumping Towards the Origin

Abstract

Given an initial point $x_0\in {\mathbb{R}}^d$ and a sequence of vectors $v_1,v_2,\dots$ in ${\mathbb{R}}^d$, we define a greedy sequence by setting $x_n=x_{n-1}\pm v_n$ where the sign is chosen so as to minimize $\Vert x_n\Vert$. We prove that if the vectors $v_i$ are chosen uniformly at random from ${\mathbb{S}}^{d-1}$ then elements of the sequence are, on average, approximately at distance $\Vert x_n\Vert \sim \sqrt{\ddot{I}€d/8}$ from the origin. We show that the sequence $(\Vert x_n\Vert {)}_{n=1}^{\infty }$ has an invariant measure $\ddot{I}{€}_d$ depending only on $d$ and we determine its mean and study its decay for all $d$. We also investigate a completely deterministic example in $d=2$ where the $v_n$ are derived from the van der Corput sequence. Several additional examples are considered.