Thread: A little math problem

  1. #1
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396

    A little math problem

    Here's something I've encountered in some code I'm writing.

    Given:
    p, q are two real values in the range [0..1]
    m is the average of p, q, i.e. (p+q)/2,

    Can it ever be the case that:

    p^p * q^q < m^(p*q)

    Where '^' is exponentiation, not XOR?

    Anyway, the point is, if the above relation can NEVER be true, then I can make an enormous optimization somewhere.

    I'm sure somebody in the infotheory literature has already proved/disproved this, but I haven't found it yet.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Bad news. You algorithm fails for both ends of your range - 0 and 1.

    edit - I mean Good news - you are looking for a failure!
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    If p==0 and q==1, then true is the result.

    0^0 * 1^1 is less than .5^0
    Mainframe assembler programmer by trade. C coder when I can.

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    So, any time p or q is zero, the right side of the equation will be 1, unless p & q are both zero (assuming 0^0 is not 1...? http://en.wikipedia.org/wiki/Exponen...Powers_of_zero)
    Mainframe assembler programmer by trade. C coder when I can.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Would this be a valid counterexample?

    p = 0.01, q = 0.9

    0.01^0.01 ~= 0.955
    0.9^0.9 ~= 0.91
    0.955 * 0.91 ~= 0.869

    m = (0.01 + 0.9) / 2 = 0.455
    0.455^(0.01 * 0.9) ~= 0.993

    0.869 < 0.993
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Are you sure your signs aren't backwards? I checked one million points in the unit square, and left side > right side was true exactly 0 times.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by tabstop View Post
    Are you sure your signs aren't backwards? I checked one million points in the unit square, and left side > right side was true exactly 0 times.
    Ugh. Yes, I believe the comparison is backwards. Good catch.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So we don't have LaTeX. But we'll try:
    By the AM-GM inequality, (pq)^(1/2) <= m. Raising both sides to the pq power, gives (pq)^(pq/2) <= m^(pq). (Since p, q, and m are positive, raising to a power keeps the inequality.)
    Now, p^p * q^q = (pq)^(pq/2) * [p^(p-pq/2) q^(q-pq/2)]. (That's properties of powers.) Since p and q are both positive and less than 1, p > pq > pq/2, and q > pq > pq/2. That means both of the powers inside the brackets are positive; therefore p^(p-pq/2) is positive and less than 1 and q^(q-pq/2) is positive and less than one. Therefore the whole brackets is positive and less than 1.

    Consequently, p^p * q ^ q < (pq)^(pq/2) [since it is equal to the right-hand side times a number less than one]. Sandwiching, p^p*q^q < m^(pq), always.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Help!!c problem in math
    By feelsunny in forum Tech Board
    Replies: 2
    Last Post: 10-06-2007, 03:35 AM
  3. Math Problem....
    By NANO in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 11-11-2002, 04:37 AM
  4. math problem
    By unixOZ in forum Linux Programming
    Replies: 4
    Last Post: 10-19-2002, 12:17 AM
  5. Little math problem
    By Thantos in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-27-2001, 07:44 PM