Let $x \in [-1/2,1/2]$ and $X_1,\ldots,X_n$ be drawn iid from the uniform distribution on $[-1,1]$.
Question. Given $\varepsilon \ge 0$ an integer $k \in [1,n]$, what is a good lower-bound on the probability $p_{n,k,\varepsilon}$ that: for every $x \in [-1/2,1/2]$, there exists $S \subseteq \{1,2,\ldots,n\}$ with $1 \le card(S) \le k$ such that $|\sum_{i \in S} X_i-x| \le \varepsilon$ ?
I'm particularly interested in the case $k=n$.
Notes.
- If one could get a good lower-bound for the probability of approximating a fixed $x \in [-1/2,1/2]$ as a sum $\sum_{i \in S}X_i$, then one could use a covering argument on the interval $[-1/2,1/2]$ to get a uniform bound.
One could generalize the above problem as follows. Let $0 \le r < 1$ and $B_r^m$ be the origin-centered ball of radius $r$ in $\mathbb R^m$, and let $X_1,\ldots,X_n$ be drawn iid uniformly from the unit ball $B_1^m$.
Question. What is a good lower-lower bound for the probability $p_{m,r,n,k,\varepsilon}$ that: for every $x \in B_r^m$, there exists $S \subseteq \{1,2,\ldots,n\}$ with $1 \le card(S) \le k$ such that $\|\sum_{i \in S} X_i-x\| \le \varepsilon$ ?
As before, I'm particularly interested in the case $k=n$.
