https://mikespivey.wordpress.com/feed

This year’s NCAA basketball tournament has just ended, which means a lot of people are currently cursing their bracket picks. That also means it’s a great time for a retrospective: How could one go about picking a better bracket? There are all kinds of considerations here, but in this post we’re going to focus on just one feature: team seedings.

In the NCAA tournament all 64 teams are placed in one of four regional tournaments, and the teams in each regional tournament are given seeds numbered 1 through 16. The regional tournaments are set up so that #1 seeds play #16 seeds, #2 seeds play #15 seeds, and so forth, for the first round. In the second round, the winner of 1 vs. 16 plays the winner of 8 vs. 9, the winner of 2 vs. 15 plays the winner of 7 vs. 10, and so on, continuing through four rounds. After the fourth round, fifteen teams from each region have been defeated, and the remaining team is the winner of the region and goes to the Final Four to play against the other regional winners.

The NCAA men’s tournament expanded to 64 teams in 1985. This gives us 40 years’ worth of information on how teams actually perform relative to their seeds. In this series of blog posts, we will use this information to investigate how you can improve your chances of winning your tournament bracket pool using information from the team seeds.

(For this purposes of this project, we are ignoring the play-in teams in the men’s tournament. Also, we will not include information from the NCAA women’s tournament, since the dynamics appear to be different: The top seeds and a small number of programs tend to dominate in a way that does not happen with the men’s tournament.)

The first thing to do is figure out the historical win rate for the various seed matchups. Kaggle’s Machine Learning Mania 2026 contains the all the data we need (much more than we need, in fact). We extract the data and keep only the yearly seed information from 1985 on, including which seeds won which matchups.

After all the data extraction, cleaning, and computation involved, we end up with a 16 x 16 matrix for seed vs. seed win/loss records from 1985 to 2025. The full matrix is given in the file below. A few details are worth pointing out.

First, the #1 seed has a winning record of 98.8% against the #16 seed. From 1985 to 2025, inclusive, there have been 40 NCAA tournaments (41 years less one for Covid-19), which means 160 games that have pitted a #1 seed against a #16. We know that a #16 seed has only won twice (UMBC over Virginia in 2018 and Fairleigh Dickinson over Purdue in 2023), giving a 158/160, or 98.75%, winning percentage for the #1 seed here. The 0.988 that appears in the table serves as a sanity check on our calculations.

In addition, several higher-numbered seeds have winning records against lower-numbered seeds (noted in orange). Many of these are based on only one or a few games, but one in particular is not. With 160 matchups, the #9 seeds actually have a winning record against the #8 seeds: 51.9%. There are also many, many seed vs. seed matchups that have never occurred in the tournament (noted in light yellow). Finally, several seeds have 100% winning records against particular other seeds (noted in light blue if not already colored orange). While historically accurate, these are based on only a few games and are suspicious from a modeling/analysis standpoint.

The sparsity of the historical win rate matrix and the nonzero entries based on only few matchups are problems for us if we’re trying to do a full seed-vs-seed analysis. All is not lost, though: We can smooth the matrix in some fashion, using the historical information we do have to estimate the information we do not.

There are a few options available to us here, but perhaps the simplest robust choice is to use the Bradley-Terry model. In our terms, this model says that the probability that seed i defeats seed j in the tournament is

where and are the overall strengths (in some sense) of teams i and j, respectively. And we have a good way to estimate the value for each seed i: Use maximum likelihood estimation and the historical seed vs. seed win data so that the ratio formula above best explains all observed matchups simultaneously. (This process is described in detail in the Bradley-Terry model page.)

