It seemed reasonable,
that we should be able to analyze when you're probing with the symbolic method.
So, we can resist putting in one foot note, in our book, either.
And that one said that we don't know the answer to this exercise.
Now we couldn't figure out how to use the symbolic method to analyze linear probing.
It seemed like their answer was so simple and
so similar to birthday coupon collector, that we should be able to get it.
And really we put this in as a challenge to students and researchers.
Really, you know, we should be able to do this one.
And it took some years, but eventually, and you can read about this on,
in the second edition of the book turn out this problem has a very,
a deep connections to properties of commentarial objects.
Like, random graphs.
The Gambler Ruin problem.
Path links in trees and many other classic algorithms.
And it's explained by A distribution called an Airy law.
And very fascinating amount of mathematics to explain this.
And Knuth was one of the people who solved it.
And Phillipe and some co-authors solved that, as well.
Although, actually, still we don't quite exactly,
precisely know the answer to this exercise, we know quite a bit.
So there's actually still a footnote left in the second edition.
But linear probing is worth studying to see both the potential and
the limitations of what we know about analysis of algorithms at this point.
One of the foundations mentioned here is properties of mappings and
that's what we're going to talk about next.