1 00:00:00,279 --> 00:00:03,897 next we're going to talk about strings and tries. 2 00:00:03,898 --> 00:00:10,211 These are combinatorial objects that have really come under scrutiny because of 3 00:00:10,211 --> 00:00:15,364 computational applications. But they're very well suited to the 4 00:00:15,364 --> 00:00:19,370 analytic techniques that we've been talking about. 5 00:00:19,371 --> 00:00:25,028 Again I think we're in the second half of the class and this is lecture eight. 6 00:00:25,028 --> 00:00:30,572 And we're going to look at these data structure, these combinatorial objects as 7 00:00:30,572 --> 00:00:34,757 unlabeled classes mostly. So we'll be talking about OGFs. 8 00:00:34,757 --> 00:00:40,685 And again we'll give some examples in lecture, but there are many more in 9 00:00:40,685 --> 00:00:45,273 Chapter 8 of the book. So first thing we're going to talk about 10 00:00:45,273 --> 00:00:51,405 is bit strings with, with restrictions and we did some examples of this as our 11 00:00:51,405 --> 00:00:57,109 motivating examples for the analytic combinatorics in Lecture 5. 12 00:00:57,110 --> 00:01:01,752 But what we'll talk about today is answering questions like this. 13 00:01:01,752 --> 00:01:06,849 So this is a number of random bitstrings of 70 or 80 bits. 14 00:01:06,850 --> 00:01:13,040 And I've got highlighted in there the first, the currents of 000 in each bit 15 00:01:13,040 --> 00:01:16,254 string. So a natural question is what's the 16 00:01:16,254 --> 00:01:20,869 expected wait time? That is how many random bits do we need to 17 00:01:20,869 --> 00:01:25,447 see before we get to 000 in a, in a random bit string. 18 00:01:25,447 --> 00:01:32,561 Or what's the, some of these bit strings have no 000s well maybe not. 19 00:01:32,562 --> 00:01:39,666 So, but if you look at shorter ones, like at this distance, then there'd be no 0000. 20 00:01:39,666 --> 00:01:45,468 So the question is, what's the probability that you don't have 000 in an N, N-bit 21 00:01:45,468 --> 00:01:50,070 random bit string. And questions like this actually have lots 22 00:01:50,070 --> 00:01:55,810 of important, practical applications where the 0s and 1s correspond to electrical 23 00:01:55,810 --> 00:02:02,107 signals and certain kinds of devices can't take long strings of for, for example. 24 00:02:02,107 --> 00:02:09,027 So let's review what we talked about for the symbolic method for bit strings. 25 00:02:09,028 --> 00:02:14,736 It's one of the very simplest examples of analytic combinatorics. 26 00:02:14,736 --> 00:02:21,939 How many binary strings are there within bits is of course, they're 2 to the N. 27 00:02:21,940 --> 00:02:28,898 And we can do that with the symbolic method, by constructing the class of all 28 00:02:28,898 --> 00:02:32,984 binary strings, B, as a sequence of 0 or 1 bits. 29 00:02:32,984 --> 00:02:38,561 And then our normal symbolic transfer takes Z0 plus Z1 to 2Z. 30 00:02:38,561 --> 00:02:44,507 And sequence of anything of one over one minus that, so that tells us that the OGF 31 00:02:44,507 --> 00:02:50,267 that enumerates the number of binary strings is B of Z equals 1 over 1 minus 32 00:02:50,267 --> 00:02:54,786 2Z, and so, the coefficient is Z to the N and that is 2 to the N. 33 00:02:54,786 --> 00:03:00,813 That's our basic construction for binary strings using the symbolic method. 34 00:03:00,814 --> 00:03:06,122 And then we have an alternate way of expressing the same thing. 35 00:03:06,123 --> 00:03:11,271 If you say that a bit string is either empty or it's a bit followed by a bit 36 00:03:11,271 --> 00:03:16,494 string, a recursive definition, then you get down to the same result. 37 00:03:16,495 --> 00:03:24,440 In this one generalizes to help us answer questions like how many N-bit strings have 38 00:03:24,440 --> 00:03:30,145 no two consecutive 0s. And again, using the same reasoning, we 39 00:03:30,145 --> 00:03:36,801 could say that a bit string with no two consecutive 0s is either empty or it's a 40 00:03:36,801 --> 00:03:43,633 single 0 or it's a 1 or a 01 followed by a bit string of those tw consecutive 0s. 41 00:03:43,634 --> 00:03:49,880 That's, the natural construction for this class of combinatorial objects. 42 00:03:49,880 --> 00:03:55,581 And then that translates through the normal translation theorem to this OGF 43 00:03:55,581 --> 00:03:59,896 equation. 1 plus Z plus quantity Z plus Z squared 44 00:03:59,896 --> 00:04:03,910 times B00. And then we can solve that and we get a 45 00:04:03,910 --> 00:04:09,290 polynomial, a ratio of two polynomials for the generating functions. 46 00:04:09,290 --> 00:04:14,906 And our asymptotic, that's a classic example in asymptotic analysis the 47 00:04:14,906 --> 00:04:20,686 coefficient of Z to the N in that function it's going to be, well, in this case it's 48 00:04:20,686 --> 00:04:25,978 exactly the Fibonacci numbers. But in general, if it's any polynomials, 49 00:04:25,978 --> 00:04:31,380 you look at the largest root of the polynomial in the denominator. 50 00:04:31,381 --> 00:04:38,621 And that gives an, an asymptotic expression for the coefficient of, of B to 51 00:04:38,621 --> 00:04:44,622 the N in that generating function. So simply by finding the appropriate root 52 00:04:44,622 --> 00:04:50,856 of the polynomial, we get the asymptotics. And for any polynomial, it's going to be 53 00:04:50,856 --> 00:04:56,790 the form of constant times the root to the Nth power unless there happen to be 54 00:04:56,790 --> 00:05:01,561 multiple roots. So, in this case the it's the golden 55 00:05:01,561 --> 00:05:07,896 ratio, phi to the Nth power and then the constant also is explicitly determined. 56 00:05:07,896 --> 00:05:11,536 So that's example that we did in Chapter 5. 57 00:05:11,536 --> 00:05:17,548 So, first thing we want to do today is extend that how many binary strings have 58 00:05:17,548 --> 00:05:22,492 no runs of p consecutive 0s. And that's going to extend in a natural 59 00:05:22,492 --> 00:05:27,126 way very much like the derivation that I just did. 60 00:05:27,126 --> 00:05:34,019 So the construction then is a string with no runs of p consecutive zeros is a string 61 00:05:34,019 --> 00:05:39,936 of zeros of length less than p, followed by either an empty string or a 1one 62 00:05:39,936 --> 00:05:45,112 followed by a string with no runs of p consecutive zeros. 63 00:05:45,113 --> 00:05:52,390 So that's just a generalization of the construction that I did on the last slide 64 00:05:52,391 --> 00:06:00,708 and again that immediately translate. A string of zeros of length less than P is 65 00:06:00,709 --> 00:06:05,734 1 plus Z plus, so forth, up to Z to the P, minus 1. 66 00:06:05,735 --> 00:06:10,279 And then E translates to 1 and ZP, BP of Z. 67 00:06:10,280 --> 00:06:17,607 And, so solving that equation gives BP of Z equals, again, a ratio of two 68 00:06:17,607 --> 00:06:22,186 polynomials. And again, the coefficient of Z to the N 69 00:06:22,186 --> 00:06:28,881 in that is asymptotic to a constant times a largest route to the Nth power where 70 00:06:28,881 --> 00:06:33,621 that dominant root is something we can calculate. 71 00:06:33,621 --> 00:06:38,467 And also, the coefficient is explicitly available. 72 00:06:38,467 --> 00:06:45,970 So this no runs of P consecutive zeros comes down to finding the dominant root of 73 00:06:45,970 --> 00:06:50,261 that polynomial, 1 minus 2Z plus Z to the P plus 1. 74 00:06:50,262 --> 00:06:57,901 And this is using the Sage mathematical system to just find those roots and you 75 00:06:57,901 --> 00:07:04,359 can use any system that you want and I didn't calculate the constants. 76 00:07:04,360 --> 00:07:09,727 But let's, let's look at so anyway those are those results. 77 00:07:09,728 --> 00:07:14,512 Now let's look at what we can infer from, from that result. 78 00:07:14,512 --> 00:07:19,459 So this is the summary of where we were for consecutive zeros. 79 00:07:19,460 --> 00:07:26,012 The OGF, S sub P of Z, is going to be the sum of N, the number of bit strings of 80 00:07:26,012 --> 00:07:31,391 length N with no runs of P consecutive zeros times E to the N. 81 00:07:31,391 --> 00:07:39,797 And that we have an explicit formula for that OGF, 1 minus E to the P over 1 minus 82 00:07:39,797 --> 00:07:45,567 2Z plus E to the P plus 1. Now this is similar to the situation we 83 00:07:45,567 --> 00:07:51,330 had with permutations. We can convert that into a probability by 84 00:07:51,330 --> 00:07:57,401 appropriate evaluating it, appropriate value of the argument. 85 00:07:57,401 --> 00:08:04,469 If you look at SP of Z over 2, then the Z to the N becomes a 1 over 2 to the N Z 86 00:08:04,469 --> 00:08:09,586 over 2 to the N. So what that is the probability that a bit 87 00:08:09,586 --> 00:08:16,517 string of length N has no run of P0s. So it's a PBF just by expressing, just by 88 00:08:16,517 --> 00:08:20,910 evaluating the article, the argument at Z over 2. 89 00:08:20,910 --> 00:08:29,533 So now, if we take Z equals 1 then that's just summing the what is that? 90 00:08:29,533 --> 00:08:36,494 That's the sum on N of the number of bit strings of length N with no runs of P 0s 91 00:08:36,494 --> 00:08:40,209 divided by 2 to the N, which is the sum on N. 92 00:08:40,209 --> 00:08:45,444 The probability that the first N-bits have no runs of P0s. 93 00:08:45,445 --> 00:08:51,522 So and that's the same as the sum that the, of the probability that the end of 94 00:08:51,522 --> 00:08:57,096 first run of P0s is bigger than N. So number of bit strings of length N with 95 00:08:57,096 --> 00:09:01,889 no runs divided by 2N. There's a probability that the first end 96 00:09:01,889 --> 00:09:06,633 bits have no runs of P0s. And that's the same as the probability 97 00:09:06,633 --> 00:09:11,889 that the position of the end of the first run of P0s is bigger than N. 98 00:09:11,889 --> 00:09:19,122 But that's exactly the average position of the end of the first run of p 0 so that's 99 00:09:19,122 --> 00:09:25,523 the average weight time. So this argument just gives us these two 100 00:09:25,523 --> 00:09:29,900 theorems. The first one is the probability that the 101 00:09:29,900 --> 00:09:36,108 n bit random bit string has no run of b 0. It's the coefficient of z to bn and sp 102 00:09:36,108 --> 00:09:40,734 evaluated over time. Two, that's the second line here. 103 00:09:40,734 --> 00:09:45,993 And so going from the solution on the previous slide. 104 00:09:45,993 --> 00:09:51,047 It's going to be our dominant root divided by two to the n. 105 00:09:51,047 --> 00:09:57,868 And then the other thing is the expected wait time is just our generating function 106 00:09:57,868 --> 00:10:02,747 evaluated at one half. If you evaluate that generating function 107 00:10:02,747 --> 00:10:08,315 at one half to see that all is left the 1 minus 2c cancel out plus one half to the p 108 00:10:08,315 --> 00:10:12,944 plus 1 in the denominator so it becomes 2 to the p plus 1 minus 2. 109 00:10:12,944 --> 00:10:18,674 So that's using the symbolic method, get information explicit version of the 110 00:10:18,674 --> 00:10:24,496 generating function and then evaluating that generating function to get the 111 00:10:24,496 --> 00:10:30,201 analysis of the properties of the consecutive zeros in a random bit string. 112 00:10:30,201 --> 00:10:37,520 Now, so just to summarize for small values of p, which are usually what's of 113 00:10:37,520 --> 00:10:43,389 interest. So that's our generating function, when P 114 00:10:43,389 --> 00:10:48,882 equals 1, is 1 minus c over 1 minus 2Z, 2 Z squared. 115 00:10:48,882 --> 00:10:55,926 So the probability of approximate probability of no zeros in random bit 116 00:10:55,926 --> 00:11:02,295 strings of size n is 1 half to the N. And then, 10, that's is 0.0010 and 100 is 117 00:11:02,295 --> 00:11:06,497 10 to the minus 30th and the average wait time is 2. 118 00:11:06,497 --> 00:11:16,055 For 3 zeroes, then we can do the explicit eh, those are the values of the roots. 119 00:11:16,055 --> 00:11:23,582 And it turns out that, probability of no run of two zeroes in ten bits is about 120 00:11:23,582 --> 00:11:27,956 point one four. And 100 bits is ten to the minus nine. 121 00:11:27,956 --> 00:11:32,251 And the wait time for the first run of 2 zeros is about 6. 122 00:11:32,251 --> 00:11:38,363 For three zeros now probability of no run of three zeros becoming more and more 123 00:11:38,363 --> 00:11:41,946 likely. So for ten bits it's about even chance 124 00:11:41,946 --> 00:11:48,418 that there's no run of three zeros. For 100, 100 bits still fairly unlikely. 125 00:11:48,419 --> 00:11:55,390 4 zeros now 10 bits, three quarters of the time you're not going to have 4 zeros in a 126 00:11:55,390 --> 00:11:59,105 row. You have to wait 30 bits to get your first 127 00:11:59,105 --> 00:12:03,408 run of 4 zeros on average. But for 100 bit is still. 128 00:12:03,409 --> 00:12:07,363 Pretty unlikely that you won't have four zeroes in a row. 129 00:12:07,363 --> 00:12:12,868 And then for five zeroes now it's almost 90% chance that you're not going to have 130 00:12:12,868 --> 00:12:15,781 five consecutive zeroes in ten random bits. 131 00:12:15,781 --> 00:12:20,842 20% chance you're not going to have five consecutive zeroes in 100 random bits. 132 00:12:20,842 --> 00:12:26,277 And the wait time is 62. And then for 6 0's, it's almost certain 133 00:12:26,277 --> 00:12:32,547 and it's even chances in a string or a random string of 100 5ths that you won't 134 00:12:32,547 --> 00:12:38,086 have 6 consecutive 0's. And your wait time is over 100, 126. 135 00:12:38,086 --> 00:12:43,915 So those are facts that we can derive from this analysis. 136 00:12:43,916 --> 00:12:51,933 And actually this type of statistic is one way to test whether a set of strings is 137 00:12:51,933 --> 00:12:55,422 random. In fact, it's always worthwhile to 138 00:12:55,422 --> 00:12:59,090 validate these types of mathematical results. 139 00:12:59,090 --> 00:13:04,892 And in situations like this when it's so easy to write code to validate these 140 00:13:04,892 --> 00:13:11,527 results, we should go ahead and do it. So this is a java program that takes as 141 00:13:11,527 --> 00:13:18,427 argument size and number of trials and what it 's going to do is, it 's going to, 142 00:13:18,427 --> 00:13:24,763 this one actually reads the bits from standard in so we separate. 143 00:13:24,764 --> 00:13:29,246 Separate out what the bits are, from analyzing them. 144 00:13:29,246 --> 00:13:33,379 So this will read W bits at a time from standard in. 145 00:13:33,380 --> 00:13:38,790 So like in that example, W was 75. And there were a bunch of occurrences of 146 00:13:38,790 --> 00:13:44,577 75 bits that were supposed to be random. And then for each P it'll check whether 147 00:13:44,577 --> 00:13:49,842 there's a 0 P consecutive zeros and then it'll just print out the empirical 148 00:13:49,842 --> 00:13:53,996 probababilities. And then this is just the code to check 149 00:13:53,996 --> 00:13:58,208 for P consecutive zeros, so this is a very straightforward. 150 00:13:58,209 --> 00:14:01,956 Program that reads in a bunch of bit strings. 151 00:14:01,956 --> 00:14:08,250 And then prints out the out of all those bit strings, what's the empirical 152 00:14:08,250 --> 00:14:14,970 probability that, you find, one, two, three, four, five, up to P consecutive 153 00:14:14,970 --> 00:14:19,300 zeroes. And so for the example that I used on the 154 00:14:19,300 --> 00:14:22,955 first slide. This the data that it gives. 155 00:14:22,955 --> 00:14:27,485 And so actually, those were the first line of, 10,000 bits. 156 00:14:27,485 --> 00:14:32,763 10,000 bit strings of size 100. And for those bit strings those are the 157 00:14:32,763 --> 00:14:38,652 probabilities that. 0, 1, 2, 3, 4, 5, 6, 0s occurred and those 158 00:14:38,652 --> 00:14:46,632 compare very favorable with what we just saw was predicted by the theory. 159 00:14:46,632 --> 00:14:53,272 So, we can think that those bits are. Pass this test for randomness. 160 00:14:53,272 --> 00:14:59,119 Or we can think of this as validating the theory that we just arrived. 161 00:14:59,119 --> 00:15:06,713 Predicting, for example, that you have 45% chance of finding, say, 6 consecutive 0's. 162 00:15:06,714 --> 00:15:12,842 In the random bit strings. Okay, so that's a fine generalization of 163 00:15:12,842 --> 00:15:19,967 the simple example, example that we did for how many bit strings that had, don't 164 00:15:19,967 --> 00:15:25,397 have two consecutive zeros. Now so to check [laugh]. 165 00:15:25,397 --> 00:15:33,003 So now the next thing that we want to do is consider other specified patterns so 166 00:15:33,003 --> 00:15:37,767 say it's not 000 that we're interested in, but say 001. 167 00:15:37,767 --> 00:15:45,521 So now in blue you can hardly see but the wait time for 000, that's the one that I 168 00:15:45,521 --> 00:15:51,507 did before, is in, is in red, and it's an average about 18 for these. 169 00:15:51,508 --> 00:15:58,061 But in blue is the wait times for 001, so And the first line, the first occurrence 170 00:15:58,061 --> 00:16:03,439 of 001 is starting at the 9th bit. In the 2nd it's at the 4th bit, and so 171 00:16:03,439 --> 00:16:07,170 forth. And this time, the expected wait time for 172 00:16:07,170 --> 00:16:11,801 001 in this set of bitstrings is only 6, it's much, much less. 173 00:16:11,801 --> 00:16:16,496 And now we're wondering, are these bitstrings really random? 174 00:16:16,496 --> 00:16:21,013 What's going on here? Well the, the fact is that the pattern 175 00:16:21,013 --> 00:16:25,397 itself definitely is a factor in what the wait time is. 176 00:16:25,397 --> 00:16:28,478 And that's what we're going to look at next. 177 00:16:28,478 --> 00:16:34,874 So we showed before that the probability that an end bit random bit stream doesn't 178 00:16:34,874 --> 00:16:39,524 have four zeros in a row. Is about point nine six to the end. 179 00:16:39,524 --> 00:16:46,825 So and the expected wait time is 30, and the question is does, does that same thing 180 00:16:46,825 --> 00:16:50,787 hold for 0, 0, 0 1 or any other pattern of four bits. 181 00:16:50,787 --> 00:16:56,129 And the answer is no. So in every, every, one, one that we did 182 00:16:56,129 --> 00:17:00,607 the 0, 0 1 occurs much earlier than the 0, 0, 0, 0. 183 00:17:00,607 --> 00:17:07,386 So it's a little intuition behind that. So let's say, consider the first 184 00:17:07,386 --> 00:17:14,499 occurrence of three zero's in a row. Now the next bit could be either zero or 185 00:17:14,499 --> 00:17:18,598 one. So our two patterns are equally likely 186 00:17:18,598 --> 00:17:24,932 once, once we found zero, zero, zero. But the thing is, if we were looking for 187 00:17:24,932 --> 00:17:31,210 zero, zero, zero then that would mean that we're looking for four zeros and we didn't 188 00:17:31,210 --> 00:17:34,376 find it. It would mean that we have zero, zero, 189 00:17:34,376 --> 00:17:40,052 zero one in our bit stream and we're going to have to wait at least four more bits 190 00:17:40,052 --> 00:17:44,805 before we can find zero, zero, zero. But if we were looking for zero, zero, 191 00:17:44,805 --> 00:17:49,623 zero, one, and we had a mismatch, it would mean that there's four zeroes, and the 192 00:17:49,623 --> 00:17:53,632 next bit could give us a match. So if we're going from left to right 193 00:17:53,632 --> 00:17:58,600 looking for these two patterns, it's not surprising that we're going to find zero, 194 00:17:58,600 --> 00:18:02,286 zero, zero, one first. Find three 000 in a row we get a good 195 00:18:02,286 --> 00:18:07,590 chance of being the next[INAUDIBLE], but if we're finding looking for 4 zeros in a 196 00:18:07,590 --> 00:18:12,504 row and we find 3 zeros then we're going to have to wait a long time for the next 197 00:18:12,504 --> 00:18:15,535 bit. That's the intuition behind why it occurs 198 00:18:15,535 --> 00:18:18,931 much earlier. So, but now we want the answer to this 199 00:18:18,931 --> 00:18:21,948 question. What's the probability that a random bit 200 00:18:21,948 --> 00:18:25,376 string doesn't contain that pattern? Zero, zero, zero one. 201 00:18:25,376 --> 00:18:29,855 It's a little bit counterintuitive that it's not the same for any set of four 202 00:18:29,855 --> 00:18:32,596 bits. But it's definitely not, as we'll see. 203 00:18:32,596 --> 00:18:37,008 Or what's the wait time for the first occurrence of 0001? 204 00:18:37,008 --> 00:18:41,744 And what about other patterns like 1110, or 1111 and so forth? 205 00:18:41,744 --> 00:18:48,050 So the idea that it's the pattern itself that determines the probability existence 206 00:18:48,050 --> 00:18:54,218 and the expected wait time has to do with a phenomenon called auto-correlation. 207 00:18:54,219 --> 00:18:59,987 That's what we're going to look at next. So what we'll do is use the symbolic 208 00:18:59,987 --> 00:19:06,827 method to get explicit equations for the generating function for number of bit 209 00:19:06,827 --> 00:19:10,680 strings not containing a specified pattern. 210 00:19:10,680 --> 00:19:18,191 And it's remarkably easy to develop such an equation with the symbolic method. 211 00:19:18,191 --> 00:19:23,019 So what we'll say, is we'll take any pattern p. 212 00:19:23,019 --> 00:19:29,305 So it's a, a pattern of bits. And s sub p is the binary strings that 213 00:19:29,305 --> 00:19:33,441 contain, do not contain that pattern at all. 214 00:19:33,441 --> 00:19:39,907 And then we'll define t sub b, p, to be the binary strings that end in p. 215 00:19:39,908 --> 00:19:46,947 And have no other occurence of p inside. So that's two well defined sets of bit 216 00:19:46,947 --> 00:19:51,571 strings. And so what we're going to do is have two 217 00:19:51,571 --> 00:19:57,895 different constructions that relate these classes of bit strings. 218 00:19:57,895 --> 00:20:02,287 So the first one is based on the following observations. 219 00:20:02,287 --> 00:20:07,625 These two sets are disjoined. That is the t sub p has the pattern in it. 220 00:20:07,625 --> 00:20:13,214 S sub p does not have the pattern in it. So there's no string that's in both of 221 00:20:13,214 --> 00:20:16,771 them. Empty string doesn't contain a pattern. 222 00:20:16,771 --> 00:20:20,570 So it's in s sub p. And the other thing is, if we have a 223 00:20:20,570 --> 00:20:25,816 string in s sub p, and we add one bit to it, either we're going to get a string 224 00:20:25,816 --> 00:20:31,148 that's in s sub p, or, that bit will complete the pattern, and we'll get a 225 00:20:31,148 --> 00:20:35,679 string that's in p sub p, the only occurrence of the pattern. 226 00:20:35,680 --> 00:20:42,936 So based on those observations we have this symbolic equation our construction 227 00:20:42,937 --> 00:20:49,884 that relates these classes of string. S sub p plus T sub p is either empty or 228 00:20:49,884 --> 00:20:55,340 it's S sub p with a bit added. So that's the first equation. 229 00:20:55,341 --> 00:21:02,206 And here's the second construction that relates these two combinatorial classes. 230 00:21:02,207 --> 00:21:08,552 It's based on the idea of what's called an auto, auto correlation polynomial. 231 00:21:08,552 --> 00:21:13,951 That is a property of a pattern. And the idea is, we take the pattern in 232 00:21:13,951 --> 00:21:17,463 black. And then slide the pattern to the left 233 00:21:17,463 --> 00:21:20,656 over itself. And so, well, at the beginning, the 234 00:21:20,656 --> 00:21:25,806 pattern matches itself. And, The number of trailing bits we used 235 00:21:25,806 --> 00:21:29,167 as an exponent. So we start out with a z to the zero in 236 00:21:29,167 --> 00:21:33,074 the polynomial. And then we slide over 1, 2, 3, 4 5 237 00:21:33,074 --> 00:21:39,146 positions, and when we slide over 5 positions, then the trailing bits match 238 00:21:39,146 --> 00:21:45,306 the leading bits of the pattern, the 1 0 1 0 at the beginning matched the trailing 4 239 00:21:45,306 --> 00:21:49,132 bits. And we slid 5 positions, so we put z to 240 00:21:49,132 --> 00:21:52,914 the 5th. And then 2 more positions the 2 trailing 241 00:21:52,914 --> 00:21:56,523 bits match the 2 leading bits, that's z to the 7th. 242 00:21:56,524 --> 00:22:01,605 So in all the possible slides, the only match of the trailing bits with the 243 00:22:01,605 --> 00:22:05,142 leading bits is as positions zero, five and seven. 244 00:22:05,142 --> 00:22:10,369 That defines the autocorrelation polynomial of the pattern for this one. 245 00:22:10,370 --> 00:22:15,800 It's auto autocorrelation polynomial is 1 plus Z to the 5th plus Z to the 7th. 246 00:22:15,800 --> 00:22:21,546 And that's going to play a role in the development of another relationship 247 00:22:21,547 --> 00:22:27,598 between the two combinatorial classes we just defined, this is the second 248 00:22:27,599 --> 00:22:32,998 construction. So remember S sub P doesn't contain the 249 00:22:32,998 --> 00:22:39,594 pattern and T sub P ends in the pattern but has no other occurrence of the 250 00:22:39,594 --> 00:22:43,123 pattern. And so, the idea is if you take any string 251 00:22:43,123 --> 00:22:48,269 in T sub P And then you add a tail corresponding to the tail that you'd get 252 00:22:48,269 --> 00:22:51,764 to complete the pattern, in the auto correlation. 253 00:22:51,764 --> 00:22:57,166 So the first ones null, the second one, if you add the five bits that you shifted off 254 00:22:57,166 --> 00:23:01,186 at the end of the pattern, you get an occurence of the pattern. 255 00:23:01,187 --> 00:23:06,828 And again if you add the seven bits you get an occurance of the pattern. 256 00:23:06,828 --> 00:23:11,910 So in those three cases, null one corresponding to each bit in the 257 00:23:11,910 --> 00:23:15,986 auto-correlation polynomial you'll get a string. 258 00:23:15,986 --> 00:23:22,544 That if you have a, a string in s sub p that does not contain that the pattern if 259 00:23:22,544 --> 00:23:26,858 you add the I'm sorry. If you have a string in t sub p. 260 00:23:26,858 --> 00:23:32,035 And you add these tails then you'll get a string in s sub p. 261 00:23:32,035 --> 00:23:37,482 But from knocking off the pattern. So every time the result is a string in s 262 00:23:37,482 --> 00:23:42,594 sub p followed by the pattern. So S of P times the pattern is T sub B 263 00:23:42,594 --> 00:23:48,684 times the one place for each bit in the correlation polynomial. 264 00:23:48,684 --> 00:23:53,388 So that's going to give us the combinatorial construction. 265 00:23:53,389 --> 00:23:59,515 So we have those two constructions. One if you add a bit to a string in S, you 266 00:23:59,515 --> 00:24:05,467 get either a string in S of P, and the other one is if you take a string in T and 267 00:24:05,467 --> 00:24:11,899 you got a, a chance for every bit in the auto correlation polynomial to make a 268 00:24:11,899 --> 00:24:17,341 string in s followed by the pattern. Those are the two construction. 269 00:24:17,341 --> 00:24:23,768 And these use the these two constructions are set up for the symbolic method. 270 00:24:23,768 --> 00:24:28,579 They just use the basic operations. So they immediately correspond to 271 00:24:28,579 --> 00:24:34,832 generating function equation. First one Z0 plus Z1 is 2Z and otherwise 272 00:24:34,832 --> 00:24:40,530 it just directly corresponds to the adding of generating functions. 273 00:24:40,531 --> 00:24:46,972 In the second one, the pattern has OGFZ to the P so SP times Z to the P equals PP. 274 00:24:46,972 --> 00:24:52,642 And then what's left over here is the correlation polynomial itself. 275 00:24:52,642 --> 00:24:58,842 So now we have 2 equations in S and P that we can solve, and the correlation 276 00:24:58,842 --> 00:25:03,016 polynomial of the pattern is part of the answer. 277 00:25:03,016 --> 00:25:08,038 So, that's a solution of those two simultaneous equations. 278 00:25:08,039 --> 00:25:14,229 The, this is the OGF for the class of binary strings that contain no occurrence 279 00:25:14,229 --> 00:25:19,292 of the specified pattern. Now for any particular pattern, we can 280 00:25:19,292 --> 00:25:25,250 plug in the correlation polynomial and again we have a ratio of two polynomials. 281 00:25:25,250 --> 00:25:29,978 We find the dominant root. The one in the denominator in our count is 282 00:25:29,978 --> 00:25:36,262 asymptotic to that root to the nth. Power multiplied by a constant that we can 283 00:25:36,262 --> 00:25:42,120 compute explicitly. So this is a methodology that's going to 284 00:25:42,120 --> 00:25:48,542 work for any pattern at all. So here's the end result for 4-bit 285 00:25:48,542 --> 00:25:53,662 patterns. So of all possible 4-bit patterns actually 286 00:25:53,662 --> 00:26:00,340 there's only four different possibilities for the auto correlation. 287 00:26:00,341 --> 00:26:05,313 It turns out. Uh,[cough] so that classifies the four bit 288 00:26:05,313 --> 00:26:12,581 patterns with those auto correlations. They, they all s, start with the one in 289 00:26:12,582 --> 00:26:17,365 well, those are the auto correlations that can come up. 290 00:26:17,366 --> 00:26:23,949 So those lead to those different o g fs. And so they all have different dominant 291 00:26:23,949 --> 00:26:27,647 roots. And I didn't computer the constants here. 292 00:26:27,647 --> 00:26:32,886 They're all pretty close to one. And then you can see that, now this one 293 00:26:32,886 --> 00:26:36,873 with one zero, zero, it's a slightly smaller number. 294 00:26:36,874 --> 00:26:42,999 We, when we raise that number to the 10th power we're going to get a smaller number 295 00:26:43,000 --> 00:26:47,465 and for the 100th power it's going to be much, much smaller. 296 00:26:47,466 --> 00:26:54,060 It's interesting in maybe counter intuitive, but these are the results. 297 00:26:54,060 --> 00:27:00,338 You're going to wait about twice as long for 4 zeros or 4 ones as you are for 298 00:27:00,338 --> 00:27:06,469 anyone of those six patterns. Or another way to look at it is that. 299 00:27:06,470 --> 00:27:16,121 0000, 4 zeros is a 100 times more likely to be absent in 100-bit strings than all 300 00:27:16,121 --> 00:27:21,242 of these other patterns, say 0001 0011 00111. 301 00:27:21,243 --> 00:27:30,769 So studying this table maybe, is a, a good way to win some bar bets, perhaps. 302 00:27:30,769 --> 00:27:40,746 It's kind of surprising that we can so completely characterize this problem with 303 00:27:40,746 --> 00:27:47,678 analytic combinatorics. That's the study of bit strings with 304 00:27:47,678 --> 00:27:53,290 restrictions and these studies extend in various ways.