Sunday, April 13, 2014

194: Voyages Through Animalspace

Audio Link

Before we start, I'd like to thank listeners WhWaldo and DLove21 for posting some more great reviews to iTunes.   Thanks guys!    And to you other listeners out there, don't forget, you too could be mentioned in an upcoming podcast by posting a nice review.   

Anyway, on to today's topic.   Yesterday I was at the Oregon Zoo with my daughter, and we saw lots of cute and not-so-cute animals, including a tortoise, lizards, tigers, sea otters, and a chimpanzee.   It's always amazed me that such a variety of animals could evolve on our planet, and through a variety of mutations some primal forms have led to all these diverse and dissimilar creatures.   For a long time I found this hard to grasp, until I read Richard Dawkins' famous book "The Ancestor's Tale".    In one chapter of the book, he described evolution as a grand mathematical journey through a special kind of multidimensional space.   Somehow this geometric view of evolution made it seem more real, and more sensible to me than it had ever been before, so I thought I would go ahead and share it with you.

What do we mean by a journey through a geometric space?   Let's start by talking about a journey through an ordinary three-dimensional space.   Think of a 3-D graph you might set up in a tool like Excel, showing your location in your house in terms of length, width, and height relative to the front door.   So a dot at coordinates (0,0,0) might indicate that you are at the front door, while (10,10,10) might show that you are in your computer room a short distance away on the second floor.     Suppose you ask the question:  is it possible to get from the front door to the computer room?   The answer is yes if you can draw a continuous path in your graph from coordinates (0,0,0) to (10,10,10), in which every point along the way is physically reachable.    If your computer room is unreachable- say your wife encased it in steel walls on all sides to keep you from playing so many video games-- this is represented by impassible blacked-out regions in your graph, preventing you from drawing this continuous path.

Now let's look at how we can model animal evolution as a graph.   Think about several characterists of animals, such as fuzziness, size, and strength.    You could draw points on a 3-D graph showing where some similar animals fall in these dimensions.   Perhaps your house cat would be close to the graph's origin, while a Siberian tiger would be represented by a point further out.    Let's ask the question:  can we travel on a continuous path, where motion is due to genetic mutations resulting in a living creature slightly different on one of our three dimensions, from the housecat point to the tiger point?      It's pretty easy to imagine mutations that make an animal slightly larger, stronger, or fuzzier.     Nobody would seriously propose, for example, that there is a blacked-out region somewhere betweem the cat and tiger where, after a certain size, there is no way a creature with that specification could be alive.    So we can easily imagine that the cat and the tiger are related.

Looking at just these three dimensions is obviously a massive simplification, as there are thousands of dimensions along which an animal can be described:   diet type, eyesight, hearing, and many other things you probably can't even think of if you're not a professional vet.   So the three dimensions we are limited to in our sad dimensionally poor existence, at least from our perception, are not sufficient to describe a creature.   But the core concept remains:  any animal can be thought of as a point in a large multidimensional graph.   Graphs with more than three dimensions can be easily modeled with modern computer systems, though we can't physically look at more than three in a single figure.   If you want to figrue out if some animal can have an evolutionary relationship to another animal, you just need to ask:  can you conceive a continual path from one to the other in this gigantic space?   It doesn't matter if the path is incredibly long- evolution has millions of years to work with.  

The most challenging part is that there are lots of blacked-out regions on this graph, representing non-viable monstrosities:   the point with the size of a housecat and the bite strength of a tiger, for example, can probably never be reached, though if you try to pet my cat while he's washing himself you may get pretty close.    As Dawkins points out, "in the multidimensional landscape of all possible animals, living creatures are islands of viability separated from other islands by gigantic oceans of grotsesque deformity.   Starting from any one island, you can evolve away one step at a time, here inching out a leg, there shaving the tip of a horn, or darkening a feather."    So the islands that Dawkins describes in his graph can be thought of as connected by thick sandbars, showing paths from one to the other where the intermediate creatures are reasonable.    The journey from a T. Rex to a chicken may seem incredible, but I don't find it that hard  to imagine a very long continuous series of changes that trace this journey in this strange type of space:  changes in size, gradual transformation of arms to wings, hardening of teeth into a beak, etc.

