The Lumber Room

"Consign them to dust and damp by way of preserving them"

Archive for June 2010

Convex, continuous, Jensen’s

with 3 comments

On the principle that things I’ve forgotten at least thrice are worth remembering…

A convex function (need a mnemonic?) is f such that
\displaystyle f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y) for any λ in [0,1].

Midpoint convex (almost) implies convex
A natural question is whether we need all λ in [0,1]; what about just ½? Functions which satisfy
\displaystyle f(\frac{x+y}{2}) \le \frac{f(x)+f(y)}{2}
are called midpoint convex.

It turns out that when things are “nice” as in most frequently encountered cases, a midpoint convex function is convex. (A counterexample is this crazy non-measurable nowhere-continuous bounded-in-no-interval function: since R is a vectorspace over Q, there is a basis (that includes π, say), and any real number x has a unique representation as a finite rational sum of basis elements. Define f(x) to be the coefficient of π in the representation of x. This function is in fact linear over Q.)
For midpoint convex to mean convex, any of the following conditions will do:

  • f is continuous [Proof: prove the inequality for λ with denominators that are powers of 2, then use denseness in R.]
  • f is continuous at some point (any one point will do) [Proof: see next section]
  • f is (Lebesgue) measurable
  • f is bounded on some measurable set with positive measure

Convex functions are continuous
In fact, a stronger theorem is true: If a midpoint convex function is discontinuous at a single point, then it is unbounded on every interval and (hence) discontinuous everywhere.
Proof: Suppose wlog that f is discontinuous at 0, that f(0)=0, and that a sequence x_n \rightarrow 0 has f(x_n) \rightarrow m for some positive m. Prove that \liminf f(2^k x_n) \ge 2^k m, so f is unbounded near 0. Then use this to show unbounded everywhere.

Note that convex functions are bounded on every interval, so by above theorem they are continuous.

Convex functions are differentiable almost everywhere
In fact a convex function has left and right derivatives at all points, these are monotonically increasing, and there are only countably many points where they don’t coincide.

All the above is from pages 10 to 16 of this book I had found through googling; if anyone’s reading this, please tell me if you know better proofs.

A proof of Jensen’s inequality
Here, Jensen’s inequality is the statement that for a convex function f,
\displaystyle \mathbb{E}\left[f(X)\right] \geq f\left(\mathbb{E}\left[X\right]\right) .

An equivalent definition of a convex function is that at any point we can find a line through the point that lies entirely below the function. (Why?) In other words, for any point a, there is a “slope” m such that
\displaystyle f(x) \ge f(a) + m(x-a) for all x.
With this definition, Jensen’s inequality has an absurdly short proof: take a to be the mean \mathbb{E}\left[X\right], then take expectation.

Written by S

Tue, 2010-06-29 at 02:32:05 +05:30

Posted in mathematics

Examples of bad design

with 12 comments

Design is hard. Don Norman, author of the wonderful book The Design of Everyday Things (written in 1988 and still a classic!) asked a question in the first five minutes of a recent talk:

Imagine you’re on the first slide of your powerpoint presentation and want to move to the next slide. Your remote control has two buttons. They are unmarked, but one button points up and one button points down.

Which button do you press?

It turns out that half the people would press up, half the people would press down, and everybody thinks their choice is obvious.

Even in cases where most of us get it right (like elevators), some are still confused. So it is easy to make mistakes, especially when designing the interface to a complex system. But it takes a special genius to take something simple and make it confusing:

Buttons with adjacent descriptions

Do the arrows describe the buttons beside them?

(from Stack Overflow.)

Written by S

Tue, 2010-06-29 at 01:03:27 +05:30

Posted in Uncategorized

Randomness and reality

with 5 comments

We know the arXiv (pronounced “archive”) — it has scientific papers. The snarXiv is a hilarious parody, which randomly generates titles and abstracts that look like papers in high-energy physics. The generator is surprisingly sophisticated; you can play arXiv vs. snarXiv to see if you can distinguish fake titles from the real thing. I started off well but could manage only ≈70% accuracy after 30 guesses. (Although I don’t know anything about high-energy physics, I vaguely know a little mathematical terminology, and tried guessing based on heuristics like “this is too weird to be generated by the grammar” — and failed.) You can read his About page for details. (“Sug­gested Uses for the snarXiv: [..] If you’re a grad­u­ate stu­dent, gloomily read through the abstracts, think­ing to your­self that you don’t under­stand papers on the real arXiv any better. If you’re a post-doc, reload until you find some­thing to work on.”)

