# What is wrong with this inequality?

Hello all,

I have this formula ##\left[2\sqrt{Q\left(\sqrt{2\eta}\right)}\right]^N## where Q is the Q Gaussian function which can be upper bounded by the Chernoff bound ##Q\left(\sqrt{2\eta}\right)\leq exp\left(-\eta\right)##, and thus the original formula can be upper bounded as ##2^Nexp\left(-\frac{N\,\eta}{2}\right)##. Right? Now I need this upper bound to be less than a certain value, say ##\varepsilon\leq 0.5##, i.e. ##2^Nexp\left(-\frac{N\,\eta}{2}\right)\leq \varepsilon##. It seems straightforward to solve this inequality to find N for a given ##\eta##. However, when I did, and did the verification, the term ##2^Nexp\left(-\frac{N\,\eta}{2}\right)## isn't less than ##\varepsilon##. Do I need to be careful about something here that I might have missed?

Thanks

RUber
Homework Helper
How confident are you in the Chernoff bound?

RUber
Homework Helper
Are you using ##Q(x) \leq e^{- x^2/2}##? If so, then you forgot to account for the difference in the variance caused by taking the sqrt(2x).
I would recommend reworking the steps for the Chernoff bound from the beginning.
A possible shortcut might be using wolframalpha.com. If you put in Gaussian(x) and Gaussian( \sqrt(2x)), you will notice that a ##\sqrt{2x}## terms comes out in front of the formula, giving:
##Q(\sqrt{2x})=\sqrt{2x} Q(x) ## So, ##Q(\sqrt{2x}) \leq \sqrt{2x} e^{- x^2/2}##
But I have not done any of the analysis, so I can't say if this even makes sense.

Are you using ##Q(x) \leq e^{- x^2/2}##? If so, then you forgot to account for the difference in the variance caused by taking the sqrt(2x).
I would recommend reworking the steps for the Chernoff bound from the beginning.
A possible shortcut might be using wolframalpha.com. If you put in Gaussian(x) and Gaussian( \sqrt(2x)), you will notice that a ##\sqrt{2x}## terms comes out in front of the formula, giving:
##Q(\sqrt{2x})=\sqrt{2x} Q(x) ## So, ##Q(\sqrt{2x}) \leq \sqrt{2x} e^{- x^2/2}##
But I have not done any of the analysis, so I can't say if this even makes sense.
Yes, I am using this. I think it is straightforward: Put ##\sqrt{2\eta}=x##. It is used all the time in my field. I don't think this is the problem. I think the problem has to do with the convergence of the term ##2^Nexp\left(-\frac{N\,\eta}{2}\right)##.

RUber
Homework Helper
So you started with:
## 2^N e^{-N\eta / 2} < \varepsilon ##
and solved for N ... but the inequality didn't hold. When this happens, you most likely found the wrong N. The bigger N is, the smaller the term, so when in doubt, you can increase N and make it go under epsilon.
Here is how I would solve for N ( log refers to the natural log) :
## \log [ 2^N e^{-N\eta / 2}] < \log[\varepsilon ]##
##N (\log 2 - \eta /2) < \log \varepsilon ##
## N > \frac{\log \varepsilon}{\log 2 - \eta /2}##
Note the direction change of the inequality since (log 2 - eta/2 ) is negative.
N should be relatively large and positive, since log epsilon is negative and you divide by a negative quantity.
Is this what you found for N?

So you started with:
## 2^N e^{-N\eta / 2} < \varepsilon ##
and solved for N ... but the inequality didn't hold. When this happens, you most likely found the wrong N. The bigger N is, the smaller the term, so when in doubt, you can increase N and make it go under epsilon.
Here is how I would solve for N ( log refers to the natural log) :
## \log [ 2^N e^{-N\eta / 2}] < \log[\varepsilon ]##
##N (\log 2 - \eta /2) < \log \varepsilon ##
## N > \frac{\log \varepsilon}{\log 2 - \eta /2}##
Note the direction change of the inequality since (log 2 - eta/2 ) is negative.
N should be relatively large and positive, since log epsilon is negative and you divide by a negative quantity.
Is this what you found for N?
My actual problem is very complicated, and here I tried to simplify it. In my problem ##\eta## is also a function of N, and with another constraint in N, which results eventually on a quadratic function in N. I will try to given more details if the problem is not obvious from what I posted. Why ##log(2)-\eta/2## is negative for all ##\eta##?

RUber
Homework Helper
I assumed that eta was non-negative, since it was under the square root in the beginning. Are you considering imaginary inputs for the Gaussian?
*edit*
I suppose it does not need to be negative for all eta...sorry. Maybe it has to be broken into cases?

I assumed that eta was non-negative, since it was under the square root in the beginning. Are you considering imaginary inputs for the Gaussian?
*edit*
I suppose it does not need to be negative for all eta...sorry. Maybe it has to be broken into cases?
Yes it is non-negative. Also, I need N to be greater than or equal 2.

RUber
Homework Helper
If eta< 2log2 (approx. 1.386) and epsilon is less than 1, then N would have to be negative.

Alternately, following the vein of post #3. Solving for N in the inequality
##\left[ 2 \sqrt{2\eta } e^{-\eta^2/2}\right]^N < \varepsilon ##
Generates something like
##N> \frac{\log \varepsilon}{\log (2\sqrt{ 2\eta}) - \eta^2/2}## for ##.12>\eta \text{ or } \eta>1.6##

EngWiPy