There's actually one more detail of this space that makes evolution slightly easier to believe than it might sound at first.   We've been talking about continuous paths, but that is an oversimplification.   Every genetic change is actually a tiny discrete 'jump' from one point to another, so the paths do not have to be fully continuous.   So, for example, the jump from total blindness to  light-sensitive spots, then to recessed spots filled with fluid, and so on to a full eye may seem to have many discontinuities, but that's okay, as long as none of the discontinuities is large enough that it can't be jumped by a small genetic mutation.   So some thin blacked-out regions of this graph may not be insurmountable.   There are of course some discontinuties that can't be jumped-- a bird with a petroluem-based jet propulsion system might be plottable here, but it would require such a massive set of changes at once that it's probably effecitvely impossible.   The blacked-out regions between our superbird and the chicken are likely just too thick to allow an evolutionary jump.

Anyway, maybe this only helps for math geeks, but I found Dawkin's spatial explanation a really intuitive way to think about evolution.  Next time you play with your cat or dog, remember that he's not just a pet, he's a unique point in a massive multidimensional space.

And this has been your math mutation for today.


Sunday, March 23, 2014

193: Nonrandom Randomness

Audio Link

Recently my wife got a bit annoyed with me as we drove to a restaurant on our Saturday date night. The problem was that, as usual, I plugged my iphone into my car's radio to play music for our drive, telling it to shuffle the playlist and select random songs. On this particular night, my iphone decided to play four David Bowie songs in a row. Now I should admit that Bowie does take up a nontrivial proportion of my usual playlist, about 160 or so out of the 1000 songs on the list. But it was still pretty surprising that we heard nothing but Bowie on the drive; my wife thought I had set the iphone on Bowie-only just to drive her nuts. Is such a streak a reasonable result for a truly random song shuffle?

Well, to answer this, we should think about the probability-- does it make sense that every once in a while, we would experience a streak like this? It's kind of similar to the "birthday paradox", which you may have heard me mention before. Suppose you are at a party with a bunch of friends, and ask them all their birthdays, looking to see if any two share the same one. You would think that the probability of two people with the same birthday would be pretty low, since if you ask a random person their birthday, the chance of them sharing your birthday is only 1 in 365. But actually, the probability reaches 50 percent as soon as you have 23 people at the party. This seems pretty counterintuitive at first. But think about the number of pairs you have with 23 people: the total number of possible pairs of people is 23 times 22 over 2, or 253. When you look at it this way, the number of pairs seems in the right ballpark to have a decent chance of a shared birthday.

The actual calculation is a bit more complex. An easy way to look at it is by analyzing the party attendees one at a time, and calculating the chances that we do NOT have two people sharing the same birthday. We want to calculate, for each person, the chance that they do not share a birthday with any of the previously analyzed visitors. P1, the probability that there are no shared dates yet after looking at the first person, is 1, since there are no people before him. P2 is 364/365, the chance that visitor #2 does not have the same birthday as visitor #1. P3 is 363/365, the chance that visitor #3 doesn't have his birthday on any of the two days seen so far. And so on. The final probabiity that nobody has shared birthdays is P1*P2*P3*..., up to the number of party attendees. You can see the full probability calculation for this situation at the Wikipedia page linked in the show notes. The ultimate result, as I mentioned before, is that if you have 23 attendees, the probability is only about 49% that there are no shared birthdays.

So, now that we understand the birthday paradox, or at least you're willing to entertain the notion if it hasn't fully sunk in, what does that have to do with shuffled songs? Well, as one author points out at, you can think about shared artists for songs as something like shared birthdays. My playlist has way fewer artists represented than the number of days in a year, and I have been playing them over and over on many car trips. In the particular case of Bowie, we can see that the odds are better than average, as he represents about 1/6th of my typical playlist. Thus any time a Bowie song plays, there is roughly a 1 in 6 cubed, or 1 in 216, chance it starts a streak of four. And I've gone on a lot more than 216 car rides in my life. So it's not only not unusual, but expected, for me to see regular Bowie streaks. And that doesn't count streaks by other musicians as well, who have slightly lower odds but also are expected to occasionally appear several times in a row.

We also need to keep in mind the human predisposition to look for patterns in randomness. Back when song shuffling first became available on music players, it was a known problem that people would often randomly get the same song twice in a row or only a few songs apart, and then assume something must be wrong with their device. And of course, once people experience this once, they will suffer from a confirmation bias, looking for instances where the same song is repeated and concluding that these verify the supposed technical glitch. Something about our brains just isn't hard-wired to understand or accept the coincidences inherent in randomness. One simple solution was biased random selection, where the device purposely can avoid playing the same artist or song twice in a row based on user settings. Another change that helps is that current ipods and similar devices shuffle the music like a deck of cards, creating a full random ordering of all the songs in the playlist, rather than randomizing after each song. Thus inherently prevents repeats until the user chooses to re-shuffle their list.

