Friday, July 17, 2015

Comparing Sports Legends

When Novak Djokovic beat Roger Federer to win the Wimbledon men’s singles championship on July 12th, he gave his supporters fresh ammunition to argue that he is playing better tennis than anyone in history. It was his 14th victory in his past 21 matches against the Swiss maestro.
Younger fans might presume that only Mr. Federer’s superlative run from 2004-09 could compete with Mr. Djokovic’s dominance. But those with longer memories could make a compelling claim for Rod Laver, who won a record 200 tournaments from 1956-76, or even Bill Tilden, who dominated the 1920s. Mr. Federer’s oft-cited status as the best player ever, and Mr. Djokovic’s as the heir apparent, rest on a widely held but hard-to-prove assumption: because the quality of play has increased so much over time, today’s finest sportsmen must be superior to their predecessors.



Cross-era comparisons are easiest in sports like running, jumping and weightlifting, which are measured in units like time, distance or mass. In general, performance in such contests has improved substantially over the years: the average top-ten finisher in the men’s 100-metre sprint has cut his time from 11.2 seconds in 1900 to just under ten now, and in the marathon from around two hours and 35 minutes in 1939 to two hours and five minutes today. The gains have been greater still in events that require complex equipment or techniques: the current pole-vault world record, at 6.16 metres, is over 50% higher than the best height a century ago.



However, the pace of progress has tended to slow. Most events—with the men’s 100 metres an exception—have settled into a plateau, where new world records are set less often and surpass the old marks by smaller margins. For example, the best men’s 800-metre time has shrunk by a mere 0.82 seconds since 1981, versus almost four seconds in the 26 years before that. And in a few disciplines, improvement has ground to a halt completely. The average times for female short- and middle-distance runners have not budged in 30 years (though some 1980s records by eastern European competitors may have been aided by performance-enhancing drugs). Some “speed limit” is inevitable—humans will never run as fast as an aeroplane, or jump into outer space—and athletes may be approaching it much faster than is widely believed. Mark Denny of Stanford University calculates that most human race times are within 3% of their potential best.



Outside athletics, performance is harder to measure. In bowling, for example, the number of perfect 300 games per year in America rose nearly 40 times during the 30 years to 1999. But connoisseurs attribute much of this to strategically oiled lanes that guide the ball towards its target, rather than any broad-based gain in skill. Golf has demonstrated the opposite pattern: in response to better players wielding better clubs, designers have built longer golf courses with more hazards, such as lakes and bunkers.



Yet even these measurement difficulties pale in comparison with those in interactive sports, in which opponents affect each other. If players improve at the same rate, scoring levels will remain flat. The challenge of comparing players from different eras in games like football—Pelé, Maradona or Messi?—has fuelled many a bar-room brawl. But analysts have devised a few statistical methods to resolve these debates, and estimate how the greats of the past might fare against modern competition.



In a 1985 essay Stephen Jay Gould, a Harvard biologist, proposed using variance among athletes to measure quality of play. If a sport draws on a small population of potential players, mediocre ones will be able to get jobs. Facing inconsistent opposition, the best will produce outstanding results. In contrast, in a sport with a large talent pool, everyone who plays professionally will be reasonably excellent. As a result, the best players will be closer to the average. Gould concluded that the more individual performances in a league differ from each other, the weaker it is likely to be. 



This principle underlies a study by Charles Davis, an Australian researcher. He calculated the standard deviation—a measure of how closely clumped together or spread out players’ performances are—of cricketers’ batting averages in different time periods. He found that variance among batsmen was indeed about 25% lower in 2000 than during the 1930s, when Don Bradman, widely regarded as the sport’s greatest player, was at his peak. However, Bradman exceeded the average of his peers by an unparalleled 4.4 standard deviations, making him a one-in-100,000 outlier. That suggests that he would still be in a class of his own today, though his Test-match average might be in the 70s or 80s rather than his actual 99.94.



Another approach is to look for natural experiments buried within interactive sports. Perhaps the best one can be found in baseball. During World War II, most of the best baseball players were sent off to fight. In order to replenish their rosters, teams had to hire new players. These new players were much worse than the ones they replaced--at the skills they were hired to perform. So the replacement hitters were much worse at hitting than the hitters who went off to war, and the replacement pitchers were much worse at pitching than the pitchers who went off to war.