(via)

He also has a random theorem generator that generates “theorems” that look very real. (With typical proofs, too.) You may also remember SCIGEN, which generates random computer-science papers, including one that was accepted by a bogus conference. There’s also a brilliant Postmodernism generator (reload to get a new essay as good as “real”), and one for teenage poetry.

All this must remind some people of the Sokal affair, a brilliant hoax perpetrated by physics professor Alan Sokal who submitted a meaningless essay on science to the leading postmodern journal Social Text — it was accepted, demonstrating that they would “publish an article consisting of utter nonsense if (a) it sounded good and (b) it flattered the editors’ ideological preconceptions”. There is a crucial difference — while the earlier examples quoted here (except possibly the postmodernism and poetry generators) show that non-experts cannot distinguish the real from the randomly generated, Sokal showed that the so-called “experts” in postmodernism aren’t very discriminating either.
His paper included such wonderful gems, hilarious nonsense to any mathematician and clearly far-fetched to even a non-mathematical reader, as:

Just as liberal feminists are frequently content with a minimal agenda of legal and social equality for women and ‘pro-choice’, so liberal (and even some socialist) mathematicians are often content to work within the hegemonic Zermelo-Fraenkel framework (which, reflecting its nineteenth-century liberal origins, already incorporates the axiom of equality) supplemented only by the axiom of choice.

He also pleased the editors by claiming that Lacan’s gibberish was proved by quantum theory, and Derrida’s nonsense by general relativity. In fact the entire paper is essentially an exercise in “glueing together, without any logic, quotes from several famous French and American intellectuals who make quite ignorant statements about physics or mathematics, with, however, great self-confidence”.

You can read the Wikipedia article, or Martin Gardner’s essay Alan Sokal’s Hilarious Hoax, to see the kind of bullshit that passes for “scholarship” in post-modernism today. It does get hard to believe. Not only did Lacan (a leading name in postmodernism) famously and meaninglessly say, in the same essay:

Thus the erectile organ comes to symbolize the place of jouissance, not in itself, or even in the form of an image, but as a part lacking in the desired image: that is why it is equivalent to the square root of –1 of the signification produced above, of the jouissance that it restores by the coefficient of its statement to the function of lack of signifier (–1).

and also that “a torus … is exactly the structure of the neurotic”, but, when asked about it and given a way out with the suggestion that perhaps it was an analogy, he insisted:

This torus really exists and it is exactly the structure of the neurotic. It is not an analogon; it is not even an abstraction, because an abstraction is some sort of diminution of reality

and so on. (Even after all this was torn apart by Sokal and his coauthor in their later book Intellectual Impostures/Fashionable Nonsense, some postmodernists insist… Why, even after Sokal’s paper was revealed to be a hoax, the journal’s editors insisted that it didn’t matter at all; the paper was still “valuable” as a “symptomatic document”.)

Why does this all matter? If these people get off by pushing senseless words around, why not ignore them and let them have their fun? Well, that’s what we do in practice, but there are serious consequences beyond the fact that they are paid to spew garbage: “the problem is not only that a few individuals go out of their way when they talk about science, but that their cultural environment (commentators and journalists) tolerates and even encourages this sloppy way of thinking”, and one of their goals is to undermine science (not merely to highlight the social and cultural context), and deny that anything such as objective truth exists. [Sokal points out: "Anyone who believes that the laws of physics are mere social conventions is invited to try transgressing those conventions from the windows of my apartment. (I live on the twenty-first floor)."] The feminist “philosopher” Luce Irigaray believes, for example, that E=mc2 is sexist (her phrase: “sexed equation”). Why? Because the equation

privileges the speed of light over other speeds that are vitally necessary to us. What seems to me to indicate the possibly sexed nature of the equation is not directly its uses by nuclear weapons, rather its having privileged what goes the fastest…

… Let her try replacing it with her preferred speeds? She also claims that the reason we have not been able to develop fluid mechanics as much as solid mechanics is because science is masculinist. You can read more such delightful (or infuriating) babble along with the authors’ observations in their book, or this review, or this review, or this review, etc.

