Video 7-4: Probabilistic Turing machines

0:03 In the next section, we'll study some formal models for what computation with randomness could mean. And um I just want to set the stage solidly for talking about what running time here is. And um you'll see it's not it's not actually a problem in the end, but uh to capture the full possibility of what could happen, I think it's it's useful to start general. uh as as before we'll we'll think of a a minimalistic model of computation during machines again um so uh the formal definition was in unit 2 if you want to look up the details uh here we add a little bit to this Turing machine so again Turing machine uh it has some states it has an input alphabet which is the initial things written on the input tape um a superset of that is the set of all symbols I can write on the tape. Then I have the transition function. That's the program, the most important bit. I have an initial state. I have some blank symbols that the tape is filled with if I haven't touched it yet. And I have a specific state where I terminate if I ever reach this. Um now a probabilistic Turing machine is that same thing and it's a deterministic Turing machine which maybe is um worth stressing.

1:25 uh where we additionally have um another readonly tape which is conceptually filled with random bits. So it's an additional tape. So the machine has two heads. We've talked about multi-tape touring machines very briefly in unit 2 or at least it's on the slides. Uh in general you can define touring machines with several tapes and you can show that you can simulate everything on one tape with a bit of a blow up in space uh blow up in time guess and space but time is more more affected. Uh so here again we do the same. So think of your your touring machine with the states here. There's the uh infinite tape for the input. Oh, this keeps there's some some weird operation I do and then it loses focus in the window and doesn't come back until I'm on the keyboard.

2:31 So, that's the the input and output tape which you can read and write. And then there's the random tape. where you can still move your head back and forth, but you can only read. There's no writing facility.

2:52 Now, I guess you can imagine how this would be formally defined. Um, the key thing that changes is the the transition function. The input now is not just a state currently of the current position. And so, I didn't finish drawing the read write heads, I guess. So there's the the read right head here that can move left and right and there's the random bit read right head but this can only uh read things. So it's not a read write head it's just a read head. So the transition function uh what the machine can do is it can take this symbol and it can take the symbol on the random tape as an input. Previously it only had the state and the symbol and the tape. Now we have an additional symbol random bit R. And the next state as before is a new state for the internal uh memory. It's a new tape symbol I write on the input output tape. Could be the same as a.

3:57 It's a head movement for the input output tape and a head movement on the random tape but no written symbol because it's a readonly tape. Okay. So far so good. Uh and in particular the the whole machine is supposed to be deterministic. Once you fix the random bits there's nothing further random. All the randomness or all the uh um non-determinism comes from those random bits. If you fix what's in the red tape then um the rest is is determined.

4:35 We'll uh eventually get to the point that we say this tape is filled with random coin flips or uh bits that are chosen from this Bernoli 1/2 distribution and uh all well there's your iid mutually independent all identically distributed.

4:54 So to define what computation is, we go we go through the same steps as in unit two, but I I compressed them uh a lot. Uh back then we had the configuration of a Turing machine which was just a concise way to write what's on the tape and what the current state is uh state of the machine is which and where the tape head is and that's all we needed to know. So the compressed way to store that was this alpha Q beta where your uh tip tip symbol contains alpha beta cont concatenated Q is your state and the position of Q within alpha beta indicated where the head is and if I remember correctly it was on the first symbol of beta. Okay. Um now we have a second tape. So we have a second component in the configuration. It's just a pair of of those things. And the second component works exactly the same except that now these row and sigma together are the content of this uh the red tape of the uh random bit tape.

5:57 Okay. Then we can define this uh computation relation uh where it really is a function here because it's deterministic uh in almost the same way as we had back then. uh you follow the um the transition function. The configuration uniquely determines the state you're in, what you read as symbols. So you know what uh the output will be. Then you replace the state with the new state. You move the heads if needed and maybe you uh replace a symbol here if you write a new symbol just as we had it back then. And based on that we can we can define what is the function computed by a Turing machine. And so um the difference here is that the actual input is just some string X and uh we have some random bits to somehow decide. And uh for now let's say if we fix the random bits row as as part of the input I can write m of x and row the random bits are given is a certain value y exactly when from the starting from the initial configuration I can reach uh the terminating condition where I reach this halting state and I've produced y on the input output tape.