However, pitchers are only selected for their ability to pitch. They are not selected for their ability to hit. As a result, the replacement pitchers were probably just as good at *hitting* as the pitchers who went off to war were.



This creates a natural experiment. The group of pitchers who played in MLB during the war (the "guinea pigs") were equivalent hitters to the group of pitchers who played in MLB before and after the war. But they were batting against a group of pitchers who were much worse at pitching (the "laggards") than the group of pitchers who played in MLB before and after the war. As a result, we would expect pitchers that played during the war to produce better hitting numbers than pitchers who played before and after the war did, because they were of equal quality as hitters but faced far weaker competition. Sure enough, that's exactly what happened. Pitchers hit about 60% as well as non-pitchers in 1942 and 1946, but 65-66% as well as non-pitchers from 1943-45. This is pretty strong evidence that hitting by pitchers is a good measure of overall quality of play: during the wartime years, when we *know* there was a sharp decline in quality of play, pitchers hit much better than they did in the surrounding seasons.
With the hypothesis that hitting is a good measure of quality of play supported by the war years, we can then zoom out and examine how pitchers have hit during the entirety of baseball history. As the graph shows, their hitting has gotten steadily worse over time. In the early 1870's, when the game was in its infancy, they hit 90% as well as non-pitchers. By 2015, they only hit about 45% as well, a gap of 45 percentage points. That suggests that a league-average hitter in 1871 would hit about 55% as well as an average hitter today.



Next, we apply this method to Babe Ruth. In the 1920's, pitchers hit about 65% as well as non-pitchers. Today, they hit 45% as well. So we can subtract 20 percentage points from Ruth to get an estimate of how well he would perform today. He hit about 45% better than average during his time, so that equates to about 25% better than average today. The best modern players, like Mike Trout or Miguel Cabrera, hit precisely around 25% better than average.



Finally, we can use this measure to estimate an overall effect on wins and losses. A league-average team will by definition win half of its games. If you subtract 20 percentage points of offense--so they score 80% as many runs as average, while allowing an average total--that team would be expected to win about 38% of its games.



Fortunately for fans of Mr. Djokovic, tennis seems to have improved faster than bat-and-ball games. In 2014 Jeff Sackmann, a statistical analyst, examined the performances of players since 1970 who were ranked in the top 50 for two consecutive years. He found that they scored an average of 2.2% fewer return points against other top-50 opponents in the second season than the first, because the players who entered the group in the second year were better than the ones they had replaced. Compounded over 44 years, that pace of improvement suggests that Mr. Laver would struggle to win a single game, let alone a set or match, against Mr. Federer or almost any other modern opponent. And unlike the plateaus seen in many forms of racing, the rate of progress has slowed only modestly to 1.5% in recent years. Even Mr. Djokovic will probably pale in comparison to future talent.

Sunday, March 8, 2015

Wikipedian Philosophy

A common legend on wikipedia is the following: Start on any wikipedia page, and click on the first link not in parenthesis or brackets, and repeat.  The claim is that this always leads to the page philosophy.  Is this true?  If so, why?

First of all, after some testing, I found that some websites didn't go to Philosophy.  Some, like Louisiana Voodoo, have redirect crashes, which messes up the process (If not for that odd hyperlink, that would work too.  My OCD was trying to edit that page.)  But, under running many examples (try xefer.com/wikipedia) I noticed that this worked for around 95% of pages.  (The only way it doesn't go to philosophy is if there is a loop, or a redirect crash.)

Below is an image of some pages leading to philosophy in a graph



Now, that's all good and dandy, but the question is why?  Well, it's a convention that wikipedia articles discuss the category under which the article fits in the first sentence.  And literally everything fall under philosophy.

That reasoning is the generic one offered by wikipedia, but I am not convinced yet.  Why aren't there more loops.  Like rabbit is similar to [[hare]] -> Hare is similar to [[rabbit]].  Why not?

