[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 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++ == 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 ≥ 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/(2T_n)
• we want the above probability to be very small (n^-α), to make that (1/2)^k/(2T_n) = 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.