7:15 This is almost the same as before except that I have the second component but for the function computed I'm kind of ignoring it. I just say there's uh something will happen to the random bits but I don't actually care. These are just defining what the steps in between are. But this is deterministic. Okay, important. If I fix the random bits row, everything is predetermined and the machine depending on how it's programmed either it can reach a halting state or it may not, it might be broken. Um, but this will be one well-defined sequence of steps. And if it reaches some configuration, it reaches uniquely only this one. And so, uh, y is is well defined. It's either not terminating then there's no value or it's a single value. Okay, many many words for saying deterministic. Of course, now uh we don't want to fix the random bits. They're not part of the input. These are uh randomized machines.

8:22 So the randomized computation will become a random variable. I'm essentially now taking this function m computed by the machine. I keep the input but row is now formed by random variables namely by these uh iid peri 1/2 random variables. Okay.

8:46 And so uh now um this this computation or this this function computed by the Turing machine has become a random variable. And we can talk about probabilities for for computations. For example, the probability that the machine computes a certain output Y is the probability over uh well all the all the bits that make it output Y. So far so good. In principle, now a randomized Turing machine could have different outputs, right? It doesn't need to compute the same value Y. It could compute different values Y and it could also sometimes not terminate.

9:29 Of course, uh from a programmer's perspective, what we really want is a machine that outputs the right thing with at least a good probability. But we'll come back to that a bit later. uh for the moment uh this I think is is very natural but there's a big caveat here in that um there was a lot of cheating involved in all those definitions and the first cheat uh the cheat becomes obvious at this point down here where I said uh we put in these these random variables and sometimes the machine doesn't terminate which means it might need an infinite amount of of random variables.

10:10 So how am I even going to write down the configuration? Uh so all of this is um is getting a bit more tricky just because of this possibility that the machine keeps asking for more bits. But then why would it do that? Like can't we just restrict it to uh cases where we never use infinitely many random bits? Why would you? It sounds completely stupid. uh in particular we had this in unit two as well. We said in general during machines if you give me some arbitrary program they might do all sorts of nonsense but for the discussion of P versus NP and all that we restrict to total uh machines that always terminate after a fixed amount of time and you can always convert if a machine would be running for longer you keep a timer and when it when its time is up you just shut it down. Now uh for randomized um touring machines for probabilistic touring machines there are some simple tasks that seem not to work with that and so we don't want to disallow this infinite computations and here's a a simple example uh again I'm sure people will have seen random rejection sampling but let me go through this uh slowly and you'll you'll revisit it in the tutorials just to make extra sure. So um the way we define things is everything that we have that is random are random bits and they are uniformly random bits.

11:43 Now suppose we want to simulate um a six-sided die a uniform six-sided die. How can we do that? Uh I mean I could I could start with okay I'm I'm flipping one bit and ask uh is the number odd or even and then I've nicely divided things up. So I have three options left. Is it say if it's odd if is is this one three or five? How do I do that with just bits? Seems tricky but luckily there's a um a general solution that always works and is is a a lovely algorithm uh which is called rejection sampling. So for this concrete example, it's spelled out here. Uh I just called it roll die the function. We'll uh refer back to that a few times. uh it keeps looping in uh it does this as a potentially infinite loop. You draw three random bits that gives you eight possible answers.

12:45 Uh you take this as a representation of a number between zero and seven and then if it's out of bounds the die should have a number between 1 and six. If it's out of bounds which means here it's zero or seven then you discard this. you reject that random outcome and you just try again. Whereas if it is between one and six then you output that number. Okay? Have you seen this before? Rejection sampling is an idea is a it's a general trick. If if you have something that's hard to sample from, you sample from a super set and then check have you hit the set you wanted to sample from? And if not, you just try again. And um the the beauty of it is that it is very easy to show that it is perfectly uniform. Whenever you uh return something, it has to be perfectly uniform because you gave all the outcomes one to six exactly the same probability namely uh one out of eight.

13:46 Now uh the downside of course is it might never terminate if you're constantly unlucky. If uh your random bits are always zero, then this algorithm never returns.