The first person to publicly announce this phenomenon was Randall Munroe, the writer of the webcomic xkcd.  In his 903rd comic (see xkcd.com/903) , Munroe challenged readers to find webpages that don't go to philosophy, leading to more OCDers like me, who removed redirects to make the pattern more oblique, from about 90% to 95% of pages.

But even that is unsatisfying.  WHY???  When I am lost (I don't know about you),  I turn to math.  To those of you that are interested in doing the math yourself, consider wikipedia a random, connected graph, with large minimum degree, and derive the predicted longest path.  After doing this, one finds that it is probable to find a path that has 100%*(1-e^-2) ~ 87% of the vertices, or pages, in the graph.  In other words, it isn't surprising to find a page that has around 87% of the pages leading to it.

For a detailed mathematical explanation: http://math.mit.edu/~cb_lee/resource/mindegree-random-subgraph.pdf

Sunday, March 1, 2015

Yugioh January 2015 Tier List

1.  Shaddoll

This deck has a huge engine, with Shaddoll cards activating after being sent to the grave.  It can be combined with decks like Lightsworn, which have strong beasts but tend to be a bit slow.  Its fusion monsters can be summoned with Shaddoll fusion, which also activates the Shaddoll effects while bringing out major beatsticks like Construct (see above) and they also funnel shaddoll fusions back to hand.

2. Qliphort (Qli)

This deck is the only deck with major pendulum support, automatically bumping Qli up our list as Pendulum is OP and breaks the game.  Pendulum monsters are indestructible, as they never get destroyed, and you can easily summon 5 lv 8+ monsters with pendulum summoning.  Plus, cards like scout (see above) and saqlifice fix pendulum's only disadvantage: getting pendulums to the hand.

3. Burning Abyss


This deck is Mermail 2.0, and its stronger than ever due to Dante's milling abilities (see above) which fuel the rest of the deck.  Cards like Cir or Scarm are stronger versions of their Mermail equivalents, while the Mermail deck is stuck due to the banlist, Burning Abyss is literally on fire (no pun intended.)  As I mentioned with Shaddoll, this can also be used as an engine for other decks, but Shaddoll monsters have slightly better mill effects...

4.  SatellarKnight



SatellarKnight drops from 1st to 4th after the new banlist, but still is incredibly strong, with graveyard funneling like Vega and Altair (see above) which gurantee at least 4 satellarknights on the field per turn.  Combine this with a pretty strong spell support, and you find SatellarKnight can crush opponents pretty fast.

5. Ritual Beast


Ritual Beast monsters really on Contact fusion, or fusion with polymerization, to run their decks.  They can fusion summon a monster, use its effect (like Ulti-Cannahawk above) use its effect, then return the fusion material to the field, and summon another monster endlessly.  This leads to quick OTKs.

Honorable Mention. Dragon Rulers


Dragon Rulers are back ... with the new emphasis on card shifting, Dragon Rulers are used by almost any top player in addition to one of the top decks in order to get some more firepower during the OTKs.  This makes for an ultra-dangerous combo, with cards like El Shaddoll Winda already wrecking enough damage.



Analysis and Counters for top decks:

These top decks are strong basically because they haven't been touched by the banlist as they are being promoed.  Keeping this in mind, there isn't much we can do against them.  But here are 4 counter decks

4. Exodia

This classic is a troll, lengthening duels to piss off cookie cutter opponents who want OTKs.  Cards like Battle Fader buy time, and LP doesn't matter too much as long as you survive the onslaught...

3.  Macro-Rabbit

This deck will defend against decks like Shaddoll, SatellarKnight, and Burning Abyss, which rely on graveyard funneling, punishing them by banishing their cards instead.  This doesn't affect the others as they bounce right back from being banished or even worse, they don't get banished!

2. Special Summon Shut Down

Using cards like the Seal of Orichalcos and vanity's emptiness really slow down opponents decks, shutting down all their options.  The only flaw with this deck is that you have to draw the right cards, which is why this is #2.

1. Grave Banning/ MST

This is probably the best counter against the main decks. Use cards like the End of Anubis, Shadow Imprisoning Mirror, and Necrovalley in order to ban all effects, shutting down the crazy effects of the top decks, and put in cards like Horus of the black flame, which will block all spells (shutting down Qli) or MST, which is more instable (because you need to draw it).  Finally, you can combine this deck with the Orichalcos/Vanity combo, and you've got a great counter deck.  Plus, use decks like Vampires, which benefit from cards sent to grave.

This Banlist is pretty crappy, and I hope it resolves soon.  Personally, my favorite troll deck this season is firekings, as they wreck spec summons (although they don't prevent them from coming back.)  Have fun and don't be a cookie cutter!





Edit: I was only considering OCG decks.  The real banlist would look like this:

1. Nekroz
This deck is INSANELY FAST.  NO OTHER DECK COMES CLOSE TO THIS.  For comparision's sake, it took 90% of the world championship titles recently.  The engine is huge and recycling, posing no issues, and the deck can easily summon huge beatsticks, each with insane effects.  This ritual deck puts pendulum to shame.  THIS IS TIER 0. THE ONLY OTHER DECK TO BE TIER 0 WAS DRAGON RULERS.  (Note: this deck is guarenteed to get hit by the new banlist)

2. Qliphort

Discussed earlier, but Apoqliphort Towers also posses a major threat to decks like Nekroz, which is helpful.

2. Burning Abyss

No, I did not make a mistake, Qliphorts and BA are tied for second.  Both are utterly destructive, and can float the field as well as wipe it.  Both are insane (they pale in comparision to nekroz though.)  Both decks are Tier 1

4. Shaddoll

Discussed earlier, but it is currently at Tier 2

4. Satellarknight, Yosenju

Both of these decks are Tier 2 due to their nice engines and speed, but they aren't ridiculous, which drops them to tier 2.

Saturday, February 28, 2015

Math Problems for Fun

For those of you who like math problems that require more thought than your average competition math problem, check out my new blog: mathaday.blogspot.com

Monday, December 29, 2014

Big Numbers ( I mean REALLY BIG NUMBERS)

Try playing this game at a party:

Two people have index cards and they do the following


You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number—not an infinity—on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature.

Whoever writes the larger number wins.  Of course, the rules don't allow "The number of grains of sand in the Sahara Desert" as that isn't well defined.  After trying this game on multiple people, this is what I found.

Most people attempt the following:

999999999999999999999999999999999999999999999999999999999999999999999999999999999

But what they don't realize is that writing ones takes less time, and therefore one can make the number bigger.  But of course, this is squashed by the clever kid who writes the following:

9999999999999999999999999999999999999999999999999999999999^9999999999999999999999

But even this is quite small, as one can do the following:

9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9

which completely squashes the one before.  (Note: after I told someone about how 1's are easier to write, and the 9^9^9... strategy, she tried the following

1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1^1)

Place value, multiplication, exponentials, etc... can all express the same numbers.  But it is how concisely they are that makes them different.  The key to the biggest number contest is not swift penmanship, but rather a potent paradigm for concisely capturing the gargantuan.

Humankind is naturally curious about larger, bigger, etc..., the stars in the sky, the sand grains in the desert, etc..., and we find a whole new dimension of numbers arises with a revolution within the numerical system.  Originally, there was I, II, III, IV, V, ... within the Roman numeral system, but as time came, things besides addition came to importance, such as multiplication, which completely invalidated the usage of Roman numerals in favor of the Arabic denumeration.  And so we find that the evolution of these big numbers comes with major revolutions in not just mathematics but the world, with the enlightenment after the scientific revolution being a prime example.  Big numbers mark a major step in human progress.

Large numbers make previously large things not too large.  For example, in ancient times, the number of grains of sand in a desert was used as an example of ginormous amount. Historian Ilan Vardi cites the ancient Greek term sand-hundred, colloquially meaning zillion; as well as a passage from Pindar’s Olympic Ode II asserting that "sand escapes counting."  However, with the advancement of  
exponentiation with Archimedes, such a number didn't look too large.  As Archimedes put it, the number of grains of sand needed to cover the universe only needs 4 characters to write: 10^63 (he didn't count the carrot.)

However, the reverse is also true within large numbers: numbers that are seemingly small within a more potent paradigm may be actually gargantuan.  Consider, for example, the oft-repeated legend of the Grand Vizier in Persia who invented chess. The King, so the legend goes, was delighted with the new game, and invited the Vizier to name his own reward. The Vizier replied that, being a modest man, he desired only one grain of wheat on the first square of a chessboard, two grains on the second, four on the third, and so on, with twice as many grains on each square as on the last. The innumerate King agreed, not realizing that the total number of grains on all 64 squares would be 2^64-1, or 18.6 quintillion—equivalent to the world’s present wheat production for 150 years.

Returning to our bigger number contest, are exponentials the best we can do?  It seems as so humans never came to develop a better encoding scheme until the twentieth century, when the forefathers of computer science developed a much stronger paradigm.  These people, called formalists, wished to rigorify the axioms of mathematics, and one key area of interest was the definition of "computable."  For most until then, primitive recusiveness defined computability, or in other words, being able to compute within a 'reasonable' amount of time.  However in 1928, Wilhelm Ackermann showed the flaw in this definition through a function that was clearly computable, but exhaustively so.  The annoyingly recursive rules for his function went as so:

A(m,n) = 

Case 1: m = 0 => n+1
Case 2: m>0 and n = 0 => A(m-1, 1)
Case 3: m>0 and n>0 => A(m-1, A(m, n-1))

And this function usually scales as the following

A(1) = 1+1
A(2) = 2*2*2
A(3) = 3^3^3^3
etc...

And Ackermann proved that no matter what whole number inputs are given for m and n, the function will eventually give a answer, albeit after a LONG time.  Wielding the Ackermann sequence, we can clobber unschooled opponents in the biggest-number contest.  Just for the fun of it, I recommend writing the following on your sheet of paper:

Ackermann(Ackermann(googolplex, googleplex),Ackermann(googolplex, googolplex))  ;)