To see an extreme case of our human predisposition towards finding patterns, try flipping four coins, writing down the results, and asking a friend if they appear random. No matter what pattern you get, it will probably look nonrandom to your friend! If you get 3 or 4 of the same result, such as Heads Tail Heads Heads, it will certainly seem like the coin was biased. If you have 2 of each result, there is no way to avoid having it look like a pattern: either a repeated pair like HTHT, or a symmetric pair like HTTH. You have to really think about it to convince your brain of the randomness of such a set of coin flips.

So, when dealing with birthday sharing at parties, coin flips, music shuffling, or annoyed spouses, remember that sometimes truly random results can seem nonrandom, and try to take a step back and really think about the processes and probabilities involved.

And this has been your math mutation for today.


Sunday, February 23, 2014

192: A Logical Language

Audio Link

If you're a speaker of English, which is pretty likely since you're listening to this podcast, you may have found yourself occasionally frustrated by its arbitrary nature, and the difficulties and ambiguities this sometimes causes.    Why are there so many ways of spelling "their" there?   Why should you have to twist your tongue if you want to sell sea shells by the seashore?   And if you talk about a little girls' school, why should listeners be confused about whether the school or the girls are little?    It may not surprise you to learn that the desire for a more well-defined and mathemtically sound human language has been around for a long time.   In fact, it has been over 50 years since Dr. James Cooke Brown first defined the language Loglan, a new human language based on the mathematical concepts of the predicate calculus.    Later iterations of the language, after an internal poltiical struggle against Dr. Brown by language enthusiasts, were renamed Lojban.   In theory, Lojban, unlike English and other natural languages, is claimed to be minimal, regular, and unambiguous.

How do they define Lojban as such a clean language?    First they made a careful choice of phonemes, basic sounds, chosen from among the ones most common in a variety of world languages.    Each distinct-sounding phoneme is connected to uniquely defined symbols, removing any possible confusion about how to pronounce a given word:  a word's sound is completely determined by how it is spelled.   Then they defined a set of around 1,350 phonetically-spelled basic root words using these phonemes, being careful to not create homonyms or synonyms that could lead to confusion.   The number of letters in a word and its consonant-vowel pattern determine what type of word it is:  for example, a two-letter word with a consonant followed by a vowel is a simple operator, while five-letter words are what is known as "predicates".    Replacing many aspects of parts of speech such as nouns and verbs from traditional languages, the formation of sentences is based around the predicates, which are in many ways analogous to the logic predicates of mathematics.   For example, the predicate "tavla" means "x1 talks to x2 about x3 in language x4", with x1, x2, x3, and x4 being slots that may be filled by other Lojban words.  

To get a better idea of how this works, let's look at a specific example.   In the opening I alluded to the sentence "That's a little girls' school", which is ambiguous in English:  is it a school for little girls, or a little school for girls?    In Lojban, if it is the school that is little, the translation is "Ta cmalu nixli bo ckule".   The predicate "cmalu" defines something being small.   "Nixli" means "girl", and "ckule" means "school".   The connector "bo" groups its two adjacent words together, just like enclosing them in parentheses in a mathematical equation, showing that we are talking about a school for girls, and it is that whole thing which is small.   Alternatively, if we said "Ta cmalu bo nixli ckule", the virtual parentheses would be around "cmalu" for is-a-small and "nixli" for girl, showing that what is small is the girls, not the school.   If there were no "bo" at all, there is a determinstic order-of-operations just like in a mathematical equation:   the leftmost choice of words is always grouped together.   So "Ta cmalu bo nixli ckule" and "Ta cmalu nixli ckule" are equivalent.   Pretty simple, right?   Well, maybe not, but after you stare at it for a while it kind of makes sense.   And it does eliminate an ambiguity we have in English, at least for this case.

The adherents of these logical languages claim many potential benefits from learning them.   They were originally developed to test the Sapir-Whorf Hypothesis, which claims that a person's primary language can determine how they think.   Whatever the merits to this idea, I have a hard time seeing Lojban as a valid testing tool, unless a child is raised with this as his primary language without learning any natural languages-- and that would be rather cruel to a child, I think!    But many other virtues are claimed.    Since the language is fully logical, it should facilitate precise engineering and technical specifications; a goal I can sympathize with, since I regularly deal at work with challenges of interpreting plain-English design specs.   It is also claimed as a building block towards Artificial Intelligence, since its logical nature should make it easier to teach to a computer than natural languages.    It is also claimed as a culturally neutral international language, though it has fallen far short of other choices like Esperano in popularity.     And its adherents also enjoy it as a "linguistic toy", helping to research aspects of language in the course of building an artificial one.

