A little math problem
Here's something I've encountered in some code I'm writing.
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.
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!
If p==0 and q==1, then true is the result.
0^0 * 1^1 is less than .5^0
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)
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
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.
Originally Posted by tabstop
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.