Ackermann numbers are pretty big, but they’re not yet big enough. The quest for still bigger numbers takes us back to the formalists. After Ackermann demonstrated that ‘primitive recursive’ isn’t what we mean by ‘computable,’ the question still stood: what do we mean by ‘computable’? In 1936, Alonzo Church and Alan Turing independently answered this question. While Church answered using a logical formalism called the lambda calculus, Turing answered using an idealized computing machine—the Turing machine—that, in essence, is equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world. Turing’s paper describing his machine, "On Computable Numbers," is rightly celebrated as the founding document of computer science.
"Computing," said Turing,
is normally done by writing certain symbols on paper. We may suppose this paper to be divided into squares like a child’s arithmetic book. In elementary arithmetic the 2-dimensional character of the paper is sometimes used. But such use is always avoidable, and I think it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, on a tape divided into squares.
Turing continued to explicate his machine using ingenious reasoning from first principles. The tape, said Turing, extends infinitely in both directions, since a theoretical machine ought not be constrained by physical limits on resources. Furthermore, there’s a symbol written on each square of the tape, like the ‘1’s and ‘0’s in a modern computer’s memory. But how are the symbols manipulated? Well, there’s a ‘tape head’ moving back and forth along the tape, examining one square at a time, writing and erasing symbols according to definite rules. The rules are the tape head’s program: change them, and you change what the tape head does.
Turing’s august insight was that we can program the tape head to carry out any computation. Turing machines can add, multiply, extract cube roots, sort, search, spell-check, parse, play Tic-Tac-Toe, list the Ackermann sequence. If we represented keyboard input, monitor output, and so forth as symbols on the tape, we could even run Windows on a Turing machine. But there’s a problem. Set a tape head loose on a sequence of symbols, and it might stop eventually, or it might run forever—like the fabled programmer who gets stuck in the shower because the instructions on the shampoo bottle read "lather, rinse, repeat." If the machine’s going to run forever, it’d be nice to know this in advance, so that we don’t spend an eternity waiting for it to finish. But how can we determine, in a finite amount of time, whether something will go on endlessly? If you bet a friend that your watch will never stop ticking, when could you declare victory? But maybe there’s some ingenious program that can examine other programs and tell us, infallibly, whether they’ll ever stop running. We just haven’t thought of it yet.

