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.