9
$\begingroup$

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

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.