What the hell is a harmonic mean? OR: A few thoughts on traffic intersections

July 14th, 2011  |  Published in amth, math, maths, meth, minth, morth

"In which Karl works through math he should have understood a decade ago"

Traffic



Something I was thinking about as I biked about my current home of North Austin, where they have been adding traffic lights to accommodate the increasing population...

Suppose you are trying to time a stoplight. That is, you are tasked with setting the durations, order, and whatnot of the various stages of the light cycle. What quantity exactly do you try to maximize?

So actual traffic intersection design is a tricky balancing act--you want to get lots of cars through, but you're not going to want to make it unsafe in doing so. You'll also want some notion of "fairness"--it's a Bad Thing to keep a car stopped at a red light for 20 minutes, even if by so doing you maximize the number of cars getting through the intersection per minute.

Let's simplify, however, and just think about maximizing one variable. What do we choose? Well, the first thing I thought of was throughput--the number of cars getting through the intersection per minute. A well-designed intersection will try to maximize this.

Suppose, however, we don't have a way of measuring this directly, but we do have the cars' average speed from the time they enter the vicinity of the intersection to the time they leave it. What then? (You may ask yourself what "average" speed here means--that's actually exactly what we're going to answer.)

The first thing I thought in my Texas-summer-induced haze was that we would just maximize the arithmetic mean of the cars' speeds. The arithmetic mean will give us the "average", right? Well...

What is the Harmonic Mean?



I didn't hear the phrase "harmonic mean" until about my junior year in college, and I didn't really figure out what it was until somewhat recently. Basically, the harmonic mean is the best way to average rates of things--if you have a bunch of quantities which all take the form "unit1's per unit2" (miles per hour, price per earnings, etc.), then the harmonic mean is likely the average you want.

If you have n numbers x_1,\ldots, x_n, then the harmonic mean H of them is given by

H(x_1,\ldots,x_n) = \frac{n}{\frac{1}{x_1} + \ldots + \frac{1}{x_n}}.


Say we fix a distance d and have two cars drive distance d. The first goes speed r and the second goes speed s. What do we want out of an "average speed"? Well, we want a speed a such that if a single car were to go distance 2d at speed a, it would take the same amount of time as if the car were to travel the first distance d at speed r, and then travel the second distance d at speed s. This is exactly what the harmonic mean gives us! (A short proof of this fact appears at the end of this note; if it's not obvious to you--it wasn't to me--give it a look, or, better, try to prove it yourself--it's not complicated.)

So...



So I realized I want the harmonic mean instead of the arithmetic mean! Neat! Done! We'll time the stop light in such a way that we maximize the harmonic mean of the speeds of the cars within some vicinity of the intersection. That'll be $200,000 please, City of Austin.

That was an unsatisfying explanation.



I agree! So I sat down and tried to think of a more convincing argument that maybe a well-designed intersection should maximize the harmonic mean of the speeds of the cars traveling through it.

A wholly and totally reasonable quantity to want to minimize is the sum time all the cars spend in an intersection. That is, suppose we have n cars, and each car i spends time t_i in the vicinity of the intersection. Then we will want to minimize the function

\sum_{i=1}^n t_i.


A bit more accurately, suppose we have a stoplight setup \ell. The time it takes car i to get through the intersection is a function of \ell. So really what we want to minimize is

\sum_{i} t_i(\ell).


Great. Let's further suppose the distance traveled by these cars is d (that is, the length of the "vicinity" to which we're referring is d). Further, each car i goes an average speed v_i(\ell), which is a function of the stoplight setup: different intersection setups will yield different average speeds for cars. (Again, the "average speed" of a car here is going to mean what you probably think it means if you've gotten this far.)

So let's do a little bit of algebra! If you're not familiar with the notation, \arg\min_x f(x) gives you the value of x at which the function f is minimized. Similarly, \arg\max_x f(x) gives you the value of x at which f is maximized. The variable x with respect to which we are finding the argmin/argmax here is something like "all conceivable intersection setups".

\arg\min_x \sum_i t_i(x)


= \arg\min_x \sum_i \frac{d}{v_i(x)}


= \arg\min_x \sum_i \frac{1}{v_i(x)}


= \arg\max_x \frac{1} {\sum_i \frac{1} {v_i(x)}}


= \arg\max_x \frac{n} {\sum_i \frac{1} {v_i(x)}}


= \arg\max_x H(x).


(The first step holds because v=d/t; the second step holds because the numerator will stay the same regardless of what we choose for x; the third step holds because \arg\min_x f(x) = \arg\max 1 / f(x) for any f; the fourth holds for the same reason as the second.)

Neat! We have shown that constructing our intersection to minimize the total amount of time cars spend in it is the same thing as designing our intersection to maximize the harmonic mean of the speeds of the cars within its vicinity (and NOT the arithmetic mean).

This isn't a particularly interesting result, but it wasn't immediately obvious to me.

Anyways, moral of the story: if you are averaging rates, think very seriously about using the harmonic mean.

So is maximizing the harmonic mean of velocities really different from maximizing the arithmetic mean?



Yes! Suppose we are considering two stoplight setups \ell_1 and \ell_2, and suppose we are running a simulation with two cars. In \ell_1, the two cars have velocities 1 and 9. In \ell_2, the cars have velocities 4 and 4. Now,

H(\ell_1) = \frac{2}{ (1/1) + (1/9) } = 1.8


H(\ell_2) = \frac{2}{ (1/4) + (1/4) } = 4


So if we are picking stoplight setups based on harmonic mean of velocities, we'll pick \ell_2. However, if we're picking based on arithmetic means, we'll pick \ell_1 (which gives an arithmetic mean of 5, vs \ell_2's arithmetic mean of 4).

So the type of average we use matters!

(You can verify for yourself that \ell_2 minimizes the total time spent in the intersection.)

Post-scriptum: Promised proof of above statement



OK, so we are showing that if car 1 goes distance d at speed r and car 2 goes distance d at speed s, then the ideal average speed a is the harmonic mean of r and s. By "ideal average speed" I mean simply the following: suppose we have car 3, which goes distance 2d at speed a. Then it takes the same amount of time for car 3 to go 2d at speed a is it does to go d at speed r and then d at speed s. Denote by t_1 the time it takes car 1 to go distance d; denote by t_2 the time it takes car 2 to go distance d; denote by t_3 the time it takes car 3 to go distance 2d. Then what we want to show holds is that

t_1 + t_2  = t_3.


In fact, the average speed a that makes this true is the harmonic mean of r and s.
Assume a is the harmonic mean of r and s. Then:

t_1 + t_2 = \frac{d}{r} + \frac{d}{s}


= d \cdot \left( \frac{1}{r} + \frac{1}{s} \right)


= \frac{d} {\left( \frac{1}{r} + \frac{1}{s} \right)^{-1}}


= \frac{2d} {2\left( \frac{1}{r} + \frac{1}{s} \right)^{-1}}


= \frac{2d}{a}


= t_3.


This completes the proof.

Comments are closed.