blog
   

304.2006   The optimal compression scheme
(which is, for all practical purposes, impossible to implement)

Suppose you'd like to invent a new compression scheme for pictures taken by people with their digital cameras. We want this compression scheme to be good through at least the year 2050 (at which point it will be replaced by JPEG 2050 :) How small can you make those files? Maybe 50% smaller than traditional JPEG? Or 80% smaller? Well, here's a (purely theoretic) way to store every file in less than 8 bytes.

It is estimated that the world population by 2050 will be just under 1010. Imagine that every single person in the world took a digital photograph every minute of every day from now until 2050. How many pictures would that be?

A slight overestimate is 1010*60*24*366*50 < 2.64×1017. If we had 58 bits, we could store 258 > 2.88×1017 different integers, and 8 bytes = 64 bits is more than enough.

So how does the compression work? Easy: we just number every digital picture taken between now and the end of 2050. This is picture 1, this is picture 2,... , this is picture 20,392,394,910. The compression algorithm simply stores which picture number was taken. The decompression algorithm reconstructs the picture.

Of course there is a lot "cheating" going on there. First, there is of course no practical way to build such a decompression algorithm, since it would need to "know" all of the pictures which would be taken between now and 2050 -- certainly predicting the future is a harder problem than image compression! Second, even if we could build such a decompression function, this function would effectively be storing all the data of all the pictures ever taken in this time period! That's a huge function, dude. And having to store that function would almost obviate the benefits of any compression scheme. Finally, the compression algorithm itself is also practically immpossible to write, since we have no way to really know which "picture number" we are currently at -- but that point is moot next to the first two.

In any case, I still think we can come up with a better image compression scheme than the current popular formats! Clever coders, consider this a challenge :)

103.2006 A brief note about people who have only taken the Staten Island ferry once in their lives
They're still there.
632.2005 The Evil that is Google Print
Ignorance has held back many a good thing. Luckily, we have responsible journalism to hold back that pesky ignorance. Until, that is, those writers feel threatened in their own ignorance.

Suppose someone proposed a new tax law in which everyone except authors/journalists/publishers got a huge tax cut. Nothing would get worse for those media minions; they'd just miss out on the cut. Do you think it would pass?

To give a yet more obvious thought experiment: suppose someone wanted to undertake an operation to own a copy of virtually every book ever made, and implement a search mechanism by which virtually anyone could find the book they wanted, and then read that book for free. Do you think authors would like that?

No, I wasn't thinking about Google Print just then. I was thinking about something called a "library." It's funny how authors aren't complaining about those so much.

Of course, there is a difference -- libraries pay for the copy they receive, whereas Google will be paying nothing (to the publishers, at least). But then again, and this is the point most journalists seem to wallow in missing, no one can read a copyrighted book directly from Google Print. It's just a portal to find books; not to read them. Buying or borrowing the book found is what follows in the life of the happy user.

So, let's start from libraries, and modify it, from the author's point of view, to Google Print. We lose a tiny fraction from the publisher's revenue (and hence an even tinier fraction of the author's income), and we gain a gigantic leap in publicity.

How much is that publicity worth? Well, let's put it this way -- how many web sites call Google and ask them to not be searchable from their main page? A huge number of web pages can be viewed in their entirety from Google's cache - even pages whose only source of revenue is ads - and I haven't heard of any lawsuit from A Group of Concerned Web Publishers.

This is a call to abjure the nescient avarice of the pusillanimous journalist. An automatic card catalog which doesn't give away your content (yes, that's what Google Print is), is a good thing, for searchers and searchees alike.

232.2005 The Linear Algebra of Social Identity
This entry is inspired by the abundance of inanity (=inaneness) inundating * almost every personal description profile to be found on facebook or friendster.

I propose an experiment in machine learning: your corpus is the set of all profiles of undergraduates on facebook. Step 1) establish a list of common cliches, "I just want to be myself," "live in the moment," "live each day as if it's your last." (etc.) Step 2) summarize each person by the cliches in their profile. Step 3) run a clustering algorithm to find which cliches go together. Try to minimize the number of clusters without sacrificing too much predictability of which cliches are most likely to be found together. (Added complexity: try to predict which cliches are likely to be found in the profile within one friend-distance.)

The result: a cluster basis of cliches for the social identity world of the current American undergrad generation. My hypothesis: the basis is actually rather feeble, bland, and depressingly uniform in essence. The grand irony is that so much attempted originality is just thinly veiled emulation of the perceived creativity of our pithless cultural avatars.

