Are there problems that are optimally solved by guess and check? For example, let's say the problem is: What is the square root of 3 (to x bits of precision)?
One way to solve this is to choose a random real number less than 3 and square it.
1.40245^2 = 1.9668660025
2.69362^2 = 7.2555887044
...

Of course, this is a very slow process.  Newton-Raphson gives the solution much more quickly.  My question is: Is there a problem for which this process is the optimal way to arrive at its solution?
I should point out that information used in each guess cannot be used in future guesses.  In the square root example, the next guess could be biased by the knowledge of whether the square of the number being checked was less than or greater than 3.

Let us interpret "Guess and Check" broadly, and attempt a mathematical answer.
There are quite a few instances where a Randomized Algorithm works on average faster than any known non-randomized algorithm. In a small number of cases, one can even prove that the average performance of a certain randomized algorithm is better than that of any deterministic algorithm.