At this point, I should add that I actually have a bit of a personal perspective on the viability of this kind of approach to technical specs.   It is claimed that the logical and precise nature of Lojban will mean that if engineers would just learn it, all our specs would be clearer and unambiguous, leading to great increases in engineering productivity.    But I work in the area of Formal Verification, where we are trying to verify chip designs, often having to convert plain-English specs into logically precise formats.    For many years there were different verification languages proposed for people to use in specifications, many offering minimal, highly logical, and well-defined semantics.   But the ones that caught on the most in the engineering community and became de facto standards have not been the elegantly designed minimal ones, but the ones that were most flexible and added features corresponding more to the way humans think about the designs.    So I'm a little skeptical of the idea that engineers would willingly replace English with a language like Lojban in order to gain more logical precision.  

In any case, I think the biggest failure of Lojban has been that there are not enough people willing to learn it.    Perhaps the human brain's language areas might just not be hard-wired in a way that naturally supports the predicate calculus.     Even the page states "At any given time, there are at least 50 to 100 active participants...   A number of them can hold a real-time conversation in the language."   So out of 50-100 people who are paying attention, only a subset of these can actually speak it?   In comparison, Esperanto, an artificial international language designed by idealists in the late 19th century, has tens of thousands of speakers, and an estimated thousand who learned the language natively from birth.  And even Klingon, an artifcial language invented for "Star Trek" and of no practical use to anybody, is rumored to have more fluent speakers than Lojban.

So, if you want to learn a cool way to think differently about language and make it more mathematically precise, go ahead and visit the Lojban institute online and start your lessons.   But if you're hoping to make your engineering specifications more precise, communicate with your neighbors, or bring about world peace, you're out of luck.   So remember to teach your children English as well.

And this has been your math mutation for today.


Sunday, February 2, 2014

191: Liking The Lottery

Audio Link

If you're the kind of person who listens to math podcasts, you've probably heard the often-repeated statement that a government-run lottery is a "tax on stupidity", due to the fact that stupid people are likely to waste their money on something that has a negative expected value.   But is the case really that open-and-shut?    Does the negative expected value of a lottery automatically make it not worth playing, and would this situation reverse if the expected value ventured into the realm of the positive?

Let's start by reviewing the concept of expected value.   At a basic level, this is the sum of the possible values of your lottery ticket, each multiplied by the probablility of getting that value.   As a simple example, suppose you have a local lottery where you pay 1 dollar to guess a number from 1 to 10, and if you're right, you get 6 dollars back.   Your expected value is 9/10 times -1, since in 9 out of 10 cases you lose your dollar, and 1/10 times 5, for a total of -40 cents of expected value.    This represents the likely average return per round if you play hundreds of rounds of this lottery.   Expected value calcuations for real-life lotteries are similar, except that they deal with very tiny probabilities and values in the millions.     Real-life lotteries almost always have negative expected values; for example, one link in the shownotes calculates expected value of a recent Powerball ticket at -1.58.   Actually, for real life lotteries there are some complicating factors that reduce it further:   you have to account for possibly splitting the jackpot with someone else who guessed the same numbers, and also the hefty chunk of taxes that Uncle Sam will take out of your winnings, but let's simplify this discussion by ignoring those factors.

Now here's the critical question:  suppose after many weeks of a growing Powerball jackpot, which happens sometimes if there is no winner, the pot grows to the hundreds of millions, and the expected value crosses over into positive range.   Is it now a more rational decision to play the lottery?   I would argue no:  you are still much more likely to be struck by an asteroid or lightning, die from a bee sting,  or suffer a plane crash than to win.   The expected value calculation really only kicks in if you are buying millions of tickets, in which case you can use it to figure out if your massive bet is likely to be profitable.   In the show notes you can find a link to an amusing article about an investment group that actually did try to buy all the tickets to a Virginia lottery one year, but was a bit hosed by the fact that not all the tickets could be printed in time.

Another way to realize the limited usefulness of the expected value is to think about a slightly odd lottery, as suggested in a blog by statistician Alan Salzberg:  suppose you could spend all your savings for a 1 in  1000 chance to win 10 billion dollars.      If you have less than 10 million dollars in the bank, this game actually has a positive expected value.    Would you play it?   I think 99.9% of people would think playing such a game is insane.   When you can only play it once, you need to think about things other than the statistical average of thousands of trials.   What is the likely net effect on your life if you play it once?   Chances are overwhelming that this lottery would leave you penniless.

