Let $\zeta := \exp(2\pi i/n)$ be an $n$th root of unity. Let $B>0$. I am curious if there are any decent tail bounds on the random variable $|\sum_{j = 0}^{n-1}D_j\zeta^j|$, where $D_j\gets [-B, B]$ i.i.d. For example
- It is trivially $\leq Bn$
- If one replaces $\zeta^j$ with $(-1)^j$ (or $1$), it is straightforward to show that it is $O(\sqrt{n}B)$ with high probability $\geq 1-\exp(-n)$
Can one prove something similar in the presence of the complex phases $\zeta^j$? One can use a standard Chernoff argument to get that it is at least $t$ with probability at most
$$\mathbb{E}[\exp(\lambda|\sum_j D_j\zeta^j|)]\exp(-\lambda t)$$ where $\lambda>0$ is a free parameter. The next step of a Chernoff bound is to appeal to independence and break up the expectation into a product of expectations --- I don't know how to do that without applying triangle inequality (which destroys the potential for cancellation).
The main other idea I have is to write
$$|\sum_j D_j \zeta^j|>t\iff \sup_{\theta} \Re(\exp(i\theta)\sum_j D_j\zeta^j)>t$$
where $\theta\in[0,1]$. This reduces to proving that
$$\sup_\theta \sum_j D_j\cos(\frac{2\pi j}{n}+2\pi\theta)>t$$
which seems possible, but not yet obvious. For example, the Chernoff argument now yields the upper bound
$$\exp(-\lambda t)\prod_j \mathbb{E}_{D_j}\exp(\lambda D_j\cos(\frac{2\pi j}{n}+2\pi \theta))$$
Here, I could (probably?) upper bound $\cos(x) \leq 1$ to reduce to the standard case, though I am not confident this is valid (when $\cos(x)<0$ it seems iffy, but symmetry of $D_j$ might make it fine, idk).
Even more, I'm not confident this isn't highly lossy, e.g. if there is a more standard argument to obtain a tighter bound.