What is wrong with this inequality?

[EngWiPy]

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]

How confident are you in the Chernoff bound?

 

[RUber]

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.

 

[EngWiPy]

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]

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?

 

[EngWiPy]

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]

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?

 

[EngWiPy]

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]

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$