So, if the expected value calculation doesn't make sense, how do we figure out if playing the lottery is rational?   I think the key factor is the cost to you of spending the price of the lottery ticket.  Assuming you are doing OK economically, spending a couple of dollars every week can probably be considered effectively zero cost:  you are likely to casually spend more than that on potato chips from vending machines, lattes at Starbuck's, etc.    For this near-zero cost, what value do you get?   There is that thrill of scratching off the numbers or watching the drawing, and having that infinitesmal but nonzero chance of becoming an instant millionaire; given the low cost, maybe that alone makes it worthwhile.   You also know that your ticket cost has contribtued to your state government; your feelings on that may vary, but even if you're a hardcore libertarian, there may be at least a few government services you are OK with funding.   And you're probably happier giving money voluntarily than being required to by law, which would be the effect if nobody played the lottery and income or sales taxes had to be raised instead.

Now I'm not saying that lotteries are always a good idea:  the arguments I just made are predicated on the fact that the lottery ticket is effectively zero cost to you.   If it is not-- if the 2 dollars per week would make a real difference in your life, or you are spending more money than you can afford to lose-- you need to realize that the chances of winning something are so infinitesmal that this is really not a wise expenditure.    It's always kind of sad to see blue-collar-looking people pump what seems like hundreds of quarters into Oregon Lottery video poker machines in bars.   Saving up the money annually to buy asteroid insurance would be more likely to benefit their families in the long run. 

But overall, does playing the lottery mean you're stupid?   This looks to me like an area where many people blindly apply a mathematical formula without really thinking about what it means.    Assuming the cost of a lottery ticket is effectively zero when compared to your income, it looks to me like the answer is no, playing the lottery may be perfectly rational.

And this has been your math mutation for today.


Saturday, December 28, 2013

190: Loving Only Numbers

Audio Link

Before we start, I'd like to thank listeners sblack4, WalkerTxClocker, and LaxRef for some more nice reviews on iTunes.  Thanks guys!

Now, on to today's topic.   During this holiday season in the U.S., many of you are spending time with your families, and taking pity on those who don't have many relatives to visit.     (Or  taking pity on those with too many relatives visiting.)    Sometimes this might bring to mind the strange story of one  mathematician who chose never to marry or have children, instead devoting his entire life to his mathematics:   Paul Erdos, as profiled in Paul Hoffman's famous biography "The Man Who Loved Only Numbers".   Erdos was a Hungarian Jew born in Budapest in 1913.  He originally left his country out of fear of  anti-Semitism soon after receiving his doctorate, and then spent the rest of his life, until his death in 1996, traveling from university to university taking various temporary and guest positions.

There are many surprising and contradictory aspects to Erdos's life.   You would think that someone who chose not to start a family or even to settle in one place would be some kind of social recluse, but Erdos was the opposite.   He considered mathematics to be a social activity, not the domain of isolated geniuses behind closed doors.   His travels were constantly motivated by the desire to collaborate with other mathematicians, where he would help them solve particularly tough problems.   Though he wasn't the leader in any single field of mathematics, never winning the Fields Medal for example, he co-authored about 1525 papers in his lifetime, with 511 different co-authors.   Despite being very odd, and sometimes coming across like a homeless drug addict due to his lack of social graces, he was very popular and well-liked in the mathematical community. 

Due to his large number of co-authors, the concept of an 'Erdos Number' became a common in-joke in the math world.   If you wrote a paper with Paul Erdos, your number was 1.  If you wrote a paper with a co-author of his, your number was 2, and so on.  It is said that nearly every practicing mathematician in the world has an Erdos number of 8 or less.  Incidentally, I found a cool Microsoft site online (linked in the show notes)  to search for collaboration distances between two authors, and found that despite being an engineer rather than a mathematician, I have the fairly respectable Erdos number of 4.   Perhaps the most famous person with a low Erdos number is baseball legend Hank Aaron.   Since he and Erdos once signed the same baseball, when they were both granted honorary degrees on the same day and thus were sitting next to each other when someone requested an autograph, Aaron's Erdos number is said to be 1. 

