Randomized Algorithm that tells us success or gives up

Question

This is a homework problem, so all I'm looking for is some sort of starting point on this problem as I'm not really sure where to begin. The problem is as follows:

Suppose that we need to compute a function f (x) for binary input strings x. We only have a randomized algorithm A(x) working in polynomial time (making use of as many random bits as needed). The answer given by A(x) is never wrong, but with probability ≤ 0.9 it can be “I give up”. Show that then there is another randomized algorithm B(x) that computes the right answer in a polynomial expected time.

Answer 1

The key to this problem is the "expected time" part.

Let's say, because $A(x)$ works in polynomial time, that it runs in $O(n^p)$ for input size $n$ and polynomial degree $p$.

We can construct an algorithm using $A$ that is guaranteed to calculate the answer eventually:

g(x) {
     a = A(x)
     if a is not defined:
         return A(x)
     else
         return a
}

Simply, continue trying $A$ until you get the answer.

This algorithm will take an integer number of iterations to return an answer. This gives us a probability distribution:

$$P(1) = \frac{1}{10}\\P(2)=\frac{1}{100}\\\vdots\\P(k) = \frac{1}{10^k}$$

Using this, you can calculate the expected number of iterations before a correct answer is returned, and with that number you can calculate the runtime of $g$, which will be polynomial.