Skip to main content
2 of 2
added 6 characters in body
Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56

Thinking about the negative side, you can't guarantee arbitrarily many runners to reside in a common $1/2-\epsilon$ of the circle for any $\epsilon>0$.

Take $N$ to be a sufficiently large polynomial of $n$, and let $F$ denote the first $n$ columns of the $N\times N$ discrete Fourier transform matrix with unit-modulus entries. Next, let $D$ be an $n\times n$ diagonal matrix whose diagonal entries are drawn iid uniformly from the complex unit circle. Interpret each row of the matrix product $FD$ to be the locations of the runners at time $t\equiv 0,\ldots,N-1 \bmod N$. (We took $N$ much larger than $n$ in order to sample the running paths so much that we wouldn't "miss" a cluster.)

Using a complex version of Hoeffding's inequality, there is a positive probability that for every $t$, the sum of the runners' locations (as complex numbers) has modulus smaller than

$$\sqrt{4n\log 4N}=O(\sqrt{n\log n})=o(n),$$

whereas the modulus would need to be $\Omega_\epsilon(n)$ if the runners resided in a common $1/2-\epsilon$ of the circle.

Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56