The $K$-th nearest neighbor random walk on a Poisson point process gets trapped

Abstract

The $K$-th nearest neighbor random walk $(X_n{)}_{n\ge 0}$ on a homogeneous Poisson point process $\ddot{I}‡$ on ${\mathbb{R}}^d$ ($d\ge 1$), starts at the origin and at each step picks its next Poisson point among its closest neighbors according to i.i.d. labels having the same distribution as $K$. Our main result (Theorem 1) states that the number of Poisson points visited by $(X_n{)}_{n\ge 0}$ admits an exponential decay whenever the random variable $K$ has a bounded support (BS). In particular, the $K$-th nearest neighbor random walk visits finitely many Poisson points if and only if $K$ satisfies Assumption (BS). To prove it, we introduce the key notion of pioneer point which allows us to deal with the region of ${\mathbb{R}}^d$ already explored by $(X_n{)}_{n\ge 0}$. Still under Assumption (BS), we also prove an exponential decay for the Euclidean length of the trajectory performed by $(X_n{)}_{n\ge 0}$ (Theorem 2). Finally, and quite surprisingly, we exhibit an example of label distribution with bounded support for which the $K$-th nearest neighbor random walk discovers new Poisson points after a number of steps whose tail distribution is at least polynomial (Theorem 3).