So much for postmodern theories of science. There is, of course, no reason to believe that postmodernist theories elsewhere stand on any better foundation, beyond the fact that “postmodern” is mostly a meaningless word thrown around to let one get away with empty “discourses”. Although some of the reviews are written optimistically, with titles like “Farewell to a Fad”, it’s not clear that idiocy is going away. For a great post on “post-modern” literature, see Postmodernism and its discontents – a heretic speaks up!.


More examples in the comments below. [Note: If you got some garbled draft in your feed reader, sorry, it's because of WordPress #@$#! access keys that steal Ctrl-P to mean "Publish". To disable it I use a modification of this script, but it needs Greasemonkey.]

Written by S

Sat, 2010-06-19 at 23:59:58 +05:30

Posted in funny

Unwilling translators

with one comment

Besides the Mahabharata’s translation into Old Javanese (and other Southeast Asian languages) in the 10th/11th century, the first translation into a non-Indian language was into Persian, commissioned by Akbar in 1591.

The translator, Badāyūnī or Badāōnī, relates how it came to be:

The following considerations disposed the emperor to the work. When he had heard the Shāhnāmah, and the story of Āmīr Ḥamzah, in seventeen volumes transcribed in fifteen years, and had spent much gold illuminating it, he also heard the story of Abu Muslim, and the Jāmi’-ul-hikāyat repeated, and it suddenly came into his mind that most of these books were nothing but poetry and fiction; but that, since they were first related in a lucky hour, and when their star was in the act of passing over the sky, they obtained great fame. But now he ordered those Hindu books, which holy and staid sages had written, and which were all clear and convincing proofs and the pivot on which all their religion, and faith, and holiness turned, to be translated from the Indian into the Persian language, and thought to himself, “Why should I not have them done in my name? For they are by no means trite, but quite fresh, and they will produce all kinds of fruits of felicity both temporal and spiritual, and will be the cause of circumstance and pomp, and will ensure an abundance of children and wealth as is written in the preface of these books.”

So apparently, Akbar thought they (Hindu books) were more than mere poetry and fiction, and yet fresh, and he even believed (essentially) the phalashruti told in the books.

But the translator Badāōnī himself, an orthodox Mullā, doesn’t seem to have agreed with his emperor, or liked the job:

The Emperor sent for me and desired me to translate The Mahābhārata, in conjunction with Nāqib Khān. [...] The consequence was that in three or four months I translated two out of eighteen sections, at the puerile absurdities of which the eighteen thousand creations may well be amazed.

<!–(The sections are parvas. The “18000 creations” is a Muslim belief, and unconnected with the recurrence of the number 18 in the Mahābhārata.)–>
Besides finding sections full of “puerile absurdities”, he also found sections objectionable and disturbing to his Muslim sentiments. It led him to complain:

But such is my fate, to be employed on such works. Nevertheless, I console myself with the reflection that what is predestined must come to pass.

Akbar seems to have been merely amused by this reaction:

We thought that [Badāōnī] was an unworldly individual of Ṣūfī tendencies, but he seems to be such a bigoted lawyer that no sword can sever the jugular vein of his bigotry.

The rest of the translation had to be completed by others.

Written by S

Fri, 2010-06-11 at 23:53:55 +05:30

Posted in funny, literature

Tagged with ,

Don’t mess with a genius

with 7 comments

Or: What happens when Newton’s laws are violated

Recently, I read a book called Newton and the Counterfeiter, subtitled The Unknown Detective Career of the World’s Greatest Scientist. It focuses on an awesome phase of Isaac Newton’s later career that, like his pursuits in alchemy, gets little mention in most accounts. The story, of Newton’s job as Warden of the Mint and his efforts bringing criminals to justice, contains many elements of a modern crime thriller: including an ingenious arch-adversary, Newton visiting the gin houses of London in disguise, personally interrogating suspects, playing good cop–bad cop, and using every trick in the book, before the book had been written. The story begins, as many of them do, at the beginning.

The beginning

Isaac Newton, 55 years old and just recovered from his nervous breakdown, was looking for a post in the city (London), having lived in the village of Cambridge ever since his student days. As a Great Man now, he had already been rewarded with a seat in parliament (the only thing ever recorded spoken by him is a request to close the window), but it appeared harder to get him a job. Finally, his friends pulled the right strings, and Newton moved in as Warden of the Mint in 1696.

The job was meant to be a sinecure (he had been promised that the position “has not too much business to require more attendance than you may spare”), and no one expected him to do anything special. Today though, we can look back and confidently say that Newton is the greatest Warden the Mint ever had. Unfortunately, this is not saying much, because it appears Newton is also the only good Warden the Mint ever had.

The Mint

The Royal Mint at the time had two officials in charge, both appointed by the king and with no well-defined hierarchy between them. The Warden of the Mint, with a salary of 400-odd pounds a year, was in charge of the Mint’s facilities, and the Master of the Mint, with a salary of 600 pounds a year plus (more substantial) a percentage of every coin made, was in charge of the actual production of new coins.

When Newton moved in as Warden, the Master was the notoriously corrupt and incompetent Thomas Neale, who was so lost in his gambling habit and his numerous enterprises that the operations of the Mint were, well, not in mint condition.

This was a bad time, because counterfeiting, clipping, and arbitrage had weakened the economy to the extent that there was a shortage of cash everywhere, most tax payments and trade had stopped, panic was rising, and civil war was imminent.

Counterfeiters

Counterfeiting was easy money, and everyone took to it. The government declared it high treason, a hanging offence, but this only made juries more reluctant to hang their peers. Of those counterfeiters who were brought to trial, many escaped conviction, even one of them through a wonderful incompetence defence:

[I]nept counterfeiters attempting to exploit the currency crisis supplied the Old Bailey with a constant diet of rapidly dispatched defendants. Perhaps the most spectacular display of incompetence came from an unnamed “inhabitant of the parish of St. Andrews Holbourn,” brought to trial accused of copying French coins. His work was astonishingly awful, and he was acquitted, the jury accepting his rather bold argument that the poor quality of his work confirmed that “he had tryed to Coin with Pewter as aforesaid for Diversion, or the like, but never was concerned in Coining any manner of Money.” Few others tried this defense.

The Great Recoinage: Newton takes over

Faced with no alternative, the government had decided that the Mint would recoin everything — the Great Recoinage was to take place. It aimed to melt and restrike, in three years, more coins than it had produced in three decades. How anyone expected it to happen with Neale in charge of it is a mystery. As the recoinage began, it quickly turned into a farce, and it was clear to everyone that it would be an impossible task.

Newton saw what was happening, and couldn’t stand it. He read up on the history of the Mint, studied its operations, studied Neale, accumulated all the knowledge necessary, and somehow intimidated and pushed Neale aside in a bloodless coup, and took over the Great Recoinage himself. He streamlined the production, conducting probably one of the earliest “time-and-motion studies” (he synchronized workers’ operations to the rate of their heartbeat), running the mint from 4am to midnight, and finished the “clearly impossible task” ahead of schedule.

Warden duty

Newton's unusual coat of arms

After saving the country from economic ruin, by doing something that wasn’t even his own job, Newton finally turned to a duty that his post actually came with — protecting the currency, by “enforcing the King’s law in and around London for all crimes committed against the currency”. This meant doing a policeman’s work — or rather, that of “a criminal investigator, interrogator, and prosecutor rolled into one”. He found the idea distasteful, not to mention the kind of men he would have to come in contact with, and requested that this be assigned to someone else, but when his request was denied he turned to the task in all seriousness.

Despite having hardly been a man of the world until then, he very quickly figured out what he had to do, better than anyone else had done. (In the mere four years he was Warden, he got dozens of counterfeiters hanged.)

He descended into the underworld … hiring men to go undercover, interrogating suspects, planting informers in prisons, the works. To avoid issues of jurisdiction he got himself appointed Justice of the Peace for nineteen counties surrounding London. Most criminals (one is almost tempted to say victims) were entirely unprepared against this kind of systematic prosecution, “utterly unprepared to do battle with the most disciplined mind in Europe”.

Except one.

Arch-nemesis

William Chaloner, counterfeiter, confidence trickster, and various things besides, the ingenious man who would one day challenge Sir Isaac Newton, had started small. He had set out from home — or had been thrown out — as a youth to apprentice under a nail-maker, where he learnt the basics of counterfeiting instead. Arriving in London with its oppressively exclusionary guild system, he somehow managed to survive, going through a series of professions including being a quack doctor, progressing to fortune teller, and then becoming a locator of stolen goods, at which he succeeded through the infallible trick of being the one to have stolen them in the first place.

[One of his most heinous sources of money was the following. Jacobite sedition—supporting the return of the deposed King James, over the reigning William of Orange—was treason and punishable with death, and there was a reward for those who gave up seditioners to the king. Chaloner tricked various printers into printing Jacobite propaganda, then used that as evidence to turn them in to be hanged, and claim his reward.]

Finally he turned to his true calling, that of counterfeiting. After coining a great deal of money (he once claimed to have produced more than thirty thousand pounds in his life, about four million pounds in today’s money) and getting caught a couple of times — once escaping conviction by turning informer, and the other time by coming up, along with his co-accused, with such a delightfully tangled mess of accusations and cross-accusations that everyone was let go out of confusion — he began to look for more safer avenues. He realised that for a man of his skill, making good counterfeit coins wasn’t the problem; having it untraceable back to him was. In an audacious plan, he realised that the safest place from which to pass his money was the Mint itself, and resolved to get into it.

He printed a couple of pamphlets giving advice to the government on how to prevent counterfeiting — here his expertise was all too evident — and even once gave a speech in parliament. Newton ignored him at first and denied him entry even to look at the machines in the mint, until Chaloner lost patience and decided to attack the man himself. (He alleged that the mint was making side money by participating in counterfeiting itself. The worst part was, some of these accusations were true: some dies had disappeared from the mint. Newton was put on trial and forced to defend himself, and nearly lost his job.)

Big mistake.

Newton was finally annoyed, and made it his goal to destroy him. Over the next two years, he devoted much of his life to ruining Chaloner’s. With customary ruthlessness, he set about accumulating evidence and witnesses. By now Chaloner was in custody again — bank notes and a Malt Lottery had just come into existence, and of course he counterfeited them — so he was out of the way. Newton got spies and informers planted in all the right places, he tracked down old contacts of Chaloner — friends, female coiners he’d had affairs with, wives of former associates — and subpoenaed (or just intimidated) them into giving testimony, anticipated who would try to flee to Scotland when, and prepared an impenetrable web of evidence. It is more complicated than that, and Chaloner still did his best from behind bars and the whole cat-and-mouse game has more details than I have any remaining patience to go into now :-), but you can read about them in the book. Chaloner was brought to trial. He tried every defence in succession, from pleading innocence to madness to pointing out (validly) that he was being tried by a Middlesex jury for crimes committed in London. He was convicted nevertheless, and after Newton ignored all the piteous mercy petitions he wrote, was hanged, drawn and quartered.

