Tuesday, March 04, 2008

[TECH] Converting an Las Vegas algorithm from an Expected Time Bound to High Probability bound.

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 Tn be the expected runtime(or any resource) for a Las Vegas algorithm. The plain vanilla Las Vegas algorithm have the following structure.

  /*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 Tn gives the expected time on how long this loop runs. What we can do is as follows

  • Let the algorithm run for exactly 2Tn steps, if the algorithm quits before that we are fine, if the algorithm does not quit after Tn times then stop and restart.

counter = 0;
 /*Pick a random sample*/
 if(counter++ == 2Tn){
    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 ≥ aTn] ≤ 1/a

  • P[X ≥ 2Tn] ≤ 1/2
  • Lets assume that the algorithm runs for k ≥ 2Tn time steps, then we should have done a reset exactly k/(2Tn) times.
  • The probability of doing a reset equals P[X ≥ 2Tn] = P[reset].
  • Lets assume all the events are independent then the probability of resetting k/(2Tn) P[reset k/(2Tn) times] = P[algorithm running k time steps]
  • P[reset k/(2Tn)] ≤ (1/2)*(1/2)*(1/2)...k/(2Tn) times
  • P[reset k/(2Tn)] ≤ (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 2Tnαlog(n)
  • So with high probability after 2Tnαlog(n) time steps if we quit the loop then we give the correct answer.
  • So we just have taken an expected bound Tn and converted into ∼O(log(n)Tn) time algorithm with high probability rather than expected bounds.

No comments: