next we're going to talk about strings and
tries.
These are combinatorial objects that have
really come under scrutiny because of
computational applications.
But they're very well suited to the
analytic techniques that we've been
talking about.
Again I think we're in the second half of
the class and this is lecture eight.
And we're going to look at these data
structure, these combinatorial objects as
unlabeled classes mostly.
So we'll be talking about OGFs.
And again we'll give some examples in
lecture, but there are many more in
Chapter 8 of the book.
So first thing we're going to talk about
is bit strings with, with restrictions and
we did some examples of this as our
motivating examples for the analytic
combinatorics in Lecture 5.
But what we'll talk about today is
answering questions like this.
So this is a number of random bitstrings
of 70 or 80 bits.
And I've got highlighted in there the
first, the currents of 000 in each bit
string.
So a natural question is what's the
expected wait time?
That is how many random bits do we need to
see before we get to 000 in a, in a random
bit string.
Or what's the, some of these bit strings
have no 000s well maybe not.
So, but if you look at shorter ones, like
at this distance, then there'd be no 0000.
So the question is, what's the probability
that you don't have 000 in an N, N-bit
random bit string.
And questions like this actually have lots
of important, practical applications where
the 0s and 1s correspond to electrical
signals and certain kinds of devices can't
take long strings of for, for example.
So let's review what we talked about for
the symbolic method for bit strings.
It's one of the very simplest examples of
analytic combinatorics.
How many binary strings are there within
bits is of course, they're 2 to the N.
And we can do that with the symbolic
method, by constructing the class of all
binary strings, B, as a sequence of 0 or 1
bits.
And then our normal symbolic transfer
takes Z0 plus Z1 to 2Z.
And sequence of anything of one over one
minus that, so that tells us that the OGF
that enumerates the number of binary
strings is B of Z equals 1 over 1 minus
2Z, and so, the coefficient is Z to the N
and that is 2 to the N.
That's our basic construction for binary
strings using the symbolic method.
And then we have an alternate way of
expressing the same thing.
If you say that a bit string is either
empty or it's a bit followed by a bit
string, a recursive definition, then you
get down to the same result.
In this one generalizes to help us answer
questions like how many N-bit strings have
no two consecutive 0s.
And again, using the same reasoning, we
could say that a bit string with no two
consecutive 0s is either empty or it's a
single 0 or it's a 1 or a 01 followed by a
bit string of those tw consecutive 0s.
That's, the natural construction for this
class of combinatorial objects.
And then that translates through the
normal translation theorem to this OGF
equation.
1 plus Z plus quantity Z plus Z squared
times B00.
And then we can solve that and we get a
polynomial, a ratio of two polynomials for
the generating functions.
And our asymptotic, that's a classic
example in asymptotic analysis the
coefficient of Z to the N in that function
it's going to be, well, in this case it's
exactly the Fibonacci numbers.
But in general, if it's any polynomials,
you look at the largest root of the
polynomial in the denominator.
And that gives an, an asymptotic
expression for the coefficient of, of B to
the N in that generating function.
So simply by finding the appropriate root
of the polynomial, we get the asymptotics.
And for any polynomial, it's going to be
the form of constant times the root to the
Nth power unless there happen to be
multiple roots.
So, in this case the it's the golden
ratio, phi to the Nth power and then the
constant also is explicitly determined.
So that's example that we did in Chapter
5.
So, first thing we want to do today is
extend that how many binary strings have
no runs of p consecutive 0s.
And that's going to extend in a natural
way very much like the derivation that I
just did.
So the construction then is a string with
no runs of p consecutive zeros is a string
of zeros of length less than p, followed
by either an empty string or a 1one
followed by a string with no runs of p
consecutive zeros.
So that's just a generalization of the
construction that I did on the last slide
and again that immediately translate.
A string of zeros of length less than P is
1 plus Z plus, so forth, up to Z to the P,
minus 1.
And then E translates to 1 and ZP, BP of
Z.
And, so solving that equation gives BP of
Z equals, again, a ratio of two
polynomials.
And again, the coefficient of Z to the N
in that is asymptotic to a constant times
a largest route to the Nth power where
that dominant root is something we can
calculate.
And also, the coefficient is explicitly
available.
So this no runs of P consecutive zeros
comes down to finding the dominant root of
that polynomial, 1 minus 2Z plus Z to the
P plus 1.
And this is using the Sage mathematical
system to just find those roots and you
can use any system that you want and I
didn't calculate the constants.
But let's, let's look at so anyway those
are those results.
Now let's look at what we can infer from,
from that result.
So this is the summary of where we were
for consecutive zeros.
The OGF, S sub P of Z, is going to be the
sum of N, the number of bit strings of
length N with no runs of P consecutive
zeros times E to the N.
And that we have an explicit formula for
that OGF, 1 minus E to the P over 1 minus
2Z plus E to the P plus 1.
Now this is similar to the situation we
had with permutations.
We can convert that into a probability by
appropriate evaluating it, appropriate
value of the argument.
If you look at SP of Z over 2, then the Z
to the N becomes a 1 over 2 to the N Z
over 2 to the N.
So what that is the probability that a bit
string of length N has no run of P0s.
So it's a PBF just by expressing, just by
evaluating the article, the argument at Z
over 2.
So now, if we take Z equals 1 then that's
just summing the what is that?
That's the sum on N of the number of bit
strings of length N with no runs of P 0s
divided by 2 to the N, which is the sum on
N.
The probability that the first N-bits have
no runs of P0s.
So and that's the same as the sum that
the, of the probability that the end of
first run of P0s is bigger than N.
So number of bit strings of length N with
no runs divided by 2N.
There's a probability that the first end
bits have no runs of P0s.
And that's the same as the probability
that the position of the end of the first
run of P0s is bigger than N.
But that's exactly the average position of
the end of the first run of p 0 so that's
the average weight time.
So this argument just gives us these two
theorems.
The first one is the probability that the
n bit random bit string has no run of b 0.
It's the coefficient of z to bn and sp
evaluated over time.
Two, that's the second line here.
And so going from the solution on the
previous slide.
It's going to be our dominant root divided
by two to the n.
And then the other thing is the expected
wait time is just our generating function
evaluated at one half.
If you evaluate that generating function
at one half to see that all is left the 1
minus 2c cancel out plus one half to the p
plus 1 in the denominator so it becomes 2
to the p plus 1 minus 2.
So that's using the symbolic method, get
information explicit version of the
generating function and then evaluating
that generating function to get the
analysis of the properties of the
consecutive zeros in a random bit string.
Now, so just to summarize for small values
of p, which are usually what's of
interest.
So that's our generating function, when P
equals 1, is 1 minus c over 1 minus 2Z, 2
Z squared.
So the probability of approximate
probability of no zeros in random bit
strings of size n is 1 half to the N.
And then, 10, that's is 0.0010 and 100 is
10 to the minus 30th and the average wait
time is 2.
For 3 zeroes, then we can do the explicit
eh, those are the values of the roots.
And it turns out that, probability of no
run of two zeroes in ten bits is about
point one four.
And 100 bits is ten to the minus nine.
And the wait time for the first run of 2
zeros is about 6.
For three zeros now probability of no run
of three zeros becoming more and more
likely.
So for ten bits it's about even chance
that there's no run of three zeros.
For 100, 100 bits still fairly unlikely.
4 zeros now 10 bits, three quarters of the
time you're not going to have 4 zeros in a
row.
You have to wait 30 bits to get your first
run of 4 zeros on average.
But for 100 bit is still.
Pretty unlikely that you won't have four
zeroes in a row.
And then for five zeroes now it's almost
90% chance that you're not going to have
five consecutive zeroes in ten random
bits.
20% chance you're not going to have five
consecutive zeroes in 100 random bits.
And the wait time is 62.
And then for 6 0's, it's almost certain
and it's even chances in a string or a
random string of 100 5ths that you won't
have 6 consecutive 0's.
And your wait time is over 100, 126.
So those are facts that we can derive from
this analysis.
And actually this type of statistic is one
way to test whether a set of strings is
random.
In fact, it's always worthwhile to
validate these types of mathematical
results.
And in situations like this when it's so
easy to write code to validate these
results, we should go ahead and do it.
So this is a java program that takes as
argument size and number of trials and
what it 's going to do is, it 's going to,
this one actually reads the bits from
standard in so we separate.
Separate out what the bits are, from
analyzing them.
So this will read W bits at a time from
standard in.
So like in that example, W was 75.
And there were a bunch of occurrences of
75 bits that were supposed to be random.
And then for each P it'll check whether
there's a 0 P consecutive zeros and then
it'll just print out the empirical
probababilities.
And then this is just the code to check
for P consecutive zeros, so this is a very
straightforward.
Program that reads in a bunch of bit
strings.
And then prints out the out of all those
bit strings, what's the empirical
probability that, you find, one, two,
three, four, five, up to P consecutive
zeroes.
And so for the example that I used on the
first slide.
This the data that it gives.
And so actually, those were the first line
of, 10,000 bits.
10,000 bit strings of size 100.
And for those bit strings those are the
probabilities that.
0, 1, 2, 3, 4, 5, 6, 0s occurred and those
compare very favorable with what we just
saw was predicted by the theory.
So, we can think that those bits are.
Pass this test for randomness.
Or we can think of this as validating the
theory that we just arrived.
Predicting, for example, that you have 45%
chance of finding, say, 6 consecutive 0's.
In the random bit strings.
Okay, so that's a fine generalization of
the simple example, example that we did
for how many bit strings that had, don't
have two consecutive zeros.
Now so to check [laugh].
So now the next thing that we want to do
is consider other specified patterns so
say it's not 000 that we're interested in,
but say 001.
So now in blue you can hardly see but the
wait time for 000, that's the one that I
did before, is in, is in red, and it's an
average about 18 for these.
But in blue is the wait times for 001, so
And the first line, the first occurrence
of 001 is starting at the 9th bit.
In the 2nd it's at the 4th bit, and so
forth.
And this time, the expected wait time for
001 in this set of bitstrings is only 6,
it's much, much less.
And now we're wondering, are these
bitstrings really random?
What's going on here?
Well the, the fact is that the pattern
itself definitely is a factor in what the
wait time is.
And that's what we're going to look at
next.
So we showed before that the probability
that an end bit random bit stream doesn't
have four zeros in a row.
Is about point nine six to the end.
So and the expected wait time is 30, and
the question is does, does that same thing
hold for 0, 0, 0 1 or any other pattern of
four bits.
And the answer is no.
So in every, every, one, one that we did
the 0, 0 1 occurs much earlier than the 0,
0, 0, 0.
So it's a little intuition behind that.
So let's say, consider the first
occurrence of three zero's in a row.
Now the next bit could be either zero or
one.
So our two patterns are equally likely
once, once we found zero, zero, zero.
But the thing is, if we were looking for
zero, zero, zero then that would mean that
we're looking for four zeros and we didn't
find it.
It would mean that we have zero, zero,
zero one in our bit stream and we're going
to have to wait at least four more bits
before we can find zero, zero, zero.
But if we were looking for zero, zero,
zero, one, and we had a mismatch, it would
mean that there's four zeroes, and the
next bit could give us a match.
So if we're going from left to right
looking for these two patterns, it's not
surprising that we're going to find zero,
zero, zero, one first.
Find three 000 in a row we get a good
chance of being the next[INAUDIBLE], but
if we're finding looking for 4 zeros in a
row and we find 3 zeros then we're going
to have to wait a long time for the next
bit.
That's the intuition behind why it occurs
much earlier.
So, but now we want the answer to this
question.
What's the probability that a random bit
string doesn't contain that pattern?
Zero, zero, zero one.
It's a little bit counterintuitive that
it's not the same for any set of four
bits.
But it's definitely not, as we'll see.
Or what's the wait time for the first
occurrence of 0001?
And what about other patterns like 1110,
or 1111 and so forth?
So the idea that it's the pattern itself
that determines the probability existence
and the expected wait time has to do with
a phenomenon called auto-correlation.
That's what we're going to look at next.
So what we'll do is use the symbolic
method to get explicit equations for the
generating function for number of bit
strings not containing a specified
pattern.
And it's remarkably easy to develop such
an equation with the symbolic method.
So what we'll say, is we'll take any
pattern p.
So it's a, a pattern of bits.
And s sub p is the binary strings that
contain, do not contain that pattern at
all.
And then we'll define t sub b, p, to be
the binary strings that end in p.
And have no other occurence of p inside.
So that's two well defined sets of bit
strings.
And so what we're going to do is have two
different constructions that relate these
classes of bit strings.
So the first one is based on the following
observations.
These two sets are disjoined.
That is the t sub p has the pattern in it.
S sub p does not have the pattern in it.
So there's no string that's in both of
them.
Empty string doesn't contain a pattern.
So it's in s sub p.
And the other thing is, if we have a
string in s sub p, and we add one bit to
it, either we're going to get a string
that's in s sub p, or, that bit will
complete the pattern, and we'll get a
string that's in p sub p, the only
occurrence of the pattern.
So based on those observations we have
this symbolic equation our construction
that relates these classes of string.
S sub p plus T sub p is either empty or
it's S sub p with a bit added.
So that's the first equation.
And here's the second construction that
relates these two combinatorial classes.
It's based on the idea of what's called an
auto, auto correlation polynomial.
That is a property of a pattern.
And the idea is, we take the pattern in
black.
And then slide the pattern to the left
over itself.
And so, well, at the beginning, the
pattern matches itself.
And, The number of trailing bits we used
as an exponent.
So we start out with a z to the zero in
the polynomial.
And then we slide over 1, 2, 3, 4 5
positions, and when we slide over 5
positions, then the trailing bits match
the leading bits of the pattern, the 1 0 1
0 at the beginning matched the trailing 4
bits.
And we slid 5 positions, so we put z to
the 5th.
And then 2 more positions the 2 trailing
bits match the 2 leading bits, that's z to
the 7th.
So in all the possible slides, the only
match of the trailing bits with the
leading bits is as positions zero, five
and seven.
That defines the autocorrelation
polynomial of the pattern for this one.
It's auto autocorrelation polynomial is 1
plus Z to the 5th plus Z to the 7th.
And that's going to play a role in the
development of another relationship
between the two combinatorial classes we
just defined, this is the second
construction.
So remember S sub P doesn't contain the
pattern and T sub P ends in the pattern
but has no other occurrence of the
pattern.
And so, the idea is if you take any string
in T sub P And then you add a tail
corresponding to the tail that you'd get
to complete the pattern, in the auto
correlation.
So the first ones null, the second one, if
you add the five bits that you shifted off
at the end of the pattern, you get an
occurence of the pattern.
And again if you add the seven bits you
get an occurance of the pattern.
So in those three cases, null one
corresponding to each bit in the
auto-correlation polynomial you'll get a
string.
That if you have a, a string in s sub p
that does not contain that the pattern if
you add the I'm sorry.
If you have a string in t sub p.
And you add these tails then you'll get a
string in s sub p.
But from knocking off the pattern.
So every time the result is a string in s
sub p followed by the pattern.
So S of P times the pattern is T sub B
times the one place for each bit in the
correlation polynomial.
So that's going to give us the
combinatorial construction.
So we have those two constructions.
One if you add a bit to a string in S, you
get either a string in S of P, and the
other one is if you take a string in T and
you got a, a chance for every bit in the
auto correlation polynomial to make a
string in s followed by the pattern.
Those are the two construction.
And these use the these two constructions
are set up for the symbolic method.
They just use the basic operations.
So they immediately correspond to
generating function equation.
First one Z0 plus Z1 is 2Z and otherwise
it just directly corresponds to the adding
of generating functions.
In the second one, the pattern has OGFZ to
the P so SP times Z to the P equals PP.
And then what's left over here is the
correlation polynomial itself.
So now we have 2 equations in S and P that
we can solve, and the correlation
polynomial of the pattern is part of the
answer.
So, that's a solution of those two
simultaneous equations.
The, this is the OGF for the class of
binary strings that contain no occurrence
of the specified pattern.
Now for any particular pattern, we can
plug in the correlation polynomial and
again we have a ratio of two polynomials.
We find the dominant root.
The one in the denominator in our count is
asymptotic to that root to the nth.
Power multiplied by a constant that we can
compute explicitly.
So this is a methodology that's going to
work for any pattern at all.
So here's the end result for 4-bit
patterns.
So of all possible 4-bit patterns actually
there's only four different possibilities
for the auto correlation.
It turns out.
Uh,[cough] so that classifies the four bit
patterns with those auto correlations.
They, they all s, start with the one in
well, those are the auto correlations that
can come up.
So those lead to those different o g fs.
And so they all have different dominant
roots.
And I didn't computer the constants here.
They're all pretty close to one.
And then you can see that, now this one
with one zero, zero, it's a slightly
smaller number.
We, when we raise that number to the 10th
power we're going to get a smaller number
and for the 100th power it's going to be
much, much smaller.
It's interesting in maybe counter
intuitive, but these are the results.
You're going to wait about twice as long
for 4 zeros or 4 ones as you are for
anyone of those six patterns.
Or another way to look at it is that.
0000, 4 zeros is a 100 times more likely
to be absent in 100-bit strings than all
of these other patterns, say 0001 0011
00111.
So studying this table maybe, is a, a good
way to win some bar bets, perhaps.
It's kind of surprising that we can so
completely characterize this problem with
analytic combinatorics.
That's the study of bit strings with
restrictions and these studies extend in
various ways.