656.2004 Screw Novelty
I thought about updating this blog a lot more often in order to make it more interesting. Didn't work out. (Compare this blog with the one just before it, immediately below.)

There's just something about mass producing novelty which I find unappealing. Novelty seems to me akin to superficial beauty -- it's skin-deep, at best. How many daily-updated blogs are really interesting? I think very few. Granted, even this blog is not that interesting, but I prefer this style to the more common, write whatever I'm thinking whenever I think it near the keyboard style.

I don't quite understand the way this particularly bad blog works (eg who really writes the entries), but it illustrates my point.

So what else can a good blog have besides novelty? Interesting content, obviously. I think people also tend to look for personality and a sense of confiding of secrets in blogs. Perhaps by reading someone else's blog, you feel more connected to them. You gain a sense of true, contemporary, and real companionship in a non-judgmental way. If you really wanted to talk to the people whose blog you read, you can do so (by email).

My goals in keeping a blog are probably a little different than most other people. Instead of expounding upon a single theme such as politics or some private industry sector or listing the details of my day-to-day life or even talking about my relationships, I want to express my (relatively) abstract ideas. I would like to record, in a sort of personality driven manner, my pseudo-random cerebral journeys down a diversity of curiosity-borne paths.

600.2004 Novelty vs. content
So I did a mini-experiment to try and see how often people read this blog. The answer: not very often. But then again, I don't add to it very often, do I? So why should I expect the interest to be high?

I say things on my site that I would consider interesting to read (for example, some ideas about abstract religion). But that (good content) in itself is not quite enough for popularity (unless you have a huge amount of it, perhaps). It seems that continuous novelty is vital to a webpage which interests people.

What's so good about new stuff? Old stuff is still worthwhile, sometimes better for the time-testing, and there's more than enough of it to consume a lifetime.

