A little math problem

This is a discussion on A little math problem within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Here's something I've encountered in some code I'm writing. Given: p, q are two real values in the range [0..1] ...

  1. #1
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239

    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
    Katy, Texas
    Posts
    2,309
    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!
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

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

    0^0 * 1^1 is less than .5^0
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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)
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,582
    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
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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,185
    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    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,185
    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, 10: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, 03: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21