Applying the Bradley-Terry model gives us the updated win-rate matrix below. This matrix looks much more reasonable: Every matchup has a win probability, and the probabilities seem reasonable (the #1 vs. #16 win rate of 98.8% is even preserved). The oddly high percentages below the diagonal have been smoothed out, leaving only three win rates in the orange, all of which seem plausible.

Now, how do we use this model to pick a good bracket? We will continue the discussion in the next post, where we discuss how to maximize your expected bracket score.

A few years ago I answered a question on Cross Validated about the existence of a closed form for the mean residual life of the Weibull distribution, a popular distribution in reliability analysis. The short answer is that it depends on what you mean by closed form. There is an expression for the Weibull MRL in terms of the upper incomplete gamma function , but that’s generally not considered to be closed form. On the other hand, many modern programming languages like Python and C# have numerical packages that include , so if your interest is numerical computation you can use one of these instead of a general numerical integration routine to implement the Weibull MRL. (Side note: Both of the linked implementations are to the regularized upper incomplete gamma function.)

On to the derivation. The mean residual life function is, for a general probability model,

where

is the survival function , and is the cumulative distribution function for the probability model.

The Weibull probability density function is

so the Weibull mean residual life function is

Now, use the substitution . Then .

Since , this yields , so that . Then

This can be rewritten slightly by using a recurrence property of the upper incomplete gamma function:

Either of these two representations of for the Weibull model is fine.

Be careful with using numerical implementations of the upper incomplete gamma function, though. The Python and C# methods I linked to in the first paragraph both implement the regularized upper incomplete gamma function. Basically, that means they implement rather than . If you use one of those methods, make sure you multiply the result by to match the formulas given here.

Recently I came across the following on a site that provides questions on probability and statistics for tech interviews. I solved it, and so I thought I would give my solution here.

Suppose there is a new vehicle launch upcoming. Initial data suggests that any given day there is either a malfunction with some part of the vehicle or possibility of a crash, with probability p which then requires a replacement. Additionally, each vehicle that has been around for n days must be replaced. What is the long-term frequency of vehicle replacements?

I’m going to interpret “long-term frequency” as the expected amount of time that a vehicle is in operation before it is replaced. With that interpretation, the probability that a vehicle will need to be replaced after k days, if , is , as the vehicle will need to work fine for the first days (with probability for each day) and then break or crash on day k, with probability p. The probability that a vehicle will need to be replaced after n days is , as this is the probability that the vehicle will work fine for days. (It doesn’t matter whether it breaks on day n or not; it will still be replaced after day n.) Letting , the expected amount of time that a vehicle is in operation is thus (using the definition of expected value) given by

Here, in the first line we use the trick of rewriting as and then swapping the order of summation. In the second line we use the geometric sum formula, and in the third line we use the quotient rule for derivatives.

In this post I’m going to discuss two “proofs” by induction. That is, they’ll both be attempts at proving a statement, but they’ll both have flaws in their arguments. My hope is to alert people to potential errors when attempting to prove a statement by induction.

Claim 1: For all n, .

“Proof”: Let denote that claim that . Suppose that is true for some k; that is, suppose . Now, is the claim that . If is true, then , which proves that the truth of implies the truth of . By the principle of mathematical induction, then, is true for all n; that is, for all n.

Claim 2: For all , all people in a group of size n share the same birthday.

“Proof”: Let denote the claim that all people in a group of size n have the same birthday. Clearly, is true, as all people in a group of size 1 have the same birthday. Now, suppose that is true; that is, all people in a group of size k have the same birthday. Suppose now that we have a group of people. Single out one of those people; perhaps his name is Al. Without Al, we have a group of k people, all of whom must, by our inductive hypothesis, share the same birthday. Now, swap Al with one of those other k people. Now Al is in a group of k people. Again, by hypothesis all of them must share the same birthday. So Al must have the same birthday as all the others in his group. Thus these people all share the same birthday, and so is true. By the principle of mathematical induction, then, every member of a group of size n must have the same birthday.

Clearly, both Claim 1 and Claim 2 are incorrect. The question, then, is this: Where are the errors in their “proofs”?

For the “proof” of Claim 1, the argument that implies is actually valid. The logic error lies in the failure to prove a base case. And in fact, is false for any base case you can think of, so any attempt to prove a base case will fail. And if there’s no valid base case, then the chain-like logic of induction doesn’t have an initial link to start with. Thus the “proof” is invalid. The moral of the story here is that, while proving the base case may seem perfunctory, it’s actually crucial to the logic of induction.

For the “proof” of Claim 2, the error is more subtle. The argument for the base case is valid. The argument for implies is also valid—except for one, single, solitary value of k. When , and we remove Al from the group of two people, we then have Al and a group of size 1. Swapping Al with that one other person does put Al in a group of size 1, and he does share the same birthday as everyone else in the group (namely, just himself), but he doesn’t necessarily share the same birthday with that one other person. So does not imply , even though does imply for all larger values of k. Thus while the first link in a chain-like induction argument holds, the attempt to attach a second link to the first one fails. So we can’t attach any more links, and so the “proof” is invalid. The moral of the story here is that, for an induction argument to work, implies has to be true for all values of k (well, values at least as large as the value for k used in the base case). If it fails for even one value of k, then the induction chain breaks at that point, and the statement may not be true for any values larger than k.

A few months ago Mathematics Magazine published a paper of mine, “A Combinatorial View of Sums of Powers.” In it I give a combinatorial interpretation for the power sum , together with combinatorial proofs of two formulas for this power sum. (An earlier version of some of the results in this paper actually appeared in a blog post from several years ago.)

Recently, however, I received an email from Michael Maltenfort at Northwestern University, pointing out a couple of errors in the paper. I’m recording those errors here.

The most serious mistake Maltenfort pointed out to me is the paper’s claim that m is a nonnegative integer. The formulas actually require m to be a positive integer. For example, in the paper I state the following.

Theorem 1 (Original). The power sum is the number of functions such that, for all , .

However, when this doesn’t work. The power sum as I stated it entails adding up n copies of 1 and so evaluates to n. On the other hand, the set is the set . This means that all functions from to vacuously satisfy the condition in the theorem. The theorem as stated in the paper is off by 1, then, for the case .

Maltenfort suggests changing the lower index on the sum to start at , so that we have the following.

Theorem 1 (Updated). The power sum is the number of functions such that, for all , .

As long as we are fine with the convention that (and I am a fan of this convention in a combinatorial setting), this allows the formula to hold in the case as well.

Maltenfort also points out that the two formulas for the power sum need to be updated in order for them to hold for the case. My paper has

Theorem 2 (Original): , and

Theorem 3 (Original): .

These should be updated to

Theorem 2 (Updated): , and

Theorem 3 (Updated): .

The other mistake in the paper is in the definition of the induced permutation . The definition for in the paper has the requirement

That should instead be

Thanks to Professor Maltenfort for these corrections!

References

Spivey, Michael Z. “A Combinatorial View of Sums of Powers,” Mathematics Magazine, 90 (2): 125-131, 2021.

The Riemann zeta function can be expressed as , for complex numbers s whose real part is greater than 1. By analytic continuation, can be extended to all complex numbers except where .

The power sum is given by . (Sometimes M is given as the upper bound, but for this post it’s more convenient to use .)

Recently I learned of a really nice relationship between the zeta function and the power sum for . It’s due to Mináč [1], and I reproduce his proof here.

Theorem: For positive integers a, .

Now, of course M in is a positive integer, so what do we mean by integrating from 0 to 1? Well, it’s also known that is a polynomial of degree in M. For example,

So what we mean when we’re integrating from 0 to 1 is that we’re integrating the polynomial representation of from 0 to 1.

Proof. First, we need a few known facts about the Bernoulli numbers and Bernoulli polynomials:

1. The known representation of the power sum in terms of Bernoulli polynomials: .
2. The derivative of a Bernoulli polynomial: .
3. Some specific values of Bernoulli polynomials: .
4. All the odd Bernoulli numbers (except ) are 0.
5. A relationship between the zeta function and Bernoulli numbers: .

Now, using these facts, we have

For example, Theorem 1 gives us that

References

[1] Ján Mináč, “A remark on the values of the Riemann zeta function,” Expositiones Mathematicae, 12: 459-462, 1994.

One of the most important theoretical results in linear programming is that every LP has a corresponding dual program. Where, exactly, this dual comes from can often seem mysterious. Several years ago I answered a question on a couple of Stack Exchange sites giving an intuitive explanation for where the dual comes from. Those posts seem to have been appreciated, so I thought I would reproduce my answer here.

Suppose we have a primal problem as follows.

Now, suppose we want to use the primal’s constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by 9, the second constraint by 1, and add them together, we get for the left-hand side and for the right-hand side. Since the first constraint is an equality and the second is an inequality, this implies

But since , it’s also true that , and so

Therefore, 18 is an upper-bound on the optimal value of the primal problem.

Surely we can do better than that, though. Instead of just guessing 9 and 1 as the multipliers, let’s let them be variables. Thus we’re looking for multipliers and to force

Now, in order for this pair of inequalities to hold, what has to be true about and ? Let’s take the two inequalities one at a time.

The first inequality:

We have to track the coefficients of the and variables separately. First, we need the total coefficient on the right-hand side to be at least 5. Getting exactly 5 would be great, but since , anything larger than 5 would also satisfy the inequality for . Mathematically speaking, this means that we need .

On the other hand, to ensure the inequality for the variable we need the total coefficient on the right-hand side to be exactly . Since could be positive, we can’t go lower than , and since could be negative, we can’t go higher than (as the negative value for would flip the direction of the inequality). So for the first inequality to work for the variable, we’ve got to have .

The second inequality:

Here we have to track the and variables separately. The variable comes from the first constraint, which is an equality constraint. It doesn’t matter if is positive or negative, the equality constraint still holds. Thus is unrestricted in sign. However, the variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can’t let that happen. So the variable can’t be negative. Thus we must have .

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize .

Putting all of these restrictions on and together we find that the problem of using the primal’s constraints to find the best upper bound on the optimal primal objective entails solving the following linear program:

And that’s the dual.

It’s probably worth summarizing the implications of this argument for all possible forms of the primal and dual. The following table is taken from p. 214 of Introduction to Operations Research, 8th edition, by Hillier and Lieberman. They refer to this as the SOB method, where SOB stands for Sensible, Odd, or Bizarre, depending on how likely one would find that particular constraint or variable restriction in a maximization or minimization problem.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

It’s fairly well-known, to those who know it, that

.

In other words, the square of the sum of the first n positive integers equals the sum of the cubes of the first n positive integers.

It’s probably less well-known that a similar relationship holds for , the function that counts the number of divisors of an integer:

.

In this post we’re going to prove this formula for .

First, it’s pretty easy to see what the value of is for prime powers; i.e., integers of the form , where p is prime. Since the only divisors of are , the number of divisors of is given by .

Let’s check the identity we’re trying to prove when . We have

We also have

Clearly, the two expressions are equal, so the identity we’re trying to prove holds in the prime-power case. (And, in fact, the derivation uses the identity about the sum of the first several positive integers mentioned at the beginning of the post!)

Let and . What we’ve shown thus far is that .

Now, we’re going to pull some elementary number theory. One fact about is that it is multiplicative; i.e., when m and n are relatively prime. This is one of the first properties you learn about once you learn its definition, and we’re not going to prove it here.

It turns out that both f and F are multiplicative as well! First, the product of two multiplicative functions is also multiplicative. (This is a one-line proof using the definition of multiplicative.) So is multiplicative.

Another property of multiplicative functions is that if g is multiplicative, then is also multiplicative. This is a special case of the more general result that the Dirichlet convolution of two multiplicative functions is multiplicative. (In the Dirichlet convolution , take h to be the identity function; i.e., .) This means that our functions f and F defined in the previous paragraph are both multiplicative.

Therefore, with the prime-power factorization of n given by , we have

For an even further generalization, see Barbeau and Seraj [1]. (The proof we give in this post follows the same basic argument as the proof of Proposition 1 in Barbeau and Seraj’s paper.)

1. Barbeau, Edward, and Samer Seraj, “Sum of cubes is square of sum,” Notes on Number Theory and Discrete Mathematics 19(1), 2013, pages 1–13.

Today’s Google doodle honors mathematician Benoit Mandelbrot. He would have been 96 today. If you’re interested in learning more about his life and work, the Google doodle link contains a short summary. If you want to go deeper, you can read the Wikipedia article on him.

I only have one small thing to add. A few years ago I wrote an interactive text-based game, A Beauty Cold and Austere. You can read some reviews of it and play it here, and you can read some of my thoughts about it here. The connection to Mandelbrot is that I used part of the Mandelbrot set for the cover art for the game, as you can see below.

Equations of the form are called Mordell equations.  In this post we’re going to prove that the equation has no integer solutions, using (with one exception) nothing more complicated than congruences.

Theorem: There are no integer solutions to the equation .

Proof.

Case 1.  First, suppose that there is a solution in which x is even.  Since , .  Looking at the equation modulo 8, then, we have

.

However, if we square the residues and reduce them modulo 8 we have .  So there is no integer y that when squared is congruent to 7 modulo 8.  Therefore, there is no solution to when x is even.

Case 2.  Now, suppose there is a solution in which x is odd.  If so, then we have or .

If then we have .  However, if we square the residues and reduce them modulo 4 we get .  So there is no integer y that when squared is congruent to 2 modulo 4.  Thus there is no solution to when .

Now, suppose .  Applying some algebra to the original equation, we have

.

By assumption, .  If has prime factors that are all equivalent to 1 modulo 4, then their product (i.e., ) would be equivalent to 1 modulo 4.  Thus has at least one prime factor q that is congruent to 3 modulo 4.

However, if , then .   This means that .  However, thanks to Euler’s criterion, only odd primes q such that can have a solution to .  Since , has no solution.  Thus there is no solution to when , either.

Since we’ve covered all cases, there can be no solution in integers to the Mordell equation .