14:01 Now, of course, you also know if you've seen rejection sampling, if you do this in practice, it it never causes problems in at least in this algorithm uh because the expected running time is constant. uh so uh to uh to prove that you can compute what is the probability of doing another iteration of the loop and here uh the probability to leave the loop is six out of eight options. So in in uh 75% of the cases we're done after one iteration and uh in 75% of the remaining 25 cases we're done after two iterations. And so you see where this is going. Um so the number of iterations I didn't put this on the slide for some reason uh is a geometric distribution and the number of so success means three fours that is I'm I'm doing exactly the same as if I was flipping an a biased coin where with probability 75% I'm immediately successful and otherwise I keep trying and I count how many tries did I need. So that's exactly the geometric definition geometric distribution by definition and then uh you could either look up we know the expected oh this uh the expected value the expected value of the geometric distribution is just one over p. That's worth keeping in mind. But of course you can prove it using the sum the series that is on the slide sorry P here it's one over P and the proof is is just this sum that's by definition the uh that's the definition of the expected value.

16:08 So this algorithm is correct. It uh uniformly samples. Its running time is a bit wonky. It sometimes takes longer and sometimes takes shorter. U but it's well characterized. We can understand how long it takes. It's a random variable that's well understood and it has a small expectation. So um after a constant amount of time or constant amount of iterations, you'll have your output. So why did we talk about this? I mean number one it's a it's a beautiful algorithm worth knowing rejection sampling is a beautiful idea but it also shows you if you were to try this sampling in a different way without this kind of um infinite loop it seems really hard to do and so uh we seem to want to deal with infinite runs in this context. Question Uh so the question is can you use arithmetic coding for this? Yeah I think you'll end up with the same problem. Um yeah think think about it. Uh I mean you uh you could essentially turn if you if you want to sample from a more complicated distribution or maybe even a sequence of things then arithmetic coding is a is a good way to turn uh to to generate a sampler that is um efficient in terms of the number of bits that it uses. But you can't avoid this case that you have to keep going with arithmetic coding.

17:51 The nice thing is you'll you'll prove in the tutorials that it's not possible. So it's not it's not a hard proof if you look at it from the right way. Uh for here I'll I'll just leave it with the statement that we seem to want to keep infinitely running or potentially infinitely running probabilistic Turing machines because they have they have practical use cases. Um, again, you'll you'll look at this a bit more in detail in the tutorials, and this is only one example.

18:27 So, what does that mean for our definitions? What could possibly go wrong, right? Uh, number one, um, if you have a randomized during machine, it could still do the same nonsense as before. You could enter an infinite loop even if that doesn't consume more random bits. Okay, but that type of problem we can actually discuss away. Uh that's the same as before and we can we can keep a counter or there's there's ways to deal with this. But there's a new problem that didn't occur before which is what we used in this roll die. uh we keep um we we have branches in the code and these are based on random bits and there is a possibility to be constantly unlucky like in the the case of rolled die always always take zeros. So um formally you could say for every time t that you put your timer on there's a certain probability non zero that you need more than that many steps and the computation is doing something sensible there is a new thing that didn't happen for deterministic Turing machines before. It did happen though for nondeterministic Turing machines. Um and the formal definition there is just said okay the running time then is infinite. If there's an option non-deterministically to keep going forever then that should should be infinite time. Okay, so we'll probably have to keep that. But now like for our algorithm roll die, is that a problem or isn't it or and also can we define the expected running time here? Like it seems the expected number of loops was not a problem. But can we define properly what the expected running time of our touring machine model is in uh in the presence of these weird cases where it keeps running forever.

20:22 Well, the answer is of course yes, but that's the reason why I introduced some of the abstract probability spaces uh terminology. You can you can properly define it. And here's here's one way to do it. Um the key question is what what probability space do we need? It seems if you start with random bits and everything's finite, oh everything's lovely discrete. Yeah. But if things are infinitely long, uh not so not so quick. So if you had um finite bit strings, then that's discrete even if they're infinitely many. What we really need here is an omega language uh or I mean I wrote this here or I'll write this here in the way formal language people would write it. 01 to the omega means it's um technically as a function that maps the natural numbers to 0 ones. That's one string. If you uh come back if you think about finite strings you could say a finite string is what? Well, it's mapping the numbers zero up to some number to elements in the alphabet. That's a string. And so the generalization is well, I'm doing the same, but it's an infinite domain. I'm mapping all of the natural numbers to a bit.

