Video 1-1: Random Shuffle

0:02 In the first unit, we will look at some mathematical techniques for proofs. Maybe uh for most of you repetition, but I want to briefly refresh it. And then in the last part, we'll look at some more specialized proof techniques specific to algorithms, namely to prove termination and correctness. And uh these are not often covered in in standard undergrad math courses or introductory math courses, discrete math courses. uh but they are very relevant for algorithms. So I want to briefly show you those uh but we'll start very basic with um essentially the the templates of how to prove various statements of a specific form.

0:58 Before we get to the proof techniques, I want to motivate a bit why this is maybe a good idea to have. And for that, let's look at a toy problem that maybe you thought about at some point or maybe not. Uh we want to put an array of elements into a random order. And a bit more precisely, I'd like to have these n elements. So here again my uh my usual notation has a bit of a programming style. So um arrays are with the left index inclusive and the right index exclusive which has the benefit that if you just take the difference that's the number of elements and n minus 0 is n. So I have these elements at these indices and I'd like after this algorithm finishes these elements to be in any of the possible orderings with equal probability.

1:52 Imagine you're uh you're creating some computer game or you want to write uh an online poker website. You really want a shuffle algorithm to uh randomly shuffle cards. So here's um maybe a reasonable way to do this. Your algorithm my shuffle is given this array and then for each element in this array it picks a random position that it's swapped to. And again here I'm relying on some some library function here that gives you a random integer between zero and n. We can get further into how to do that and whether that's possible and so forth. If you wor if you worry about it, there is actual randomness in the universe for all practical purposes. You can build little hardware devices that measure the the resistance at some some electrical resisting resistor element and that is random enough to get out some random bits. It is rather slow to do it that way. So you can't get a lot of random bits per second out of these devices.

3:02 And then there are computational methods pseudo random generators that you may have heard of that are the the other option you have in this case. Uh let's abstract from that here. So we'll just here for for theoretical purposes assume this is perfectly uniform between zero and n and then we'll swap the element. Okay. Uh certainly after this has been run, most elements have been moved around a few times and it seems hard to really uh still see anything about the original order of the elements.

3:43 To make that extra clear, um here's a a little animation of this algorithm. Let's see if I zoom in. This is the same code that we had. Okay. Um, and the algorithm steps through these. Uh, that's not what I want. First one, you go through each of these indices I, you pick a random index to exchange that with, swap it, and then you move on to the next index I. uh these little strange dice here with a side with zero points is just the random number between zero and n in this case or n minus one. Uh here the random number is one. So you don't have a swap you swap with yourself. I moves to the next uh oh we again pick the same thing randomly. Sometimes randomness is is strange. And now with next I R is still three. Here we've found um position two sorry index two. So we do another swap and then the last iteration is for i as n minus one and again r is two. I'm doing my swap and I'm done.

5:03 Okay. And of course you can do this again. Then you have another random order at the end. The question is does this produce what we would like? Does this generate a random permutation? If you stare at the code for a while, uh maybe you figure it out or maybe not. Um what you could come up with is let's run this um several times on lists of a certain size. Um here I'm having lists of five uh of size five. That's maybe a bit too much. Let's just run it on two element lists. So there's only two options which order they come out, right? one first or two first. And it seems they come out with roughly the same probability. That's what we'd expect, right? And if you do it for three, then yeah, similar. And maybe for five. Okay, there's just a lot more, right? Those 120 different ones. Maybe if you keep this running for a while, we're all will be at the same height.

6:14 or not, who knows? We'd need a proof for that. Now, here I can maybe convince you if I run this and add a million simulations, I didn't cheat. It's just after a million, the law of large numbers kicks in so much that the future iterations don't change much. And this is not at all uniform. Okay, so this algorithm is fundamentally flawed. And maybe you've spotted this. Uh maybe not.

6:57 So if we do simulate this algorithm precisely for two elements, it is indeed equally likely that the two outcomes result. If you do the same for three elements, it already starts to look a bit shady. And this is what we've seen in the example. If you precisely compute the probabilities, then you get this picture. And it seems to get worse and worse. Okay, that's what we've seen. Uh and again, there's also an animation for the exact probabilities. Um you can compute this by just replacing the random simulation with all the different options you have to produce a random number. And for for these small examples, you can just go through all possible options and add up how many of them end up with the same list at the end. And it turns out indeed this is not uniform. So what should we do? The algorithm is broken. We found this out now almost by example, but it's very easy to miss.

8:13 The solution in this case is rather easy. First of all, don't use this code. Use this code instead. The difference is one subtle change. We uh started with our random index now at i and not at zero all the time. Again, uh one way to think about it is that um for each element I I'm choosing its uh its element from the elements further to the right that right for you. Uh and then after I've chosen this element, this is no longer moved around again. And I'm jumping a bit ahead of myself. How would you prove that this indeed works? inductively. Uh in the first step, this is I is zero. So for the position zero, I choose one out of all elements uniformly at random. I swap it there. This element is now great. This is as random as we wanted. Now I'm excluding this first element from consideration. And look at i equals 1, the second element. And again ask out of the remaining ones but not this first one which I've already excluded. Out of those remaining ones I pick one uniformly at random and put it there and so on.

9:37 This subtle change with the algorithm does what it's supposed to do. You change to this where here is an I. Then the exact probabilities are exactly uniform.

10:03 Okay. Again, um in this case, in hindsight, if you think about the two algorithms, um it's rather easy to prove that the first one cannot possibly work. Why? Um maybe, um let me show this with the dice again.

10:27 You have an input here and you run this. That's the correct one. Sorry, this one. In each round, you have one out of six possible options. And these are independent. So I have 36 total things that can happen. And I'm distributing this. Sorry, not 36. 6 to the^ six. a lot more but it's sum some multiple of six um and I have for six runs with six factorial 720 different orderings what's six to the^ six uh a large number let's go to three where it's a bit easier to compute we have three to power three different choices for selecting our dice here. That's 27. But we only have six different orderings. Now, the crucial thing is uh there's no way as 27 doesn't uh properly divide by six. There's no way to distribute the 27 outcomes to the six desired events, the different orderings, without giving some event a bit more probability than another.

11:48 And so there's there was no hope that this could work. On the other hand, the um correct algorithm takes one option out at each point. So I have 3 * 2 * 1 different random events and that works out to be three factorial which is precisely the number of different orderings of the list. So there I have a match one to one between the uh random things I can generate, the random choices I have um and the desired outcomes. So there is a way to map them oneonone. Now this is necessary. It's not guaranteeing that the algorithm is correct. For that you would still need to do an inductive proof using the techniques we haven't covered yet. The point about this example also was not so much to scare you with all the probability calculations. My point here really was uh for questions like this, it's rather important to have some way of specifying formally what an algorithm does. Just looking at the code is not super uh reliable.

12:57 I hope I fooled some of you into thinking that the algorithm first was correct and I guess now you understand it cannot and next time you will recognize this algorithm. But what do you do if you see a new problem with a much more complicated piece of code? Then we want to be able to pull out some BAML techniques out of the drawer.