Three days ago I was walking to Simmons for dinner, and on the way there met a group of hummingbirds (no, as much trivia as I enjoy, names for groups of animals are not one of them). I quickly concluded that the hummingbirds were not very intelligent. When they saw me coming, they fled down to the next fence segment. By the time I have walked to that segment, they flee to the next one down instead of in any other direction. It took the hummingbirds on average five fence segments before they figured out my linear trajectory, and one of them took nine.
This reminded me of high school. For some reason, I was ridiculously frequently the first person to get to class (here at MIT, I still am). As I watched the other students enter the room and sit down, eventually I thought about what would happen if you made each student guess the order in which the students who got to the room before them came, under the unrealistic simplifying assumption that no students communicate their order and no student comes in at a point visible to any after hser; in other words, the students enter one at a time.
The first two students, unless fatally stupid, will always guess the order up to them correctly. The first student submits a null list and the second student has only the first student before hser. The third student has to choose one of 2!=2 orders, the fourth student has to choose one of 3!=6 orders, the fifth student has to choose one of 4!=24 orders, and so on with the nth student choosing one of (n-1)! orders. Now, what’s the expected value of the number of students who guess a correct order? For n students in a class, it is . This is incredible from certain standpoints. Suppose you had a room with an infinite number of students. The number of students expected to correctly guess the order by which students before them entered the room is e≈2.718281828459, since the sum of the reciprocals of the factorials is exactly that Taylor series. The reason this is amazing is because we know two students are guaranteed to submit the correct ordering, and yet despite infinitely more chances, expectation says guessing ability in the room is above average if even a third student guesses an order correctly. This is the amazing rate at which the difficulty of guessing the correct order increases as more students come, completely overpowering even an infinite number of chances to guess. After all, the factorials increase faster than even any exponential, and the rate at which they do increase is vividly portrayed in this example.
In any case, this also relates to another problem that is significantly more difficult. As a person allergic to quite a few foods, I frequently read ingredients labels. Ingredients in ingredients labels have the property that they are arranged in decreasing order of relative weight. Thus, the nth item in an ingredients list is at most 1/nth the weight of the food, and usually significantly less. This is useful if I see something I’m allergic and want to see if it’s in trace enough amounts for me to get away with it (although I usually end up taking the allergy pill anyway). Here’s the more interesting question. What is the expected value of the fraction of the weight of the food the nth ingredient on the list takes up. For a one-item list, this is trivial: the one item takes up a fraction of 1 of the weight. For two items, one could see that the first item is expected to be 3/4 of the weight and the second item is expected to be 1/4. With three items this is already tricky. With more items, we might need to do geometric probability in extra dimensions. And thus, it is time to find another approach.
Except, of course, I haven’t found it yet.