Suppose $X_1, \dots, X_n$ are $n$ independent copies of a real random variable $X$. Then, what is the largest value of:

$$\alpha_X = \min_{a_1,\dots, a_n \in [1,R]} \Pr\left[\sum_i a_i X_i <1\right]\cdot \Pr[X\geq 1]?$$

When $R$ is small, then we can take $X$ to be a random Bernoulli or a normal variable. In that case, the above product is of the order of $\frac1{R\sqrt{n}} \cdot 1$.

When $R$ is large, we can take $X$ to be $0$ with probability $1-1/n$ and $1$ with probability $1/n$. Then the above product is of the order of $1\cdot \frac1n$.

It seems to me that $\alpha_X$ can never be much larger than $\max(\frac{1}{R\sqrt{n}}, \frac{1}{n})$. For the small $R$ case, I think one can use the local limit theorem to argue. But any ideas about how to analyze the full regime?

  • $\begingroup$ Is $X$ assumed to be non-negative? Otherwise the random variable that is $1$ with probability $1/2$ and a huge negative number with probability $1/2$ gives you $\alpha_X=\frac 12(1-2^{-n})$ regardless of $R$. $\endgroup$ – fedja May 16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.