Month: November 2012

Product of polygon diagonals

Posted on by John

Suppose you have a regular pentagon inscribed in a unit circle, and connect one vertex to each of the other four vertices. Then the product of the lengths of these four lines is 5.

More generally, suppose you have a regular n-gon inscribed in a unit circle. Connect one vertex to each of the others and multiply the lengths of each of these line segments. Then the product is n.

I ran across this theorem recently thumbing through Mathematical Diamonds and had a flashback. This was a homework problem in a complex variables class I took in college. The fact that it was a complex variables class gives a big hint at the solution: Put one of the vertices at 1 and then the rest are nth roots of 1. Connect all the roots to 1 and use algebra to show that the product of the lengths is n. This will be much easier than a geometric proof.

Let ω = exp(2πi/n). Then the roots of 1 are powers of ω. The products of the diagonals equals

|1 – ω| |1 – ω2| |1 – ω3| … |1 – ωn-1|

You can change the absolute value signs to parentheses because the terms come in conjugate pairs. That is,

|1 – ωk| |1 – ωn-k| = (1 – ωk) (1 – ωn-k).

So the task is to prove

(1 – ω)(1 – ω2)(1 – ω3) … (1 – ωn-1) = n.

Since

(zn – 1) = (z – 1)(zn-1 + zn-2 + … 1)

it follows that

(zn-1 + zn-2 + … 1) = (z – ω)(z – ω2) … (z – ωn-1).

The result follows from evaluating the expression above at z = 1.

Related: Applied complex analysis

Pure possibility

Posted on by John

Peter Lawler wrote a blog post yesterday commenting on a quote from Walter Percy’s novel The Last Gentleman:

For until this moment he had lived in a state of pure possibility, not knowing what sort of man he was or what he must do, and supposing therefore that he must be all men and do everything. But after this morning’s incident his life took a turn in a particular direction. Thereafter he came to see that he was not destined to do everything but only one or two things. Lucky is the man who does not secretly believe that every possibility is open to him.

As Lawler summarizes,

Without some such closure — without knowing somehow that you’re “not destined to do everything but only one or two things” — you never get around to living.

It’s taken me a long time to understand that deliberately closing off some options can open more interesting options.

More creativity posts

How well do moments determine a distribution?

Posted on by John

If two random variables X and Y have the same first few moments, how different can their distributions be?

Suppose E[Xi] = E[Yi] for i = 0, 1, 2, … 2p. Then there is a polynomial P(x) of degree 2p such that

|F(x) – G(x)| ≤ 1/P(x)

where F and G are the CDFs of X and Y respectively.

The polynomial P(x) is given by

V‘ M-1 V

where V is a vector of dimension p+1 and M is a (p+1) × (p+1) matrix. The ith element of V is xi and the (i, j) element of M is E(Xi+j) if we start our indexes start from 0.

Reference: “Moments determine the tail of a distribution (but not much else)” by Bruce Lindsay and Prasanta Basak, The American Statistician, Vol 54, No 4, p. 248–251.

The most interesting logs in the world

Posted on by John

I occasionally get comments from people who see “log” in one of my posts and think “log base 10.” They’ll say they get a different result than I do and ask whether I made a mistake. So to eliminate confusion, let me explain my notation.

When I say “log,” I always mean natural log, that is, log base e. This is the universal convention in advanced mathematics. It’s also the convention of every programming language that I know of. If I want to use logarithms to a different base, I specify the base as a subscript, such as log10 for log base 10.

The reason logs base e are called natural, and the reason they’re most convenient to use, is that base e really is natural in a sense. For example, the function kx is its own derivative only when k = e. And the derivative of logk(x) is 1/x only when k = e.

All logarithms are proportional to each other. That is, logb(x) = loge(x) / loge(b). That’s why we can say something is logarithmic without specifying the base. So we might as well pick the base that is easiest to work with, and most people agree that’s base e. (There are some exceptions. In computer science it’s often convenient to work with logs base 2, sometimes written lg.)

Logarithms base 10 have the advantage that they’re easy to compute mentally for special values. For example, the log base 10 of a 1,000,000 is 6: just count the zeros. So it’s good pedagogy to introduce logs base 10 first. But natural logs are simpler to use for theoretical work, and just as convenient to compute numerically.

Along these lines, when I use trig functions, I always measure angles in radians. Just like all advanced mathematics and all programming languages.

As with natural logs, radians are natural too. For example, the derivative of sine is cosine only when you work in radians. If you work in degrees, you pick up a proportionality constant every time you differentiate a trig function.

Natural logs and radian measure are related: Euler’s formula eix = cos(x) + i sin(x) assumes the base e and assumes that x measured in radians.

Related post: Relating lg, ln, and log10

Dual polyhedra for kids