Newton’s later years

In 1699 the worthless Neale finally died, and Newton became Master of the Mint on Christmas Day, his 57th birthday. The responsibilities of the job had already been de facto handled by Newton for years, but Neale had gained all the proceeds from the coining — 22,000 pounds. Newton now became the only recorded Warden to become Master. Although the Great Recoinage was over, the Mint still was in production, and Newton made 3500 the first year. He finally gave up his Cambridge professorship which he had still retained, went on to become genuinely rich for the first time, and seems to have led a contented life. Much later he lost 20000 pounds in the South Sea Bubble, the world’s first stock market crash — Newton is attributed to have said: “I can calculate the movement of the stars, but not the madness of men”.

He was knighted in 1705, the first scientist to be knighted (though possibly for political reasons rather than either his science or Mint work), and died in 1727, aged 84. Despite being one of the greatest and most influential scientists of all time, he wrote:

I don’t know what I may seem to the world, but as to myself, I seem to have been only like a boy playing on the sea shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered around me.

His memorial at Westminster Abbey bears was proposed to bear the inscription: “If you doubt that such a man could exist, this monument bears witness”.



More details:

Others I haven’t seen or read:
Talk by Thomas Levenson, author of the book (Running Time: 1:03:30)
Book review in The Guardian
Book review in The Telegraph
Book review in Powell’s books
Another book review in The Guardian
Story in NPR radio [23 min 23 sec]
Post by Levenson at Executed Today
Long review/book abridgement! at Chicago Boyz
Also:
The author has a blog

Written by S

Fri, 2010-06-04 at 10:25:19 +05:30

Follow

Get every new post delivered to your Inbox.

Join 73 other followers