1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is wrong with this inequality?

  1. Aug 19, 2015 #1
    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
     
  2. jcsd
  3. Aug 19, 2015 #2

    RUber

    User Avatar
    Homework Helper

    How confident are you in the Chernoff bound?
     
  4. Aug 19, 2015 #3

    RUber

    User Avatar
    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.
     
  5. Aug 19, 2015 #4
    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)##.
     
  6. Aug 19, 2015 #5

    RUber

    User Avatar
    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?
     
  7. Aug 19, 2015 #6
    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##?
     
  8. Aug 19, 2015 #7

    RUber

    User Avatar
    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?
     
  9. Aug 20, 2015 #8
    Yes it is non-negative. Also, I need N to be greater than or equal 2.
     
  10. Aug 20, 2015 #9

    RUber

    User Avatar
    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##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What is wrong with this inequality?
  1. What's wrong with this? (Replies: 17)

Loading...