# A matrix with a dense submatrix - application of Chernoff’s Inequality

I am trying to solve an exercise from this book, which I will post here for convenience.

I have a bit of a problem understanding how the hint of using Chernoff's bound implies the claim. Specifically let $X = \sum_{i=1}^n X_i$ where $X_i$ are indicator random variables defined in the hint and $E[X] \leq p t$. We are asked to show that

$$Pr[ X \geq pt + t\delta] \leq 1/m^2,$$

where $t = \lceil 4p\log{m/\delta^2} \rceil.$ Using the suggested Chernoff's bound we obtain that the above probability is bounded by

$$e^{-t^2 \delta^2/2t} = e^{-4p \log{(m/\delta^2)} \delta^2}.$$

And it does not seem to follow that the last expression is bounded by $1/m^2.$ So either one needs to use a different approach or I am missing a crucial detail.

I am tempted to think that perhaps the author meant to take a different value of $t$ but the next exericse builds uppon this specific order of $t$.

Hence I am wondering

Where is the mistake in my reasoning? How to solve this problem correctly?

If $p\geq 1/2$ then

$$e^{-t^2 \delta^2/2t} = e^{-4p \log{(m/\delta^2)} \delta^2}\leq e^{-2 \log m}=1/m^2$$

and the argument goes through.

If $p<1/2,$ we argue directly.

For a contradiction, assume that all $m\times t$ submatrices have density of 1's $>1/2.$

Let $t=2v+1$ be odd. The even case is similar and easier.

This means that, for each row of the full matrix, there are at least $v+1$ 1's in every single $2v+1$ subset of indices corresponding to the $t$ selected columns. This means that there can be at most $v$ 0's in any row of the matrix, otherwise we could join $v+1$ $0$'s to any $v$ $1$'s and violate the assumption on density of 1's of all submatrices.

Thus there are at most $v$ 0's and at least $n-v$ $1$'s in each row of our matrix. Therefore the density $\rho$ of $1$'s on each row satisfies $\rho \geq 1-(v/n),$ but since $t=2v+1\leq n,$ we have $v\leq (n-1)/2<1/2$ which implies $\rho>1/2$ and gives us the required contradiction with the average density of each row of $H$.