But as you would expect with someone who constantly travelled and never settled down, Erdos had a rather quirky personality that people who worked with him would need to get used to.   He had his own unique vocabulary, for example.   Children would be referred to as "epsilons", referencing the Greek letter typically used to refer to infinitesmally small quantities.   Women and men were "bosses" and "slaves", while people who got married or divorced were "captured" and "liberated".    Perhaps this reflected an internal attitude that negatively impacted his potential for dating, even if he had ever given a thought to such things.    If someone retired or otherwise left the field of mathematics, Erdos would refer to them as having "died".   At one point he was very sad about the "death" of a teenage protegee, having to clarify to symathetic friends that the cause of death was his discovery of girls.    The United States and Soviet Union were "Sam" and "Joe".   He referred to God as the "Supreme Fascist" or "SF" for short, apparently in protest at being expected to obey the will of divine beings. 

Related to proving mathematical results, Erdos had one piece of private vocabulary that was very important to him.   He always imagined that somewhere up in the heavens, God had a Book in which were listed the most elegant and direct proofs for every conceivable mathematical result.    He wasn't sure if he believed in God, but he definitely believed in the Book.    So if he heard a solution to a problem that he liked, he would always say, "That's one from the Book".   And if he heard a proof that was valid but seemed very awkward or roundabout, he would acknowledge its validity, but still want to search for the one in the Book.   A classic example of a non-Book proof might be Andrew Wiles's famous proof of Fermat's Last Theorem:  while it was fully valid and a work of genius, it took hundreds of pages and is understood by very few people in the world.   Many still hope that a more elegant solution is out there somewhere, waiting to be found.

Despite Erdos's genius and his sociability, there were many aspects of modern life that either baffled him, or were simply considered beneath his notice, and as a result he constantly depended on his many friends to help him get by.   He didn't learn to butter his bread until the age of 21, for example, and always needed help tying his shoes.     If left alone in a public place, he would panic and have a lot of difficulty finding his way back to his university or hotel room.    If he suddenly thought of a solution to a problem he had been working on, he would call his colleagues at any hour of the day or night, with no consideration for whether it might be a convenient time.    He didn't like owning anything, travelling with a single suitcase and requiring his hosts to wash his clothes several times per week.  (It always had to be his hosts doing the washing, since he never bothered to learn how to use a washing machine.)    The last novel Erdos read was in the 1940s, and he did not watch movies since the 1950s.

On the positive side, his lack of concern for money made him quite generous to fellow mathematicians and others in need.   When he won the $50000 Wolf Prize, he used most of the money to establish a scholarship fund in Israel.   He would sometimes give small loans of $1000 to struggling students with strong potential in math, telling them to pay him back whenever they had the money.   At one point he was seen to take pity on a homeless man just after cashing his paycheck:  he took a few dollars out of the envelope to meet his own needs, then handed the rest of the envelope to the stunned beggar.    In addition, Erdos would put out "contracts" on math problems he wanted help solving, ranging from $10 to $3000 depending on his estmates of the difficulty.   Some of his friends pledged to continue honoring the contracts after his death; at the time, it was estimated that he had about $15000 in contracts still outstanding.

Anyway, this short summary just touches on a few of the bizarre personality quirks in the unusual life of Paul Erdos.    If you are as intrigued as I was, be sure to check out Hoffman's biography, "The Man Who Loved Only Numbers".    And may the Supreme Fascist grant you a happy new year.

And this has been your math mutation for today.


Sunday, December 8, 2013

189: Squaring The Circle

Audio Link

Recently the phrase "squaring the circle" seems to have been popping up more often than usual, perhaps in response to certain problems currently faced by the U.S. government.    I could easily do a very long podcast on some of those topics, but you're probably here to talk about math, not politics.    So let's get back to that phrase, "squaring the circle", which means to solve an impossible problem.   It descends from a problem originating from ancient times:  with no tools except a compass and a straightedge, can we construct a square with the same area as a given circle?   Mathematicians struggled with this problem for thousands of years, until it was definitively proven impossible in 1882.   

Before we discuss why this is impossible, let's review what the problem is.   We start out with a circle of a known radius, drawn on a piece of paper.   For simplicity in this discussion let's assume that the radius is 1, with the radius itself defining our unit of measurement.   We are allowed to use a compass, which lets us draw a circle around any point with a given radius, and a straightedge, which allows us to draw a line connecting any two points.   By the way, no cheating and using markings on the straightedge for measuring distances.   Using just these tools, and without being allowed to do things like create new lines of precise lengths, we want to draw a square on the paper whose area matches that of the circle.    In effect, this means that starting from a circus of radius 1, and thus an area equal to pi,  we need to construct a square with area pi, and thus with each side equal to the square root of pi.

