twenty-one things tagged “math”

Fundamentals of Lambda Calculus for People Who Love Birds

This (beautifully formatted and well-paced-and-delivered and surprisingly sparsely attended) talk by Gabriel Lebec on the fundamentals of Lambda Calculus is one of my favorite talks ever.

As Lebec explains, the lovely bird names come from this book called “To Mock a Mockingbird” by mathematician and logician Raymond Smullyan. The naming is simply delightful. As Matthew Gilliard explains:

The premise is that there are enchanted forests which contain many (or sometimes very few) talking birds. Smullyan dedicated the book to Haskell Curry - an early pioneer in combinatory logic and an avid bird-watcher. The birds, which I suppose represent the combinators, have an interesting characteristic:
Given any two birds A and B, if you call out the name of B to A it will respond by calling out the name of some bird to you.

This bird whose name A calls when you call B is denoted as AB. Once you have several birds in place, a single call can cascade around the forest with each call following rules depending on who produces it.

The very first bird we are introduced to is the Mockingbird whose characteristic behaviour is that whatever name you call to the Mockingbird, it will reply as if it is the bird whose name you called. This is denoted:

Mx = xx

For any bird x we can say that Mx (the result of calling x to a Mockingbird) is the same as xx (the result of calling x to a bird of type x). It really does mock other birds! And what’s more, the existence of the Mockingbird, in combination with various others, unlocks some really fascinating group behaviour from these birds.

And!

Soon we discover that birds have certain properties: The can be fond of other birds, they can be egocentric if they are fond of themselves. The can be hopelessly egocentric if they only ever talk about themselves. There are happy birds, normal birds, agreeable birds and many others. We also meet other types of birds with specific properties - the Lark, the Kestrel, Sage birds, Bluebirds, aristocratic birds, Eagles, the list goes on and on. Luckily there is a Who’s Who list of birds in the back to keep track.

The Iyers, The Iyengars, The Lowells, The Cabots, and God

This is the city of Madras
The home of the curry and the dal
Where Iyers speak only to Iyengars
And Iyengars speak only to God.

I’d read this years ago some place and forgot where. Thought it would be in some Religious Studies textbook back from when I was (briefly) a Religious Studies major. Nope! It was the great Paul Erdős!

Erdős said he’d modelled it after this ditty about the privileged New England families famously known as the ‘Boston Brahmins’.

This is good old Boston
The home of the bean and the cod
Where the Lowells speak to the Cabots
And the Cabots speak only to God.

From Vijaysree Venkataraman’s article.

A Vickrey Auction

When you end up paying the price you bid (“first price”), you have a strong incentive to lie about how much you’re willing to pay. Suppose there’s an item for sale that you’d be happy paying up to $1,000 for if necessary, but of course you’d rather pay less. In a first-price auction, if you bid $1,000 and you lose. Well, someone else was willing to pay more than you were willing to, so that’s OK, but if you win, you know that nobody else offered that price and you’d be slapping yourself for not going for $950 and saving a little. Or, who knows, maybe there are really few buyers and you later discover that the second person was only valuing the item at $600? Damn, you could have walked away with it for $610!

[. . .]

In a second-price auction, there’s no reason for you to do that. You can simply say exactly the maximum price you are willing to pay, and there’s never any advantage for you in saying anything else:

  • You don’t want to post a higher bid since you might be forced to pay it, and you don’t want to do that.
  • You don’t want to post a lower bid since you might lose the item for no good reason at all.
  • You’ll end up paying exactly what it takes to win the item: one dollar or one cent more than the next person’s maximum bid.

So, a second-price mechanism encourages everyone to bid truthfully, and the item ships to the person who really values it at the highest price. It’s the best outcome for the seller and as good an outcome for everyone else as they could wish for.

Incidentally, note that this is exactly what happens in ordinary public auctions (“going once, going twice… sold!!”) Everyone walks in with an idea of how much they’re willing to pay, and they keep bidding one dollar more than the current price until they hit their max—but they’re never forced to reveal their max and what they end up paying is just one dollar (or penny, or whatever) more than the second-highest bidder.

– Alon Amit on Quora (emphasis mine.)

Quite a bit of Game Theory stuff on Wikipedia as well.

Numbering from Zero

Dijkstra on why numbering should start from zero.

Numbering is done with natural numbers. Let’s take zero to be the smallest natural number1. For the sequence (2, 3, 4, … ,12), using the convention (2 ≤ n < 13) is appropriate because

  • For a sequence starting with zero, like (0, 1, 2, 3), the left hand condition leaks into unnatural numbers if you use “less than”: (-1 < n).
  • For an empty sequence, the right hand also leaks into the unnatural if you use “less than or equal to”: (n ≤ 0)

And minorly, because these are the true of another convention (1 < n ≤ 12)

  • Difference between bounds (13 - 2 = 11) is the length of the sequence
  • I know that these two sequences are adjacent: (2 ≤ n < 13) and (13 ≤ n < 24)

All that’s prep for:

When dealing with a sequence of length N, the elements of which we wish to distinguish by subscript, the next vexing question is what subscript value to assign to its starting element. Adhering to convention a) yields, when starting with subscript 1, the subscript range 1 ≤ i < N+1; starting with 0, however, gives the nicer range 0 ≤ i < N. So let us let our ordinals start at zero: an element’s ordinal (subscript) equals the number of elements preceding it in the sequence. And the moral of the story is that we had better regard – after all those centuries!2 – zero as a most natural number.

There’s also this little nugget

I think Antony Jay is right when he states: “In corporate religions as in others, the heretic must be cast out not because of the probability that he is wrong but because of the possibility that he is right.”

  1. TIL that this can be so. ↩︎

  2. Don’t know what he means here… ↩︎