Nope, Turing proved that the halting problem, as it is called, is uncomputable, by a stunning example of self reference.  One can write the following program:

If this program halts, run forever, else halt.

And this contradiction proves the halting problem's uncomputability.  

What does this have to do with big numbers?  Well, Tibor Rado published an article about the biggest numbers anyone had every heard of.

His idea was the following.  He defined the function busy beaver(n) to be the maximum number of steps a program of length n on our Turing tape can go on while still halting.  Now lets suppose this halts.  If we want to see if a random program halts, we wait until it crosses BB(n) steps, and then conclude it doesn't halt, which makes the halting problem computable; a contradiction.  Therefore, BB(n) is uncomputable.  And more than this, lets suppose we have a function D(n) that is larger than BB(n) for every n and is computable.  Then, we can have a program that takes D(n), and checks every number from it down to see if it is BB(n), and therefore we have a way to compute BB(n), which is a contradiction.  Therefore, BB(n) grows faster than ANY computable function.  Now this beast can knock out Ackermann or any other function that comes upon the way.

What if your friend knows about BB(n).  Well, lets supposed we have control of some Oracle which can figure out whether any program halts.  If we use the same method of constructing the BB numbers except on Oracle computers, we will get BB lv 2 numbers, which are uncomputable even by the Oracle.  And we can construct another oracle for oracles, etc... the construct a list of continually more potent BB numbers.  Now you got your friend beat.