This is one of the most ancient problems known to mathematics, first appearing in some form in the Rhind Papyrus, found in ancient Egypt and dating back to 1650 B.C., though the Egyptians were happy with an approximate solution, treating pi as 256/81 rather than its real irrational value.     The Greeks who followed them, starting with Anaxagoras in the 5th century B.C., had a more sophisticated understanding of mathematics, and were the first to insist on searching for a fully accurate solution rather than an approximation.    Philosopher Thomas Hobbes inaccurately claimed to have squared the circle in the 1600s, leading to an embarrassing public feud between him and mathematician John Wallis.   There were many other discussions and attempts to solve this problem down through the centuries, most amusingly even including two days of frantic scribbling by Abraham Lincoln at one point in the 1850s.    It may have been for the best that he gave up math and returned to politics.

Nowadays, the basic concept of why circle-squaring can't be done is not that hard to grasp, with an elementary knowledge of high-school level math.   Ultimately it stems from the equivalence between geometry and algebra shown by the field of analytic geometry.   View the paper on which you drew the starting circle as a coordinate plane, with every point described by an x and y coordinate.   Recall that both lines and circles are described by simple types of equations in such a plane.   Lines are described by linear equations of the form y = mx + b, and circles are essentially polynomials in the form x^2 + y^2 = r^2.     As a consequence, compass and straightedge constructions are essentially computing a combination of linear and square root functions of your starting lengths.    This means that any multi-step construction is building up a set of these linear and square root operations.

But remember the target we were shooting for:  we want a square of the same area as our starting circle, so each side of our square measures the square root of pi.   However, pi is a transcendental number:   this means you cannot get to this value by solving any set of  polynomial equations with integer coefficients.   Note that this is a stronger condition than being irrational:  many irrationals are non-transcendental.   The square root of 2, for example, is irrational, but can be derived from the simple equation "x^2 = 2."   If a number is transcendental, this implies that no combination of linear and square-root operations, starting with an integer length, could ever reach a value of pi or its square root, and thus our construction of a length pi starting from a circle off radius 1 is impossible.    This last part of the argument, the fact that pi is trancendental, was the hardest part of the proof, and the most recent to be put in place, proven in 1882 by German mathematician Ferdinand von Lindemann.       While we can create constructions for arbitrarily precise approximations, we can never correctly derive a square with the exact same area as a given circle.

We should also point out that this impossibility is implicitly assuming we are talking about ordinary, Euclidean geometry.   If our discussion is including curved spaces, as we discussed in episode 35, all bets are off.    These curved spaces have many properties that upend our usual notions of geometry, such as triangles whose angles sum to more or less than 180 degrees.   If instead of a flat plane we are sitting on the surface of a curved saddle or a sphere, then we can essentially get a 'free' pi by drawing a line that becomes a curve due to the space's curvature, eliminating a key component of the impossibility proof.     I think we can all agree, though, that the ancient Greeks who posed the problem would consider this type of solution to be cheating.

What is most amusing about squaring the circles is that even after its impossibility was very solidly proven in 1882, enthusiastic amateurs kept on trying to "solve" the impossible problem for many years after.   This has some analogues in government as well...  but I'll try again to keep off that tangent.     You may recall that back in episode 20, I talked about an 1897 attempt by a confused Indiana resident to legislate that pi was really equal to 3.2-- this was partially based on his supposedly successful attempts to square a circle using this value.    Before you laugh too hard at him or the legislators who actually listened to him, we should note that somehow he got his bogus circle-squaring method published in the American Mathematical Monthly, which will forever be an embarrassment to that publication.    In 1911, British professor E.W. Hobson wrote, "Every Scientific Society still receives from time to time communications from the circle squarer and the trisector of angles, who often make amusing attempts to disguise the real character of their essays...  The statement is not infrequently accompanied with directions as to the forwarding of any prize of which the writer may be found worthy by the University or Scientific Society addressed, and usually indicates no lack of confidence that the bestowal of such a prize has been amply deserved as the fit reward for the final solution of a problem which has baffled the efforts of a great multitude of predecessors in all ages. "       The circle squaring craze seems to have mostly died off in the latter part of the 20th century, but a 2003 article by NPR's "Math Guy" Keith Devlin mentioned that he still regularly received crackpot letters from circle-squarers.   And even today, if you look up squaring the circle on Yahoo Answers, you'll find a post by some misguided soul who refuses to believe that the problem is unsolvable, stating that " Its possible we lack the mathematical and conceptual understanding to construct it."   I guess anything is possible, but if you trust modern mathematics at all, it's pretty clear that the circle will never be squared. 

And this has been your math mutation for today.   


Monday, November 11, 2013

188: Democracy Doesn't Work

Audio Link

