Video 7-5: Las Vegas and Monte Carlo algorithms

0:04 In the next section, we'll look at uh some some classification for different types of randomization u randomized algorithms, different types how you can use randomization. And that will also influence a bit how easy they are used uh for certain applications. And uh let's start with the easiest one, the Las Vegas algorithms. And these are all named after casino gambling towns for no particular reason. Um I mean there's there's randomness involved in gambling for sure, but it's going to be Monte Carlo and and Las Vegas algorithms. And why one is one and the other is the other remains unclear. So uh we'll we'll consider here a general uh problem to compute. So some function that maps some input to some output strings. But it's an complete function, total function and unambiguous. If you want to model decision problems as we will do in the next unit uh more more uh intensively, then really what you're looking at is a language and the output is just 01 accept or or reject.

1:07 Um you could also say that's the characteristic function of the set L. Uh but the setup is general. You can also produce outputs. Then a a Las Vegas algorithm is a randomized algorithm A where um we have three conditions. First of all, it should always terminate but only almost surely. So there's a probability one for it to stop but it might potentially run forever in like the uh example of the roll die uh procedure we had last time. the algorithm should always answer correctly or the only thing we allow it is to output a specific signal. Um, I kind of failed. Um, I don't know what the answer is. But there's um there's a a benefit from having this signal as opposed to just an arbitrary wrong answer where the algorithm is confidently saying, "Yeah, that that's the answer." And it's not. Here we're getting this this signal that something failed and you can't reliably have any answer. But uh for each input the algorithm either produces the correct output the single unique correct output or this I gave up and uh it should at least half of the time in terms of probability uh produce the correct output. If it always said I don't know then it wouldn't be much use.

2:35 Now uh it turns out this definition is is generous and you can restrict parts of it without losing any problems that you can solve. So every Las Vegas algorithm that satisfies these three conditions can actually be slightly strengthened. And in particular you can get rid of this uh I don't know state. um you can transform an algorithm into a new Las Vegas algorithm which now has probability one to output the correct answer. Um I guess here unlike in the case of termination if you terminate you terminate with positive probability. So here it's written as probability is one to output the right answer. uh but I guess you can say it never outputs anything different because whenever it terminates it does so because of an input that has positive probability. So it this really means we can never output anything else. It's not just almost surely if you care about the difference. Uh we have to pay a little bit for this. So um the expected time that our new algorithm takes is bounded in terms of twice the time that the algorithm previously took.

4:06 But we only get a guarantee for the expected time. But still that's that's good enough. And the algorithm often good enough I guess. And the algorithm is still a Las Vegas algorithm. So it still terminates almost shortly.

4:23 You'll see how this works in full generality in the exercises. Uh is a I think insightful little construction. Now uh you can also go the other way around here. Um in this first part we um essentially got rid of this don't know version. Uh you can also get rid of the possibility that the algorithm may not terminate in uh after a fixed number of of steps. So you can also take any um any Las Vegas algorithm. Okay. This is a the more general version here. any any algorithm that just has um probability one to output the correct answer always answers correctly. Uh you can transform it into one. So here we have no guarantee on the time, right? Uh it can be transformed into one that is at least correct half the time as for Las Vegas on the previous slide. And you have a guarantee on the time namely the time on any fixed input. So this is a worst case statement because it holds for all X. The time that this algorithm takes is at most twice the expected time of the thing you started with. But it always terminates after that number of steps. So not just with probability one but always always. Okay. Uh you'll also see how to do this. Um the general construction is not very hard.

5:48 Um I'll just want to show you some some example in a minute. Um to introduce some names for this. uh of both of these variants. an algorithm that uh is always correct but may not always terminate or an algorithm that most of the time is correct but may occasionally say I don't know but at the expense of that uh always terminates after a bounded time both are known as Las Vegas algorithms and so uh we don't have good terminology to distinguish them that would be established um I try to give them some names so that we can refer to them in the exercises So the first version is is the always decisive algorithm because it never says I don't know. Uh the second type is the always terminating one for hopefully ob obvious reasons. All right. Um in a concrete example it's often not that hard to uh make that transformation. Remember we had this roll die uh procedure which did a perfectly uh random sample out of six numbers but it had this infinite loop potentially infinite loop even though we convinced ourselves it's only a measured zero um set where it wouldn't terminate and the expected time is actually constant and all that you can transform that into a Las Vegas u algorithm of the other type by just not doing the loop but outputting don't know if the first attempt failed.

7:20 Uh that's not too far from the general construction. Uh Las Vegas algorithms obviously have the benefit that they don't make mistakes even if the running time is um not always predetermined. So especially the always decisive version um is is useful if you want to use it as a drop-in replacement for some deterministic function. And well-known examples exist uh where again the output is always the same, right? Quicksort never not sorts. It's just that the time it takes is random and can be larger or smaller. Uh but in these cases, you also have the the combination of of these two properties from the previous slide, right? Quick sorting, quick select, they are both always decisive and always terminating. So again, examples that once you're once you're at this um in in not too bad examples of problems, you can you can get both always terminate and always correct. Okay.

8:29 Now um the full power of randomization may come only at the expense of accepting wrong outputs. So far that's unclear. It's just a claim. But to set the stage, let's do the definition for that case, too. Um, it might be much easier to allow a random to allow a randomized algorithm to output something wrong. And um, we just don't want that to be arbitrary so that it's still useful. And there's this two slightly different ways how you could formalize this. Uh, this is then called a Monte Carlo algorithm. the uh Monaco version of Las Vegas or I don't know the posh version of well whatever uh again why one is called one Monte Carlo and the other Las Vegas uh I don't think there's a good pneummonic both is probably going to end expensive Monte Carlo algorithms um are only expected to be correct for half of the time and then the question is do they have a bounded ed error or an unbounded error which looks very similar but really the difference is whether you have um a fixed constant away from 1/2 that doesn't depend on the input and cannot shrink with n to zero whereas the unbounded error could essentially allow that. So it's you could say it's the same as above but you swap the quantifiers right for every x there is an epsilon so that the probability is is stricter than 1/2 but the epsilon may depend on the input whereas here it's it's crucial that this error probability is independent of the input.

10:11 And this may seem like a nitpick, but we'll see. That's um important for uh for uh theoretical and practical reasons. Um so in particular, it's maybe worth stating what the definition does not say. Uh in particular, it doesn't say anything about the other cases. If the algorithm has to be correct with little more than half the probability, what does it do in the other cases? we don't care. Okay, it uh might output some arbitrary uh value and uh I guess the definition doesn't say whether it terminates. Um we'll usually see that uh you can enforce termination in this case. Um basically if it runs too long, you just output something random. If you can make sure that this doesn't happen with too big a probability, that's fine.