Posted on by John

Here are a dodecahedron (left) and icosahedron (right) made from Zometool pieces.

dodecahedron and icosahedron

These figures are duals of each other:  If you put a vertex in the middle of each face of one of the shapes, and connect all the new vertices, you get the other shape. You could use these as a tangible way to introduce duality to kids.

There are lots of patterns that kids might discover for themselves. The dodecahedron has 12 faces and 20 vertices; the icosahedron has 20 faces and 12 vertices. At each vertex of the dodecahedron 3 five-sided faces come together; at each vertex of the icosahedron 5 three-sided faces come together.

The two polyhedra have the same number of edges. You can see this by taking one shape apart to make the other. A more sophisticated explanation is that Euler’s theorem says that V + F = E + 2. When you swap the roles of V and F, V+F doesn’t change, so E cannot change.

Here’s a hint on making an icosahedron with Zometool. Stick the red struts with the pentagonal ends into every pentagonal hole on one of the balls. Now if you connect each of the outer balls to each other, you have an icosahedron. You can leave the red pieces inside, or you can use a few of them as a temporary scaffolding to get started, then remove them.

If you do leave the red pieces inside, it’s hard to put the last few pieces in place because the shape is so rigid.

icosahedron with struts to its center

More geometry posts

Probability of long runs

Posted on by John

Suppose you’ve written a program that randomly assigns test subjects to one of two treatments, A or B, with equal probability. The researcher using your program calls you to tell you that your software is broken because it has assigned treatment A to seven subjects in a row.

You might argue that the probability of seven A’s in a row is (1/2)7 or about 0.008. Not impossible, but pretty small. Maybe the software is broken.

But this line of reasoning grossly underestimates the probability of a run of 7 identical assignments. If someone asked the probability that the next 7 assignments would all be A’s, then (1/2)7 would be the right answer. But that’s not the same as asking whether an experiment is likely to see a run of length 7 because the run could start any time, not just on the next assignment. Also, the phone didn’t ring out of the blue: it rang precisely because there had just been a run.

Suppose you have a coin that has probability of heads p and you flip this coin n times. A rule of thumb says that the expected length of the longest run of heads is about

-frac{log n(1-p)}{log p}

provided that n(1-p) is much larger than 1.

So in a trial of n = 200 subjects with p = 0.5, you’d expect the longest run of heads to be about seven in a row. When p is larger than 0.5, the longest expected run will be longer. For example, if p = 0.6, you’d expect a run of about 9.

The standard deviation of the longest run length is roughly 1/log(1/p), independent of n. For coin flips with equal probability of heads or tails, this says an approximate 95% confidence interval would be about 3 either side of the point estimate. So for 200 tosses of a fair coin, you’d expect the longest run of heads to be about 7 ± 3, or between 4 and 10.

The following Python code gives an estimate of the probability that the longest run is between a and b inclusive, based on an extreme value distribution.

def prob(a, b, n, p):
    r = -log(n*(1-p))/log(p)
    cdf = lambda x: exp(- p**x )
    return cdf(b + 1 - r) - cdf(a - r)

What if you were interested in the longest run of head or tails? With a fair coin, this just adds 1 to the estimates above. To see this, consider a success to be when consecutive coins turn up the same way. This new sequence has the same expected run lengths, but a run of length m in this sequence corresponds to a run of length m + 1 in the original sequence.

For more details, see “The Surprising Predictability of Long Runs” by Mark F. Schilling, Mathematics Magazine 85 (2012), number 2, pages 141–149.

Related: Need help with randomization?

Life lessons from functional programming

Posted on by John

Functional programming languages are either strict or lazy. Strict languages evaluate all arguments to a function before calling it. Lazy languages don’t evaluate arguments until necessary, which may be never. Strict languages evaluate arguments just-in-case, lazy languages evaluate them just-in-time.

Lazy languages are called lazy because they avoid doing work. Or rather they avoid doing unnecessary work. People who avoid doing unnecessary work are sometimes called lazy, too, though unfairly so. In both cases, the term “lazy” can be misleading.

Imagine two computers, L and S. L is running a queue of lazy programs and S a queue of strict programs. L may do less work per program by avoiding pointless calculations. But it may accomplish more productive work than S because the time it saves executing each individual program is used to start running the next program sooner. In this case the lazy computer is getting more productive work done. It seems unfair to call the computer that’s accomplishing more the “lazy” computer. This also could apply to people. Sometimes the people who don’t appear to be working so hard are the ones who accomplish more.

A person who approaches life like a strict programming language is not very smart, and even lazy in the sense of not exercising judgment. Conversely, someone who bypasses an unnecessary task to move on to necessary one, maybe one more difficult than the one skipped over, should hardly be called lazy.

Related posts