My question is related with this question on combinatorics of 0-1-matrices from MO. Trying to obtain a (asymptotic) lower bound for $\alpha(n)$ by probabilistic approach (see, for instance, “The probabilistic method” by N. Alon and J. Spencer), I encountered the following problem.
Given a natural number $n>1$, find a bound $\alpha (n)>0$ (the bigger, the better) satisfying the following condition.
If for each positive integer $k$ and each sequence $m_1, \dots m_k$, where each $m_j$ is an integer from $0$ to $n$, we define mutually independent random variables $x_1,\dots, x_k$ such that for each $j$ a variable $x_j$ equals $1$ with probability $m_j/n$ and equals $0$ with probability $1-m_j/n$ then
$$P(x_1+\dots+x_k<\lfloor \alpha(n)(m_1+\dots+m_k)/n \rfloor)<1/n.$$
I hope that we can make $\alpha(n)\ge c/\log n$ for some $c>0$ and all sufficiently large $n$.
Thanks.
It seems the following
My probabilistic approach failed. To see this put $$x=x_1+\dots +x_k$$ and $$\mu=E(x)=\frac{m_1+\dots+m_k}n.$$ By Multiplicative Chernoff Bound, for any $0<\alpha<1$ we have
$$P(x\le \alpha\mu)\le e^\frac{-(1-\alpha)^2\mu}2.$$
which suggests $$ e^\frac{-(1-\alpha)^2\mu}2<\frac 1n,$$
which implies $$\alpha<1-\sqrt{\frac{2\ln n}{\mu}},$$
which is useless for $\mu\le 2\ln n$.
This has a simple explanation for the initial question from MO: if in our matrices are small number of $1$’s and a large number of $0$’s then a random choice is a bad choice for a big sum.