When does a random trigonometric sum approximate $1$? I am looking for an upper bound $R=R_{n,\varepsilon}$ such that for given $\varepsilon>0$ and real numbers $\alpha_1, \dotsc, \alpha_n$ in, say, $[1,2]$, there is $x\in [1,R]$ such that
$$
\frac 1n\sum_{k-1}^n\cos(\alpha_k x)\geq 1-\varepsilon
$$
Dirichlet's principle states that $x$ can be (an integer) smaller than $\varepsilon^{-n}$.
We are actually interested in the case where the $\alpha_i$ are iid, say, uniform over $[1,2]$, so pathological cases of badly approximable $n$-tuples can be ignored, and a result holding with high probability would be great.
The main problem is that $n$ goes to infinity, our feeling is that we could get something in $\varepsilon^{-n/2}$, using  Fubini's theorem, but it is not clear.
 A: $\newcommand\ep\varepsilon\newcommand\al\alpha$Let $X_k:=\cos(\alpha_kx)$. Then $X_1,X_2,\dots$ are iid random variables such that $P(X_1<1)=1$ and hence $\mu:=EX_1<1$, so that $\mu<1-\varepsilon$ if $\varepsilon\in(0,1-\mu)$. So, by the law of large numbers, with high probability we get the inequality
$$
\frac 1n\sum_{k=1}^n\cos(\alpha_k x)<1-\varepsilon, 
$$
opposite to your desired one, for all large enough $n$.
So, your idea of randomizing the $\alpha_k$'s to exclude "pathological cases" is not working.

On the other hand, we can get the upper bound $2\pi\lceil(2\pi^2/\ep)^{n/2}\rceil$ on $x$ even without randomization. Indeed, by the simultaneous version of Dirichlet's approximation theorem, for any real $\al_1,\dots,\al_n$ and any natural $N$ there exist integers $p_1,\dots,p_n,q$ such that $1\le q\le N$ and $|2p_i\pi-2q\pi\al_i|\le2\pi/N^{1/n}$ for all $i\in[n]:=\{1,\dots,n\}$. So, letting $x:=2q\pi$ and using the inequality $\cos(2p\pi)-\cos(2p\pi+t)\le t^2/2$ for integral $p$ and real $t$, we have
$$1-\cos(\al_k x)=\cos(2p_k\pi)-\cos(2q\pi\al_i)
\le2\pi^2/N^{2/n}\le\ep$$
for all $k\in[n]$ if $N=\lceil(2\pi^2/\ep)^{n/2}\rceil$.
Therefore and because $1\le x=2q\pi\le2\pi N$, we get the upper bound $2\pi\lceil(2\pi^2/\ep)^{n/2}\rceil$, of the desired form, on the smallest number $x\ge1$ such that
$$
\frac 1n\sum_{k-1}^n\cos(\al_k x)\ge1-\ep.
$$