21:43 That's an omega word. So this one one B is called an omega word. Okay, I have to be a bit clearer. That's omega and that's W. And then I can talk about these in the same way. And you can talk about regular omega languages in the same way you do regular expressions for finite languages. There's some some cute automa theory in there, but we won't need that. Um, you could also think of these as infinite as as real numbers between 0 and one written as as uh infinite binary uh fractions. So in particular this is actually a bjection. You can take your infinite omega word and just write zero dot and then the digits the the bits and that's a number between zero and one and you can exactly represent all real numbers that way. Okay, it's kind of almost by definition. So maybe it's not super exciting. Um huh. by section. I'm not sure like maybe um uh the problem is there's potentially several representations for the same real number. Um you know uh 0.01111 is the same as 0.10 0.

23:14 Uh so maybe take this Um I don't want to lie. So maybe bjection is pushing it too far. Uh because these are as as real numbers. These are the same but as uh omega strings they're different. Cool. So maybe that's the reason why um why uh we don't directly go to real numbers. Um you know as a computation this might trigger different different computations. They're different bits. Okay. So um morally you can think about them as kind of real numbers uh but just the representations as infinite representations. Um clearly you see that it's a continuum right? These are at least as big as the real numbers between zero and one. So you can't they're certainly not discreet uh but they might be a bit bigger. So um also for our configuration of the Turing machines formally let's just write that the the sigma here so the the remaining part the right part on the infinite tape let's say that's an omega word so we're on the safe side if the machine needs more bits there's always going to be more bits because it's infinite. It's a bit annoying that we can't write down a configuration anymore because it's infinitely big. Uh but let's let's ignore that. Uh it's not a big problem really. We don't write them down.

25:05 What we need now is um a proper probability space for these infinite bit strings because that's what we want to take expectations over and compute probabilities from. And it turns out that's that's a known thing you it's known as as the Bernoli probability space. And um as for the boral sigma algebra for real numbers where you had open intervals as the kind of minimal elements here you have uh um I don't know the sometimes called cylinder sets but I guess it's just a prefix. So um the pi x are just all the um infinite 01 strings that start start with a certain prefix x is a you can think of it as kind of a restricted way to represent intervals uh in in in the real numbers or real number intervals you can have an arbitrary start and end point. Uh these numbers here are in a way always diatic intervals. They start at a negative power of two and have a length negative power of two.

26:19 Um right if you if you say this set is all the real numbers it corresponds to real numbers between 0 x 0 x1 up to whatever xn and then zeros all the way up to zero then the same axis and then all ons, Formally, pix is just a set of omega strings. Um, and it's all those omega strings that start with a given finite prefix. So, important here is that should have made that in red. Um, the prefix has to be a finite prefix. And it turns out you can turn this into a a sigma algebra by taking the closure under these operations. So you take all those pix sets and you take countable unions and complements and that is a a well- definfined sigma algebra the boli sigma algebra. So that's the measurable sets we can talk about. Okay, these pi axis unions and complements thereof and uh what's the probability? um you can you can assign the measure of of 1 pix and uh it's very natural I think that you say if we've seen a certain prefix of a certain length I've seen n random bits so it should be 2 to the minus n as the probability to see the exactly that string and the rest is I don't know what what comes after I'm summing all of them and so uh you only fix the probability only fixes the prefix So this defines the probability for the generators and the probability for any other set you can derive from that and using the abstract properties and uh you'll do that in the tutorials um to practice it.

28:31 Uh okay maybe let me briefly sketch how this could look like. Um if if you go back to our RO die example, what are the kind of bit strings where it terminates?

28:52 Uh it always chooses three bits at a time. And all of these as I'm drawing here are numbers between one and six. That's that's six, right? Yeah. So in all of these cases we're done.

29:18 In these two cases we continue. So you have to zoom in here. Then you do the same uh eight cases. So we have 0 0 0 and then 0 0 0 1 one and all the other options 0 one one etc. Here we terminate again for these two we have to continue and this of course gives you some large tree. Um what's the probability that this guy terminates? Well, it's the measure of all it's P of I guess I want to can I sum here? I guess it it technically is closer to an integral. Let's let's integrate over all row. Do I have a yeah 01 omega? I guess is the closest. Oh, not again. This is super annoying.

30:56 This one's also frozen. So that's not a good sign. Well, you would want to go over all these infinite uh the omegas words row where the algorithm terminates and sum up their uh measure.

