Some times its not always possible to derive the High Probability bounds (1-n^{-α}) for Las Vegas algorithms, I found an interesting way to convert any Las Vegas algorithm with expected bounds on the resources to the High Probability bounds. Assume that T_{n} be the expected runtime(or any resource) for a Las Vegas algorithm. The plain vanilla Las Vegas algorithm have the following structure.
while(1){ /*Select a random sample*/ if(answer found) quit; }
Basically any analysis of the above randomized algorithm should tell how long should we run the loop. So let T_{n} gives the expected time on how long this loop runs. What we can do is as follows
- Let the algorithm run for exactly 2T_{n} steps, if the algorithm quits before that we are fine, if the algorithm does not quit after T_{n} times then stop and restart.
counter = 0; while(1){ /*Pick a random sample*/ if(counter++ == 2T_{n}){ counter=0; /*restarting*/ } if(answer found) quit; }
We can now show that the above algorithm will now give high probability bounds. Let X be the random variable which indicates the runtime of the algorithm. Then using Markov inequality P[X ≥ aT_{n}] ≤ 1/a
- P[X ≥ 2T_{n}] ≤ 1/2
- Lets assume that the algorithm runs for k ≥ 2T_{n} time steps, then we should have done a reset exactly k/(2T_{n}) times.
- The probability of doing a reset equals P[X ≥ 2T_{n}] = P[reset].
- Lets assume all the events are independent then the probability of resetting k/(2T_{n}) P[reset k/(2T_{n}) times] = P[algorithm running k time steps]
- P[reset k/(2T_{n})] ≤ (1/2)*(1/2)*(1/2)...k/(2T_{n}) times
- P[reset k/(2T_{n})] ≤ (1/2)^{k/(2Tn)}
- we want the above probability to be very small (n^{-α}), to make that (1/2)^{k/(2Tn)} = n^{-α}). So the value of k for which this happens is 2T_{n}αlog(n)
- So with high probability after 2T_{n}αlog(n) time steps if we quit the loop then we give the correct answer.
- So we just have taken an expected bound T_{n} and converted into ∼O(log(n)T_{n}) time algorithm with high probability rather than expected bounds.
No comments:
Post a Comment