The Art of Logic

A modest proposal to ensure geographic mixing at Nationals

2011-08-09T10:41:00.010-04:00

I wrote an article for the Rostrum (which I'll link to once it comes out in September) about using geographic and strength criteria to mix teams in preliminary rounds at NFL Nationals. In other words, I advocate the use of a system that ensures that each team will debate a broad cross-section of different opponents, from different parts of the country and at different skill/experience levels, as measured by NFL debate points. I won't repeat the arguments here about why I think this is a worthwhile goal, except for this one thought: Geographic mixing makes it likely that the less experienced teams -- who probably have not travelled far afield -- will debate opponents at Nationals they have never seen before. Even with geographic mixing, there is still a chance that national circuit teams might face an opponent in preliminary rounds at Nationals they have debated many times during the invitational season. That is why there is also a need for skill/experience level mixing. Both are necessary to make it likely every team will see "new" opponents at Nationals.

I will focus on two technical concerns about my proposal in this blog post.

Concern 1: Can two criteria really be maximized at the same time?

Yes and no. In a strict sense, no: only one variable can truly be maximized at a time. That is to say, you can have a round where the average geographic distance between opponents is maximized, or you can have a round where the average difference of skill/experience between opponents is maximized, but you can not have both at the same time. However, in a looser, more practical sense, the answer is yes: you can have a round where opponents are well-mixed geographically (even though not maximally mixed) AND well-mixed skill/experience-wise (even though not maximally mixed). Let me show you with the sample data I used in the Rostrum article.

Here are 26 fictitious teams, spread throughout the country in geographic clusters, and at different skill/experience levels (normally distributed from 0 to 1 in my sample data). I imagined that the NFL points could be scaled so the weakest team to qualify was given a rating of 0 and the most experienced a 1, but they do not need to be scaled at all for this method to work. The median distance between every possible pairing in the whole set is 2138 miles. The median difference in experience is 0.28 units.

If one tries to maximize geographic spread, the round 1 pairings that are selected would look like this:

The median distance between two opponents in each pairing is 3333 miles, and the shortest distance is 2452 miles. In other words, every match chosen is above the average of 2138 miles. This is maximized; it is a Pareto optimal solution, meaning that any change to improve a pairing by swapping opponents would have to make another pairing worse. The net result can not be improved. In the first round, teams in the middle of the country would debate coastal teams. As the tournament proceeds, each team would get opponents from every geographic region of the country.

If one tries to maximize the differences of skill/experience levels, the round 1 pairing would look like this:

The median difference between opponents is 0.45 units, and the least difference is 0.42 units. Every match chosen is above the average of 0.28 units. Again, this is a Pareto optimal solution. In the first round, mid-level teams would debate either inexperienced or highly experienced teams. No inexperienced team would be matched against a highly experienced team -- this would force two mid-level teams to debate. However, in further rounds, each team would get opponents at every different level.

What happens if you try to maximize both? The resulting pairings (which were published in the Rostrum) would look like this:

The median distance is 3092 miles, and the shortest distance is 2003 miles (with only 15% of matches below the average of 2138 miles). The median difference is 0.45 units, and the least difference is 0.23 units (with 23% of matches below the average of 0.28 units). Although these pairings do not maximally mix for geography, they do pretty well. And likewise for difference in skill/experience level. This represents a lower boundary of how well this method could work. If we use a larger data set, such as the 200+ teams at Nationals, then it becomes easier to find pairings that maximize both criteria.

Concern 2: Would this method create the same pairing year after year?

It seems like it might: an optimal solution for one year seems like it might be the same, or very similar, the next year. No one wants to see the same opponent in preliminary rounds two (or more) years in a row at Nationals.

However, this kind of optimization is chaotic, meaning it is extremely sensitive to small changes.

Fitting a normal curve

2011-05-31T11:17:00.012-04:00

I show my students histograms of more or less normally distributed real-life data. I have found it difficult, though, to get a Normal curve that fits nicely on top of the histogram. Is there a way to do a best-fit regression in this situation? I looked around and can't find one, so here's a procedure I came up with. I'm not sure if it's the best possible fit, but it's a good fit.

Using the fact that a normal distribution is given by the equation you can work backwards to see how to make the data linear. That is, is a linear transformation of normally distributed data. Here is a histogram.

I used the midpoint of each bin as the x data, and then I transformed the y data as described.

The one trick is that, for x values below the mean, the transformed y data points need to be negative. That can create a little ambiguity for the middle bin, but it's not too hard to tell here that 2.5 is a little below the mean. If in doubt, try both. I ran a linear regression on and found that This can be transformed back into which is almost ready to graph. All it's missing is the leading coefficient. A little work shows that the standard deviation is 0.88, and therefore the final equation is Here's the histogram, with the overlaid normal curve, which does not fit especially well.
However, this shows that this real-life data does not exactly follow a normal distribution, since this is about as well as we could hope it would fit.

I-85 %

2011-04-05T20:00:00.006-04:00

The U.S. interstate system takes remarkably straight paths between major cities: specifically, I believe that the true distance between two cities is, on average, only 6/7 of the interstate driving distance. Here's a statistical activity I made for my students:

http://www.mediafire.com/file/h29bsfs2cgoiro0/interstates.doc

If they do a decent sample size, say n = 25, they will almost certainly reject the null hypothesis I state in the problem.

Critical thinking course

2011-03-25T10:11:00.014-04:00

There are a few methods for teaching critical thinking skills to public speaking and/or debate students.

One approach is to include a unit on critical thinking within a public speaking course (usually near the end) or an introduction to debate course (usually near the beginning). The unit might include Toulmin's simple framework for analyzing the claim, evidence, and warrants of arguments; it might teach students to identify informal fallacies; or perhaps the instructor gives students a checklist of basic questions to ask themselves about their arguments, e.g., "Who is the source of this information?", "How was this information collected?", etc. This approach tends to be informal (lacking strict logical rigor), simple to understand and apply, and not specific to any content domain. This is the approach I use in my debate textbook: I have an early chapter on Toulmin's framework.

Another approach is to require would-be debaters to take a separate course to improve their critical thinking skills. Some debate teams require debaters to take an additional course in logic (often in the philosophy department), which tends to be very mathematical and rigorous, perhaps even confusing, and hardly ever useful for debate contexts. I recently saw a team that requires debaters to take an additional course that surveys argumentation in different fields: legal and constitutional reasoning, political science, economics, critical theory, etc. The debaters get a primer on each topic, and some exposure to what constitutes good arguments in each field. This approach certainly gives debaters deep knowledge about various fields, but it leaves them weak on the general evaluation of new arguments in other fields.

Instead, I believe the best approach is to take the informal model but cover it as a stand-alone course (in the Communications department). I imagine this course would usually be taken by second-year debaters, but there's no reason it couldn't be open to other students as well. Perhaps the best way to organize such a critical thinking course would be:

- arguments about definitions
- arguments about facts
- arguments about cause and effect
- arguments about values

And I think the best way to treat it would be, as Neil Postman suggested in Teaching as a Subverse Activity, a collection of questions upon which to discuss. The teacher could ask framing questions, provide key readings, and open the discussion up. Here's what I envision in each section.

Definitions

There needs to be a discussion about language. Specifically, students should discuss the arbitrariness of signs, the inherent ambiguity of language, and the tempting but ultimately false notion of essentialism. A simple example can spark a great discussion: "Define 'table'" or "Define 'bed'" seem so simple but become so difficult as you start to unpack it. It might even be worth starting a discussion about "discourses": how definitions are field-contextual and make sense only relative to other concepts in that field. A great example is the word "reduction" -- you should look at the Wikipedia disambiguation page to see how many different meanings there are.

The students need to discuss how to resolve definitional disputes: etymological-historical, current usage, explicit agreement, etc. It might be worth spending some time looking at Venn diagrams to compare definitions and to model syllogisms; it's good to make sure that students leave this unit clearly understanding that definitions (and syllogisms) never provide us new information about the world.

Facts

Orwell's "Politics and the English Language" makes a great transition from discussing language to discussing facts, since his main point was in how bad actors could intentional mislead with ambiguous language. It's perhaps worth having a more general discussion about the trustworthiness of sources, intentional and unintentional bias, and the appeal to authority. I've always thought it a good idea to fuse the topics of small-"m" cultural marxism and media literacy in one discussion: in other words, discuss biases of class as well as reportorial laziness, enthusiasm for expert sources (government or science), and the herd mentality. Focusing students on what isn't reported is often more effective than letting them getting bogged down in discussions about whether the stories that are reported are biased. All this is an elaboration on the trustworthiness of sources.

Getting into the nitty-gritty of the facts themselves, I think it's wise to spend time talking about the logical process of generalizing. When can we go from limited, anecdotal experience to say safely that something is usually or always true? This can lead nicely into a discussion about surveys, sampling, and statistical concepts about generalizing -- at a non-technical level. If students understand how to interpret surveys and margins of error, understand the basic logic of them, and know what to look out for (biased questions, biased sampling frames, sample size), then they're doing quite well. As a final note, Stephen Budiansky wrote a fascinating article called, "The numbers racket: how polls and statistics lie" (US News and World Report, July 11, 1988). He provides great examples of commonly circulated statistics that are just plain made up. There are books out there, too, such as Lies, Damned Lies, and Statistics that have good chapters for excerpting on this point.

Cause and Effect

First of all, it's worth discussing how statisticians and scientists set up experiments to prove cause and effect.

From logic, it's also worth discussing necessary versus sufficient causes. And, of course, the slippery slope fallacy. I like to get them diagramming causal arguments early, and once we start talking about the slippery slope fallacy, I introduce them to Ishikawa fish diagrams. I think it's also important to show them with several examples how cause and effect can easily run opposite to their intuition. A good example: kids who drink more milk have bigger feet. Is it because (a) milk causes bigger feet? (b) bigger feet cause kids to drink more milk? or (c) there's a third variable at play -- age? Self-selection is a wonderful example, too: kids who take the Princeton Review do better, on average, on their SATs. Is it because (a) Princeton Review helps? or (b) kids who take the SAT seriously also self-select to take the prep course?

From a systems perspective, students should learn a little about chaos theory (a system where initial conditions matter hugely, not one that is chaotic, thank you very much Jurassic Park), feedback loops, and the like. Economics provides a useful field here, to discuss how all the various parts of a system might push and pull on each other.

And from a real-world perspective, students should discuss what makes everyday predictions about politics, economics, and international relations credible or not. Is it reasoning by historical analogy? Is it clear analysis?

Values

Students can get overwhelmed with the details of different philosophies, so to try to alleviate their confusion, I kept readings short (or just stick to secondary sources); I keep the number of philosophers I introduce them to at a minimum; I choose the more straightforward philosophers only. No Nietzsche, no Habermas, etc. This doesn't need to be a survey course. Instead, I frame it for them as simply as possible: "What is the right thing to do?" I tell them that the particular language and details of each philosophy are less important than understanding the philosopher's answer to my question. I stress for them that there are really only three kinds of answer to my question: (1) what some set of rules tells us is right (the dogmatists), (2) there is no such thing as a right thing to do (the nihilists); and (3) we don't know what the right thing to do is, but we do our best each time to figure it out (the pragmatists). Realizing that most moral philosophers fall into one of three temperaments is a relief. Furthermore, I make sure to bring in lots of ethical and policy dilemmas, and I encourage them to answer wearing each philosopher's hat, as it were.

For dogmatists, I might start with natural law (perhaps Aristotle or Aquinas), leading into a discussion of the appeal to nature fallacy. Of course, you also have to discuss the utilitarians, Kant, and the social contractarians (Hobbes and Rawls -- it's nice for students to see a conservative and a liberal contract view). All together that makes five philosophers to discuss, and I think it's good for students to see how one dogmatic philosophy can completely oppose another. Given an ethical or policy dilemma, it's very interesting to set up five-way debates.

For nihilists, I would tend to focus on criticisms more generally, rather than specific philosophers. There are the criticisms that no universal moral system can be formulated (but there is such a thing as justice). Then there are the moral relativists who would argue that there is no such thing as morality, period; it's just a social construct. I find that this part of the unit isn't especially interesting and one moves quickly into the pragmatists.

For pragmatists, I think I would start with a little Hume, before discussing the existentialists. (I find Sartre's ideas are fairly comprehensible to students.) Then I would move on to the "democrats": those would argue that morality should be defined by agreement and consent. Again, with two nihilistic positions (moderate and extreme) and three pragmatic positions, one can set up interesting five-way debates.

Those are my recommendations. There are good books out there that support a structure like I've suggested, such as William Hughes' excellent Critical Thinking, but I'd honestly rather piece it together with readings, real-world examples, and discussions. With a typical 12-13 week semester, that would give you three weeks per unit. Debaters would leave with a better sense of how to argue topicality (definitions), disadvantages (cause and effect), and critiques (values) -- and would hopefully be more careful researchers after the unit about facts.

Bracketology

2011-03-21T22:27:00.003-04:00

Nate Silver, who does the NY Times blog fivethirtyeight (usually on elections, but now on more), did an analysis and reports that the elimination bracket style used by the NCAA (and debate tournaments) isn't exactly fair:

http://fivethirtyeight.blogs.nytimes.com/2011/03/15/when-15th-is-better-than-8th-the-math-shows-the-bracket-is-backward/

Specifically, it makes me wonder why we don't go to the style used by the NHL: amongst whichever teams are left, top seed plays bottom seed, second seed plays second worst, etc. In the NCAA, fixed brackets style, if the bottom seed upsets the top seed, suddenly the bottom seed now has an easier schedule than it deserves. In the NHL, re-seeding style, the bottom seed would have to keep upsetting all the top seeds to keep going.

Lock-in

2011-02-03T19:59:00.006-05:00

I thought the writer Neal Stephenson did an excellent job of explaining the phenomenon of lock-in with regards to rocket technology in this article: http://www.slate.com/id/2283469/pagenum/all. It is an excellent reminder that the technologies we have are often the result of contingent (historical) factors rather than rational ones. Here are two examples of lock-in that are near and dear to my heart -- that is, they drive me crazy:

1. Have you ever wondered why the US math curriculum goes Algebra 1, Geometry, Algebra 2? It's a completely irrational system that no sane person would design. Algebra 2 classes start off with an extensive review of algebra since it's been 15 months since the students last saw algebra. In fact, the review can last nearly a quarter of the year. Perhaps the review period would last only a few weeks if the students were to go directly from Algebra 1 to Algebra 2. What's worse, many students aren't really developmentally ready for Algebra 1 when they take it; many need a more robust pre-algebra course. A more rational sequence would be Geometry/Pre-Algebra, Algebra 1, Algebra 2. Geometry is developmentally appropriate in 8th grade and serves as a perfect medium for pre-algebra concepts: that x stands for something that is unknown but fixed, and that one can use geometric properties to deduce x, makes sense in a geometric context. One can even get at the idea of x as a variable with similarity and ratios. And yet, year after year, school district after school district decides to keep the irrational sequence unchanged.

Why? At around the turn of the last century, when high schools were the new thing, students took Algebra and Geometry. Period. Geometry, with its logical proofs, was deemed material for seniors. As time went on, more classes were added on, always at the end. First, Algebra 2/Trigonometry was added. Then, Pre-Calculus was the senior math class. Now it's Calculus -- and thus, Algebra 1 got pushed down to 8th grade.

2. You know I'm going to talk about debate tab. I have never tabbed a tournament on notecards, but I know exactly how to do it because I've used the current generation of debate tab programs. The programs are electronic notecards. Don't get me wrong -- I'm very glad that we have the programs! They automate the mindless tasks and don't make careless mistakes like people do. My point is that when the tab programs came along, they were designed to do the existing tournament practices, only more efficiently. The debate community hasn't seriously thought about whether we can design better practices that can only be done by computers. In other words, we are locked-in to tournament procedures (brackets, speaker points, dropped high-low speaker points) that were designed to be (relatively) easy to do by hand, even though we have phenomenally powerful optimizing devices at our fingertips.

A high-low pairing algorithm literally ranks all the teams and then pairs them off two-by-two. Why not have a computer run 10,000 possible pairings and pick the best one?

A method to create balanced groups

2011-02-02T13:34:00.014-05:00

I like for my students to work together in groups. Unfortunately, they always choose to sit with their friends. So I have to assign their groups.

Let's say on the first day of class, I give them a 20 point quiz to see how much of last year's math they remember. I can also use that information to create balanced groups; I don't want to put all the weak students in one group and all the strong students in another. Rather, I would like each group to include weak students, strong students, and average students.

One way to look at this problem is that I want each group's average to be close to the class average. One could design an algorithm to create the groups this way. But I realized as I was designing it that one has to make ad hoc rules that throw out (a) groups composed of entirely average students and (b) groups composed evenly of strong and weak students but no average ones. I wanted a more elegant algorithm.

The other way to look at the problem is that I want each group to be as diverse as possible. If one maximizes each group's standard deviation, then (a) groups are ruled out. It is true that (b) groups would have the largest standard deviation possible -- but the magic here is that standard deviation is non-linear. Let's say that you have starting forming two groups -- group 1 {S, W, W} and group 2 {S, A, A} -- you have two more students to assign {S, A}. It is true that assigning the strong student to group 1 {S, S, W, W} makes its standard deviation bigger than assigning to it the average student {S, A, W, W}. In other words, std. dev. 1s > std. dev. 1a. But the key is that it makes a much bigger difference to group 2: std. dev. 2s is much, much bigger than std. dev. 2a.

Algebraically, (std. dev. 1s - std. dev. 1a) < (std. dev. 2s - std. dev. 2a). Equivalently, (std. dev. 1s + std. dev. 2a) < (std. dev. 2s + std. dev. 1a). Without algebra, the point is that (b) groups would never happen if you try to maximize the standard deviation of each group -- overall, you're always better to maximize the standard deviation of the least diverse group first. With this fact in mind, this becomes a simple maximization problem. This is an extremely powerful idea: to create the most balanced groupings, you make each group as diverse as possible. Below is an example. A fictional class of six will be divided into two groups.

As you can see, each colored line represents a possible set of groupings. The worst groupings are highlighted in red, the mediocre groupings are highlighted in yellow, and the good groupings are highlighted in green. The first cell under a group is its standard deviation, and the second cell is the group's average. I ranked the groupings by creating a geometric average (a b) ^ 0.5 of the two groups' standard deviations. I do generally agree with the rankings. In the red groupings, the groups are skewed: all strong students in one, all weak students in the other. As a result, both groups have low standard deviations. In the yellow groupings, one group is skewed, and the other group includes too many average students. As a result, one group has a high standard deviation, while the other has a low standard deviation. In the green groupings, both groups are balanced, so both have decent standard deviations.

As you'll notice, even for the best groupings, the average standard deviation of the groups doesn't exceed the standard deviation of the entire class. That's as it should be, but I'll leave that proof to an industrious reader.

Another, more realistic (though still fictional) example follows: dividing a 16-student class into four groups. There are too many possible groupings to list (more than 2.6 million), so I used an algorithm to pick a reasonably good solution. (I started by putting the four students in the very middle in different groups, then given that initial condition, the algorithm then assigned the remaining students in a way that attempted to maximize each group's standard deviation.) You can see the results below:

I lettered the students from A to P, strongest to weakest, and indicated a percentage grade for each. The four middle students were G, H, I, and J. You can see that the algorithm was able to do a decent job of maximizing each group's standard deviation (its explicit task); some came out slightly ahead, but they're all relatively large. But you can see how well the algorithm did creating balanced groups: 82.2, 82.4, 84, and 84.2. Remember, this result is an accidental byproduct of trying to create a solution that maximizes each group's standard deviation.

Why do I care so much about this? For one, I really do like having an algorithm that creates evenly balanced groups in my class. But two, I want build this algorithm into a tabulation program -- for partial round robins. In a partial round robin, each team should hit a representative cross-section of the pool. Consider a 12-team round robin with 6 preliminary rounds. It's too tight to run a regular tournament and respect win-loss brackets. But if you can rank the teams before they arrive, then using my algorithm, each team could debate six opponents that are strong, mediocre, and weak.

Differing opponent strengths

2010-01-20T13:34:00.012-05:00

Below is a graphic of a traditionally-run tournament.

The horizontal axis shows each team's final strength; the vertical axis shows each team's average opponent strength; the size of the bubble shows, for each team, the standard deviation of its opponents' strengths. A small bubble represents a team that debated opponents that were all very close together in strength. A large bubble represents a team that debated a wide cross-section of opponents, some weak and some strong.

I think about how a debate tournament ought to look, if it's paired fairly. It seems to me that every team ought to have a good cross-section of opponents. Thus, a fair tournament would be like a partial round robin. We would know that 3-3 teams were truly middle-of-the-pack because of their abilities, not because they got an unfair draw. The bubbles in the diagram would be bigger (each team sees a true cross-sections of opponents) and closer to the horizontal line (average opponent strength for each team would be closer to the overall average opponent strength).

It's relatively easy to pair a tournament like this, even on the fly. To pair a round, you can look at each team's opponents and decide what is missing so far. After three rounds, a team might have debated a 0-3, a 2-1, and a 3-0 opponent; they would now debate a 1-2 opponent. It is true that the opponent records change after the fourth round, but the process is repeated, and by the end, most teams will debate a decent cross-section of opponents from 0-6 to 6-0. Of course, traditional tournaments do not do this; teams debate opponents within brackets. Why?

The reason is that brackets increase the accuracy of rankings. Consider a 4-2 team. Does it deserve to break? If the tournament pairs it against a representative cross-section, this team would debate a 6-0 opponent, a 5-1, a 4-2, a 3-3, etc. There's only one opponent with an equal record -- but it's precisely the comparisons to very similarly-abled opponents that shed the most accurate information about a team's true strength. In a brackets system, the same team would likely debate several 4-2 opponents. There are more points of comparison, allowing for finer rankings. The downside, though, is that a team could go through the preliminary rounds of the tournament debating opponents that are all at exactly the same level. It seems to me like something valuable would be lost.

Of course, these two virtues -- fairness and accuracy -- trade off. You can't maximize both. But there are several ways to get a reasonable equilibrium. For example, pair odd rounds to have every team debate a reasonable cross-section of opponents (i.e., across brackets), and pair even rounds to increase accuracy of rankings (i.e., within brackets).

A new measure of team strength: weighted wins

2009-12-31T10:44:00.049-05:00

I've been thinking about and working for a while on a more accurate method of estimating a team's strength. Bear in mind, I'm not talking about the method for generating final preliminary rankings. The final ranking method is unlikely to ever change, which is not really a bad thing. There's a reason we're all rightfully attached to it: wins and total speaker points may not be the most accurate way to assess a team's strength, but it does seem the most just: those are the wins and points a team earned. So, I'm interested in how to estimate a team's strength only in order to make better power matches during the prelims, not to decide which teams break or don't break. As a second caveat, let me state that there's no way to say objectively that rankings are "correct"; a good ranking method is a good estimate of team strength, which varies anyway from round to round. All you can do is look at whether a ranking method yields some common sense results.

With those caveats stated, here's the first problem with win/loss record as a measure of team strength: no team debates a representative sample of the teams at the tournament. Every team debates six opponents out of n teams at the tournament. Except for round robins and very small tournaments, the proportion isn't very large. At a normal-sized tournament, it might be under 10%. Recognizing this, tournaments do not use randomly selected opponents. Brackets select a subset of opponents for teams to debate, and the results are more informative than if opponent selection is random. While there are many pathways through the tournament (e.g., WWWLLL versus WLWLWL), usually the key is what caliber of opponent a team beats and by what caliber of opponent a team is beaten. For example, a team who beats a 2-4 and loses to a 4-2 will, because of the way the brackets work, most often end up with a 3-3 record, revealing that this team is probably in the middle third of the tournament. Of course, sometimes the brackets don't work perfectly in this way; for example, a team that beats a 4-2 might end up with a 3-3 record. Clearly, in this case, the overall win/loss record is not an accurate reflection of one or both teams' strength.

It is possible to create many different, more accurate measures of team strength that account for schedule strength using complicated formulas. But I think a measure needs to be relatively easy to understand and transparent, if it's to be adopted. The measure I developed (from a suggestion from Steve Gray) is weighted wins/weighted losses. Let's say team A beats teams B, C, and D, and loses to team G: 3 wins, 1 loss. But what if team B was a 3-1 team, team C was a 2-2 team, team D was an 0-4 team, and team G was a 3-1 team? The win against B ought to count for more than the win against D. The weighted measures would give team A exactly 8 "wins" (3 wins + 3 + 2 + 0) and 2 "losses" (1 loss + 1): it gains an extra "win" for every win of each opponent it beats (B, +3; C + 2; and D, + 0) and incurs an extra "loss" for every loss of each opponent that defeats it (G, - 1). As a first step, this already makes an enormous difference in assessing a team's true strength. Teams that defeat good opponents have more weighted wins than teams that defeat mediocre opponents, even if they have the same win/loss record. (Of course, it's possible that a team that has only been paired against mediocre opponents is actually very good -- which will get sorted out through power-matching!)

The method becomes enormously powerful if it re-iterates: for example, team A is now treated as having 8 wins and 2 losses, just as all its opponents are shown with their weighted wins and losses. Let's say B has a weighted record of 5-2; C, 4-4; D, 0-7; and G, 6-2. In the second iteration, team A will have 12 re-weighted wins (3 wins + 5 + 4 + 0) and 3 losses (1 loss + 2). The process can continue to be re-iterated until a reasonable stopping point, say, a team has as many or more weighted wins than there are teams at the tournament (or as many losses)! Based on this rule, the process will re-iterate about log(n) times for an n-team tournament.

For simplicity's sake, I would turn the weighted wins and weighted losses into one statistic:

where r is the number of rounds at the tournament. The first term will create something like a handicapped win percentage.

I ran this method on a small four-round tournament, which took only three iterations. You can see the results here:

In only one case, highlighted yellow, did the method rank a team above someone that it beat. I highlighted in green three teams that dramatically moved up under this ranking and in pink four teams that dramatically moved down. Based on their schedule strengths, these all seem pretty defensible to me.

Some might point out that there's an inherent difficulty created by "upsets," where good teams happen to get knocked off by bad teams. How much is the good team "punished," or pushed down in the rankings, by that loss? I thought a different kind of data set, where the teams play a much more representative sample, would show the basic sanity of the weighted wins approach. I used it to rank the 2009 NFL regular season because there are so many "upsets" in football (about 25%! -- much higher than debate tournaments, where there are about 5%). You can see how well the method I described handles the unusual losses:

As you can see, it does a reasonable job, despite lots of unusual losses.

Pascal's triangle (modified)

2009-12-15T18:35:00.019-05:00

I started thinking about this problem in a specific debate context (for a specific application), before realizing that it isn't so useful after all. Still, the math is quite interesting.

Here's the original question that got me thinking: Is there a way to assign weighted wins -- round 1 wins count for so much, round 2 wins count for something different, and so on -- such that a tournament can produce a ranking that is consistent with the actual results, such that if team A beats team B, and they finish with the same win-loss record, A must be ranked above B? (Thanks to Steve Gray for coming up with the original idea to use weighted wins this way.) The point values for each round must be decreasing for this to work. If team A beats team B in round 1 for 1 point, then all subsequent point values must be smaller, or else B would have the chance to tie (with an equal number of wins) or surpass A (with an equal number of wins -- of course, B should surpass A if it wins more total rounds than A). I tested out a specific set of weighted win points that meets both of these conditions: {1, 0.9, 0.89, 0.889, 0.8889, 0.88889}. I'll write more on why this particular set works later in this post. The results of the test follows:

Pick any point where you might compare two teams, and you can see that you can always tell who got there by winning the earlier round(s). As you can see from the bottom row, it is possible to distinguish every one of the 64 possible pathways (2^6) that a team could take through the tournament (e.g., WLLWWL), and the results line up nicely in order -- that is, an earlier win always ranks a team higher (e.g., WWLWLL is ranked higher than WLLWWL). The earlier win is ranked higher, because that way, there is no possibility a team is ranked lower than someone they beat. NB: This only works if everyone debates within brackets. It fails to hold as a true assumption for pull-up rounds, so this system would fail utterly for round robins.

However, it is not the pull-up problem that scuppers this system (I think it's somewhat solvable for one-win pull-up rounds with half-points). The problem is that this system produces a ranking that is consistent with the actual win-loss results; it does not necessarily produce the most desirable ranking. True, teams are never ranked below someone they beat, but this system overdoes it: teams are ranked by the order in which they won rounds. What about an excellent 4-2 team with great speaker points who loses the first two random rounds to the top 4-2 teams? To the good, this excellent 4-2 team will be ranked below the top two 4-2 teams (because LLWWWW is worth fewer points than, for example, WLWWWL and LWWWLW); to the excess, this team will be ranked below EVERY 4-2 team who happened to win either of the first two rounds. It's throwing the baby out with the bath water. Furthermore, it makes no sense to use weighted wins as a third or fourth tie-breaker. If speaker points are the first tie-breaker, then it becomes possible to rank a team below someone they have beaten. It's an all-or-nothing solution, and no one would think that the rankings it produces are good.

The math behind this problem turns out to be more interesting than the originally intended application. Some patterns emerge in any set of numbers that work for weighted wins. In the set of numbers {a, b, c, d, e, f}, the terms must be decreasing, so a > b > c > d > e > f is the first condition. However, not just any set of decreasing terms will work. For example, if the weighted win points were {1, 0.9, 0.8, 0.7, 0.6, 0.5}, the system breaks down: for two 2-0 teams, a round 1 and round 6 win totals 1.5 points, but it should beat a round 2 and round 3 win, which totals 1.7 points. Therefore, the second, trickier condition is that the decreases must decrease, that is, while the slope is negative (negative first derivative) the set must have upward concavity (positive second derivative). Going to my original set of numbers {1, 0.9, 0.89, 0.889, 0.8889, 0.88889}, the terms are decreasing, meeting the first condition, and the decrease is decreasing {-0.1, -0.01, -0.001, -0.0001, -0.00001}, meeting the second condition.

Looking at the chart, every unmarked place is one where any set of numbers that meets only the first condition will be true. For example, on the line of round 3, as long as a > b > c, then a+b > a+c > b+c; it's analytically true. Every marked place is one where a set of numbers that meets only the first condition might fail; only sets meeting both conditions must be true. For example, on the line of round 4, a+d must be > b+c only if the second condition is also met. I made up a term for a set that meets the conditions of this problem: an "inequality ordered set." The definition would be: a set of numbers, such that for any two equally-sized subsets created without repetition of terms, the subset with the single largest term always has the largest sum. For example, a+f > b+c and a+e+f > b+c+d.

I wondered whether it is possible to create an infinitely long "inequality ordered set." Two possible ways to create such an infinite set: {1, (1/x), (1/x^2), ...} and {1, 1-(1/x), 1-(1/x)-(1/x^2), ...}. For the first kind, the smallest x that still works is about 2. For the second kind, the smallest x that still works is about 1.25. I'm working on writing a proof of these.

Topic side bias

2009-09-13T17:34:00.017-04:00

A Numbers Game did some interesting work on the side bias of various college topics, here, specifically, controlling for team strength. In that spirit, I decided to use a different method and see how the results compared.

I used a matched pairs method: for each team, there is a matched pair of results: that team's win percentage on the affirmative, and that team's win percentage on the negative. If the two results show no difference, then the team did equally well (or equally poorly) on both sides of the topic. If the two results do show a difference, there are three possible explanations: (1) the team isn't equally strong on both sides of the topic, e.g., the 2A isn't as good as the 2N; (2) the team hit an unequal set of opponents on the two sides; or (3) there is side bias on the topic. When one looks at all the teams on a topic, (1) is unlikely because the whole point is to control for team strength by assuming that the average team is equally strong on either side, (2) cancels out when one looks at the entire pool, and (3) is left as the most plausible outcome. Although this method still relies on the assumption of invariant strength (that a team has a fixed strength, the same on both sides of the topic, unchanging throughout the year), so does any other method that attempts to control for team strength. With those disclaimers, here are the results:

The third column shows the mean of the matched pairs computation: for each team, I subtracted its negative win percentage from its affirmative win percentage, and I averaged this score over all the teams that year. The fourth column shows a calculated (not the actual) affirmative win rate. They compare closely to the actual rates A Numbers Game already found. The two that are highlighted differ slightly. The affirmative win rate for the China topic my analysis suggests is slightly lower than the actual rate. The affirmative win rate for the courts topic my analysis suggests that the negative had an advantage, while the actual rate showed an affirmative advantage.

Category 1 is roughly the 0-50th percentile (in terms of rounds of competition); category 2 is 50-75th; category 3 is 75-87th; category 4 is 87-94th; and category 5 is 94-100th. You can see the results clearly in both: the less experienced teams had greater success on the negative; the more experienced teams did better (relatively or absolutely) on the affirmative. The reason why the originally calculated affirmative win rate was too low was because there are so many more less experienced teams that bring down the average matched comparison -- but they debate few rounds, so they do not have a big effect on the total ballot count. (I looked at the same tables for other years, but there were no patterns as clear as '05-06 and '06-07.)

One final note: All of the whole years' analyses are significant to at least the 95% level except for '06-07, which is only significant at about the 85% level. I used a 1-sample t-test, since the distributions are more or less normal:

(This is '08-09, but all the distributions look like this.) In fact, the distribution looks a little tighter than the normal curve (given the population's mean and standard deviation), since so many teams have 0% aff-neg win spread. The cumulative frequency graph is even more persuasive:

The blue line represents a normal CDF, given the population's ('08-09) mean and standard deviation. Anything below the line on the left or above the line on the right is tighter than normal. The reason is that the standard deviation is pulled way out by the teams that competed for few rounds (who had very high variability in the spread, from -1 to 1). For '08-09 for example, the standard deviation for the whole population is 0.31; excluding teams with fewer than 9 rounds experience, 0.22.

Based on A Numbers Game's question, I created a Lorenz curve for '08-09:

A few data points in words:

The top 5% of teams debated 19% of all rounds.
The top 10% of teams debated 34% of all rounds.
The top 20% of teams debated 54% of all rounds.
The top half of teams debated 83% of all rounds.

Judge side bias -- the whole field

2009-08-25T22:16:00.013-04:00

I've been intrigued by A Numbers Game's information about judge side bias. Rather than looking at particular judges, I wanted to look at the distribution of all the judges. I plotted the (prelim) judging records of all the college tournaments in '04-05 (data from Bruschke's Debateresults.com)

(Excel workbook.) The vertical axis shows how many prelim rounds a judge judged; the horizontal axis shows the percentage of aff wins a judge gave. As you can see, the shape of the dot plot shows a clear pattern: as judges see more rounds, they cluster more tightly around the mean [.4840, according to A Numbers Game], and the plot narrows at the top. This is as it should be: the more rounds you judge, the less likely you get lots and lots of strong aff. teams (or weak aff. teams) by chance. But how to quantify this pattern and ask exactly how it compares to what we'd expect to see by chance?

What makes this challenging is that the sample sizes differ for each judge. Some judges judged 80 rounds, some two. Normally, you'd expect to have a standard sample size. So I calculated the probabilities at various sample sizes, specifically, at a six-round increment to make the lines. The green lines mark the 68% confidence interval (roughly 1 standard deviation above and below the mean ); the yellow lines the 95% confidence interval (roughly 2 standard deviations); and the red lines mark the 99.8% confidence interval (roughly 3 s.d.s). This is an unusual method, so let me explain what I think it shows. If every judge saw 36 rounds, then we would expect 68% of those judges voted aff. between 40 and 60% of the time (you can trace to see that the green lines do indeed pass through these points). So far, so good. My somewhat original assumption is that you can add these slices up: since for x rounds judged, 68% of those judges in that horizontal slice should be between the green lines, then for all the judges in the whole vertical column, 68% should be between the green lines.

It turns out a little worse than expected, at 33.5%, but not by much. And, as A Numbers Game has shown, this is about the same for the other years, too.

Another way to visualize strength-of-schedule pairings

2009-08-07T16:58:00.007-04:00

I've written about a type of pairing I call a strength-of-schedule pairing. The basic idea is that a team that has had a weak schedule so far (measured by opp. wins, opp. speaks, etc.) gets a strong opponent for the next round. (Of course, all of this is within a bracket, so weak and strong are relative to the average team strength and schedule strength in that bracket.) It sounds simple enough, but it has to work both ways -- both teams get the opponent they deserve in each other.

It hit me how to help people visualize how this pairing method differs from the traditional. First, picture a Cartesian grid, depicting one bracket, like so:

A position along the x-axis shows a team's strength (say, speaker points) above or below the average, 0, of the bracket. (If it helps, you can think of these as standard deviations above or below the mean; or, you can think of these as speaker points above or below 28.) A position along the y-axis shows a difficulty of a team's schedule above or below the average. Quadrant I contains the good teams in the bracket that have had tough schedules; quadrant IV contains the good teams that have had easy schedules.

Ideally, you want debaters from quadrant I (strong teams, strong schedules) to face debaters from quadrant III (weak teams, weak schedules), debaters from quadrant II (weak teams, strong schedules) to face each other, and debaters from quadrant IV (strong teams, weak schedules) to face each other -- to even everything out. Let's look at how the two traditional methods fare. I generated 16 random points on the grid, and based on their scores, power-matched them using these two methods.

First, high-high-pairings:

The best team faces the second best; third, the fourth; on down to the second worst facing the worst. Two debates are matched between quadrants I and IV. These are unfair to quadrant I teams, who are good teams, with tough schedules, facing yet another good team. There are four debates between quadrant II and III. These are unfair to quadrant III teams, who are weak teams, with easy schedules, facing yet another weak team. I'd say there's really only one good match: the quadrant IV team to the other quadrant IV team. All in all, many of these debates are likely to exacerbate the range of schedule strength teams face. Score: 1/8.

Second, let's look at the high-low pairing method, using the same 16 points:

The best team debates the lowest, then the second best debates the second worst, and so on. This is not much of an improvement in terms of equalizing schedule strength. There are two debates between quadrant I to II -- unfair to quadrant II teams, weak teams, tough schedules, facing another good opponent. There are two debates between quadrant III and IV -- unfair to quadrant IV teams, good teams, easy schedules, facing another weak opponent. And there are two that are truly wretched: quadrant II (weak teams, tough schedules) to quadrant IV (strong teams, easy schedules) -- unfair to both quadrant II and IV teams!! There are really only two good matches, between quadrant I and III teams. Score: 2/8.

Here's what a strength-of-schedule pairing looks like, for the same points:

I didn't tweak it! This is what came out of my algorithm. All eight matches accord with the preferences I spelled out: Is debate IIIs, IIs debate IIs, and IVs debate IVs. I added in the dotted line to show that most of them have this rough symmetry, where the x score of one is nearly as possible -y of the other, and vice versa. Given the random distribution of the points, it's pretty darn good. All in all, this will equalize as much as possible the schedule strength faced by each team in this bracket. Tough schedule? Weak opponent. Easy schedule? Strong opponent. Score: 8/8.

Network graph theory and debate tournaments

2009-08-04T19:00:00.009-04:00

I recently saw A Numbers Game's charts of debate tournaments, which look like modified network graphs, and it inspired me to post about some thoughts I'd had a few years ago about graph theory and debate tournaments. (Network) graph theory is a fascinating branch of mathematics, and it is directly applicable to debate tournaments. Basically, a network graph is anything that maps all the pathways (edges) between some nodes (vertices). A network graph of a debate tournament shows the match-ups (edges) between the teams at the tournament (vertices). An edge without an arrow would just show a match-up between two teams; an edge with an arrow would indicate the winner of it. A network graph can show the results of all six (or eight or whatever) preliminary rounds simultaneously. You can see a lot of interesting patterns that would be hard to notice any other way; I've used network graphs as a way to illustrate how a tournament played out.

You might think, since graphs are a complete mapping of all the preliminary round results, that they could be used to rank all the teams at a tournament from first seed to worst. However, if you tried to use a graph this way, you'd run into three different problems. Graphs are best for illustrative purposes (and one alternative use I'll suggest at the end).

The first problem with trying to use a graph to seed the teams is that you still need a lot of tiebreakers. Here's a simple example:

As indicated by the graph, team A beat B and C, and teams B and C both beat D. The problem is that B and C can't be ranked against each other from this information alone. Given the results, the final rankings must contain the sequences {A, B, D} and {A, C, D}, but both {A, B, C, D} and {A, C, B, D} satisfy this. The problem is that, except for round robins, there will always be teams that didn't meet at the tournament, and thus, pairs of vertices without edges.

Ok, so, you still need tiebreakers, but a network graph as a ranking mechanism presents a second, bigger problem: "contradictions." Let's say we run a really small tournament, and we must force A and B to debate twice. Here's one possible outcome that creates a contradiction:

A (aff.) beat B, but B (aff.) beat A. If we try to use the network graph to rank these two teams, we'd be forced to give two contradictory statements. (It's worth remembering that a team's strength is not invariant: teams can be better on one side than the other, they can have off rounds or lucky rounds, and judges also play a factor.) This is simple enough to resolve: we can use speaker points to rank one team higher than the other. Here's a slightly more complex version of the same problem:

A beat B (rd 1), B beat C (rd 2), and C beat A (rd 3). There's a contradiction here also. It will have to be resolved by "upsetting" one result, that is, a team must be ranked below an opponent whom they beat. For example, a final ranking might be {A, B, C}, which means that C's victory over A was "upset" or "overruled" because A had more overall wins, better speaker points, etc., than B or C. Bear in mind that doing a graph didn't create this problem; it merely exposed it. We're mostly oblivious to it because cume sheets show wins, points, etc., and don't provide a network graph. Look carefully through the results of nearly any tournament, and I'd be willing to beat you can find at least a few teams who are ranked below (based on overall record, speaks, etc.) an opponent they beat. Here's another example:

Any such type of contradiction, no matter how many teams, is known as a simple cyclical graph, if there's only one cyclical pathway. The good news is that, however long a simple cyclical graph, only one result has to be upset: {A, B, C, D} only upsets D's victory over A. (A complex cyclical graph would contain multiple, intersecting cycles and be a much bigger headache, but my hunch is that they are extremely rare.)

The third problem with using a network graph as a ranking mechanism is perhaps its biggest, if not mathematically, then for the debate community to stomach:

Notice the problem? There are no cycles; everything flows in only one direction. The rankings, according to the graph, are unambiguously {A, B, C, D, E, F}. Here it is again:

C beat D, but at any tournament, D would be ranked higher, because C is 1-2 and D is 2-1. In the situation I graphed, C is the better team but had a tougher schedule. (It's also possible to create an example in which D is the better team but just had an off-round or a crazy judge.) There's no cycle in the graph, so there's no need to have an upset, but I believe every debater and coach would say D should be ranked higher. Total wins as the first method of ranking is sacrosanct to the debate community, and with good reason. Total wins is clear and unambiguous; a network graph is abstract and complex. I know I would never want a tournament to start interpreting results with a network graph; it would create too much room for error when deciding breaks.

This last problem is insurmountable. I think the lesson is that we need to take every effort to make schedule strength more equitable, but there's no mathematical way to jigger results to somehow weight or re-interpret an unfair set of pairings. The cat's out of the bag, and we just have to say, "Sorry, tournaments aren't always fair," at that point. The bottom line is that network graphs will never and ought not be used for tournament rankings. But there's is an alternative use for graph theory: as a tiebreaker at round robins.

Let's say a six-team round robin has these final results:

Team Record
A 4-1
B 3-2
C 3-2
D 3-2
E 2-3
F 0-5

There's a three-way tie for second place. My suggestion is that round robins can use an idea from graph theory as the first tiebreaker, before resorting to speaker points. I believe that direct results ought to be respected as much as possible, and in round robins, you have direct results for every head-to-head match up. Who cares that team C spoke prettier than B or D if C lost both of those rounds? Here's the graph of this hypothetical round robin:

Now, you may notice that C beat A, which suggests that C is the best of the three, or you may focus on the fact that D beat both B and C, which suggests that D is the best. Both may catch your eye, but there's a way to quantify an exact result. But first, you need to turn the graph into an incidence matrix, like so:

A column represents a team's wins; a row, its losses. Hence, reading down column A, you see that team A beat B, D, E, and F; reading across column A, you see that team A lost to C. The incidence matrix contains all the information that the graph does; it's merely another representation of the same data. You might also notice that there's an easy way to double-check the matrix:

You can add to make sure you have the right number of wins in the column and losses in the row for each team. (The incidence matrix is easy to do for multi-ballot round robins; just put the ballots won into the correct spot for each team.)

Now, we need to test possible rankings. There are six possibilities created by the three-way tie: {A, B, C, D, E, F}, {A, B, D, C, E, F}, {A, C, B, D, E, F}, {A, C, D, B, E, F}, {A, D, B, C, E, F}, and {A, D, C, B, E, F}. We create an incidence matrix for each possible ranking, a matrix of the hypothetical results that perfectly consistent the ranking order with no upsets, ties, or ambiguity. For example, for the possible ranking {A, B, C, D, E, F}, the matrix is:

The matrix shows results that would be perfectly consistent with the ranking. Now we can calculate a score for how well this ranking corresponds to the actual tournament results:

Subtract the possible ranking matrix [R] from the actual tournament results [T] and count the -1s. (You can count the +1s also; they are symmetrical.) According to this ranking, there were four "upsets": that C actually beat A, that D actually beat B, that D actually beat C, and that E actually beat D. If a tournament accepts the ranking {A, B, C, D, E, F}, it "overturns" four direct results.

How do the other rankings compare? Using the same method for each "prediction," the rankings can be compared:

Rank order "Upsets"
{A, B, C, D, E, F} 4
{A, B, D, C, E, F} 3
{A, C, B, D, E, F} 5
{A, C, D, B, E, F} 4
{A, D, B, C, E, F} 2
{A, D, C, B, E, F} 3

The best ranking is obviously {A, D, B, C, E, F}. It upsets the fewest direct results. In fact, the two that are upset make perfect sense:

that C (3-2) actually beat A (4-1) and that E (2-3) actually beat D (3-2). In a sense, these were unavoidable (or you might even say real) upsets, not artifacts created by a poor ranking. Anyway, the point is, the three-way tie could be broken in this case without resorting to speaker points. This algorithm would be relatively easy to program into a tab program for round robins.

Of course, some ties are cannot be resolved by this method, namely, if the ties are really contradictions created by cycles. There's still a place for speaker points and other tiebreakers.

Have you ever heard of Plato, Aristotle, Socrates?

2009-06-20T20:26:00.006-04:00

Aristotle wrote one of the earliest systemizations of logic, his syllogisms. Unfortunately, he made two tiny oversights. An easy and fun logic lesson with students is to use Venn diagrams to check each syllogism, like so:

A full list of the syllogisms is in this document. Thanks to Keith Devlin for the idea.

A neat application for derivatives

2009-06-11T19:49:00.008-04:00

Whoa! May was crazy. But I survived. Here's a fun problem.

The function gives a Bell curve. The function
gives a downward-opening parabola that fits exactly under the Bell curve, like so:

In other words, f(x) is a lower boundary to g(x):
How to go about proving this? Algebraically, simplifying the above doesn't do much. It turns out, though, that looking at the derivatives does prove this.
Using the Chain Rule for compounded functions on g(x) reveals the similarity between the two functions. Here's a graph of the two derivatives:

On the lower right-hand side, quadrant IV, f(x) has a more negative slope than g(x), which is easy enough to prove:
On the upper left-hand side, quadrant II, f(x) has a more positive slope than g(x), which has virtually the same proof:
(Just remember that the xs in these inequalities are negative, so the inequality signs are flipped twice, back to their original position.)

What does this prove? One final fact: at x = 0, f(0) = g(0).

As x increases, the slope of f(x) is always more negative than the slope of g(x) -- they start equal at x = 0, but f(x) decreases more rapidly, so f(x) must always be less than g(x) as x increases. On the other side, the logic is simply reversed.

Standard debate tournament calculations

2009-04-26T10:45:00.007-04:00

I thought it might be useful to post a list of standard probability/counting methods for debate tournaments. I list them in order of rapidity of growth -- the last listed expands most quickly, but they all increase without bound. For all of these, there a n teams at the tournament, and n is an even number.

First: once the teams have been separated into aff and neg pools, how many possible matches are there to consider?

Second: how many possible matches are there at a tournament, period? If you don't consider sides, then there are

possible matches. If you did consider sides (A aff vs. B is counted as different than B aff vs. A), then are twice as many possible matches.

Third: how many ways are there to separate the teams into aff and neg pools?

Fourth: once the teams have been separated into aff and neg pools, how many complete (perfect) pairings are possible?

This is the fastest growing number of all.

Pascal's triangle: a neat proof

2009-04-24T08:25:00.013-04:00

There is an interesting question about how the terms in Pascal's triangle grow. All the terms in a row obviously grow (except the 1s at the extreme left- and right-hand sides of the triangle), but the rows' totals obviously grow, too. Do any of the terms in a row converge, as a percentage of the total of the row?

The most interesting example is the middle term in a row, e.g.:

1
1 1
1 2 1

the 1 and 2 are middle terms for their respective rows. The middle term is always the largest term and grows quickly. So, which grows faster: the row total or its middle term, or is there a convergence? A few examples illustrate what happens:

The 0th row -- 100%
The 2nd row -- 50%

The numerator is the formula for the middle term (see the binomial distribution); the denominator is the row's total. The largest row that my TI-84 calculator could handle before overflowing is the 332nd. As the examples show, the denominator is "winning" -- the middle term as a percentage of the total is steadily decreasing. Pretty amazing considering just how big the middle term is; for the 332nd row, the numerator is 3.8E98!

Can we write a proof of this? Certainly. The first step is to re-write the numerator. Given that the combination is really a simplification of

so, our specific numerator can be re-written as:

To re-write the limit for our whole expression, the middle term divided by the row total, would look like this:

Now the clever step. Let's re-organize that n factorial in the numerator and expand the terms in the denominator:

All the n factorial terms are there; they just been re-organized, with the even terms on one side and the odd terms on the other. It should make sense that the terms in the numerator "sit" perfectly in the "seats" provided by the denominator: there are n terms in the numerator, and there are two groups of n/2 terms in the denominator.

The proof is basically done. One simple re-write makes the final conclusion clear:

Each fraction is now on its own. The first set of fractions are all 1s. Every other fraction must be less than 1. An infinite multiplication of fractions less than or equal to 1 must converge to 0. So, in an infinite Pascal's triangle, the middle term, although it increases without bound, is 0% of the row's total.

---

The above paragraph is incorrect. A lot more work must be done to show that the product of the remaining fractions

goes to zero. I like explanations that just make intuitive sense. So, the first term is 0.5. I noticed that the product of the next four terms (terms two to five) is slightly less than 0.5. A little cancelation helps make why clear:

Thus:

And this continues. The product of the next sixteen terms (terms six to twenty-one) is also less than 0.5. Here are the terms:

A litte cancelation starts the process:

and reorganizing the denominators makes the result clear:

Each pair of terms is slightly less than one. Each pair of terms can be written in the form:

or

The product of the next 64 terms is also less than 0.5. (The number of terms is based on powers of 4.) So, the whole product can be rewritten as 0.5^infinity... that definitely goes to zero.

Pascal's triangle and brackets

2009-04-21T17:09:00.006-04:00

As many debate coaches and competitors already know, because teams are always power-matching within brackets against opponents with the same record, it is possible to construct a simple branching diagram to predict how many teams are in each bracket, like so:

100
50 50
25 50 25

and so on. What they may not realize is the connection to Pascal's triangle, a famous problem in mathematics:

Here are the first nine rows. Each number in a row is created by adding the two numbers in the row above, the number diagonally left and the number diagonally right. The numbers in each row can easily be turned into percentages by dividing a number by the total of the row. For example, in row one, 1/1 is 100%; in row two, 1/2 is 50%; in row three, 1/4 is 25%. As you might have noticed, the total for each row is always 2^(n-1), where n is the row number. (There's also a shortcut for finding the numbers in the rows.)

Once everything has been converted into a percentage, it can be organized in a more easy-to-read chart:

Of course, some of these percentages are overly precise for a debate tournament. The percentages never quite work out exactly because of pull ups caused by uneven numbered brackets, side constraints, team constraints, etc. I always use the exact percentage to multiply by the number of teams at the tournament -- but I am never surprised by +/- 1 or even 2 teams off the prediction. Still, it can be a simple way to estimate the number of teams in each bracket, especially at a very large tournament where the constraints will have less effect. I've looked at the data from large tournaments before and found that the bracket size predictions were within a percentage point. That estimation is useful to estimate the number of teams that could break:

The left two columns show the percentages of teams with a winning record (excluding those with a 50-50% win-loss record) after various even numbers of rounds. The middle columns show the percentage of teams with winning records after various odd numbers of rounds -- always 50%. The right-most column shows the percentages of teams with winning records excluding the worst winning bracket (i.e., excluding 2-1s after three rounds, 3-2s after five rounds, and 4-3s after seven rounds).

Partial elimination round calculator

2009-04-18T10:57:00.003-04:00

I'm a big believer that every team at a debate tournament with a winning record should make it to elimination rounds. (Or, if this is simply impossible, break every team with a certain record, e.g. all 5-2s and no 4-3s. That only seems fair; breaking some 5-2s on speaker points, but not other 5-2s, places too much trust in the objectivity of speaker points.)

Of course, the problem is that breaking every team in a certain bracket creates the need to run a partial elimination round (because how often will a tournament need to break exactly 2^n teams?). The logistics of a partial elimination round can seem a bit unpredictable at first -- how many teams will need to be in the partial? how many judges will be needed? -- so I created a "partials calculator" to help estimate answers to these questions: http://www.mediafire.com/?tmtrnmqtnzu

A few notes about the calculator. I set it up with a default of 34% of teams breaking, a good assumption for the percentage of 4-2s or better, but this value can be changed in the green box. I also set up a default of one judge per two teams in the single-flighted event and one judge per three teams in the double-flighted event, although these values can also be changed in their green boxes.

The yellow highlighted boxes show when a tournament will need extra elim judges. For example, in the single-flighted event, there are very few situations where the tournament would need extra elim judges -- the most significant troubles are in the 100s-110s, where the tournament might be short 10 judges. Otherwise, there are few problems.

The double-flighted event shows two options: (a) single-flight the partial and double-flight the first elim round, or (b) double-flight the partial and single-flight the first full elim. Requiring one judge for three teams is a crucial value; there will enough judges in almost every case to single-flight one (or both) of these two rounds.

Side assignment algorithm

2009-04-15T10:10:00.002-04:00

The PDF contains a description the side assignment algorithm that I found.

Side assignment algorithm found!

2009-04-08T11:47:00.008-04:00

One of the most vexing problems in running a small tournament is assigning sides in odd rounds. If you assign the sides incorrectly in an odd round, there may be nothing but bad options left for the subsequent even round: break side constraints (a team is aff. rounds 3 and 4), break school constraints (force two teams from the same school to debate), or re-match two teams (two teams that have already met have to debate again).

For a round robin, there are very few possible solution in the third to last round. Say you have 8 teams, so before round 5 is paired, team A has three opponents remaining: B, C, and D. If A is assigned to the aff, then 2/3 of {B, C, and D} must be assigned to the neg side -- otherwise, it will be impossible to honor side constraints for rounds 5 and 6. This sounds easy until you realize that B, C, and D all have three opponents each remaining, 2/3 of whom must be assigned to the opposite side... There ends up being just a few ways to pair round 5 that are consistent with all side constraints and re-match constraints for round 6 too.

The complexity of this problem has lead tab programs to include a "schedule round robin" option that executes before any rounds have happened at all. Although round robins are the epitome of this problem, many small tournaments with heavy school constraints (many teams from the same school) also experience it, leading to late round pairings that violate many constraints -- and there's no option yet programmed that solves that. Even big tournaments suffer from a similar problem. Although there's no risk of a big tournament violating any constraints, there is always the question of how well mixed a tournament is. If the same group of teams always is aff in odd rounds {A, B, C, D, E...}, then there's no chance that A can debate B, B debate C, etc. The tournament is better mixed if round 1 affs are {A, B, C, D, E...} and round 3 affs are {A, C, E...} and so on. The current assumption is that randomness is sufficient to mix a tournament well, which might be true, but it's nice to have an algorithm in hand that guarantees that.

Now, you may be tempted to think that a computer program can solve this sequentially: pair round 3, then have it look ahead to round 4 and see if there are any problems. This may just work at a tiny tournament, but the number of possibilities becomes daunting quickly, before becoming downright impossible, even for a supercomputer (and I don't believe many tab rooms would want to book time on the Roadrunner supercomputer). If you set a pairing for round 3, then look at all the possible round 4 options that follow, there are (n/2)! options, where n = number of teams. For 40 teams, there are 2.43 E 18 options. The world's fastest computer, by my rough estimation, would take 37 minutes to verify that all the options for round 4 were bad. To put it in perspective, 2.43 E 18 is about how many stars we can see in the sky. There is a better way, and it's to do a clever simultaneous approach.

Here's the gist of what I found. The mixing issue and the constraints issue are actually two sides of the same coin. If in round 1 team A aff. defeats team B neg., and in round 2 team B aff. defeats C neg., then the computer should be able to reject several possible side assignments out of hand. The best mixed, least conflicted option is actually to put {A, B, C} on the aff. for round 3. A and B can't debate again, so they might as well be on the same side; ditto for B and C. The only possible round that's lost is A vs. C, but any other way to assign the sides rules out more possible rounds. A smart use of this fact enables the algorithm to quickly toss out many possible options and reduce it to a manageable number.

Does the algorithm actually work? Yes. I tested it on a regular laptop, and it will pair a round robin on the fly. Without giving the program any prior knowledge that a tournament will be a round robin, it just picks the best round each time in a few seconds -- and pairs the round robin correctly and completely. The algorithm itself is not complex, but I'll go into it in a later post.

Neat proofs with tangents and slopes

2009-04-02T15:42:00.006-04:00

Spring break is over, and it's time to do some math again!

Let's say you have two lines, y1 and y2, with unknown slopes. However, you do know that y1 is perpendicular to y2, like so:

Without invoking the triangle sum, how can you prove two marked angles are complementary? With a simple use of the co-function.

If angles a and b are complementary, then a + b = 90, and 90 - a = b.

The co-function of tangent is co-tangent: cot (90 - a) = tan (a)*, so cot (b) = tan (a) if a and b are complementary. Is that true? To see, a few more labels help.

Cot (b) is just x2/h, and tan (a) is just h/x1. So, is x2/h = h/x1? You bet -- the slope of lines are (negative) reciprocals of each other.

* Proving co-functions is simple. Starting with the unit circle:

The coordinates of (x, y) = (cos (a), sin (a)). However, if you begin at (1, 0) and move clockwise (therefore, an angle of 90 - a), the points are a mirror image reflected over the y = x line of those before, and therefore (y, x) = (cos(90 - a), sin(90 - a). This defines the basic co-functions: x = cos(a) = sin(90 - a), y = sin(a) = cos(90 - a). And it follows that cot(90 - a) = cos(90 - a)/sin(90 - a) = sin(a)/cos(a) = tan(a).

Strength of schedule pairings work!

2009-03-22T19:14:00.012-04:00

I created a new power matching method, a "strength-of-schedule" (S-o-S) power matching method. This method was used to run a hypothetical tournament, to compare the results to an actual tournament. (Thanks to Orion and Joe for the idea of running a hypothetical tournament.)

A major (180+ teams) 2008 national debate tournament was the point of comparison. The actual results of the seven preliminary rounds were available online. For the hypothetical tournament, round 1 used the same pre-set matches and results as the actual tournament. Round 2 and every subsequent even round used the strength-of-schedule power matching method: teams who had had good opponents so far faced the weaker ones in their bracket; teams who had had weak opponents so far faced the stronger ones in their bracket. Round 3 and every subsequent odd round used the traditional, high/low power matching method in TRPC. Once the pairing for a round was set, a "ballot" was entered for every debate. If the teams had met at the actual tournament, the real results were entered. If the teams had not met, each side received the speaker points they had earned in their respective debates for that round (against different opponents) at the actual tournament, and the winner was determined using the final rankings from the actual tournament (the higher ranking team won). Then, I power-matched then next round. Thus, the hypothetical tournament results were meant to replicate the actual tournament results as closely as possible, without bringing in any info that wouldn't have been available to a tab director during the tournament.

And the results are...

First, the strength-of-schedule power matching method generated only the correct, minimum number of pull-ups. Teams pulled up were always those with the weakest opposition record in their bracket. Otherwise, all teams were correctly paired within their brackets.

Second, the results from the hypothetical tournament closely matched those of the actual tournament. Of the 32 teams that made it into elimination rounds at the actual tournament, 30 of them would have made it into elimination rounds at the hypothetical tournament. (At the actual tournament, there was a four-way speaker point tie for 31st place, broken on opponent wins. The 30th and 32nd place teams at the actual tournament had different opponents — and lower opponent wins — at the hypothetical tournament and dropped below the threshold.)

Third, and most important, in every bracket except the 7-0s, the hypothetical tournament using the strength-of-schedule power matching method had narrower ranges for opponent wins and smaller standard deviations for opponent wins:

(With so few 7-0s, the addition of one outlier made a large impact. This is not the most revealing statistic.) The range for opponent wins for 6-1s at the actual tournament was nine, but four for the hypothetical tournament. That standard deviation was nearly halved. The range for 5-2s decreased from 15 to seven. The range for 4-3s decreased from 15 to ten.

Another telling statistic is the comparison for the top 32 teams at the actual and the top 32 teams at the hypothetical tournament:

The ranges were the same, but the standard deviation was far lower at the hypothetical tournament, meaning that more of the data points were closer to the mean opponent wins. The middle 94% of the top 32 teams, eliminating the highest and lowest outlier, is even more telling. The range for the actual tournament, even eliminating the outliers, was still 12; the range for the hypothetical tournament dropped to eight. You can see that the standard deviation is nearly one opponent win lower.

The bottom line is, it worked. There was nothing in the process that required human judgment or that would be difficult to do in a computer program:

Retrieve the relevant statistics from the tabulation program.
Assign byes.
Calculate the z-scores of a team's strength and its opponents' strength.
Populate an optimization matrix.
Solve the optimization matrix using the Hungarian algorithm.
Feed the solution back into the tabulation program as the next round’s pairings.

Alternatively, the new power-matching algorithm could be written into an existing tabulation program, eliminating steps 1 and 6.

Read the full paper for a description of the method I used: http://www.mediafire.com/?0wymlzdzwoz

And here's the Java code for the Hungarian algorithm I used: http://www.mediafire.com/?y3nqjtmnim2

Strength of schedule pairings

2009-03-15T15:28:00.012-04:00

This is a comparison of running a debate tournament in two different ways. In the left column are the results are from a tournament I helped to run, using the traditional high-low power-matching methods. In the right column are the results from re-running the exact same tournament using my strength of schedule power-matching method. (Specifically, round 1 is the same random pre-set as the original tournament; round 3 uses a traditional high-low power-match; but for rounds 2 and 4 I used my strength of schedule pairing. For each hypothetical round, i.e., every round after round 1, I referred to the actual rankings to determine the winner). Here's the comparison:

Download the Excel workbook: http://www.mediafire.com/?lanmmnnmlmn

As you can see, the groupings are tighter for 3-1s (now a range from 9 to 6) and 2-2s (now from 9 to 6). What is tougher to see is that for the 3-1s, the standard deviation of opponent wins was cut by 33%, from 1.55 to 1.00, and for the 2-2s, the standard deviation of opponent wins was cut by nearly 50%, from 1.86 to 1.05. In other words, for teams in the middle of the tournament, the schedule strengths were much more evened out.

Now, it's true that the range increased slightly for 4-0s and 1-3s. But for the 4-0s, it didn't increase terribly, and for 1-3s, it would have decreased but for one outlier (the team who had only 6 opponent wins). Furthermore, this was a small tournament with team constraints that created a lot of pull-ups; that the results show this level of improvement given those constraints is impressive.

I'm going to test this out on a much larger scale so that the constraints don't impede the algorithm nearly as much.

Circles, ellipses, and Cartesian and parametric equations

2009-03-12T08:26:00.008-04:00

Here is a great problem to introduce students to the utility of different forms of representation. Imagine two miniature train tracks that overlap: one, a circle of radius 4 inches centered at (1, 3) and the other, an ellipse with a long horizontal axis of 8 inches and a vertical axis of 4 inches centered at (0, 4).

1) At what (x, y) coordinates do the tracks cross?
2) If trains are placed at an arbitrary point on each track but travel at the same speed, will they ever collide?

To answer question 1, the Cartesian equations turn out to be the easiest way to go. The circle can be written as:

The ellipse as:

Or, alternatively, the ellipse could be:

At this point, most students recognize that the circle and ellipse equations can be set equal to each other, and they can solve for x or y (whichever is easier) in terms of the other variable, and substitute back in. And that strategy works remarkably well for these equations because the x squared terms cancel out.

To answer question 2, parametric equations are the only way to go. Indeed, a good representation can make the answer to the question obvious and lets one make an even bolder statement. The circle is easy enough to write:

The ellipse requires a little more effort. The problem says the trains are going at the same speed, but they're running on different length tracks. Specifically, the circle track length is 8 * pi, and the ellipse is approximately (square root 40) * pi in length. That means that the period of the elliptical-track train must be adjusted; that train will complete nearly 1.3 revolutions for every 1 the circular-track train completes.

Now, you have something to graph and see what the paths of the trains look like. Comparison of the x-coordinates --

and the y-coordinates --

shows that the trains will indeed cross paths (where the equations cross at the same time t on each graph; equations crossing on the x graph only or y graph only would show where they were on roughly opposite sides of their respective tracks). It becomes obvious with this representation that of course they cross paths because they have different periods (travel time for one circuit around the track). In fact, this representation should make it obvious that "ever" is too weak a question -- they must cross paths, no matter where their starting places. It is especially neat for students to see that there's no least common multiple of the periods possible; that is, the combination of the two functions is non-repeating. Take t to infinity and you'll never see the two trains at the same time in the same places they were at t = 0. Neat.

Half-round robin

2009-03-09T09:54:00.005-04:00

This idea grew out of a conversation with a Michigan coach. What if you had only 12 teams and 6 prelims? Obviously, it's going to be hard to power-match the tournament; the brackets are going to be too small too quickly (basically, nothing but pull-ups after round 3). So why not do a half-round robin? The Excel workbook shows one way to make this happen, and, as it shows, if you can seed the teams before the tournament starts, then you can make a pretty fair pairing: http://www.mediafire.com/?qzediimilke

What are normal opponents wins in a given bracket?

2009-03-06T14:08:00.006-05:00

I decided to look at several big, well-run tournaments from this year and last year. I chose big tournaments because there's less of a chance that odd results were created by restrictions given small brackets with too many teams from the same schools. I'm not going to include the tournaments' names -- this is just data. Here are the results for teams that broke:
That means at one tournament, the 6-0 with the hardest schedule faced opponents accumulating 25 wins, while at the same tournament, the 6-0 with the easiest schedule faced opponents accumulating only 22 wins. For the most part, the 6-0s at all these tournaments had reasonably narrow ranges (meaning that all the 6-0s had roughly similar strengths of schedule) except at two tournaments: the 16-25 and 19-24 are unusually broad ranges. A result of 25 opponent wins averages out to a little better than a 4-2 record/opponent; 16 OW averages out to worse than a 3-3 record! The spread for 5-1s, however, looks consistently larger, from better than a 4-2 record/opponent average down to a worse than a 3-3 record/opponent average.

The results are even more surprising when looking at seven round divisions:
The 7-0s' ranges look reasonably small, but the 6-1s and 5-2s faced very different schedules of opponents! At one tournament, the luckiest 5-2 faced opponents racking up only 21 wins (an average of a 3-4 record), while another 5-2 faced opponents racking up a whopping 36 wins (an average of better than 5-2) -- a harder schedule than the best 7-0 faced!

A hypothetical worst case debate math scenario...

2009-03-04T20:59:00.005-05:00

One other little bit of tournament math... Imagine this hypothetical team, call it team uno, the best team at a tournament, in a tournament using the traditional high-low power-matching system. First and second round are random, so it's possible team uno might hit the worst and second worst teams at the tournament in rounds 1 and 2. These two awful teams go on to a 0-6 win-loss record. Then, team uno, being 2-0 with the best speaker points, will hit the worst 2-0 with the lowest speaker points, which could conceivably lose all its remaining rounds and finish 2-4. The same for the next round, hitting the worst 3-0, which could finish 3-3, and all the way through. It is possible in this way for the top team to face six opponents with a combined record of only 14 wins in six rounds. This averages to just slightly better than a 2-4 record/opponent. (Of course, it will likely be better, but it could even be worse if there are an uneven number of teams in each bracket and the top team receives a "pull-up" and debates an opponent with a one-loss worse record in one or more "power-matched" round.) Now, I think the ideal is for the best team at the tournament to face excellent opponents (this is what power-matching systems, like the Swiss system, are supposed to do!) perhaps averaging 4-2 or 5-1 records, for combined opponent wins in the range of 24-30. A far cry from 14 -- which could easily results from pairings that the current algorithm does create and is powerless to flag or rectify.

Rat Attack

2009-03-03T11:34:00.012-05:00

On Feb. 24, 2009, NOVA ran a special on the mautaam event in India: http://www.pbs.org/wgbh/nova/rats

Apparently, once every 48 years, the bamboo flowers and produces an enormous quantity of fruit, which in turn causes a population explosion among the black rats in the forest. Once the fruit is gone, this plague of rats devours the rice fields, causing a lot of human suffering.

The math is simple: exponential population growth. What is staggering is the sheer rapidity of rat reproduction when there's no limit to the environmental carrying capacity. This is a great, real example to use with your students of exponential growth.

Here are the details I looked up: black rats have a gestation period of 21 days and can have a litter of about 10 pups at a time; female rats can nurse a litter while also pregnant; and rats reach sexual maturity in 6 weeks and therefore can have their first litter at 9 weeks of age. These facts produce explosive -- yes, explosive -- population growth. You can model the growth by tracking the size of each age cohort (newborns, adolescents, mature adults) in an Excel spreadsheet, like I did in this one: http://www.mediafire.com/?linigzqgmmk

Or, you can model the growth with a recursive formula:where a is the time in weeks. You can also come close with an explicit formula,where t is the time in weeks. I graphed this explicit formula into the Excel spreadsheet as well. The upshot is that the rat population comes close to doubling every three weeks; in the four month season of mautaam, the population grows nearly 120-fold. That's a real plague of rats.

Debate tournament math

2009-03-02T17:00:00.012-05:00

Here's how a high school or college debate tournament works: for the first two rounds of debating, each team is randomly assigned an opponent; for the third round, the winners of the first two rounds are assigned other winners as opponents, while losers debate losers. This system continues for several preliminary rounds, "power matching" teams against opponents with the same record of wins and losses, until the top "brackets" with winning records (7-0s and 6-1s, for example) move on to elimination rounds. Thus, the preliminary rounds are a type of Swiss system tournament, a format that is used in chess competition, too. The number of teams in each final bracket follows a perfect binomial distribution (plus or minus one team or two for odd numbers that require a team to be "pulled up" from a lower bracket).

This approach is generally felt to be fair, although it is a recognized problem that a good team could lose the first or second round and would have easier opponents all the way through. How often does this happen? A visualization helps:

Click on image for more detail or download from mediafire.

These are the preliminary varsity policy debate results at the 2009 Harvard invitational high school tournament. (I took out names because I don't want to seem like I'm ragging on any school; I'm really just interested in the math.) Each row represents a different bracket -- the 7-0 at the top, 6-1s one row down, etc., and the 0-7 at the bottom -- and each row is sorted best speaker points (left) to worst speaker points (right) in that bracket. Each arrow represents one actual debate between two teams, pointing to the winner but in the loser's row color. Every single round is there, but I bolded the rounds that the top nine teams won. You can see how differently the top teams (the 7-0 and 6-1s) got that record. Some 6-1s, circled, defeated at least three 5-2 or better teams. Other 6-1s, in squares, defeated only one or no 5-2s. The 6-1 on the far left defeated not one team in the top 20%. Perhaps they could have, but they never even faced off against one. They made it into elimination rounds on the basis of an easier schedule than any other 6-1.

Let me make it absolutely clear, I'm not criticizing the folks who run the Harvard tournament. They do a fine job. The problem is not with their execution. I'm sure that at every point, the 6-1s were given proper opponents for their records; the problem is that some of those opponents went on to lose many of their remaining rounds and revealed their weakness. The problem is the method, which is only as good as the current record of each team accurately reflects its true strength. Since this information can't be known in advance, the only solution so far has been to repeat the process many, many times to thoroughly test and properly rank each team in preliminary rounds. Potentially, what you're looking at above is a raw sort that still contains some errors, like ABCEDLFGJIMNP... it's getting better, but there's still a need for further sorting. Consider it this way: the first round is supposed to determine whether a letter is in the first half of the alphabet or not, by picking up two letters at the same and determining which comes first. Generally speaking, this works, and A, B, C, etc., are likely to end up in the first-half pile. But what happens if the letters you pick up to compare are T and W? T will be misleadingly placed in the first-half pile, and you hope that this doesn't happen two, or three, or seven times in a row, but clearly, it can and did happen, and a team made into the top 6% without ever facing an opponent in the top 20%.

Randomness isn't enough. There needs to be an element added to power-matching that controls for strength of schedule. If you need further convincing, here are the 5-2s highlighted:

Click on image for more detail or download from mediafire.

The circled 5-2s defeated at least one other 5-2. (It's hard to see those blue arrows, so click on the image for expansion first.) The 5-2s in squares defeated only one or two 4-3s or better -- that is, they made it into the top 20% and elimination rounds on the basis of defeating only one or two teams in the top 40%. That's quite a disparate schedule: debating other 5-2s and several 4-3s, or debating a few 4-3s and then several teams that are weaker.