So, that's bitstrings with restrictions on consecutive zeros.

this generalizes and this material is from part one of Analytic Combinatorics

in the next few slides. so I'll go quickly through it.

for people that have taken that course and people that haven't taken that

course. if you're confused by something on these

slides, you might want to watch that lecture which goes through more slowly

and in more detail. But I'll go quickly through it now.

so, our generating function is the generating function for the number of bit

strings that contain say no occurence of n consecutive 0s.

And so and then we went ahead and calculated what that looks like, just

using combinatorial construction. and it turns out to have that form.

That's just a generalization of the Fibonacci that we got for no two

consecutive zeros. and actually by multiplying by 1 minus z,

both numerator and denominator, you get a slightly smaller form of that.

that's the same function. now what's convenient about this

particular generating function is if you evaluate it at z over 2 then it just

divides by 2 to the n. And it turns into a probability

generating function. so that if in, evaluated to z equals 1,

so sorry, evaluated z equals 1 half is really what we're doing.

so that gives some number of bitstrings with no runs of M0s divided by 2N, that's

the probability that the first N bits of a bitstring have no runs of M0s.

and we're summing those probabilities that's the same as the probability that

the end of the first bitstring is bigger than N.

and that gives the expected position of the N to the first occurrence of M0s.

Just evaluating the generating function at 1 half.

So that immediately, just evaluating this set at 1 half immediately tells us

[COUGH] that the probability that in bet, bitstring has no zero and we know that.

And if we just evaluated that at 1 half, we'd get 2 to the M plus 1 minus 2.

So the expected position of the first run M0s in a random bitstring is a 2 to the M

plus 1 minus 2. And that's a simple probability

calculation. and this is interesting to think about

because if we go to different patterns that are not necessarily all zeros we

calculated the probability that a random bistring doesn't contain four zeros.

And show that the expected wait time for four zeros is 30.

what about for 001, or some other pattern?

and what's interesting if you haven't thought about it is that it's, it's not

true. The wait time is different and

probabilities are different. and for example, 0001 occurs much earlier

then 0000. And just to get a little intuition for

that, just consider the first occurrence of three zeros in a row.

So, it's equally, likely that 000 and 001 happen after that.

but if if the next bit is a 1 then you know you're going to have to wait four

more bits to find 000. but if you're looking for 001 and the

next is a 0, it could give that the next set gives a match.

So, you ought to find 0001 sooner than 0000.

That's just the intuition we'll show this analytically in, in just a minute.

so, we are interested in these problems and there's lots of practical problems

where we care about when patterns occur in random bitstrings.

So, what's the, what is the probability it doesn't contain 0001 if it's not that

and what's the wait time for 0001? Well, the generalizing the techniques

that we use with generating functions that we can actually generate, develop

explosive formulas for these generating functions.

And I'll just quickly go through this derivation again because it's from Part 1

Lecture Five. and what we do is we for any pattern, say

this pattern 101001010 we define two combinatorial classes.

One for the strings that do not contain the pattern, and one for the class of

strings that end in the pattern and have no other occurrence of it.

And then, what we do with that is we develop constructions, two different ways

to construct these classes with in terms of each other.

And that gives us simultaneous equations that we can solve to get the generating

function. so first one is, for example, to notice

that these things are disjoint. if it doesn't contain p, then it can't

end in p that Sp has the empty string. And if you add a bit to the string in Sp,

either you get the string that doesn't contain the pattern, or you get a string

that ends in the pattern. And that just corresponds to this

combinatorial construction. the second construction is a little bit

more complicated. It's developed in terms what's called an

auto-correlation polynomial, where we slide the pattern to itself over, to the

left, over itself. and if the trailing bits with the leading

bits match, then we include a term. So, zero shift makes a match.

But after a while, if we shift five positions, then 1010 matches the leading

bits and so forth. So we define this thing in this way

called the Auto-correlation Polynomial. And with the Auto-correlation Polynomial,

we can develop another combinatorial construction.

And then, we'll go through the details of this.

again, look in Lecture Five if you want to see them.

that gives the construction of these two classes, Sp and Tp, in terms of the

Auto-correlation Polynomial. So if we want to find the bitstrings that

don't contain a specified pattern, we have these two combinatorial classes.

they have their generating functions and we have the, two constructions.

And those constructions by the symbolic method, immediately translate into two

different generating function equations, involving our generating functions of

interest and the correlation polynomial. Solving those equations then we get an

explicit solution for the class of binary strings that do not contain a given

pattern. A very simple rational generating

function. so that's the ratio of two polynomials.

And so, that means that we can use the general procedure to go ahead and find

that the, an asymptotic estimate for the coefficients.

just by plugging in, finding the dominant root of the polynomial that's closest to

the origin and then getting the explicit formula for the coefficient.

right from the, the basic procedure that we've used.

Two polynomials, we know how to deal with two polynomials.

I'll leave a specific example of the Analytic Combinatorics going right from

the spec down to asymptotics for an exercise at the end of this lecture.