Here is one hypothesis: consider our `information-awareness' as another sense, akin to hearing or vision. It is not exactly a physical perception, but it is still a type of perception -- of a slightly more abstract nature. Humans desire to be perceiving all that is going on around them. We don't want to miss anything that could be important. There is an innate desire to keep our senses as observant as possible. Reading about new information is just another way of satisfying this desire.

The interesting thing about this hypothesis is that we don't care so much about the particular information we're gathering. When I read an online news article, yes I care about the story, but in 95% of the cases, I wouldn't be reading the article if I thought it wasn't about something very temporally fresh. Is novelty over-rated? What do you think?

256.2004 The Insane King Puzzler
A friend of mine, Anthony Hodsdon, gave me this puzzle a couple days ago.

An insane king sits alone on an infinite chessboard. He's probably crazy due to the vast overwhelming loneliness of being the only chess piece on an infinite board, much as Euler probably felt while exploring the far reaches of mathematics he could hardly hope to explicate to the far-inferior second-best savants of the world.

In any case, the point is that our king is bound in a straightjacket. And which way must one travel in said garment? Why straightly, of course (being a king he moves stately as well). This means the king cannot move diagonally. Rather, he can move one square per turn either up, down, left, or right.

Enter the advisary. A demoness removes squares from the board one at a time. Once a square is removed, it may not be replaced, and the king may not move there. The king and demoness take turns, the king going first (albeit a moo point). The demoness wins if she can completely surround the king -- that is, if she can remove enough squares so that the king has finitely many places to move to. Implicitly, the king "wins" if he has a strategy which will indefinitely avoid such confinement.

The question is: who will win? Assume that both players have infinite mental capacity, id est, that they both play their own optimal strategy. Of course, I wouldn't have been so eager to post this if I did not have my own solution ready as well.

231.2004 If you are insane
I was recently watching an episode of the old British television series The Prisoner in which the protagonist's mind is placed into someone else's body. This led me to wonder how I would react to such a thing happening to me. (By the way, I don't watch TV as a rule, but I'm allowed to watch old shows if they're of decent quality and commercial-free.)

So what would you do if you woke up one day to find yourself in an entirely different body? Freak out is probably the correct answer. How about something a tad more subtle, and in a way more realistic: what if nothing seemed to have changed to you, yet everyone around you kept telling you that you were a different person? For instance, suppose that you grew up as "Sue," and then one day everyone starts to call you "Arnold." Certainly this would be more than a morsel unsettling. I believe most people would simply insist incessantly that they were who they believed to be -- id est, Sue.

Unfortunately, that would not be a wise course of action. If everyone calls you Arnold, you must accept the role. How can you get along in "the world" when you no longer live there? You must learn to live in this new place where you are now Arny (for short).

An even more interesting question arises -- what is the truth? Who are you now? We have two subjective but usually reliable measurements: what you think of yourself, and what the world thinks. To be sure, this is a question worth a good deal of philosophical ponderance. I would say that you are in effect both Sue and Arnold. You are Sue in that you know of Sue, and you also know that, in your mind, you are the person who satisfies the essential properties of being Sue. You are Arnold in that everyone else sees in you some essential property of being Arnold; otherwise how could they be so presumptuous as to correct you about your own identity!

Which brings us to the question of essential properties. What makes something that which it is? What if two authorities on identity disagree? I would say that essential properties are in fact totally subjective. I will be bold enough to suggest that all identification can occur only within a mind, subjectively. Hence all essential properties are nothing more than psychological guidelines which vary between minds yet tend to agree most of the time due to the fact that we all live in the same world. They are psychological guidelines which we have developed over time to help us distinguish this one object from others similar to it. (Subplot: we need comparison before we can enact identificaiton.) And if two authorities disagree about identity, it should be no great surprise as identity is no longer an inherent property of the object in question!

Identity not an inherent property? Insanity indeed -- from two identities to zero (in five paragraphs no less).

153.2004 The When Game
This is a weird little game you can play in your head when you're in a new place on your own.

Suppose you have just arrived from the future in a time machine. The thing is, you built the time machine last night when you were a little drunk, and so it works, but it always sends you to a random place and time (but still on Earth and sometime in human history, let's say). So each time you use your time machine you have to figure out when you are.

The trick is to forget your entire real life and become absorbed with this time travel daydream. Once you do that, you can look around you with a fresh perspective, and observe all the little clues which give away which era it is, which century, which year, etc.

Looking at calendars or newspapers is basically cheating, so don't do that. But consider things like architectural styles, or the fashions of clothes people are wearing, or the technology being used nearby. If you can hear any music or conversation, listen for clues about the current topics of popular culture.

It all sounds very silly because, of course, you know exactly when you are. But once you get the hang of truly forgetting, the game becomes more fun. It's really interesting to see which places are a dead giveaway (e.g. busy, successful places with lots of people), and which have no clues at all (such as a very old house or building with no other people in it). Try it!

143.2004 The Future
It's easy to believe in the future as long as it stays there.
415.2003 The Psychology of Wasting Time
How exactly does one waste time? The key, I think, is that it depends on the perspective of the person you ask. For instance, Alice might consider it very worth-while to play video games all day, while Bob might regard this as an utter waste.

I wanted to answer this question so I could make sure I don't waste my own time.

So here's a theory: each person has several contexts in which they see themselves as existing. These form identities for the person. For instance, I see myself as a part of the company I work for (this summer), and a part of the mathematics research community. These two contexts give me a sense of who I am, of identity. Based on this framework, I think one feels that their time is being spent well when what they're doing is contributing to one of these identities.

It's probably true that some of these identities are more important than others. It's also probably the case that some contexts are harder to contribute to than others. For instance, I could easily contribute to the community of my friends by sending out an email. But this is not quite as satisfying as publishing a new math theorem. However, the math theorem is a little harder to do. There's probably even a correlation between difficulty and satisfaction (although I can think of one or two exceptions).

414.2003 Pirate Puzzle
Yesterday a friend of mine (Steve Magill) gave me this puzzle. I haven't completely solved it yet. (Addendum: I solved it. I'll put up the solution in a little bit.)

Thirteen pirates have collected a treasure they'd like to keep in storage for a while. They are going to lock it in a chest with several locks on it. Each lock can be opened only by the right key, of which there may be a few copies. Each pirate owns several keys. The pirates would like it so that no six pirates, using their combined keys, could possibly open the chest. However, they would also like any seven pirates to be able to open the chest. The question is: what is the minimum number of locks necessary to solve their problem?

Just in case the description seems a little vague, here is a sample solution for a smaller case: suppose there are only three pirates. We would like it so that no one pirate, acting alone, could open the chest; but any two together could. Then the chest need only have three locks. Call these locks 1, 2, and 3. Give pirate A keys to 1 and 2; give pirate B keys to 1 and 3; and pirate C keys to 2 and 3. This works. Think about why it's impossible to do with only two locks.

www. Tyler Neylon .com