31:17 I lost some of the drawings, but I guess we'll have to keep the good memories of them. Let me not repeat the drawings. Maybe uh the point was you can um you can define a language of omega strings. So the the roll die example The ro die terminates if and only if the initial the row the initial bit string we start with is in some language T which is a subset of these omega languages and we can now with this um Berni probability space we can talk about what's the measure of that of that set t and you can reexpress that using these prefixes and the prefixes nicely turn into the cases where the the algorithm terminates. Um I think this is doable enough but it's worth that you do it actively in the tutorials uh just to kind of be forced to mess around with the definitions a little bit. we won't much uh use that formal like this this probability space and how to work with it we won't need it much but I think it's I always felt it was very unsatisfying that you talk about these randomized algorithms and technically in many things were not well defined the the expectations you always needed handwavy uh bits to define what they mean so with this setup set up which is not not too complicated to work with as you'll see. Uh you can you can do this uh properly and the benefit is for the probabilistic Turing machines we can pretend that there's no randomness. The randomness is up front. You decide once for these for this infinite omega word of bits and then the machine can be deterministic and um everything can be uh computed based on that.

33:34 Uh the last last bit for for this to um to finish off is generalize what is running time or our new notion of Turing machines. And um we can define the worst case time as before. So the time the machine takes on a given input is the the worst the supreum of the time steps over all computations. Uh the original unit two slides had an infom there which is nonsense. It has to be the worst case or the largest and it's supreum instead of maximum because it could be uh infinity. It could be infinity at the time. Uh but we had the very same definition for nondeterministic Turing machines there. It was also possible that some branches of the possible computations just keep running forever. So time without a qualifier is the worst case time on that input. Right? time is worst case and that's not always very helpful for the roll die problem. It would be infinite.

34:40 So time roll die on on any input. It doesn't have an input actually, right? It's just spitting out some random. It would be infinite. Oh, not again.

35:00 I don't know what this this is. It needs to be solved. This is super annoying. It happens way too often. It's a new nonsense. Um yeah, have an idea. Maybe not now. Okay, so here the the worst case time is infinite, but we can define an expected time now that we have a probability space at hand. And that's just the expected value of this. And here's a last bit of notation we'll sometimes use. I write in the subscript of the expected value uh um operator, the random thing that we take the expectation over. This doesn't technically add anything. It's just for clarity of the presentation. This is stressing that the random thing we're talking about here is the random bits. Everything else is deterministic. And then formally you can say the expected time what we take expectation over is uh the smallest number of time steps t that it takes from the initial configuration to reach the halting configuration. If you start on a specific random row, that's the random bit. Okay, read. Uh this is this is the random part.

36:21 And then of course also the t is a random thing because it depends on row. So uh the whole thing is is the whole infamy is random. the shortest number of steps to reach the holding state from a random from for a specific sequence of bits and the expectation over that over all the bits that gives you the expected running time of this probabilistic Turing machine.

36:46 As before we define um instead of a specific input an input size you just take the worst case of all inputs of that size that's as before as I try to be consistent with having lowerase time to be on a specific input and uppercase time the worst case over inputs of a of a given size.

37:14 Uh, of course instead of the expectation you could also take the full distribution and sometimes we will. Um, but what's useful here for starters is the expected time is finite if and only if the probability to never terminate is zero exactly. In other words, uh we almost surely terminate if the expectation is finite. And that's pretty much what uh a sensible algorithm should do. It's okay if there is a a hypothetical option for it to run forever as long as it actually never does so with any positive probability. Right? You will remember from from probability theory that this almost surely something that happens with probability one is not so intuitive. You can up front fix some event that has probability zero but it can still happen in hindsight you know.

38:14 But we won't see it happen for our roll die algorithm. Uh just for the notation, I mean for the formal definition is not so important. Instead of time, you could also look at how many random bits did you need. That might be a useful thing to look at. You can formally define it by how far into the infinite row did you ever move. And here's a one here's a way to formalize that. But uh the intuition is just how many random bits did you use? Again, you can define this as the worst possible. Again, if you fix just the the actual input, it's a random thing. So it's the random number of random bits that you used. And the small case random is the worst overall possible random bit strings. Again, could be infinite. Uh so often times we'll talk about the expected number of random bits that we used and that's a bit of a a mind twist that the cost of random bits is also random but it's not such a bad thing if you think about it. I mean it's not it's not so unintuitive. You just consume this special operation bit give me another bit uh a certain number of times and how often might depend on the previous bits.

39:36 Nothing uh nothing more surprising than for the running time but we'll we'll use this occasionally. Uh for some for some algorithms it's important to economize on the random bits as well.