Before we start, I'd like to thank listener "Cvithlani" for posting another nice review on iTunes. This probably helped Math Mutation get back in iTunes's Science & Medicine "What's Hot" podcast list in the past few weeks. So keep those reviews coming!
Anyway, another election day has come and gone, and this reminded me that I haven't yet discussed one of the election-related topics on my to-do list, Arrow's Theorem. This theorem was first proven by economist Kenneth Arrow in 1951, as part of his Ph.D. work-- just the start of a long career that later won him a Nobel Prize. This is a theorem that basically says that according to some common criteria that we should use to define a fair voting system, no rank-order voting system can ever meet those criteria. In some ways it can be considered an extension of Condorcet's voting paradox, which I described back in podcast 183. I think the easiest way to introduce Arrow's Theorem is through an anecdote I read in the Cafe Hayek blog by Don Boudreaux.
"You walk into an ice-cream store and ask what flavors are available today. The clerk says 'We’ve got vanilla and strawberry.' You ponder for a moment and tell the clerk 'I’ll have strawberry.' Just before the clerk starts to scoop out your strawberry ice cream, he turns to you and says, 'Oh, I almost forgot. We also have pistachio.' In response, you ponder for another second and then tell the clerk, 'Well, in that case, I’ll have vanilla.'
Seems pretty absurd, right? Somehow the availability of a flavor you don't like changes your first-choice selection? But when we're talking about voting, our society really does choose like this. In the most recent election, people point to the Virginia governor's race, where many believe that Republican Cuccinelli only lost to Democrat McAuliffe because of the presence of 'spoiler' Libertarian candidate Robert Sarvis. McAuliffe won the election, but if Sarvis had not been running, then Cuccinelli would have won. Even if you disagree in this instance, articles on the spoiler effect appear during pretty much every election season in our country.
This spoiler effect is related to one of the criteria for fair voting in Arrow's Theorem, the "Independence of Irrelevant Alternatives"-- the idea that if you prefer X over Y, your feelings about some third alterative Z should not change that. There are three other criteria in the theorem. First, "non-dictatorship": no single voter should be able to decide the outcome. Second, "universality": for any set of votes, the system must provide a complete, deterministic ranking of the society's preferences as a whole. Third, "unanimity": if every individual prefers one choice over another, then so must the society as a whole. The theorem then states that if you have at least two voters and at least three options to decide among, it will never be able to meet all of these four fairness criteria. Proving this is a little messy for an audio podcast, but you can see an outline of a proof at the Wikipedia page in the show notes.
As you would expect, Arrow's theorem has led to lots of discussions about how to improve democratic voting. One simple way is to cheat and just relax one of the fairness criteria-- in fact, this has largely been done in practice, as we do have voting systems in many countries, including the United States, that do allow the spoiler effect & violate the independence of irrelevant alternatives. Another method is to always limit votes to two alternatives, since then we can have a 'fair' system according to the Arrow criteria-- but unfortunately if we divide a larger group of alternatives into pairs to try to use this method, then we find the collective choice using these multiple pairwise votes is in effect a larger tournament that is subject to Arrow-like problems. The order of pairing can have a big influence on the ultimate winner. There are also systems not based on rank order, for example 'Range Voting', giving a score to each candidate instead of a simple rank order and adding the populations's total ratings: this has its own problems though, sometimes giving a result close to society's average judgement but disagreeing with the true majority choice.
Some mathematicians have also pointed out that if you drop the assumption of finitely many voters, Arrow's theorem can be fixed, but I think there might be a few other problems if we increased our birth rate to infinity just to fix our voting system. Plus, until they reached voting age, we wouldn't be able to fairly elect a school board to oversee the education of our infinite number of children anyway, so they would not grow up to be informed voters.
All these improved voting systems, or at least the set of them that are actually possible in real life, suffer the disadvantage that they make voting more complicated in general. Given the contentiousness and error rates we have now regarding the simple problem of counting direct votes, I think that is likely a fatal flaw. At some level, we just have to recognize that any system of governance will have its inherent flaws, and that we just need to learn to cope with the fact that life is never 100% fair. And the fact that after every election, advocates for the losing side will come out and declare society fatally flawed, is just one of the prices we pay for the public having some kind of influence on its government-- every fix they advocate will result in some other form of unfairness.
Personally, I still say the best system would be the one I proposed in podcast 172, where we simply admit at some point that the election system is uncertain, and roll a die to help randomly determine the final result, with probabilities determined by the votes counted so far. Or at least, that would be the best stand-in until society gains the wisdom to make me the supreme dictator and king.
And this has been your math mutation for today.