Will we ever upgrade from this Busy Beaver mess to something greater? Its hard to see how, but then again, no one was able to predict anything would beat

9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9.

You might wonder why we can’t transcend the whole parade of paradigms, and name numbers by a system that encompasses and surpasses them all. Suppose you wrote the following in the biggest number contest:

The biggest whole number nameable with 1,000 characters of English text

Surely this number exists. Using 1,000 characters, we can name only finitely many numbers, and among these numbers there has to be a biggest. And yet we’ve made no reference to how the number’s named. The English text could invoke Ackermann numbers, or Busy Beavers, or higher-level Busy Beavers, or even some yet more sweeping concept that nobody’s thought of yet. So unless our opponent uses the same ploy, we’ve got him licked. What a brilliant idea! Why didn’t we think of this earlier?

Unfortunately it doesn’t work. We might as well have written
One plus the biggest whole number nameable with 1,000 characters of English text
This number takes at least 1,001 characters to name. Yet we’ve just named it with only 80 characters! Like a snake that swallows itself whole, our colossal number dissolves in a tumult of contradiction. What gives?

The paradox I’ve just described was first published by Bertrand Russell, who attributed it to a librarian named G. G. Berry. The Berry Paradox arises not from mathematics, but from the ambiguity inherent in the English language. There’s no surefire way to convert an English phrase into the number it names (or to decide whether it names a number at all), which is why I invoked a "reasonable modern mathematician" in the rules for the biggest number contest. To circumvent the Berry Paradox, we need to name numbers using a precise, mathematical notational system, such as Turing machines—which is exactly the idea behind the Busy Beaver sequence. So in short, there’s no wily language trick by which to surpass Archimedes, Ackermann, Turing, and Rado, no royal road to big numbers.


You might also wonder why we can’t use infinity in the contest. The answer is, for the same reason why we can’t use a rocket car in a bike race. Infinity is fascinating and elegant, but it’s not a whole number. Nor can we ‘subtract from infinity’ to yield a whole number. Infinity minus 17 is still infinity, whereas infinity minus infinity is undefined: it could be 0, 38, or even infinity again. Actually I should speak of infinities, plural. For in the late nineteenth century, Georg Cantor proved that there are different levels of infinity: for example, the infinity of points on a line is greater than the infinity of whole numbers. What’s more, just as there’s no biggest number, so too is there no biggest infinity. But the quest for big infinities is more abstruse than the quest for big numbers. And it involves, not a succession of paradigms, but essentially one: Cantor’s.


So here we are, at the frontier of big numbers, and if you try to tell your artist friend about this, they might say, "Who cares?" And in this case, it is a quite reasonable question, as there seems to be no application.  I have a couple answers to this.

