Randomized Algorithm Probability Maximization

Question

I'm a computer science undergrad and I'm just studying for finals. I came across a problem that was kind of out of place with the various dynamic programming type problems. I'll summarize it like this:

I'm given an efficient randomized algorithm, A, that returns an independent set. This algorithm returns the maximum independent set with probability at least 1/(n^3) where n is the number of vertices in the graph. Suggest another algorithm, using A, that returns the maximum set with probability at least 1/2.

I've studied randomized algorithms, but this just seems like a simple case of implementation. If I was to run A n^3 times, the probability that the maximum independent set is close to 1. Could I then say that running it n^3/2 times would give the desired effect? Am I just trying to make this harder? Any help is appreciated.

Answer 1

Close but not accurate, the probability for one of the runs to return the correct answer is at least 1/n^3. That means that the probability of getting the wrong answer in one run is (1-1/n^3), which means the probability of getting the right answer after M runs is 1-(1-1/n^3)^M.

Now recall the formula for e (Wikipedia link), if you run n^3 times, the probability is 1-1/e which is more than 1/2 (although not very close to 1), it is also trivial to get the exact number of runs to get to exactly 1/2 - (n^3)*ln(2).