The OGF, SP(z), is going to be the sum of N, the number of bitstings
of length N with no runs of P consecutive 0s times z to the N.
And that, we have an explicit formula for that OGF,
1- z to the P/1- 2z + z to the (P + 1).
Now this is similar to the situation
we had with permutations.
We can convert that into a probability by
evaluating an appropriate value of the argument.
If you look at Sp(z/2) 2,
then the Z to the N becomes 0/2 to the N.
So what that is is the probability that a bitstring of length N has no runs of P 0s.
So it's a PGF just by evaluating the oracle,
the argument at Z over 2.
So now if we take Z=1 then that's
just summing the, what is that?
That's the Sum on N of the number of bitstrings of length N with no runs
of P 0s divided by 2 to the N.
Which is the sum on N then the probability that
the first N bits have no runs of P 0s.
And that's the same that the sum of the probability
that the end of the first run of P 0s is bigger than N.
So the number of bitstrings of length N with no runs divided by 2 to N,
this is the probability that the first N bits have no runs of P 0s.
And that's the same as the probability that the position of the end of the first
run of P 0s is bigger than N.
But that's exactly the average position of the end of the first run of P 0s.
So that's the average wait time.
So this argument just gives us these two theorems.
The first one is the probability that an N bit, random bit string has no run of P 0s.
Is the coefficient Z to the N in SP evaluated Z over 2,
that's the second line here.
And so [COUGH] going from the solution on the previous
slide it's going to be our dominant root divided by 2 to the N.
And then the other thing is the expected wait time is just out
generating function evaluated at one-half.
If you evaluate that generating function at one-half, you'll see that all that's
left of 1-2Z cancels out, so it's one-half to the p + 1 in the denominator.
So it becomes 2 to the P+1-2.
So that's using the symbolic method to get information,
explicit version of the generating function.
And then evaluating that generating function to get the analysis
of the properties of the consecutive 0s in a random bitstring.
Now so just to summarize, for small values of p,
which are usually what's of interest.
So now, generating function when p =
1 is 1-z over 1-2z + z squared.
So the approximate probability of no 0 in a random bitstring,
if size N is one-half to the N and then 10, it's 0.0010,
and 100 is 10 to the -30th, and the average wait time is 2.
For three 0s, then we can do the explicit [COUGH] those are the values of the roots
and it turns out that the probability of no run of two 0s in 10 bits is about 0.14.
And 100 bits its 10 to the -9th and
the weight time for the first run of two 0s is about 6.
For three 0s, probability of no run of three 0s becoming more and more likely.
So for 10 bits, it's about even chance if there's no run of three 0s.
For 100 bits, it's still fairly unlikely.
Four 0s now 10 bits,
three quarters of the time you're not going to have four 0s in a row,
you have to wait 30 bits to get your first run of four 0s on average.