EDIT: I had calculated some of my probabilities wrongly. Also I've now mentioned that we need to randomly pick 2 distinct inputs for the function f in order to guarantee that, if f is balanced, then we know the probabilities of seeing the various possible outcomes.
The fact that the prior probability of the function being constant is not known makes this question harder, because it means we can't directly calculate the probability of success for any algorithm. We will, however, be able to calculate bounds on this probability.
I propose the following probabilistic algorithm:
- Pick two distinct 4-bit values at random, and supply each to the function f.
- If 0,0 or 1,1 is seen, output "constant" with probability 2/3 and "balanced" with probability 1/3.
- Otherwise (if 0,1 or 1,0 is seen), always report "balanced".
Let's start by looking at something we can actually calculate: conditional probabilities.
- "What is P(correct|constant), namely the probability that our algorithm gives the correct answer given that f is constant?" When f is constant, our algorithm reports the right answer 2/3 of the time.
- "What is P(correct|balanced), namely the probability that our algorithm gives the correct answer given that f is balanced?" When f is balanced, the probability of seeing 0,1 or 1,0 is 2*(8/16 * 8/15) = 8/15, in which case the correct answer will definitely be output. In the remaining 7/15 of cases -- i.e. those in which 0,0 or 1,1 is seen -- the correct answer will be output 1/3 of the time, so the total proportion of correct outputs will be 8/15 * 1 + 7/15 * 1/3 = 31/45 = 2/3 + 1/45 ≈ 0.6889.
Now suppose that the prior probability of the function being constant is p. Then the probability that the algorithm gives the correct answer is
pCorrect(p) = p*P(correct|constant) + (1-p)*P(correct|balanced).
Given that 0 <= p <= 1, pCorrect(p) must be at least min(P(correct|constant), P(correct|balanced)), and at most max(P(correct|constant), P(correct|balanced)). The minimum of 2/3 and 31/45 is 2/3, thus pCorrect is bounded from below at 2/3, for any prior probability of the function being constant. (It might help to think of p as a "mixing lever" that controls how much of each term to include. If p = 0 or p = 1, then we effectively just have P(correct|balanced) or P(correct|constant), respectively, and for any in-between value of p, we will have an in-between total.)