1.  Big numbers, as mentioned before, spark revolutions.  For example, the use of scientific notation to write big numbers sparked the enlightenment, which led to the European imperialistic period.

2.  We see the effects of these big numbers today.  Without the study of big numbers, we may not have trespassed upon the axioms of mathematics, revolutionizing math and creating computer science, something that we all value today.

3. We must remember that math's value doesn't lie within its application.  Albert Einstein, a famous physicist, once remarked, "Pure mathematics is, in its own way, a poetry of logic," something your artist friend would appreciate. 

Wednesday, November 26, 2014

The Banach Tarski Paradox for dummies

The Banach Tarski Paradox is a historically significant paradox that shows that it is possible to take a ball, break it into pieces, and rearrange the pieces in order to form two new balls, therefore doubling the mass and volume.  (Note: the following is a sketch of the proof, it has many untied ends and is NOT airtight)(knowledge of sets, and countability are assummed.  Learn more at : http://en.wikipedia.org/wiki/Set_%28mathematics%29 and http://en.wikipedia.org/wiki/Countable_set)

We will prove this in 6 simple steps:

Step 1:  Background

The set F2 is the set of all simplified "words" of a and b.  In simpler terms, it is all combinations of a, a^-1 (which for simplicity of typing, I will call -a) b, b^-1.  A sample word looks like the following

                                                          a, b, b, -a, -b, -a, b 

Now, whenever one has an 'a' and a negative 'a' next to each other, they cancel, and the same goes for b and -b.  So, F2 doesn't include:

                                        -a, a, b, b            but it does include                 b, b
We also define S(x) as the subset of F2 that starts with x.

A good way to visualize this is the diagram below, where every word is defined as a point; to get to that point, one has to take the appropriate moves, where a is right, b is up, etc, and e is the empty word:

Therefore, S(a) is represented by the green circle, S(-a) by the red circle (the gaps in the circles were due to size limits in blogger uploads) , but how does aS(-a) represent the blue circle?  First of all, aS(x) = all strings that start with x with an 'a' concatenated in front.  We know that whenever we concatenate the 'a' with a word that starts with '-a', they cancel, and we get a word that starts with any letter except 'a', as if 'a' started our new word, that means our original word was -a, a, ..., which isn't simplified.  Therefore

                                                                 F2 - S(a) = aS(-a)

Also note:  b, b, b, b, b = b5 (5 equals number of repetitions)

We define the following:

W = S(a)                 X = S(-a)                     Y=S(b)         Z = S(-b)

The reason we defined the sets the following way was to get the following properties:

if x ϵ W, then ax ϵ W , and this holds for X with -a, Y with b, and Z with -b.

Also, the union of all 4 sets is F2-{empty}, and they have no elements in common.

WE ARE ALMOST DONE WITH THE BACKGROUND.  DON'T GIVE UP!

Two sets are "equidecomposable" (symbol: ~) if you can take one set, cut it into pieces, move them around and rotate them (no dilations, inversions, etc, otherwise the size of the pieces is changed) and get the other, as shown below:

For those of you with a greater mathematical background (I don't know why you are reading this then), this notion is an equivalence class.  Challenge yourself to prove that it is.

We are finally ready to actually begin the paradox.

Step 2: Prove that a "broken circle" ~ a circle

A broken circle is a circle with a missing point on the circumference, without loss of generality call it D.  We take the circle and "cut" it into two pieces

A = {All points that can be reached by taking point D and rotating it by rotation r x times}

A will look like this {D, Dr, Dr2, Dr3, etc.} (Note: this can be expressed as e^i* theta, but the r notation conveys the same result)

B = {All points on the circle that aren't in A}

If we rotate set A by r, all the elements of A are multiplied by r, as shown below

rA = {Dr, Dr2, Dr3, etc...}

We want to make sure that for any n and m > 0, Drn is not equal to Drm.  We can do so with the following argument:

There are a countable number of m's and n's that result in Drn = Drm.  However, there are an uncountable number of angles possible for rotation.  Therefore, there exists a rotation for which no rn = rm.

Therefore, by rotating A by r and keeping B the same, a point disappeared on the circle: D.

Step 3: A circle ~ A circle missing a countable number of points

We start with the circle.  We use Step two in order to remove a countable number of points by taking out one point at a time.  We must make sure that none of points in our procedure overlap.  We will do so with the following argument:

The number of points needed to remove 1 point using the procedure in Step 2 is countable.  The number of points removed is countable.  So, we know by the fact that the union of countably many sets is countable (For those of you who are bothered by my usage of the axiom of countable choice, the ride only gets rougher.  I suggest stopping now.) that the number of points that we have to guarantee don't overlap is countable. But the number of rotations is uncountable, therefore we can find a "good" angle to rotate by which satisfies all our demands.

Step 4: A sphere ~ A sphere missing countably many points

We use the same method as in Step 3 but we now rotate along an axis of the sphere

Step 5: A ball missing its center ~ 2 balls missing their centers (notice how the steps are progressively getting shorter.)

Theorem: rotations of a ball act like elements of F2

So, we can define W, X, Y, and Z as we did before, however a and b are now rotations, and -a and -b are their inverses.  If we rotate X by a and make it aX, we find the following

F2 - S(a) = aS(-a)   =>  F2 - W = aX  => F2 = W ∪ aX, and since a is a rotation, we know that those two pieces create a ball, as F2 is the entire ball.  We can use the same logic on Y and Z and say that they make a ball too.  We must do this ignoring the centers of each ball as the union of the W, X, Y, and Z doesn't include the center.

Step 6: Ball ~ 2 Balls

By Step two, we can insert a point into each ball.




Monday, October 6, 2014

How powerful is most powerful computer possible?

(Note:  this article requires a knowledge of algebra)

As our computer's get faster and smaller, the obvious question to ask is, "How far can our computers go?"  To understand the answer to this problem, we must understand what limits the power of the idealistic computer.  The limits on our computer are the mass/energy of the system, Heisenberg's Uncertainty Principle, and the speed of light travelling through the device.

The formula for the uncertainty principle and energy mass equivalence (to convert between mass and energy) is as follows

  ∆E*∆t ≥  h/4π and E^2=m^2* c^4+ p^2*c^2
   
 We know that to maximize the energy of the system, we want to have our computer flying around at as close to the speed of light as possible, so we can just change the equation to an inequality, and since p = mass * velocity, we have velocity = c

E^2<2* m^2* c^4

We plug in this value into the uncertainty formula

∆t ≥  h/(4π* √2*m*c^2 )

Now, we also must remember to time, we must add the time it takes to send information from one side to the other.  If we call the length of the computer L, we find the additional time to be L/c.  Can L be as small as we want?  Well, if the length get too small, we will get a black hole, and to calculate when this will happen, we use the Chandrashekar limit.

L > GM / c2

Divide both sides by c to get the additional time.

L/c > GM / c^3

We add this to our time equation

∆t ≥  h/(4π* √2*m*c^2 ) + GM / c^3

We want to minimize this, so we take the derivative of this function to find where the slope of the function is zero, which will be the minimum time.  (Note:  since we want the ideal machine, we will change the inequality to an equality, which will make this an approximation.)

d∆t/dm =  -h/(4π* √2*m^2*c^2 ) + G / c^3

h/(4π* √2*m^2*c^2 ) = G / c^3

(h * c^3) / (G * 4π* √2*c^2) = (hc)/(G * 4π* √2) ~ 1.6748505 * 10 ^-16
Therefore, the maximum bits per second computable is one over our answer, which is 

6.0* 10 ^15 bits per second

So, how long would it take to "solve" chess with our ideal computer?  An article by chess.com 
(read here: http://www.chess.com/blog/watcha/limits-of-quantum-computing-in-solving-chess)
has suggested that it would take up to 10^42 bits, so to find the amount of time it takes for our 
computer to find the answer, we divide the bits by the rate

10^42 bits / 6.0 * 10 ^ 15 bits per second = 1.7 * 10 ^ 26 seconds, which to put in perspective,
the age of the universe is 4.35 +- .02* 10^17 according to most scientists.  Our best computer 
actually isn't all that fast.