Final Four Probabilities

For the first time in history, the teams in the Final Four this year are all number 1 seeds. I've been hearing about this for a while, and began to wonder... Should my reaction be "it's about time" or "wow, that's remarkable"? So I went after the numbers to try to figure it out.

The first thing you realize is that the NCAA likes to change formats pretty regularly. The current format (dating back to 2002) starts with 65 teams; the previous 16 seasons featured a 64-team tournament with the same overall structure. These (1985 - 2007) are the tournaments whose results I used. Here's what I found:

Seed	Region Wins	Percent
1	38	0.41
2	21	0.23
3	12	0.13
4	9	0.1
5	4	0.04
6	3	0.03
8	3	0.03
11	2	0.02

So, if we take history as a guide, we would put the probability of all four #1 seeds winning their regional brackets at just under 3% [.41 * .41 * .41 * .41], so it should happen once every 34 years, on average. This is the 24th year of the current format, so it happened a little sooner than we would have expected.

An interesting question is, "what is the most likely distribution of seeds in a Final Four?" Obviously, a 1 seed is the favorite to win its regional group, but other outcomes are more likely than all of them winning. Three 1 seeds and a 2 seed would be twice as likely (about 6.4%, once every 15.5 years); it happened in 1993. Close behind that, we would expect two 1 seeds, a 2 seed and a 3 seed about every 16.4 years; this was the case in 1991 and 2001.

Two years ago, no number one seeds made the Final Four (this was not quite a first - it happened in 1980 during a 48-team tournament). This is actually a relatively likely situation - you would expect it once every 12 or so years.

To close out, let's look at outcomes that we would expect more frequently, and see how they compare with history:

Final Four Seeds	Probability	Expected Time (Years)	Occurrences	Observed Rate
3 #1's	0.1654	6.04	3	0.13
2 #1's	0.3527	2.84	10	0.43
1 #1	0.3341	2.99	9	0.39

Note that the above outcomes are mutually exclusive (but not exhaustive - I mentioned the other cases above). In particular, I'm surprised by the frequency with which only one 1 seed makes it to the Final Four. I wonder what kind of odds I can get on that next year...

Divisibility Testing and Pattern Matching, Part 2

Last time, I left myself with the challenge of coming up with a regular expression to test for divisibility by 3, and left you with 3 relatively unsatisfying regular expressions to use for determining divisibility (by 2, 5 and 10). (The RE for 4 I'll count as being partly satisfying). First, why were those tests easy to code as a regular expression? If we are testing for divisibility by some number d = 2^a * 5^b, then we only have to consider the last max(a, b) digits. If our test only depends on the last few digits, then at worst we'll be able to enumerate the possibilities. The regular expression (00|04|08|12|...|92|96)$ will also correctly test for divisibility by 4.

For determining divisibility by 3, such an enumeration isn't available to us (we have to consider every digit since there is no power of 10 evenly divisible by 3). How do we know that it's possible to write a regular expression that matches on multiples of 3? Because we can write a finite state automaton that tests for divisibility by 3.

enum State
{
    Accept,
    Rem1,
    Rem2
}

bool IsDivisibleBy3(char* num)
{
    State state = State.Accept;
    for (; *num; ++num)
    {
        switch (*num)
        {
            case '0': case '3': case '6': case '9':
                break;
            case '1': case '4': case '7':
                if (state == State.Accept)
                    state = State.Rem1;
                else if (state == State.Rem1)
                    state = State.Rem2;
                else
                    state = State.Accept;
                break;
            case '2': case '5': case '8':
                if (state == State.Accept)
                    state = State.Rem2;
                else if (state == State.Rem1)
                    state = State.Accept;
                else
                    state = State.Rem1;
                break;
        }
    }
    return s == State.Accept;
}

I wrote it in this style to make explicit that it represents a finite state automaton. It's essentially an obfuscated version of what you might actually write to test for divisibility by 3:

 bool IsDivisibleBy3(char* num)
 {
     int remainder = 0;
     for (; *num; ++num)
     {
         remainder = ((10 * remainder + *num - '0') % 3);
     }
     return remainder == 0;
 }

This itself is just a slight modification of the code to read in a number and see if 3 divides it, with the important change that this one won't overflow on large input. Notice how close this code comes to implementing the rule that 3 divides a number if 3 divides the sum of its digits!

Since there exists an FSA that checks for divisibility by 3, there must be a regular expression that codes this FSA. To simplify the definition, we'll introduce some character classes:

Z = [0369], O = [147], T = [258]

These partition the digits into equivalence classes modulo 3 (and correspond to the different cases in the code - coincidence?). Then, a regular expression to test for divisibility by 3 is:

^(Z|(OZ*OZ*(TZ*O)*Z*O)|(TZ*TZ*(OZ*T)*Z*T)|(O(OZ*T)*Z*T)|(TZ*(TZ*O)Z*O))+$

If you're not into the whole brevity thing, that expands to:

^([0369] | ([147][0369]*[147][0369]*([258][0369]*[147])*[0369]*[147]) | ([258][0369]*[258][0369]*([147][0369]*[258])*[0369]*[258]) | ([147]([147][0369]*[258])*[0369]*[258]) | ([258][0369]*([258][0369]*[147])[0369]*[147]))+$

So now we have regular expressions for testing for divisibility by 2, 3, 4, 5, and 10. We could make one for 8 (it would be similar to the one for 4). Testing for divisibility by 6 is equivalent to testing for both 2 and 3, both of which we can do (but which it would not be easy to write a standard RE for, though I believe there are extensions that implement an And operator). Alternately, we could modify the one above to make sure that the last digit is even (ick - that one is left for the reader). What would a regular expression that tests for divisibility by 7 look like?

Divisibility Testing and Pattern Matching

How do you tell if a number is divisible by 10? Everybody knows you just look to see if the last digit is 0 or not. There are similar rules for checking divisibility by 5 (ends in 0 or 5) and 2 (ends in an even number). What I think is interesting is that these rules are not mathematical in the usual sense. Rather, they are based on simple textual pattern matching. That is, they don't rely on manipulating values, they just require inspecting the textual representation of the value in question.

If you are going to do pattern matching on text, the natural tool is regular expressions. Using the usual regular expression syntax, the above rules can be expressed as 0$, [05]$, and [02468]$, respectively. Those are the easy ones. Can we code more complicated divisibility tests as regular expressions? How about checking for divisibility by 4?

The mathematical shortcut for checking if 4 divides a number is to see if it divides just the last 2 digits. This works because if n = 100 a + b, 4 | n iff 4 | 100 a + b iff 4 | b. If we choose a and b so that b < 100, b will be exactly the last 2 digits of n. So we know we can get away with looking at just the last 2 digits; is there a regular expression we can use? Yes: ([02468][048])|([13579][26])$ works! Unsurprisingly, our regular expression considers only the last 2 digits.

So far, I've been considering the easy cases - testing for divisibility by combinations of 2 and 5 (which are easy since we're using the base 10 representation). You may know the shortcut for testing for divisibility by 3: add up the digits of the number, and if this sum is itself divisible by 3 then so was the original number. Is it possible to code this test as a regular expression?

To be continued...

[Erratum: the regular expression above for divisibility by 4 requires 2 digits, so it won't match 0, 4 and 8]